专栏文章

10 月做题记录

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minqm2eu
此快照首次捕获于
2025/12/02 06:45
3 个月前
此快照最后确认于
2025/12/02 06:45
3 个月前
查看原文

CF2146E Yet Another MEX Problem

经过一定尝试，我们发现区间快速求 mex 并不好做，因为 mex 本身的含义太复杂了，我们尝试解构 mex，即考虑其定义：不包含于 aa 的最小自然数。我们尝试考虑所有不包含于 aa 的自然数。
对于数列 aa，以及 x∉ax \notin a，我们记 g(a,x)g(a,x) 为 aa 中大于 xx 的数的个数。若 x∈ax \in a，我们规定 g(a,x)=0g(a,x)=0。
显然，w(l,r)=max⁡xg(al..r,x)w(l,r) = \max_x g(a_{l..r}, x)，故
ANSr=max⁡1≤l≤rmax⁡xg(al..r,x)ANS_r = \max_{1 \le l \le r}\max_x g(a_{l..r},x)
然后就是常见的、类似交换求和的技巧：
ANSr=max⁡xmax⁡1≤l≤rg(al..r,x)ANS_r = \max_x \max_{1 \le l \le r} g(a_{l..r}, x)
我们在扫描 rr 的时候维护关于 xx 的数列：bx=max⁡1≤l≤rg(al..r,x)b_x = \max_{1 \le l \le r} g(a_{l..r}, x)。
单个的 bxb_x 如何计算呢？
显然 ll 一定是选择使得 al..ra_{l..r} 不包含 xx 的最小值。由这一计算方法，我们发现可以用线段树维护。需要区间加、单点修改和区间 max。
小结：
第一步看似复杂化了问题，但实际上给了我们更多的操作空间，因为 mex 是一个被封装过的概念，我们对其进行拆解可以获得更多信息。
这与一些和式技巧十分相像。同时这也是一个比较一般的方法可以经常尝试使用。

P12427 [BalticOI 2025] Tour

这种题目一般要么乱搞（但是失败了），要么重建图，把奇怪的关系封装在图里，然后用标准算法跑。
我们以边为点，以转移关系为边建图。此时边数为 m2m^2，我们考虑增加中转点减少边数，但由于有颜色限制，我们不能直接用原图的点当中转点，而是根据二进制拆点，因为两个颜色不同，一定存在一个位不同。
我们用 id(x,j,b)id(x,j,b) 表示原点 xx 对应中转点，其满足指向其的点颜色第 jj 位都为 bb，其指出点颜色第 jj 位都为 ¬b\neg b。
最后 DFS 找环即可。

P10596 BZOJ2839 集合计数

公式要背：容斥原理 & 二项式反演
fkf_k 为钦定 kk 个元素一定在交内，其他部分任意的方案数，gkg_k 为恰好交为 kk 个元素的方案数。
fk=(nk)(22n−k−1)fk=∑k≤i≤n(ik)gi\begin{align} f_k = \binom{n}{k}(2^{2^{n-k}}-1) \\ f_k = \sum_{k\le i\le n}\binom{i}{k}g_i \end{align}
对 (2)(2) 应用二项式反演得到
gk=∑k≤i≤n(−1)i−k(ik)fi=∑k≤i≤n(−1)i−k(ik)(ni)(22n−i−1)g_k = \sum_{k\le i\le n}(-1)^{i-k}\binom{i}{k}f_i = \sum_{k\le i\le n}(-1)^{i-k}\binom{i}{k}\binom{n}{i}(2^{2^{n-i}}-1)
小结：
做题的时候也可能先想到用 (2)(2)。

审题：P11922 [PA 2025] 叠积木 / Wieża

塔的大于号看成大于等于。

P11912 [PA 2025] 集合 2 / Zbiory 2

再次被构思题创飞，solution。

典：P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava

感觉是很经典的优化建图。
首先我们以边为点重新构图就能很方便地确定边权跑最短路，但一个点周围地左右边构成完全图，所以需要优化。
由于边权是由点权（新图）差得到的，所以发现可以删到只剩一条链，链上点权有序。

P13691 [CEOI 2025] highest

很好地强化了我对倍增地理解。
倍增地本质是将操作序列进行压缩。
我们的思路是用 fj,if_{j,i} 表示从 ii 花费 2j2^j 能跳到的最远点。但仅仅这样无法转移，也无法解决询问。
原因是对于某些操作序列，我们花费 2j2^j 可能跳到某个 2 的“中间”。于是我们在用 gj,ig_{j,i} 表示花费 2j−12^j-1 跳的最远距离即可。
因为能挑到的位置显然是连续的，所以可以用 ST 表转移。这有一个细节，理论上从 ii 花费 11 不能仍停在 ii，但我们不用管类似的情况，因为总是不优。
查询时因为不能存下 nlog⁡2nn \log^2 n，所以要离线做“整体倍增”。总复杂度 (n+m)log⁡2n(n+m) \log^2 n。
不知道单 log⁡\log 怎么做的。

R19

T1

可以发现每个前缀永远都是在一个区间内的，因此最后一定形如从某个位置开始每次向左或者向右加数，并且一个数是从左还是从右加只和它后面的操作次数的奇偶性有关。
因此倒着扫一遍，维护操作次数的奇偶性，然后判断当前数字是加在前面还是后面。
时间 O(n+m)O(n+m)。
小结：赛时为了给 aa 排序用了一个计排，T 了。实际上我们只需要 aa 的 cntcnt 即可。

T2

f(n)=n−φ(n)f(n)=n-\varphi(n)，其中 φ(n)\varphi(n) 为欧拉函数。
注意到如果 n=pqn=pq，其中 p,qp,q 为不相同的质数的话，φ(pq)=(p−1)(q−1),f(pq)=p+q−1⇒p+q=m+1\varphi(pq)=(p-1)(q-1),f(pq)=p+q-1\Rightarrow p+q=m+1。
注意到在 10910^9 范围内哥德巴赫猜想是成立的，并且我们可以直接从小到大枚举较小的那个质数，判断 m+1−pm+1-p 是不是质数，在本题范围内枚举的量是很少的。
小结：因为这是个构造题，所以 nn 很可能是某个特殊形式的，我们需要多做尝试。

T3

注意倍增数组开的顺序要根据循环嵌套的顺序来，内层循环灭据的指标要开在第二维。

解法 1

路径 p,qp,q 有交 ⇔\Leftrightarrow pp 的 lcalca 在 qq 上或者 qq 的 lcalca 在 pp 上。
因此可以算光覆盖了询问的 lcalca 的权值和，加上询问覆盖的光的 lcalca 的权值和，减掉 lcalca 相同的情况。
我们先思考一个 lcalca 被光覆盖的权值和如何计算，显然就是一个路径加，单点求值。
另一个问题是单点加，路径求和，但显然可以转化成上述情况。
所有的都可以用树上差分 O((n+m+q)log⁡n)O((n+m+q)\log n) 维护。
小结：做题的时候要维持清晰，不时总结一下当前的进度，比如转化为了什么问题，有什么信息。

解法 2

根据点边容斥，一棵树总是满足点-边=1。而路径的交还是路径，路径也是树也符合点边容斥，因此我们可以求出覆盖每个点的路径个数，减掉覆盖每条边的路径个数，那么每个相交的路径会恰好被计算一次，同样是树上差分。
小结：路径求和只要是静态的是用不到树剖的。另外点边容斥很经典。

T4

不妨设 x<yx<y，== 的情况是若干条链是容易处理的。
设 g=gcd⁡(x,y)g=\gcd(x,y)，那么  mod g\bmod g 不同的点是独立的，接下来考虑 x=x/g,y=y/g,gcd⁡(x,y)=1x=x/g,y=y/g,\gcd(x,y)=1​。

解法 1

建立一个网格图，ii 的坐标是 (⌊iy⌋,(i×x−1) mod y)(\lfloor \frac{i}{y} \rfloor,(i\times x^{-1})\bmod y)，那么 +y+y 就是向下一行连边，+x+x 就是向右\向右下连边，其中最后一列的右侧是第一列。
这样我么能得到一个网格图，考虑直接按行 dpdp，用类似轮廓线 dp 的记录当前轮廓线上每个点是否选了，这样的复杂度是 O(n2y)O(n2^{y})。
注意到我们还可以反过来对列 dp，但是这样需要记录第一列和最后一列之间的边选择的状态，时间复杂度 O(n22(n/y))O(n2^{2(n/y)})。
把 yy 按照 ≤2n\leq \sqrt {2n} 分治，即可得到 O(n22n)O(n2^{\sqrt {2n}}) 复杂度的做法。

解法 2

从一个点出发进行 BFS，将点按 BFS 序排成一行，可以认为有边相连的两点不会隔太远，然后跑 x,y≤15x,y \le 15 的做法（即只记录前最后的 1515 个点）。

小结

两种做法都做了一件事，即对点重新排列使得边不会跨越太远。

M14

A

简单换根 DP，要二进制拆位。

B

先考虑一个区间 [l,r][l,r] 如何解决。设最大 highbit=phighbit = p，其出现次数为 cc。
于是当 cc 为奇数，且 len≥2len\ge 2 的时候 G(l,r)=2pG(l,r)=2^p。当 cc 为偶数的时候，len≥5len \ge 5 时 G(l,r)=0G(l,r)=0。
对于 len≤4len \le 4 的情况，我们直接暴力计算。
对于处理询问，我们可以预处理一些前缀和之类的东西来计算，并不困难。

C（待补）

n≤10n\le 10 时只需暴力枚举所有可能的树.
k=0k=0 时只需判断 nn 是否形如 2k−12^k-1.
k=1k=1 时可以暴力枚举在满二叉树上不平衡的节点, 是否合法只与此节点的深度有关. 或者直接判断 nn 是否形如 2p−2q−12^p-2^q-1.
对 kk 较大的情形, 考虑如下对树的刻画: 从上往下考虑, 假设当且节点高度为 hh, 则有两种情况
  • 他有两个高度为 h−1h-1 的子树.
  • 他有两个高度分别为 h−1h-1 和 h−2h-2 的子树.
按 hh 从大到小处理, 只需关心有多少已经生成的节点高度是 hh 和 h−1h-1, 在动态规划时记录有几个不平衡节点即可. 直接实现此做法的时间复杂度约为 O(nlog⁡n⋅k3)O(n\log n\cdot k^3).
事实上, 我们不关心具体的 hh, 因为假设有 xx 个高度为 0 和 yy 个高度为 -1 的点, 总会生成出一棵总点数为 2x+y−12x+y-1 个点的树, 因为每次合并两个点, 生成一个点. 假设有 xx 个高度为 hh 和 yy 个高度为 h−1h-1 的点, 有 kk 个不平衡节点的方案数为 fx,y,kf_{x,y,k}, 则转移时枚举 xx 个种有 cc 个不平衡的儿子, 转移到状态 f2x+y−c,c,c+kf_{2x+y-c,c,c+k}.
根据刚才的观察, 我们只需要求出所有 2x+y−1=n2x+y-1=n 的 fx,y,kf_{x,y,k} 的值. 而上述转移时 xx 几乎总是除 2. 使用记忆化搜索倒过来转移, 总共扫描到的状态数为 O(log⁡n⋅k3)O(\log n \cdot k^3). 每次枚举转移时间复杂度即为 O(log⁡n⋅k5)O(\log n \cdot k^5), 事实上常数很小, 可以通过.

D

根据传统的 dp 过程，维护 curcur、ansans 和 dif=cur−ansdif = cur - ans。
每次执行 cur=cur+ai,dif=dif+aicur = cur + a_i, \quad dif = dif + a_i。如果 cur<0cur < 0，则
dif−=cur,cur=0dif -= cur, \quad cur = 0。如果 dif>0dif > 0，则 dif=0dif = 0。不需要显式地维护 ansans。
考虑将所有数都表示成 ∑ci⋅2i\sum c_i \cdot 2^i 的形式，其中 ci=0,1,−1c_i = 0, 1, -1。
则所有加法和减法操作均摊只需要执行 O(1)O(1) 次。使用 set 维护这几个数即可。
使用 set 或者主席树直接维护 11 的连续段也是正确的。
部分分是通向正解的阶梯。
小结：因为我们维护的庞大数字不能快速地比较大小，但是能快速判断与 00 的大小关系，于是 a<b⇔a−b<0a<b \Leftrightarrow a-b<0 即可。

AT_arc104_d [ARC104D] Multiset Mean

经典 trick：一般平均值需要和元素个数搭配才能和总和相互转化，但平均值为 00 时是特殊的。
于是我们枚举 xx。将所有元素减去 xx，即求在 [1−x,n−x][1-x,n-x] 中取数使得和为 00 的方案数。这是一个多重背包。
我们记 fi,jf_{i,j} 为前 ii 个元素总和为 jj 的方案书。但是如果正负物品混到一起，写起来有点麻烦。
我们可以把正负分开处理，ff 仅记录正数情况，因为负数是对称的，00 的选取是任意的。于是
ANS(x)=(k+1)∑0≤j≤n(n+1)k/2fx−1,jfn−x,j−1ANS(x) = (k+1)\sum_{0 \le j \le n(n+1)k/2}{f_{x-1,j}f_{n-x,j}} - 1
多重背包可以前缀和优化，总复杂度 O(n3k)O(n^3k)。
关于前缀和优化多重背包
CPP
f[0][0]=1;
int sum=0;
rep(i,1,n){
  sum+=i*m,l+=m+1;
  rep(j,0,i-1) f[i][j]=f[i-1][j];
  rep(j,i,sum) f[i][j]=(f[i-1][j]+f[i][j-i])%P;
  int l=i*(m+1);
  per(j,sum,l) f[i][j]=(f[i][j]-f[i][j-l]+P)%P;
}
最后一个循环是处理物品数量的限制（前缀和 →\rightarrow 区间和），是和完全背包的区别点。

P11131 【MX-X5-T3】「GFOI Round 1」Cthugha

解法 1

建有向图，指向一个点的边权为其点权。跑 SPFA，在 SLF 和 LLL 优化的加持下可以通过（但不会 LLL，只用 SLF 会 T 一个点）。堆优化也可以。
注意 SPFA 判环中，cntxcnt_x 表示经过了几条边，所以计算应该是和松弛放到一起，而不是直接自增。

解法 2

建无向图，边权为两点权和。对于无解情况，我们发现当且仅当相邻点权值之和为负数。
于是可以跑 Dijktra。

P10715 【MX-X1-T3】「KDOI-05」简单的序列问题

转化 1：显然可以先对 aia_i 取模。SS 会有一个直接关于 aa 的计算方法：从第奇数个 11 走到第偶数个 11 之前的段的长度和（虽然这个计算方法是无关紧要的）。
转化 2：关键转化，观察转化的费用是两点权值和，涉及交换的问题我们处理起来是困难的，于是考虑把一次“交换”拆解成两次“改变”，花费为 cic_i。我们发现，只要最终 0/10/1 数量对的上，总存在交换方案与之效果相同且花费相同。并且显然对于任意交换方案，也存在与之对应的改变方案。
然后显然就可以 DP 了，可以滚动数组优化。
MicroSun 指出这题可以从区间翻转的角度解决。
如果写了有返回的函数却没返回，则会发生不可预知的错误，这体现了 -Wall 的重要性。

P11218 【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天

有点意思。最大子段和变种。
Case 1：没有“半选”，此时 00 令 sumsum 减 11，01 和 10 不变，11 令 sumsum 加 22。
Case 2：有“半选”。因为“半选”在数量不超过 2m2m 时是纯纯负收益，所以我们可以认为一开始就欠了 2m2m 的价值。补上来了就是合法解，没补上来虽然非法，但一定不如 Case 1 的答案，所以无所谓。然后最大子段和，注意需要记录前一个位置的选择情况。

经验：P11219 【MX-S4-T3】「yyOI R2」youyou 的序列 II

这种题一看就是要分析一个结论来高效判断输赢，因为这个博弈过程硬做实在太复杂了。
先考虑 [1,n][1,n] 上的博弈问题。
零散地分析一些性质：
  1. max⁡1≤i≤nai≤w1\max_{1 \le i \le n}a_i \le w_1 是 youyou 赢的必要条件。
  2. 如果存在两个点 x,yx,y 能被 yy 覆盖，但是不能被 youyou 一次覆盖，那么 youyou 会输。
性质 2 的否命题同样正确，即：如果对于所有 yy 能覆盖的点，youyou 可以一次覆盖，那么 youyou 会赢（当然假设性质 1 的条件成立）。
剩下的就是维护 yy 能覆盖的最左最右点，可以用一个数组表示长为 c2c_2 的区间和，线段树维护，查询可以二分。
最后判断一下边缘情况。
小结：
VP 的时候基本把重要的东西分析得差不多了，比如 youyou 要输的话需要有两个点形成牵制，但就是没有有效的总结出结论。
一个有效得方法是把已知得结论列下来，写到草稿纸上。
总的来说，做题的时候应该自信一点，坚决一点，细致一点。

P11220 【MX-S4-T4】「yyOI R2」youyou 的三进制数

首先要想到将原题目转化为图论模型，否则一切都无从下手。
然后观察一个性质：所有 bb 与 cc 的交点都是同一个。这点比较显然。
然后是圆方数相关计数，非常简单。可以树上差分实现。

待补：P11236 [KTSC 2024 R1] 水果游戏

一个经典的套路是：如果我们对一个问题有迭代做法，那么我们很可能可以用线段树进行多次查询的加速。
OBS 1：如果出现一个数小于两边，则两边相当于被隔开。

二维平面视角：P14255 列车（train）

将区间信息放到二维平面上问题将变得易于解决。
将区间的左端点看作横坐标，右端点看作纵坐标。我们所维护的删除区间一定是递增的。
可以用线段树维护 xx 轴上的某种“拐点”，暴力单点修改，用势能可以说明复杂度。
小结：二维平面、图，都是常用视角。

AT_arc107_d [ARC107D] Number of Multisets

朴素地设计 DP：fi,j=f_{i,j} = 大小为 ii，和为 jj 的多重集个数。
转移：
  1. 若有 11，fi,j←fi−1,j−1f_{i,j} \leftarrow f_{i-1,j-1}。
  2. 若无 11，则可以由其他情况整体除以 22 得到，即 fi,j←fi,2jf_{i,j} \leftarrow f_{i,2j}。
小结：可以和 AT_arc201_b 放到一起看。与 2k2^k 相关，涉及整体乘除 22 进行归化的思想。

P11234 [CSP-S 2024] 擂台游戏

*AT_arc186_d [ARC186D] Polish Mania

这题是不是不转换也行？
一个显然的观察：一个 Polish 序列唯一对应一颗树。
我们要统计某种复杂序列的数量，理想的方法是找到等价条件。
等价条件：
  1. ∑ai=n−1\sum a_i = n-1
  2. ∀m<n,∑1≤i≤mai≥i\forall m<n, \sum_{1\le i\le m}a_i \ge i
然后类似数位统计，加上格路计数。需要用到经典的反射容斥。

*QOJ7649 序列

非常像 BJMX 的一道题，观察到一个递归结构然后可以 DP。
一个神秘技术：nn 固定时，fn,mf_{n,m} 是关于 mm 的多项式，于是用拉格朗日插值解决 mm 很大的情况。

*AT_arc117_e [ARC117E] Zero-Sum Ranges 2

连续段 DP，熟悉不同角度的 DP。

*AT_arc118_e [ARC118E] Avoid Permutations

考虑用所有路径减去经过了黑点的路径得到答案，这里需要一个容斥。
考虑用 fi,j,kf_{i,j,k} 表示走到 (i,j)(i,j) 经过 kk 个黑点的路径数。如果黑点的排布是任意的，那么这样就可以了。
但本题黑点是按照排列来排布的，即每行仅有一个，每列也仅有一个，所以加两个 0/10/1 位来表示即可。

反悔贪心与模拟费用流：P11268 【MX-S5-T2】买东西题

可以建费用流，但是没用，不如匹配模型简洁，而且增广模式不是按照 SSP 算法的，如果先入为主会陷入误区。
我们考虑将物品按 aa 升序排列，优惠券按 ww 升序排列。不妨假设所有物品都先使用折扣。
考虑增量过程，物品 ii 如何抉择：
  1. 直接吃折扣。Δ=0\Delta=0。
  2. 拿一个没有匹配的优惠券。Δ=(ai−bi)−vj\Delta=(a_i-b_i)-v_j，jj 为某个优惠券。
  3. 拿一个有匹配的优惠券，看上去会引起一系列变动，但实际上发现被夺走优惠券的物品如果去拿另一个券，不如直接让 ii 匹配。Δ=(ai−bi)−(aj−bj)\Delta=(a_i-b_i)-(a_j-b_j)，jj 为某个优惠券匹配的物品。
我们可以考虑为优惠券赋一个新权值 dd：
  1. 未匹配，d=vd=v。
  2. 匹配 jj，d=aj−bjd=a_j-b_j。
算法过程会保证当前的答案为考虑前 ii 个物品的最优解（一般的贪心都是如此）。

P10997 【MX-J3-T4】 Partition

十分巧思的一题，把贡献拆一拆，可以等价转化为两次可重叠的染色，并且两次是独立的。

经验：P11064 【MX-X4-T4】「Jason-1」一步最优

当我们遇到一个与经典问题的相关的问题时，不要怼着一种经典算法想，因为不同算法有不同优势。像这里我没想起来经典的线段树维护最大子段和。

P11158 【MX-X6-T4】夢重力

改变统计顺序。
没有关键点的子矩形贡献为 2(n/22)2\binom{n/2}{2}，有一个关键点的贡献为 11。
后面的计数没做出来。
暴力是 O(n2)O(n^2) 的，我们考虑一行一行考虑，每行考虑纵向的一段区间，维护区间内的点，然后就可以根据点之间的空隙数数了。
之前老想用神秘数据结构。

警示：P5058 [ZJOI2004] 嗅探器

虽然这题极为简单，但还是有个细节要注意：判断割点 uu 是否可以为信息中心，要用 dfn[t] >= dfn[v] 而不是 dfn[t] > dfn[u]。因为 uu 为割点，且 tt 在子树 uu 中，并不能说明会断开，因为仍可能在同一个点双内（割点不一定会断开一切儿子）。

P7907 [Ynoi2005] rmscne

注意到合法性的“传递性”，这题就容易了。还有子区间是一个后缀的前缀。

评论

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

正在加载评论...