题解-2019省选题题解集合

佚名 6年前 (2019-05-06) 随笔 1494人围观抢沙发百度已收录

正在补坑……部分题目太水就不放代码了

省份	D1T1	D1T2	D1T3	D2T1	D2T2	D2T3
\(\mathrm {BJOI}\)				X	X	X
\(\mathrm {GZOI}\)	X		X		X	X
\(\mathrm {HNOI}\)			X	X
\(\mathrm {JSOI}\)
\(\mathrm {SNOI}\)	X	X	X
\(\mathrm {TJOI}\)		X
\(\mathrm {ZJOI}\)		X

BJOI2019

D2T1 排兵布阵

显然对于每一座城堡，只有等于某个人+1时才有可能成为最优策略，做个背包 \(O(nms)\)

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

D2T3 删数

设 \(b_i\) 为值为 \(i\) 的数的个数，发现 \(\forall i\in[1,n]\)，若不存在 \(j\) 使得 \(i\in(j-b_j,j]\)，则位置 \(i\) 需要一次“修改”，则答案就是统计位置 \([1,n]\) 共有多少位置需要“修改”

线段树维护，可以使用扫描线线段树的技巧（加tag和删tag一一对应，不用下推标记）。单点修改相当于区间修改几次；整体加减一相当于将区间左右移，这个可以记录平移偏量，对进出右边界的格子进行修改

Code

GZOI2019

D1T1 与或和

位运算的题明显按位拆开考虑，对于每一位相当于是问有多少个全 \(0/1\) 矩阵：枚举矩阵的右下角，考虑左上角关于横坐标是一个单调栈，在扫描每一行的时候维护这个单调栈即可 \(O(n^2)\)

总复杂度 \(O(31n^2)\)

D2T2 旅行者

二进制分组：进行 \(\log n\) 次分组，第 \(i\) 次按照关键点编号的二进制编码下第 \(i-1\) 位是否为一分类，每次求出从一个集合到另一个集合的最短路。总复杂度 \(O((n+m)\log^2n)\)，已然可以通过此题

直接暴力：先跑一遍最短路，将边反向后再跑一次最短路，考虑每条边的贡献（两端点最近关键点的距离，若是同一个点则不予统计）。总复杂度 \(O((n+m)\log n)\)

D2T3 旧词

做过 LNOI2014 lca 的可以秒切，那题大概就是这题去掉上头那个 \(k\) 次幂，下面是那题的题解：

可以将一个点的深度转换成该点到根节点的路径上的点个数，那么考虑将这个点的深度 \(dep\) 贡献平摊到这个点到根路径上的总共 \(dep\) 个点上去，每个点贡献为一，那么查询这个点的权值就是查到该点到根的权值和

那么 \(\sum_{i=l}^rdep[lca(i,z)]\) 的询问就是：
将\(l\)到\(r\)这些点到根的路径上的点的点权全部加一（每个点都要加一次），最后询问\(z\)到根路径上的权值和，离线扫描即可。复杂度 \(O((n+m)\log^2n)\)

回到 GZOI 这题来，这题就只要在每个点上预先设好 \(dep^k\) 的权值，加 \(1\) 变为加对应的点的权值，线段树也支持。复杂度不变依旧是 \(O((n+m)\log^2n)\)

HNOI2019

D1T3 多边形

明显这个多边形的终态是点 \(n\) 连出 \(n-3\) 条边，为了达到最优解，则每次一定会连一条边到 \(n\)，同时也一定会存在这样的一次操作，第一问得解

考虑第二问。模拟上头的贪心，发现每次可以将当前区段分为两段分治求解，即一棵树结构，答案就是这棵树不同的拓扑序数，拓扑序数的统计可以在每个节点处用组合数合并儿子们，做到这里就有 \(65\) 分了

再考虑合并儿子的式子，可以由 \(\prod \binom {sz_1+sz_2}{sz_1}\) 的形式转成 \(\frac {sz_x!}{\prod_{x\rightarrow v}sz_v!}\)，则计算了根节点后，其余节点的贡献是 \(\prod \frac 1{sz_x}\) 的形式，而一条边 \((x,y)\) 在树上对应节点的子树大小为 \(|x-y|-1\)

至于怎么快速进行一次旋转，对于每个点维护一个出边集合，找前驱后继即可

Code

D2T1 校园旅行

这题我在省选考场上被卡栈卡了 \(40pts\)，而且出题人本来打算给我的做法 \(70pts\) 的，然后就掉到队尾了 (⊙v⊙)

但是这题的 \(70pts\) 做法和 \(100pts\) 做法是两个方向 (∪_∪)，myy的做法感觉很妙

\(30pts\) 考虑一条回文路径在两端加上一对相同的点也是回文路径，所以从一个点或者一条同色边开始扩展，记忆化即可 \(O(n^2+m^2)\)

\(70pts\) 也差不多，只是在转移时两端不要同时转移，先转移一边再转移另一边，可以做到 \(O(n^2+nm)\)，但是实际在考场上测得只有 \(30pts\)，数据只放过了 \(40pts\) 然后就被卡栈惹

正解依旧使用 \(30pts\) 做法，只不过将边的数量缩小到 \(O(n)\) 级别：

将边分为三类：两端都是 \(0\)；两端都是 \(1\)；一端是 \(0\) 一端是 \(1\)
将三类边每一类单独建图，对于每一个联通块而言，若为二分图则保留一棵生成树，否则在某一个点上加上一条自环

正确性不好说明，自己去理解比较好：对于任意一条原图上的回文路径，可能会因为上面做法中只保留一棵生成树而毁坏，但连通性还是可以保证的，而且能经过保留的生成树找到对应同奇偶的替代方案（若这个图不是二分图就要加自环是因为原图中可以改变这个点的奇偶性，而新图中可以依据这条自环改变奇偶性）

Code

SNOI2019

D1T1 字符串

看到有人用 \(O(n\log n)\) 的做法，其实可以 \(O(n)\)

明显可以将相邻的相同字符合并，先处理完相邻字符都不一样的情况，最后在输出时一起输出。比如 aaabb，可以先将 aaa 和 bb 分别合并，得到 ab，排序可得答案为 4 1，再将刚被合并的相邻相同字符放进去，得到 (4) 5 (1) 2 3（其中打括号的为合并后的答案，无括号的即刚加入字符）

那么只需考虑相邻字符不同的情况惹。对于比较 \(s_i,s_j(i<j)\)，只需考虑 \(a_i,a_{i+1}\) 的大小关系即可。如此可以知道对于每一个 \(s_i\)，它与每一个 \(s_j(i<j)\) 的大小关系都是一样的，那么可以将 \(s_i\) 放在所有 \(s_j(i<j)\) 的前/后边，只要从后往前维护，就可以链表维护惹（需要维护在链表前后插值）。空间时间复杂度都为 \(O(n)\)

Code