GDOI2022普及组解题总结
前情：游记
而这篇是为了进一步总结做题相关的。
D1T2 数列游戏
把两个元素间的空隙看做一个端点，一次合并相当于不允许取一个端点。
很明显的思路是要让原来异或和为 \(0\) 的区间取不到，也就是合并掉存在异或和为 \(0\) 的区间的左右端点，那现在的问题就是找到这些区间。
注意到满足要求的区间拥有传递性（两个端点重合的区间合并起来也满足要求），于是可以维护一个并查集，如果一个区间的异或和为 \(0\)，就把它的左右端点合并起来。同一个并查集中的任意两个元素中至多保留一个，答案就显然了。
有段代码今生难忘。
for(int i = 1; i <= n; i++){
int u = find(i); if(vis[u]) continue; //然后呢，你不标记走过吗
ans += siz[u] - 1;
}
正解不对拍，爆零两行泪。
点击查看非考场代码
#include
#include D1T3
很有趣的一道题。赛时写的以为错解实际上是对的。
观察式子，发现当点数增加时必须让 \(\max(w_1,\cdots,w_m)\) 小下来，所以下推非当前最大节点是无意义的。
于是优先队列（或 set）就能轻松维护了。动态维护一个集合，每次取出非叶子中权值最大的并下推，途中记录最小值，即得。
点击查看代码
#include
#include
#include
using namespace std;
const int M = 100005;
struct edge{
int to, nxt;
}e[M << 1];
int head[M], cnt1;
void link(int u, int v){
e[++cnt1] = {v, head[u]}; head[u] = cnt1;
}
int w[M], n, f[M]; bool l[M]; long long ans = 1e18;
struct dat{
int t;
bool operator < (const dat &tmp) const{ //for set
if(l[t] && !l[tmp.t]) return 0;
if(w[t] != w[tmp.t]) return w[t] > w[tmp.t];
return t < tmp.t;
}
};
set q;
void calc(){
while(1){
int u = q.begin() -> t;
q.erase({u});
ans = min(ans, 1ll * w[u] * ((long long)q.size() + 1));
for(int i = head[u]; i; i = e[i].nxt)
q.insert({e[i].to});
if(!l[u]) break; //如果全是叶子就应返回了
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
for(int i = 2; i <= n; i++)
scanf("%d", &f[i]), link(f[i], i), l[f[i]] = 1;
q.insert({1}); ans = w[1];
calc();
printf("%lld\n", ans);
}
/*
5
10 7 3 3 2
1 1 2 2
*/
D1T4 小学生计数题
两天唯一讲解没听懂的题……
后来自己去补了补。
枚举公差。这是一个复杂度为 \(O(n \ln n)\) 的调和级数枚举。
枚举完后，枚举末尾。与末尾对应的开头也是一段区间，这个可以用逆元前缀和弄出来。
这就结束了。
总结：完全不知道“调和级数枚举”的存在，一心在想 \(dp\)，但其实该想到以前求出的答案可以被后面利用，进而自己逼近这个思想。
D2T1
只要找不是 \(n,n-1,n-2\) 约数的数，从反面找， \(\varphi(x)\) 套容斥就结束了。
D2T2
一次打开只能多浏览一个网页，关闭能关闭不止一个，容易想到往长儿子放一定不劣。
两遍 \(dfs\) 结束了。（赛时）
但是赛时讨论错了一些细节，还是必须细心些
如果讨论对可以发现就是 \(n\) + 叶子数。
D2T3
大模拟，无话可说。
1h20min 没拿到分，码力尚需加强 /kk
D2T4
好玩度仅次于 D1T4 的题。
先想暴力，发现可以用一个 bool 数组记录用前 \(i\) 个操作能否到达某个格子，然后就顺水推舟发现可以直接算每个格子最早可以几次操作到达，这个能用 dij 维护，提前预处理每个操作之后第一个每种操作，就能过了。
但是细节还是不少，写+调也花了 1h，最后的代码将也就 \(70\) 行（没怎么压行），赛后发现又挂在细节上了。
if(vx <= 0 || vx > n || vy <= 0 || vy > m) return 0; //走出去是 <1，你是不是多项式用 0 和 n 用傻了
惊险的故事：离结束 10min 时发现自己多测没清空……
点击查看代码
#include
#include
#include
#define inf 1000000005
using namespace std;
const int M = 505, N = 100005;
int dis[M][M], g[N][4], T; //dis:到达每个位置最少到什么时候
//g:每条指令后面的第一个某种指令在什么时候
int n, m, l, sx, sy; char s[N], a[M][M];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int get(char c){
switch(c){
case 'W' : return 0;
case 'S' : return 1;
case 'A' : return 2;
case 'D' : return 3;
default : return 114514; //不会 warning了
}
}
struct dat{
int x, y, dis;
bool operator < (const dat &t) const{
return dis > t.dis;
}
};
priority_queue q; bool vis[M][M];
bool dfs(int sx, int sy){
// printf("in %d %d\n", sx, sy);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
dis[i][j] = inf, vis[i][j] = 0;
dis[sx][sy] = 0; q.push({sx, sy, 0});
while(!q.empty()){
int ux = q.top().x, uy = q.top().y; q.pop();
// printf("ux = %d uy = %d d = %d\n", ux, uy, dis[ux][uy]);
if(vis[ux][uy]) continue; vis[ux][uy] = 1;
int d = dis[ux][uy];
for(int i = 0; i < 4; i++){
if(!g[d][i]) continue;
int vx = ux + dx[i], vy = uy + dy[i];
if(vx <= 0 || vx > n || vy <= 0 || vy > m) return 0;
if(a[vx][vy] == '*') continue;
// printf("vx = %d vy = %d g[%d][%d] = %d\n", vx, vy, d, i, g[d][i]);
if(g[d][i] < dis[vx][vy])
dis[vx][vy] = g[d][i], q.push({vx, vy, dis[vx][vy]});
}
}
return 1;
}
void clear(){
memset(dis, 0, sizeof(dis)); memset(g, 0, sizeof(g));
memset(s, 0, sizeof(s)); memset(a, 0, sizeof(a));
}
int main(){
scanf("%d", &T);
while(T--){
scanf("%s", s+1); l = strlen(s+1);
int p[4] = {0, 0, 0, 0};
for(int i = 1; i <= l; i++){
int op = get(s[i]);
for(int j = p[op]; j < i; j++) g[j][op] = i;
p[op] = i;
}
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%s", a[i] + 1);
for(int j = 1; j <= m; j++)
if(a[i][j] == 'R') sx = i, sy = j;
}
printf("%s\n", dfs(sx, sy) ? "NO" : "YES");
clear();
}
}
/*
2
DWAWAADWASDSWSS
8 8
.***...*
**....*.
**...**.
**.*.***
......**
.*..*..*
*...**R*
...*..**
DWAWAADWASDSWSS
8 8
.***...*
**....*.
**...**.
**.*.***
......**
.*..*..*
*...**R*
..**..**
*/
总结
本来预计有 \(630\) 分的，最后却一共挂了 \(3\) 题，全都挂在细节上，要是能对拍或至少静态查错或许还能查出 1-2 道。
D2T3 LMY 仅花了 1h 便敲完了，所以我还是码力太弱了 /kk 是不是该练点大模拟了 /kel