专栏文章

杂题选讲 做题记录

TTwilight_star
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmnl63
此快照首次捕获于
2025/12/02 04:54
3 个月前
此快照最后确认于
2025/12/02 04:54
3 个月前
查看原文
题目标题后不带任何符号的说明此题是完全独立思考通过。
题目标题后带 * 的说明此题是在获得提示后通过。
题目标题后带 ** 的说明此题是在观看题解后通过。

2025.10.10 杂题选讲

1. AT_joisc2018_c Tents**

可以注意到，若 (x,y)(x,y) 有帐篷的话，若这一行和这一列都有另外一个则无解；若这一行或这一列有另一个，则该帐篷只有一种方向；否则方向有四种可能。
于是考虑设 dpi,jdp_{i,j} 表示有 ii 行 jj 列的答案。
现在考虑新加入第 i+1i+1 行：
  • 若加入这一行没有帐篷，则有转移 dpi+1,j←dpi,jdp_{i+1,j}\gets dp_{i,j}。
  • 若加入这一行有一个帐篷，且该帐篷所在列没有帐篷，那么该帐篷所在列作为新的一列加入，则有 dpi+1,j+1←4×(j+1)×dpi,jdp_{i+1,j+1}\gets 4\times (j+1)\times dp_{i,j}。
  • 若加入这一行有一个帐篷，且该帐篷所在列有一个另外的帐篷，则考虑将另外的这个帐篷视为新的一行加入，则有转移：dpi+2,j+1←(i+1)×(j+1)×dpi,jdp_{i+2,j+1}\gets (i+1)\times (j+1)\times dp_{i,j}。
  • 若加入这一行有两个帐篷，则有转移：dpi+1,j+2←dpi,j×(j+22)dp_{i+1,j+2}\gets dp_{i,j}\times {j+2\choose 2}。
综上时间复杂度 O(n2)O(n^2)。

2. P10744 Modulo Permutations

注意到 1,21,2 后面接什么都可以，也就是填入两个序列。直接 dp 即可。
时间复杂度 O(nln⁡n)O(n\ln n)。
提交记录

3. P9461 众数 II

考虑 xx 什么时候能替代 11 作为答案。发现所涉及的所有块的 ai≥xa_i\ge x，并且最左边的块必须取 xx 开头，最右边的块必须取 xx 结尾。
直接列式子求就行了。
时间复杂度 O(nlog⁡n)O(n\log n)。
提交记录

4. P7457 The Bridge on the River Kawaii

发现 vv 很小，这下直接枚举 vv 即可。然后就是一个线段树分治+可撤销并查集即可。
时间复杂度 O(vnlog⁡n)O(vn\log n)。
不过 vv 大一点好像可以直接整体二分，可以做到 O(nlog⁡nlog⁡V)O(n\log n\log V)。
提交记录

5. P5871 Inversion*

bro 你怎么绿了。
注意到一个极长单调下降子序列为一个完全图，那么该子序列里必须取刚好一个点。那么一个合法方案就是一个极长单调上升子序列。
于是直接 dp。
时间复杂度 O(n2)O(n^2)。
提交记录

6. P3363 Cool loves jiaoyi**

唉唉双指针还是不熟。
最小极差问题考虑双指针。判断合法就直接用树剖维护最大经过点的次数即可。
时间复杂度 O(nlog⁡2n)O(n\log ^2n)。
提交记录

7. P4350 Export Estimate

本题一大难点是读懂题。
发现对 ii 操作时，其他所有点的度数都不会变，也就是原本度数为 22 的点操作完后仍然为 22。所以最终的操作次数为图中度数为 22 的点的个数，但是有一种特殊情况就是整个连通块是一个单环，此时最终会剩一个点，用并查集特判一下。
剩余边数也跟成功操作次数有关，直接算出来即可。
时间复杂度 O((q+m)log⁡n)O((q+m)\log n)，瓶颈在排序。
提交记录

8. P7220 [JOISC 2020] 掃除**

顶级数据结构题。
做法比较多，这里只讲一种。
每个点 (x,y)(x,y) 可以投射到斜面，得到一个线段 [x,n−y][x,n-y]。
（图片来源 KobeBeanBryantCox 的题解，侵删）
那么每一次纵向操作 xx 都是让所有满足 l≤xl\le x 线段 [l,r][l,r] 执行 r←min⁡(r,x)r\gets \min(r,x)。
同理，每一次横向操作 xx 都是让所有满足 r≥n−xr\ge n-x 的线段执行 l←max⁡(l,n−x)l\gets \max(l,n-x)。
那么如何维护这个操作呢？
考虑对于动态开点线段树上每一个点建一个容器。把每一个线段 [L,R][L,R] 放在满足 L≤mid≤RL\le mid\le R 的深度最浅的节点上。
对整棵树执行 r←min⁡(r,x)r\gets \min(r,x) 时，
  • 若 x≥midx\ge mid，则直接将该节点存的的所有线段的右端点 ≥x\ge x 的全部赋值成 xx。
  • 若 x<midx< mid，则将所有 l≤xl\le x 的线段取出，暴力修改这些线段的右端点，然后暴力往下递归查找这个新线段该放到哪个节点上。因为树深度为 O(log⁡n)O(\log n)，所以每个节点最多进行 O(log⁡n)O(\log n) 次该操作。
执行 l←max(l,x)l\gets max(l,x) 时同理。
于是考虑每个节点上用平衡树维护。此时发现每个线段的 [l,r][l,r] 可以分开存。因为需要，我们每个节点开两棵平衡树，一棵以 ll 升序排序，一棵以 rr 升序排序，同时还需支持区间赋值操作。这里直接用 fhq-treap 即可。那么暴力取出节点时，还需同时取出另一棵树上的对应节点。
那么总时间复杂度 O(qlog⁡2n)O(q\log^2 n)，支持在线。
提交记录

9. P7324 表达式求值**

发现 ? 是两边任取一边。
首先根据序列构建出二叉树。然后直接 dp。
考虑对于每一个数 ai,ja_{i,j}，求出最终计算结果等于它的方案数。设 dpu,0/1/2dp_{u,0/1/2} 为当前节点为 uu，且结果 小于/等于/大于 ai,ja_{i,j} 的方案数。
则当 uu 的运算符为 > 时，则有：
dpu,k=∑max(i,j)=kdplson,i×dprson,jdp_{u,k}=\sum_{max(i,j)=k}dp_{lson,i}\times dp_{rson,j}
则当 uu 的运算符为 < 时，则有：
dpu,k=∑min(i,j)=kdplson,i×dprson,jdp_{u,k}=\sum_{min(i,j)=k}dp_{lson,i}\times dp_{rson,j}
如果是 ? 则把上面两种情况加起来。
这样做是 O(nm∣S∣)O(nm|S|)。无法通过。
发现 mm 很小，所以考虑 2m2^m 的做法。对于一个 ii，设满足 aj,x<ai,xa_{j,x}<a_{i,x} 的 jj 集合 SS，那么我们根据这个，同样列出 dpS,u,0/1/2dp_{S,u,0/1/2} 表示“小”的集合为 SS 的方案数。
这样预处理的时间复杂度为 O(2m∣S∣)O(2^m|S|)。
然后对于每一个 ai,ja_{i,j}，求出满足 ak,ja_{k,j} 的 kk 构成的集合 SS，求出 dpS,rt,1dp_{S,rt,1} 即为方案数。
这样做可能会被卡常，实际上只用记 dpS,u,0/1dp_{S,u,0/1} 表示 小于/大于等于 的方案数，然后再容斥一下即可。
时间复杂度 O(2m∣S∣+nm)O(2^m|S|+nm)。
提交记录

10. P7294 Minimum Cost Paths P*

设 ansy(x)ans_y(x) 为走到 (x,y)(x,y) 的最小代价。
注意到 ansy(x+1)−ansy(x)≥ansy(x)−ansy(x−1)ans_y(x+1)-ans_y(x)\ge ans_y(x)-ans_y(x-1)。
记录 fy(x)=ansy(x+1)−ansy(x)f_y(x)=ans_y(x+1)-ans_y(x)。
那么 fy(x)=min⁡(cy,fy−1(x)+2x+1)f_y(x)=\min(c_y,f_{y-1}(x)+2x+1)。而 f1(x)=c1f_1(x)=c_1。
只要维护出 ∑i=1xfy(i)\sum_{i=1}^x f_y(i) 即可，并支持整体加一个公差为 22 的数组，以及区间取 min⁡\min（但这里是单增的，所以可以改为区间赋值）。
不知道能不能用线段树，应该挺复杂的。
这里我用的二分+栈。栈里存的是取 min⁡\min 时的断点。每一次取 min⁡\min 可以根据当前时间戳和该断点的时间戳求出该点在此时的值，如果大于 cyc_y 则直接弹出，否则保留并对后面这个部分进行二分。
而 ∑i=1nfy(i)\sum_{i=1}^n f_y(i) 只需在同时维护一个前缀和即可快速计算。
时间复杂度 O(mlog⁡m+q)O(m\log m+q)。
提交记录，最优解第一页！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...