目录
写在前面
比赛地址：https://codeforces.com/contest/1783。
CF 车队翻车咯，本来上大分，喜提 skipped
A
如果所有数均相等则无解。
否则先降序排序，交替输出 \(a_i\) 和 \(a_{n-i+1}\) 即可。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
//=============================================================
int a[1100];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
int T = read();
while (T --) {
int n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
std::sort(a + 1, a + n + 1);
if (a[n] == a[1]) {
printf("NO\n");
continue;
}
printf("YES\n");
for (int i = 1, j = n; i <= j; ++ i, -- j) {
if (i == j) printf("%d ", a[i]);
else printf("%d %d ", a[j], a[i]);
}
printf("\n");
}
return 0;
}
B
尝试达到上界。
蛇形矩阵，交替输出 \(i\) 和 \(n-i+1\) 即可。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
//=============================================================
int a[51 * 51], b[51][51];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
int n = read(), p = 0;
for (int i = 1, j = n * n; i <= j; ++ i, -- j) {
a[++ p] = i, a[++ p] = j;
if (i == j) -- p;
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
b[i][j] = 0;
}
}
b[1][1] = a[1];
for (int i = 1, j = 1, tot = 1; tot < n * n; ) {
while(++ j <= n && !b[i][j]) b[i][j] = a[++ tot]; -- j;
while(++ i <= n && !b[i][j]) b[i][j] = a[++ tot]; -- i;
while(-- j > 0 && !b[i][j]) b[i][j] = a[++ tot]; ++ j;
while(-- i > 0 && !b[i][j]) b[i][j] = a[++ tot]; ++ i;
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
printf("%d ", b[i][j]);
}
printf("\n");
}
}
return 0;
}
C
显然获胜场数越多越好，最后的胜利场数一定是最大值，先贪心地求出这个最大值 \(m\)。
再考虑其他人的获胜场数，仅需关注有多少人获胜场数大于 \(m\) 即可。编号 \(i\le m\) 的人获胜场数一定不大于 \(m\)，编号 \(i> m+1\) 的人获胜场数一定大于 \(m\)，是否选择战胜他们并不会影响排名。仅需考虑是否战胜了编号 \(m+1\) 的人，回退贪心时选择的代价最大的元素并尝试选择 \(a_{m+1}\) 即可。
赛时没考虑清楚写的相当麻烦。
//By:Luckyblock
/*
*/
#include <vector>
#include <cstdio>
#include <cctype>
#include <algorithm>
const int kN = 5e5 + 10;
//=============================================================
int n, m, a[kN], b[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), m = read();
int sum = 0;
for (int i = 1; i <= n; ++ i) a[i] = b[i] = read();
std::sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++ i) {
if (b[i] > m) break;
m -= b[i];
sum ++;
}
if (sum == n) {
printf("1\n");
continue;
}
printf("%d\n",
m + b[sum] - a[sum + 1] >= 0 ? n - sum: n - sum + 1);
}
return 0;
}
D
给定一长度为 \(n\) 的数列 \(a\)，要求进行 \(n - 2\) 次操作，第 \(i\) 次操作有两种选择：
- 令 \(a_i = a_i + a_{i+1}\)，\(a_{i+2} = a_{i+2} - a_{i+1}\)。
- 令 \(a_i = a_i - a_{i+1}\)，\(a_{i+2} = a_{i+2} + a_{i+1}\)。
求完成所有操作后，数列 \(a\) 的形态的种类数。
\(3\le n\le 300\)，\(0\le a_i\le 300\)。
2S，512MB。
设 \(i\) 次操作后，\(a_1\sim a_{i+1}\) 的形态有 \(f_i\) 种，考虑第 \(i+1\) 次操作的影响。发现并不会影响 \(a_1\sim a_{i-1}\) 和 \(a_{i+3}\sim a_{n}\) 的值，它们的形态并不会影响本次操作对 \(a_1\sim a_{i+2}\) 形态种类数，我们仅需关注 \(a_i, a_{i+1}\) 和 \(a_{i+2}\) 的值即可。更近一步地，由于 \(a_i\) 的值在操作前已经确定，\(a_{i+1}\) 的值在操作中不会改变，考虑枚举 \(a_{i+1}\) 的值，我们仅需考虑 \(a_{i+2}\) 的值即可。
记 \(f_{i, j}\) 表示进行到第 \(i\) 次操作，\(a_{i+2}=k\) 的 \(a\) 的形态数。转移时考虑枚举 \(a_{i+1}\) 的值：
- 若 \(j = a_{i+1}= 0\)，两种操作等价，有：\[f_{i,a_{i+2}} = f_{i-1, 0} \]
- 若 \(j = a_{i+1}\not= 0\)，则有：\[f_{i,k} = f_{i-1,a_{2}-j} + f_{i-1, a_{2}+j} (k=a_2 - j \lor k = a_2 + j) \]
答案即 \(\sum f_{n-2, k}\)。
总复杂度 \(O(n\times A)\) 级别，\(A\) 为值域。
注意 \(|A|\le 300 \times 300\)，\(a_i\) 可能为负数，注意添加增量避免数组下标为 0。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
const int mod = 998244353;
const int kN = 3e2 + 10;
const int kM = 3e5;
const int zero = 1e5;
//=============================================================
int n, a[kN], ans, f[kN][kM];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
f[0][a[2] + zero] = 1;
for (int i = 1; i <= n - 2; ++ i) {
int val = a[i + 2];
for (int j = 0; j < kM; ++ j) {
int nval1 = val + j, nval2 = val - (j - zero) + zero;
f[i][nval1] = (f[i][nval1] + f[i - 1][j]) % mod;
if (j != zero) f[i][nval2] = (f[i][nval2] + f[i - 1][j]) % mod;
}
}
for (int i = 0; i < kM; ++ i) ans = (ans + f[n - 2][i]) % mod;
printf("%lld\n", ans);
return 0;
}
E
AB 两人在玩一个游戏，游戏中共有 \(n\) 个怪物。对于每一个怪物，A，B 可以轮流攻击 \(k\) 次，A 先出手，两人的攻击互不影响。A 的第 \(a_i\) 次攻击才能击败第 \(i\) 个怪物，B 的第 \(b_i\) 次攻击才能击败第 \(i\) 个怪物。求所有的整数 \(k\in [1,n]\)，使得所有怪物均是被 A 击败的。
\(t\) 组数据，每组数据给定两长度为 \(n\) 的数组 \(a,b\)，代表上述游戏的参数，求所有的整数 \(k\)。
\(1\le t\le 10^4\)，\(1\le n\le 2\times 10^5\)，\(1\le a_i,b_i\le n\)，\(\sum n\le 2\times 10^5\)。
2S，256MB。
没做亏死……虽然就算做了也会翻车，乐
对于一个固定的 \(k\)，第 \(i\) 个怪物被 A 击败的条件为：\(\lceil \frac{a_i}{k}\rceil \le \lceil\frac{b_i}{k} \rceil\)，考虑反面，被 B 击败的条件为 \(\lceil \frac{a_i}{k}\rceil > \lceil\frac{b_i}{k} \rceil\)，则 \(\left(\lceil\frac{b_i}{k} \rceil,\lceil\frac{a_i}{k}\rceil\right)\) 之间至少有一个整数，则有 \(b_i<a_i\)，且 \([b_i,a_i)\) 之间至少有一个 \(k\) 的倍数。
考虑枚举 \(k\)，检查 \(k\) 的倍数是否位于某个区间 \([b_i, a_i - 1]\) 中即可判断是否有解。差分标记区间即可。
复杂度是调和级数，\(O(n\log n)\) 级别。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN], b[kN], d[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 1; i <= n; ++ i) d[i] = 0;
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i <= n; ++ i) b[i] = read();
for (int i = 1; i <= n; ++ i) {
if (b[i] <= a[i]) {
++ d[b[i]], -- d[a[i]];
}
}
for (int i = 1; i <= n; ++ i) d[i] += d[i - 1];
std::vector <int> ans;
for (int k = 1; k <= n; ++ k) {
bool flag = 1;
for (int i = 1; i * k <= n; ++ i) {
if (d[i * k]) {
flag = 0;
break;
}
}
if (flag) ans.push_back(k);
}
printf("%d\n", ans.size());
for (int i = 0, sz = ans.size(); i < sz; ++ i) printf("%d ", ans[i]);
printf("\n");
}
return 0;
}
F
写了个贪心调了一天没调出来最后发现假了，心力交瘁，改天再说、、、
写在最后
- 开车需谨慎。
- 想清楚再写，别急。
- 考虑影响因素，影响因素相对较少且无后效性考虑 dp。
- 考虑反面。
- 模型转换。
- 仁王真好玩，在线求斧哥送我仁王 2 玩。