2023年暑假集训总结/7.3
预估成绩：100+20+10+20=150
实际成绩：0+61+19+0=80
T1最大公约数
题意：有n个数，取n-1个数，求可以得到的最大gcd。
思路&做法：
有一个思路是将所有数字质因数分解，然后对于每一个质数，判断他是否在这n个数中“拖了后腿”，这样就可以O(nk)地求出答案，k是质因数的个数，理论上可以AC，但是我在考场上最后几分钟改题的时候少打了一个分号导致CE了。
有一个更优的正解：对于一个序列，求出它的前缀gcd和后缀gcd，那么这个序列去掉第i个数的结果就是gcd(psi-1,hsi+1)，时间复杂度是O(nlogn)的，写法也更优。
std：
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define W(x) write(x) #define pE() puts("") #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } const int N = 1e5 + 5; ll n, a[N]; ll ps[N], pss[N], ans; int main() { freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); n = rd(); E(i, 1, n) { a[i] = rd(); if (i == 1) ps[i] = a[i]; else ps[i] = std::__gcd(a[i], ps[i - 1]); } pss[n] = a[n]; for (int i = n - 1; i >= 1; -- i) pss[i] = std::__gcd(a[i], pss[i + 1]); // std::cout << pss[2] << ' ' << ps[n - 1] <<' ' << n << '\n'; ans = max(pss[2], ps[n - 1]); E(i, 2, n - 1) ans = max(ans, std::__gcd(ps[i - 1], pss[i + 1])); W(ans); return 0; }
T2排序1
题意：有一个长度为n的序列，对于每一个i∈[1,n)，可以且必须交换一次ai与ai+1，回答是否可以将序列变成升序且给出操作顺序。
思路&做法：
考试的时候没有时间做了，就直接输出-1，觉得应该能骗到20分左右，结果直接拿了61分。
可以感性理解一下，每一次将未归位的最小元素操作归位，记录下操作，同时判断每种操作是否用过、总操作数是否等于n-1即可。
std：
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define W(x) write(x) #define pE() puts("") #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } const int N = 2e5 + 5; int n, a[N], t[N], res[N]; bool sign[N]; int main() { freopen("b.in", "r", stdin); freopen("b.out", "w", stdout); n = rd(); E(i, 1, n) { a[i] = rd(); t[a[i]] = i; } int cnt = 0; E(i, 1, n) { // std::cout << i << ' ' <<t[i] << '\n'; if (t[i] < i) E(j, t[i], i - 1) { if (sign[j]) { W(-1); return 0; } else { res[++ cnt] = j; sign[j] = 1; std::swap(a[j], a[j + 1]); std::swap(t[a[j]], t[a[j + 1]]); } } else if (t[i] > i) for (int j = t[i] - 1; j >= i; -- j) { if (sign[j]) { W(-1); return 0; } else { res[++ cnt] = j; sign[j] = 1; std::swap(a[j], a[j + 1]); std::swap(t[a[j]], t[a[j + 1]]); } } } if (cnt == n - 1) E(i, 1, cnt) { W(res[i]); pE(); } else W(-1); return 0; }
T3集合平均
题意：给定n和k，从[1,n]中每个数至多选出k个数，问选出的数中平均数为x(x∈[1,n])的方案分别是多少。
思路&做法：
考试的时候先打了一个dfs，发现前一半答案和后一半答案是对称的，考虑对dfs进行优化，若当前已经枚举到了>n/2的数且当前平均数>n/2直接跳过。最后得了19分。然后考虑dp，发现空间复杂度是O(n^4),想不到有什么优化方法了。
正解确实也是dp，f[i][j]表示选前i个数和为j的方案数，但需要后续额外处理出平均数的答案。
std：
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define W(x) write(x) #define pE() puts("") #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } const int N = 105; int n, k, m, f[N][N * N * N]; int sum2[N * N * N]; int main() { freopen("c.in", "r", stdin); freopen("c.out", "w", stdout); n = rd(); k = rd(); m = rd(); f[0][0] = 1; ll sum = 0; E(i, 1, n) { sum += i * k; E(j, 0, sum) sum2[j] = ((j - i >= 0 ? sum2[j - i] : 0) % m + f[i - 1][j]) % m; E(j, 0, sum) f[i][j] = ((sum2[j] - (j - 1ll * i * (k + 1) >= 0 ? sum2[j - 1ll * i * (k + 1)] : 0) % m + m) % m) % m; } E(i, 1, n) { ll ans = 0; E(j, 0, sum) ans = (ans + 1ll * f[i - 1][j] * f[n - i][j] % m) % m; W(((1ll * ans * (k + 1) % m - 1) % m + m) % m); pE();
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define W(x) write(x) #define pE() puts("") #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } const int N = 105; int n, k, m, f[N][N * N * N]; int sum2[N * N * N]; int main() { freopen("c.in", "r", stdin); freopen("c.out", "w", stdout); n = rd(); k = rd(); m = rd(); f[0][0] = 1; ll sum = 0; E(i, 1, n) { sum += i * k; E(j, 0, sum) sum2[j] = ((j - i >= 0 ? sum2[j - i] : 0) % m + f[i - 1][j]) % m; E(j, 0, sum) f[i][j] = ((sum2[j] - (j - 1ll * i * (k + 1) >= 0 ? sum2[j - 1ll * i * (k + 1)] : 0) % m + m) % m) % m; } E(i, 1, n) { ll ans = 0; E(j, 0, sum) ans = (ans + 1ll * f[i - 1][j] * f[n - i][j] % m) % m; W(((1ll * ans * (k + 1) % m - 1) % m + m) % m); pE(); } return 0; }
T4排序2
题意：我们有一个序列 。 最多可以做2e5次以下操作： 宣言一个整数i，交换 ai和a(i+ai)%m 。 你的任务是调配这些操作的，使得序列 最终成为升序序列。如果不可能，请输出 -1。
思路&做法：
同样直接输出-1，但是一分都没有。
分析发现一定有解，每次持续操作最小的未归位的数即可，可以证明操作次数小于n^2。
std：
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define W(x) write(x) #define pE() puts("") #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } const int N = 105; int n, a[N], t[N]; std::vector<int> ans; void solve(int x) { ans.push_back(t[x]); std::swap(a[t[x]], a[(t[x] + x) % n]); E(i, 0, n - 1) t[a[i]] = i; } int main() { freopen("d.in", "r", stdin); freopen("d.out", "w", stdout); n = rd(); E(i, 0, n - 1) { a[i] = rd(); t[a[i]] = i; } E(i, 1, n - 1) { while (t[i] > i) solve(i); if (i == 1) { while (t[i] != 1) solve(i); } else { if (t[i] == i) continue; for (int j = i - 1; j; -- j) while (t[j] > i) solve(j); while (1) { // puts("a"); int flag = 0; E(j, 1, i) { if (t[j] != j) flag = 1; } if (!flag) break; solve(a[0]); } } } E(i, 0, n - 1) { if (a[i] != i) { W(-1); return 0; } } W(ans.size()); pE(); E(i, 0, (int)ans.size() - 1) { W(ans[i]); pE(); } return 0; }