# 别对出题人出手！ ## Difficulty Index 只考虑真正 AC 的人数。 - 预测：A < B < E < C ≈ D < F - 实际：E < A < C < D < F < B 和想象中有亿点点不同，刚开始半小时就有人 300 pts 了，差点吓死 qaq ## Test Data 实际造数据的只有我和另外一个人，期间遇到了许多问题。 标程写挂了之类的就不说了，最离谱的是这评测姬太快了？？？ 以 B 为例，原本是最多 $3\times10^2$ 个点，结果发现卡不掉 $\mathcal O\left(n^4\right)$ 的做法 orz 还有就是 F 的数据没办法直接随机生成，不然答案大概率是 `No`，构造比较复杂 qaq 尽管如此，该出锅的时候还是会出锅的，发现数据有问题可联系我。 ## Verification 没找到合适的人验题，闲人又只有我一个，所以还是我 555 ## Hello World 题目感觉是出难了的，尤其是涉及单调栈和 DP 的两道 Medium，很怕大家不会 orz 直到最近看了 19 级的数据结构 OJ 题，单调队列都有了，那单调栈也没问题吧 qwq 至于 DP，状态设计比较简单且偏递推，感觉比初级组的背包问题要简单一点吧~~大概~~。 每道题的码量都很小，不需要高深的数据结构，算是 Codeforces Like 吧 ~ 希望大家玩得开心，认识更多的朋友，如果能因此对算法竞赛产生兴趣就更好了 ~ 最后恭喜 AK 的三位同学 @GGN_2015，@Magi_karp，@communist，真的非常开心！ # A. 在魔王城失眠数数  ## Idea 睡前想的签到题。 ## Summary 给定 $x$ 求最小的 $y$ 满足 $y>x+1$，$\gcd\left(x,y\right)=1$。 ## Solution 1 设 $y=x+d$ $\left(d>1\right)$，则 $\gcd\left(x,y\right)=\gcd\left(x,d\right)=1$，显然只需求最小的 $d$。 考虑直接枚举，最坏情况下 $x=2\times3\times5\times7\times11\times13\times17\times19\times23<10^9$，$d=29$。 时间复杂度为 $\mathcal O\left(\log x\right)$。 ## Code 1 [details: C++] ```cpp #include <bits/stdc++.h> using namespace std; void solve() { int x; scanf("%d", &x); for (int d = 2; d <= 29; d++) if (gcd(x, d) == 1) return printf("%d\n", x + d), void(); } int main() { return solve(), 0; } ``` [/details] ## Solution 2 在 **Solution 1** 的基础上，注意到 $d$ 最优时必为素数，互质可用取模判断。 时间复杂度优化至 $\mathcal O\left(1\right)$ ~~虽然没必要~~。 ## Code 2 [details: C++] ```cpp #include <bits/stdc++.h> using namespace std; void solve() { int x; scanf("%d", &x); const int d[] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; for (int i = 1; i <= 10; i++) if (x % d[i]) return printf("%d\n", x + d[i]), void(); } int main() { return solve(), 0; } ``` [/detail] # B. 火火薄饼  ## Idea 计算几何带师想的简单题，从结果来看好像大家这方面都跟我差不多菜 qwq ## Summary 给定 $n$ 个点求任意四点构成的凸四边形的最大面积。 ## Solution 枚举凸四边形的对角线，再找对角线两侧距离对角线最远的芝麻。 距对角线最远的芝麻即与对角线所构成的三角形面积最大的芝麻，可用叉乘简化代码。 注意精度问题，四边形面积的两倍应是整数，用浮点数算要小心丢精度。 时间复杂度为 $\mathcal O\left(n^3\right)$。 ## Code [details: C++] ```cpp #include <cstdio> #include <algorithm> using namespace std; struct node { int x, y; }; node p[505]; int cross(node p1, node p2, node p3) { int a1 = p2.x - p1.x, a2 = p3.x - p2.x; int b1 = p2.y - p1.y, b2 = p3.y - p2.y; return a1 * b2 - a2 * b1; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y); int res = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { int s1 = 0, s2 = 0; for (int k = 0; k < n; k++) { int s = cross(p[i], p[j], p[k]); if (s > 0) s1 = max(s1, s); else s2 = max(s2, -s); } if (s1 > 0 && s2 > 0 && s1 + s2 > res) res = s1 + s2; } printf("%d\n", (res + 1) / 2); return 0; } ``` [/details] # C. 恋爱与选举与手织围巾  ## Idea 搬自：[84. 柱状图中最大的矩形](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/) ## Summary 求柱状图内矩形的最大面积。 ## Solution 用单调栈处理出每条布条两侧第一条长度比它小的布条的位置。 枚举每条布条作为矩形中长度最短的布条计算面积取最大值即可。 时间复杂度为 $\mathcal O\left(n\right)$。 ## Code [details: C++] ```cpp #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int a[maxn]; void solve() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } a[n] = -1; long long ans = 0; stack<int> s; for (int i = 0; i <= n; i++) { while (!s.empty() && a[s.top()] > a[i]) { int j = s.top(); s.pop(); int l = s.empty() ? i : i - s.top() - 1; ans = max(1ll * l * a[j], ans); } s.push(i); } printf("%lld\n", ans); } int main() { int T; scanf("%d", &T); while (T--) { solve(); } return 0; } ``` [/details] # D. 总之就是非常酸  ## Idea 不小心出难了的题，觉得难可以把 C 开头的出题人打一顿 qwq ## Summary 水平线上反复横跳恰掉下的柠檬，求最多能恰到多少个。 ## Solution 第 $i$ 个柠檬掉到地上的时刻为第 $y_i+t_i$ 秒，将柠檬关于 $y_i+t_i$ 排序。 现在，恰完第 $i$ 个柠檬后就只能恰排在它后面的柠檬，因为排前面的柠檬都已经掉到地上了。 考虑 DP，记 $dp_i$ 表示从第 $i$ 个柠檬开始恰所能恰到的柠檬的最大数量。 当且仅当 $j>i,\ \left|x_i-x_j\right|\le y_j+t_j-y_i-t_i$ 时有状态转移方程 $$dp_i=\max\left(dp_i,dp_j+1\right)$$ 注意，转移前均有 $dp_i=1$。 则从起点 $\left(a,0\right)$ 出发所能恰到的柠檬的最大数量为 $$ans=\max_{\left|a-x_i\right|\le y_i+t_i}dp_i$$ 仔细考虑，好像有点不对劲？ > 恰完第 $i$ 个柠檬后就只能恰排在它后面的柠檬，因为排前面的柠檬都已经掉到地上了。 这句话似乎有点问题？万一有多个柠檬在同一时间同一位置掉到地上呢？ 实际上这些柠檬是相邻的，DP 时会在最左边的柠檬处取到最优解，故对最终答案没有影响。 时间复杂度为 $\mathcal O\left(k^2\right)$。 ## Code [details: C++] ```cpp #include <bits/stdc++.h> using namespace std; const int maxn = 2005; pair<int, int> f[maxn]; int dp[maxn]; void solve() { int k, a; scanf("%d%d", &k, &a); f[0] = make_pair(0, a); dp[0] = 1; for (int i = 1; i <= k; i++) { int x, y, t; scanf("%d%d%d", &x, &y, &t); f[i].first = y + t; f[i].second = x; dp[i] = 1; } sort(f + 1, f + k + 1); for (int i = k - 1; i >= 0; i--) { for (int j = k; j > i; j--) { int dt = f[j].first - f[i].first; int dx = abs(f[i].second - f[j].second); if (dt >= dx) dp[i] = max(dp[i], dp[j] + 1); } } if (dp[0] - 1 == k) printf("All strike!\n"); else if (dp[0] - 1 == 0) printf("All miss!\n"); else printf("He can claim %d lemon(s).\n", dp[0] - 1); } int main() { int T; scanf("%d", &T); while (T--) { solve(); } return 0; } ``` [/details] # E. 关于 Alice 和 Bob 不喜欢造句游戏这档事   ## Idea 毒瘤博弈题，觉得毒瘤可以把 E 开头的出题人打一顿 qwq 不过结论比较简单，容易猜出来，所以还行？ 原来的版本是没有每次只能用一个新词的限制的，因为比较难所以就改了。 ## Summary 给定 $n$ 个元素，两人轮流选 $3$ 个不同元素构成三元组。 规定： - 某个元素如果被用过，那之后再用它构造三元组时，它的位置不能变。 - 除第一次操作，之后最多选一个没用过的元素来构造三元组。 - 构造的三元组不能重复，谁不能构造谁输。 求先后手谁会赢。 ## Solution 若 $n<3$，显然先手必败，考虑 $n\ge3$。 设最后被选为主谓宾的分别有 $a,b,c$ 个词，显然满足 $a+b+c=n$，有 $abc$ 种可能的造句。 若 $n$ 为偶数，则 $a,b,c$ 只可能是三个偶数或两奇一偶中的一种，则 $abc$ 必为偶数，先手必败。 若 $n$ 为奇数，则 $a,b,c$ 只可能是三个奇数或一奇两偶中的一种。 设当前主谓宾分别有 $x,y,z$ 个，开始时 $x=y=z=0$。 先手第一次造句必定使得 $x=y=z=1$，此时 $x,y,z$ 为三个奇数。 先手需要使得 $x,y,z$ 最终为三个奇数，即 $a,b,c$ 为三个奇数才能获胜。 - 若后手不使用新词造句，先手必定也能不使用新词造句。 因为 $x,y,z$ 为三个奇数，故不引进新词时有奇数种造句，最终后手不得不使用新词造句。 - 若后手使用新词造句，注意到一次最多使用一个新词，则 $x,y,z$ 变为两奇一偶。 必定有未被使用的新词，后手可使用一个来造句使 $x,y,z$ 重新变为三个奇数。 于是，先手可使得 $a,b,c$ 最终为三个奇数，先手必胜。 时间复杂度为 $\mathcal O\left(T\right)$。 ## Code [details: C++] ```cpp #include <cstdio> using namespace std; int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); if (n < 3) printf("Makise Von\n"); else printf("%s\n", n % 2 == 0 ? "Makise Von" : "EndA"); } } ``` [/details] # F. 没有人比我更懂肉灌饼   ## Idea [D. Extreme Subtraction](https://codeforces.com/contest/1443/problem/D) 加强，为了防某些神仙 AK 整的题，觉得难了的话那就对了 qwq 最后还是被 AK 了，前面还因为数据不太好构造所以比较弱，让部分同学水过去了。 本来是想现场给一组数据，就不重测了，奈何负责现场的同学手速太快已经重测了 233 水过去的同学可以试试这组数据： **Input** ``` 1 5 2 0 2 0 2 3 3 3 3 3 ``` **Output** ``` No ``` ## Summary 给定长度为 $n$ 的序列 $a,b$，有两种操作： - 选择一个 $k$ $\left(1\le k\le n\right)$ 使 $a_1,a_2,\ldots,a_k$ 分别 $+1$。 - 选择一个 $k$ $\left(1\le k\le n\right)$ 使 $a_k,a_{k+1},\ldots,a_n$ 分别 $+1$。 问能否在 $a_i\le b_i$ 的同时使 $a_1=a_2=\ldots=a_n$。 ## Solution 显然 $a_i$ 存在一个上界，即 $lim=\min\limits_{1\le i\le n}b_i$。 若存在 $a_i>lim$ 则必定不能满足火火的要求。 否则，假设可以满足火火的要求，则必定存在某次操作使 $a_i$ 相同。 记 $c_i=lim-a_i$，进行一次转化： - 操作转化： - 选择一个 $k$ $\left(1\le k\le n\right)$，然后使$c_1,c_2,\ldots,c_k$ 分别 $-1$。 - 选择一个 $k$ $\left(1\le k\le n\right)$，然后使$c_k,c_{k+1},\ldots,c_n$ 分别 $-1$。 - 问题转化：判断是否能使 $c_1,c_2,\ldots,c_n$ 相同且不小于 $0$。 考虑差分。令 $c_0=0$，记 $d_i=c_i-c_{i-1}$，再进行一次转化： - 操作转化： - 选择一个 $k$ $\left(1\le k\le n\right)$，然后令 $d_1=d_1-1$。 若 $k<n$，再令 $d_{k+1}=d_{k+1}+1$。 - 选择一个 $k$ $\left(1\le k\le n\right)$，然后令 $d_k=d_k-1$。 - 问题转化：判断是否能使 $d_1,d_2,\ldots,d_n$ 均变为 $0$。 考虑贪心，显然只需满足 $$d_1+\sum\limits_{i=2}^n\left[d_i<0\right]d_i\ge0$$ 时间复杂度为 $\mathcal O\left(tn\right)$。 ## Code [details: C++] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; const int inf = 1e9 + 5; int a[N], b[N], c[N], d[N]; void solve() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a + i); int lim = inf; for (int i = 1; i <= n; i++) scanf("%d", b + i), lim = min(lim, b[i]); long long sum = 0; for (int i = 1; i <= n; i++) { c[i] = lim - a[i]; if (c[i] < 0) return puts("No"), void(); d[i] = c[i] - c[i - 1]; if (i == 1 || d[i] < 0) sum += d[i]; if (sum < 0) return puts("No"), void(); } puts("Yes"); } int main() { int t; scanf("%d", &t); while (t--) solve(); return 0; } ``` [/details]