# 别对出题人出手!
## 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]

JLU Qingyun Cup 2020 - Solution for Senior Division