题解2023.6.5

D - Factorial Divisibility
对于a[i]>=x的数一定可以整除，考虑a[i]<x的数，因为(x+1)*x! = (x+1)!
统计ai出现的次数, 把他转换为大的阶乘, 如果, 最终1到x - 1, ai的出现次数均为0则说明可以被x!整除
 

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast) 
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
typedef long long ll;
const int maxn = 5e5 + 100, inf = 1e18;
const int mod = 1e9 + 7;
using namespace std;
ll a[maxn];
void solve() {int n, x;cin >> n >> x;map<int, int>mp;for (int i = 1; i <= n; i++) {int y;cin >> y;mp[y]++;}for (int i = 1; i < x; i++) {mp[i + 1] += (mp[i] / (i + 1));mp[i] = mp[i] % (i + 1);}for (int i = 1; i < x;i++) {if (mp[i] != 0) {NOreturn;}}YES
}
signed main()
{ios::sync_with_stdio(false);solve();
}

C1 - Make Nonzero Sum (easy version)
 思路：奇数一定不可以，偶数一定可以，两两相同放一起，不同分开
 

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast) 
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES  cout<<"YES"<<'\n';
#define NO   cout<<"NO"<<'\n';
#define endl cout<<'\n';
typedef long long ll;
const int maxn=2e5+10,inf = 1e18 ; 
const int mod = 1e9 + 7;
using namespace std;
int a[maxn];
struct node {int l, r;
}x[maxn];void solve(){int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}if (n & 1) {cout << -1 << '\n';return;}int cnt = 0;for (int i = 1; i <= n; i += 2) {if (a[i] == a[i + 1]) {x[++cnt].l = i;x[cnt].r = i + 1;}else {x[++cnt].l = i;x[cnt].r = i;x[++cnt].l = i + 1;x[cnt].r = i + 1;}}cout << cnt << '\n';for (int i = 1; i <= cnt; i++) {cout << x[i].l << ' ' << x[i].r << '\n';}}
signed main()
{ios::sync_with_stdio(false);int t;cin >> t;while (t--) {solve();}
}

C2. Make Nonzero Sum (hard version)
思路：变成了0，1，-1三种情况，对于去除0后为奇数的一定不可以，偶数的一定可以，
和(easy version)情况相似，相邻的不为0的凑在一起

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast) 
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
using namespace std;
#define ll long long
#define pcc pair<char, char>
#define pii pair<int, int>
#define inf 0x3f3f3f3f
const int maxn = 200010;
int n, a[maxn];
void solve() {cin >> n;int cnt = 0;for (int i = 1; i <= n; ++i) {cin >> a[i];if (a[i]) ++cnt;}if (cnt & 1) {cout << -1 << '\n';return;}vector<pii> res;int l, r;for (int i = 1; i <= n;) {while (i <= n && !a[i]) {res.push_back({ i, i });++i;}if (i > n) {break;}l = i;r = i + 1;if (a[r]) {   if (a[l] == a[r]) {res.push_back({ l, r });}else {res.push_back({ l, l });res.push_back({ r, r });}}else {res.push_back({ l, l });while (r <= n && !a[r]) {res.push_back({ r, r });++r;}if (a[l] == a[r]) {res.back().second = r;}else {res.push_back({ r, r });}}i = r + 1;}int len = res.size();cout << len << '\n';for (auto p : res) {cout << p.first << ' ' << p.second << '\n';}
}
int main() {ios::sync_with_stdio(false);int t ;cin >> t;while (t--) {solve();}}

G    严肃古板的秩序

思路:?只有12个,暴力,dfs3种情况,防止long long爆掉采用龟速乘
 

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast) 
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x)
typedef long long ll;
const int maxn=2e5+10,INF = 1e18 ; 
using namespace std;
int num[20],cnt = 0;
char op[3] = { '+','-','#' }, s1[20];
ll numb = 0;
bool flag = false;
ll qadd(ll a,ll b, ll p){   //龟速乘防止long long 爆掉ll res = 0;while (b){if (b & 1) res = (res + a) % p;a = (a + a) % p;b = b >> 1;}return res;
}
void dfs(ll u, ll v) {if (u == cnt - 1) {if (v == numb) flag = true;return;}if (u >= cnt) return;if (flag) return;s1[u] = op[0];dfs(u + 1, v + num[u + 2]);if (flag) return;s1[u] = op[1];dfs(u + 1, v - num[u + 2]);if (flag) return;s1[u] = op[2];if (v > 0) {dfs(u + 1, qadd(v, v, num[u + 2]));}
}void solve(){string s;cin >> s;for (int i = 0; i < s.size(); i++) {if (isdigit(s[i])) {numb =numb*10LL+s[i] - '0';}else {num[++cnt] = numb;numb = 0LL;}}dfs(0, num[1]);int cnt1 = 0;if (flag) {for (int i = 0; i < s.size(); i++) {if (s[i] != '?')cout << s[i];else {cout << s1[cnt1++];}}}else {cout << -1 << '\n';}}
signed main()
{ios::sync_with_stdio(false);solve();
}

C    忽远忽近的距离

题意：构造一个n数组，使得每个2<=|ai-i|<=3;
思路1：4,5,6可构造除7外往后的所有数
n%4==1，4,5搭配；n%4==2,4,6搭配；n%4==3,4,5,6搭配

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast) 
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>#include<vector>#include<stack>
#define ms(x,y) memset(x,y,sizeof x)
#define int long long
typedef long long ll;
const int maxn=2e5+10,INF = 1e18 ; 
using namespace std;
int start = 1;
void fun4() {cout << start + 2<<' ' << start + 3<<' ' << start<<' ' << start + 1<<' ';start += 4;
}
void fun5() {cout << start + 3 <<' '<< start + 4 <<' ' << start <<' ' << start + 1<<' ' << start + 2 << ' ';start+=5;
}
void fun6() {cout << start + 3 << ' ' << start + 4 << ' ' << start + 5 << ' ' << start << ' ' << start + 1 << ' ' << start + 2 << ' ';start += 6;
}void solve(){int n;cin >> n;if (n <= 3 || n == 7) {cout << -1 << '\n';return;}start = 1;int x = n / 4;int y = n % 4;if (y == 0) {for (int i = 1; i <= x; i++) {fun4();}}else if (y == 1) {for (int i = 1; i <= x - 1; i++) {fun4();}fun5();}else if (y == 2) {for (int i = 1; i <= x - 1; i++) {fun4();}fun5();}else if (y == 3) {for (int i = 1; i <= x - 1; i++) {fun4();}fun5();fun6();}}
signed main()
{ios::sync_with_stdio(false);solve();
}