学长出题规律：T1签到题，T2套路题（但没见过），T3神奇题（赛时想的做法几乎都是错的），T4peppapig题
学长：今天T3防AK
peppapig：今天比赛防爆零
A. Permutations & Primes 20pts
签到题，可惜没有签到；
显然，我们要让经过1的区间最多，所以将1放在序列中间；
除了1，就是2和3，所以我们把2和3放在两边，这样就可以保证中间及不同时覆盖两边且覆盖到1的区间都是合法的；
然后随便填，就完了；
赛时将1和2放在了一块，导致20pts；
其实也可以将合数放中间，1放最中间，质数放两边，这样也是最大的，就是需要筛一下；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int t;
int n;
int a[500005];
bool pri[500005];
bool vis[500005];
void w(int x) {
for (int i = 2; i <= x; i++) {
if (!vis[i]) {
vis[i] = true;
pri[i] = true;
for (int j = 2; i * j <= x; j++) {
vis[i * j] = true;
}
}
}
}
int main() {
cin >> t;
w(300005);
while(t--) {
cin >> n;
if (n == 1) {
cout << 1 << endl;
continue;
}
if (n == 2) {
cout << 2 << ' ' << 1 << endl;
continue;
}
a[n / 2 + 1] = 1;
a[1] = 2;
a[n] = 3;
int x = 4;
for (int i = 2; i <= n / 2; i++) {
a[i] = x;
x++;
}
for (int i = n / 2 + 2; i <= n - 1; i++) {
a[i] = x;
x++;
}
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
cout << endl;
}
return 0;
}
B. 树上游戏 47pts
原题：$ ARC116E $；
貌似又是套路题。。。
我们可以贪心的来考虑，假设现在我们所允许的不满意度（危险度）为 $ dis $，那么从叶子节点开始向上 $ dis $ 个长度需要有一个，然后这颗子树我们就可以删去不考虑了；
发现：如果知道答案，那么验证这个答案的合法性就变得比较容易；
做法：二分答案；
具体的，我们进行 $ dfs $，统计每个节点的危险度 $ f[x] $ 和它距离它的没有删去的儿子的最长距离 $ g[x] $，遍历完这个节点的所有儿子后统计答案即可；
最后判断当前选的点数与 $ k $ 的大小关系完成 $ check $；
赛时居然想到用找重心的方法去做，很显然是错的（新知识没掌握导致的，总是会乱想是不是刚学的）。又乱搞推出了一个看起来不太对的“通式”，整了47pts；
看来现在赛时想出正解确实不容易啊。。。
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n, k;
struct sss{
int t, ne;
}e[1000005];
int h[1000005], cnt;
void add(int u, int v) {
e[++cnt].ne = h[u];
h[u] = cnt;
e[cnt].t = v;
}
int f[1000005], g[1000005];
int dfs(int x, int fa, int dis) {
int res = 0;
bool vis = false;
f[x] = 0x3f3f3f3f;
g[x] = -0x3f3f3f3f;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa) continue;
vis = true;
res += dfs(u, x, dis);
f[x] = min(f[x], f[u] + 1);
g[x] = max(g[x], g[u] + 1);
}
if (f[x] + g[x] <= dis) { //最大的危险程度可以接受，直接删除这棵子树；
g[x] = -0x3f3f3f3f;
}
if (!vis) { //是叶子节点；
g[x] = 0;
}
if (f[x] > dis) g[x] = max(g[x], 0); //危险程度太高，需要等祖先设立；
if (g[x] == dis) { //此时必须设立，要不后代就不满足要求了；
res++;
f[x] = 0;
g[x] = -0x3f3f3f3f; //删除这棵子树；
}
return res;
}
bool ck(int x) {
return (dfs(1, 0, x) + (g[1] >= 0)) <= k; //根节点需不需要设立；
}
int main() {
cin >> n >> k;
int x, y;
for (int i = 1; i <= n - 1; i++) {
cin >> x >> y;
add(x, y);
add(y, x);
}
int l = 1;
int r = n;
int ans;
while(l <= r) {
int mid = (l + r) >> 1;
if (ck(mid)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
cout << ans;
return 0;
}
可能把 $ g $ 数组设为 $ -INF $ 以删除子树这种操作也是一种常见套路吧；
C. Ball Collector 0pts
用到了一种数据结构，叫可撤销并查集；
其实这种题又有一种常见套路：将 $ a_i $ 与 $ b_i $ 连边；
其实赛时想出来了，不过是将 $ a_i $ 与 $ b_i $ 的反面连边，然后跑 $ 2-SAT $，结果最后发现只能输出一种可行方案，不能输出最大值，这些专题确实赶得太紧了，没掌握；