20231029 NOIP#27 总结
时间安排
7:35~8:05
看题，\(A\) 一时不会，\(B\) 想到了构造方式不确定对，\(C,D\) 一档暴力。
8:05~8:35
写 \(B\) 构造，并且这个构造是对的。
8:35~9:00
写 \(C\) 的爆搜
9:00~9:30
写 \(D\) 的暴力
9:30~10:00
想到了 \(A\) 正解并写完。
10:00~10:20
写 \(C\) 的两档特殊性质
10:20~10:50
写 \(D\) 的特殊性质。
10:50~11:50
罚坐中。
题解
A.差分
发现对于 \(i\) 的修改操作在差分序列上表现为 \(swap(a[i]-a[i-1],a[i+1]-a[i])\)，所以判断 \(a,b\) 的差分序列的对应个数是否相等即可。
B.构造
最短 \(LIS\) 例：\(8>7>[5<6]>4>[1<2<3]\)
最长的直接将序列翻转 \(\pi\ rad\)，并用相同方法构造。例：\([3>2>1]<[6>5>4]<7<8\)
C.DP
令 \(f[i][j]\) 表示走到 \(i,j\) 的最后一步向下，下一步开始往右走的走法数量。
令 \(g[i][j]\) 表示走到 \(i,j\) 的最后一步向右，下一步开始往下走的走法数量。
则有转移 \(f[i][j]\) 加到 \(g[i][j+1]\) 到 \(g[i][pos]\) 上，\(pos\) 为一直向右推箱子直到推不动的位置。另一个转移同理。
答案为 \(f[n][m]+g[n][m]\)
D.倍增+二维数点
考虑链的情况，如CF1175E Minimal Segment Cover
维护 \(g[i]\) 表示覆盖 \(i\) 的线段中最大的右端点，进一步的，维护 \(g[i][j]\) 表示 \(i\) 跳 \(2^j\) 次之后的最大覆盖右端点。转移到树上就表示覆盖的深度最小的点。
对于一个询问 \((x,y)\)，若有解，则定义 \((u,v)\) 为 \((x,y)\) 经铁路到 \(lca\) 的路径上离 \(lca\) 差一步的点。
若存在铁路连接 \(u\) 子树内的某点和 \(v\) 子树内的某点，则答案为 \(dis(x,u)+dis(y,v)+1\)，否则为 \(dis(x,u)+dis(y,v)+2\)
这个判断可以用二维数点完成，具体方法为：
将每一条铁路 \((a,b)\) 转化为二维平面上的一个点 \((dfn[a],dfn[b])\)，若 \(x\in[dfn[u],dfn[u]+siz[u]-1],y\in[dfn[v],dfn[v]+siz[v]-1]\) 的二维矩阵内有点，则存在如上条件的铁路。