专栏文章

mx

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

文章操作

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

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

mx1

赛：85 + 24 + 40 + 0
补：100 + 100 + 100 + 24
总结：10610^6 不能双 log⁡\log，注意题目没写在数据范围里的部分分。

P110120 宇宙（universe）

Θ(nlog⁡Vlog⁡n)\Theta(n\log V\log n) 做法显然，直接两次二分。
观察到随着 kk 增加，ansans 和要维护的下标 pp 都是单调递增的，先推一下式子，看一下 ansans 应满足什么条件。
{ans+1>ap(x+1)×p−sp≤k×x+sp\begin{cases} & ans + 1 > a_p\\ & (x+1)\times p - s_p \le k\times x + s_p \end{cases} {ans+1>apx≤sp−pp−k\begin{cases} & ans + 1 > a_p\\ & x \le \frac{s_p-p}{p-k} \end{cases}
先排序，求出前缀和 sis_i，保证 p>kp>k 后就可以双指针求出 p,xp,x。
code

P110121 跳跃（jump）

  • 先做第一关键字。
  • 题目的关键性质：询问保证了端点都是白色，代表极长的黑色区间要么不包含，要么完全包含。
  • 如果有性质 CC，这代表可以不踩任何一个黑格子。
  • 如果没有，一段长度为 lenlen 的黑色区间，其中有 ⌊lenk⌋\lfloor \frac{len}{k} \rfloor 是必须踩的，直接缩成 len mod klen \bmod k 的区间。
  • 再考虑第二关键字。
  • 如果一个点直接跳到了白色，直接不管。
  • 否则看一下他在黑色区间的相对位置，如果他跳出去了就不管，否则让他跳回最后的白色的位置。
但这样还是太吃操作了，直接缩黑色区间，只保留 len mod klen \bmod k，这样直接跑特殊性质 CC，然后累加一下黑色区间的贡献即可。
code1
code2

P110122 圆环（circle）

前置题目
这道题中 fi,jf_{i,j} 表示考虑前 ii 个要求后，一个在 xix_i 另一个在 jj 的最小操作数。
fi,j←min⁡fi−1,j+∣xi−xi−1∣fi,xi−1←min⁡fi−1,j+∣xi−j∣f_{i,j} \gets \min f_{i-1,j}+|x_i-x_{i-1}| \\ f_{i,x_{i-1}} \gets \min f_{i-1,j}+|x_i-j|
把第二个转移拆了：
fi,xi−1={min⁡fi−1,j+xi−j,j≤ximin⁡fi−1,j+j−xi,j≥xif_{i,x_{i-1}} = \begin{cases} \min f_{i-1,j} + x_i - j,j\le x_i\\ \min f_{i-1,j} + j - x_i,j \ge x_i \end{cases}
发现第一个转移要维护区间加，第二个转移维护 fi−1,j+xif_{i-1,j}+x_i 和 fi−1,j−xif_{i-1,j}-x_i 的最小值，直接上线段树即可。
回到本题。
如果只有一个约束，有转移方程：
fi,j←fi−1,j+min⁡(∣now−lst∣,n−∣now∣)fi,now←min⁡fi−1,j+min⁡(∣j−lst∣,n−∣j−lst∣)f_{i,j} \gets f_{i-1,j}+\min(|now-lst|,n-|now|) \\ f_{i,now} \gets \min f_{i-1,j} + \min(|j-lst|,n- |j-lst|)
相比上面只是多了一项。
然后考虑一个时刻要满足两个条件怎么做。
这个时候末状态是定的，ff 数组只有一个有值。
只需钦定一个顺序，第二次转移时在不进行转移一即可。
code

mx2

赛：50 + 100 + 36 + 16
补：100 + 100 + 100 +100
总结：对拍，不要相信大样例。

P110124 Mex

mex⁡\operatorname{mex} 是 Θ(n)\Theta(n) 级别的。
一个数能成为 mex⁡\operatorname{mex} 说明 aa 中 ai=mex⁡a_i = \operatorname{mex} 的位置对应的 bi≠mex⁡b_i \not =\operatorname{mex}，第一问枚举即可。
第二问如果 ai≠mex⁡∨bi≠mex⁡a_i \not =\operatorname{mex}\lor b_i \not =\operatorname{mex} 说明这个位置随便换。
code

P110125 独立集

很好的树形 dp。
令 K=0∼n−1K = 0\sim n-1 分别 dp。
对于每个点 uu 选不选设计状态。
gug_u 表示不选 uu 时子树选择的总方案数。
fu,sf_{u,s} 表示 uu 选了 ss 个邻居的方案数，同时用 su,ks_{u,k} 记一下前缀和。
gug_u 相当于子树可以随便选。
gu=∏(gv+sv,K)g_u = \prod (g_v + s_{v,K})
fu,kf_{u,k} 的转移则考虑加入一个元素 vv。
fu,k′=fu,k×gv+fu,k−1×sv,K−1f'_{u,k} = f_{u,k} \times g_v + f_{u,k-1}\times s_{v,K-1}
时间复杂度 Θ(n3)\Theta(n^3)。
code

P110126 删点

神秘性质题。
  • 一定不会删的点：a1,an,min⁡ai,max⁡aia_1,a_n,\min a_i,\max a_i。
  • 取最左侧的极值到最右侧的极值，选这个矩形，中间的点都会被删掉。
  • 然后可能留下的点：一段前缀中 ai=a1a_i = a_1，一段后缀中 ai=ana_i = a_n。
  • 观察到对于每一种可能得删法都可以转化为不相交矩形的删除。
然后 dp，只讨论前缀的情况。
fi,jf_{i,j} 表示考虑前 ii 个点，是否能留下 jj 个。
fi,j=fi−1,j−1fi,j=fk,jf_{i,j} = f_{i-1,j-1} \\ f_{i,j} = f_{k,j}
再使用 bitset 优化即可做到 Θ(n3ω)\Theta(\frac{n^3}{\omega})。
code

mx3

赛：95 + 0 + 100 + 0
补：100 + 100 + 100 + 0
总结：梦熊大粪评测规则，最后一定要再交一次代码。

P110128 委托 (entrust)

贪心，对于一个任务肯定做完之后尽快回到 00，排序后二分做最大不相交子区间即可，注意可以落单一个。
code

P110129 骑车环行 (cycle)

先建出最小生成树，加入一条边后生成一个环，环的代价更新为边权的最大值，答案是最大值的最小值。
树剖线段树维护。

mx4

赛：100 + 50 + 0 + 0
补：100 + 100 + 100 +100
总结：T3 可以比 T2 简单。

P110132 异或子段

神秘诈骗题。
先套路地钦定一个最大值 xx，然后要考虑的就是跨过 xx 且长度为 xx 的区间，显然过不了。
剪枝，单调栈预处理左边第一个 li,ali≤ail_i,a_{l_i} \le a_i，右边第一个 ri,ari>air_i,a_{r_i}>a_i，再花 Θ(min⁡(i−li,ri−i))\Theta(\min(i-l_i,r_i-i)) 的代价检查答案。
这样复杂度神奇地变成了 Θ(nlog⁡n)\Theta(n\log n)。
证明
全局最大值先选出来，会暴力统计一个长度为 nn 的区间。
像建立笛卡尔树一样得到其余两个子区间的最大值，会产生 n2\frac{n}{2} 的贡献。
这样总贡献类似归并排序，是 Θ(nlog⁡n)\Theta(n\log n)。
code

P110133 氧气堆

  • 观察到值域很小，可以考虑值域上的做法。
  • 对每一个值维护一个链表，同时用指针 pp 表示当前扫到的最小值。
  • 但是这可能会被操作二破坏 pp 的最小性。
  • 考虑额外维护一个 minmin，由于操作二会弹出最小值，所以 min≤pmin \le p 最多只有一个。
  • 时间复杂度 Θ(n+V)\Theta(n+V)。
坑点：若当前的 p=xp=x，影响最晚的是当前插入的 xx。
code

P110134 Toptrees 领先

  • 没有简单环的无向图是森林。
  • 预处理森林里每棵树的信息，一条边合法的条件是：不使用当前树的 sizesize，能否凑出一个定值 kk。
  • 一种方法是预处理前缀背包和后缀背包，用 bitset 优化，时间复杂度 Θ(nmω)\Theta(\frac{nm}{\omega})，code。
  • 新知识：转为计数，fif_i 表示凑成 ii 的方案数，转移方程 fi=fi+fi−xf_i = f_{i} + f_{i-x}，发现这个转移方程是可撤销的。
tips
bitset 相关技巧：可以将 bitset 看作一个数组，<< 相当于往右平移，>> 相当于往左平移。
也可以看成一个数，只是从左到右表示高位到低位。

mx5

赛：未知
补：100 + 100 + 12 + 0
总结：冲不出正解要打暴力分。

P130006 阿蛮

组合意义题。
考虑一个局面 (x,y)(x,y)，当前一共有 xx 个人，第一个人及其支持者有 x−yx-y 个，它的贡献为 max⁡(0,x−2y)\max(0,x-2y)。
考虑一个局面出现的概率，总方案是 1∼x1\sim x 的排列，其中 1∼n1\sim n 保持顺序，即 (x−1n−1)×(x−n)!\binom{x-1}{n-1} \times (x-n)!。
然后计算 22 后面有 y−1y-1 个人的方案数，首先对 x−nx-n 个人随便排，再从 n−2n-2 个人选 y−1y-1 个固定，即 (y−1n−2)×(x−n)!\binom{y-1}{n-2}\times(x-n)!。
于是局面 (x,y)(x,y) 出现的概率是 (y−1n−2)(x−1n−1)\frac{\binom{y-1}{n-2}}{\binom{x-1}{n-1}}。
所以答案是
∑x=n+1m∑y=1xfx,y×max⁡(0,x−2y)=∑x=n+1m1(x−1n−1)∑y=1⌊x2⌋(x−2y)×(y−2n−1)\sum_{x=n+1}^{m} \sum_{y=1}^{x} f_{x,y} \times \max(0,x-2y) = \sum_{x=n+1}^{m} \frac{1}{\binom{x-1}{n-1}} \sum_{y=1}^{\lfloor \frac{x}{2} \rfloor} (x-2y) \times \binom{y-2}{n-1}
固定 xx，使用前缀和预处理即可。
code

P130007 菟园

先跑 kmp，建立失配树，问题转化为动态加叶子节点，动态询问子树权值，路径加。
分块，可以处理出 xx 跳出块第一个跳到谁。
然后权值可以懒标记， addiadd_i 表示跳出去之前的祖先上都需要权值 +1+1。
code

mx6

赛：100 + 0 + 6 + 4
补：100 + 100 + 100 + 20
总结：调试最后一定要注释掉。

P130011 句法分析

区间 dp 即可，签到。

P130012 树上前 k 大菊花

妙妙题，肯定是多路归并优先队列。
先考虑大菊花怎么做，把邻居降序排序，然后钦定只选 kk 个，压入最优方案。
扩展是考虑如何得到次优解，肯定是有一个指针往后移动一格导致。
很智慧的一点：当前选择是往后移当前指针，或固定当前指针，后面的指针都不能超过他。
这样只扩展出 Θ(1)\Theta(1) 个状态。
很多菊花时再用一个堆维护所有堆顶即可。
code

P130013 相关聚类

观察 11：如果是一棵树，从 k=n∼1k = n\sim 1 考虑，初始时贡献为 ++ 的数量，kk 减小 11，如果有 ++ 代价就减少 11，否则代价增加 11。
观察 22：基环树不同点在于合并了 len−1len-1 个点后就相当于连通了，代价会强制被剩下的边改变。如果环上都是 ++ 则没有影响，有多个 −- 也没有影响，因为这个时候 ++ 已经选完了。所以只有 cnt⁡(−)=1\operatorname{cnt}(-) = 1 需要特殊考虑。
当 cnt⁡(−)=1\operatorname{cnt}(-) = 1 时的合并顺序：树上的 ++，环上的 ++，树上的 −-。
当 cnt⁡(−)≠1\operatorname{cnt}(-) \not= 1 的时合并顺序：环上的 ++，树上的 ++，树上的 −-，环上的 −-。
code

mx7

赛：100 + 0 + 20 + 0
补：100 + 100 + 20 + 0
总结：构造题太难了。

P130019 地球往事

ai←ai−i,bi←bi−ia_i \gets a_i - i,b_i \gets b_i - i 然后按照 aa 递增，bb 递减的顺序排序，相当于不严格的逆序对之间会连边，求最后连通块的数量。
原题，相同的套路，set 维护每一个连通块最大的 bb，加入一个新的就合并。
每个点只会被加入一次删除一次，时间复杂度 Θ(nlog⁡n)\Theta(n\log n)。
可以用单调栈把最后的过程变成 Θ(n)\Theta(n)。

P130020 纪元

  • 一个字符串对前一个字符串有约束。
  • 具体地，设 sis_i 字符集为 Σ\Sigma，对于其中任意一个字符，都要求

mx8

VP：反正做出一道题。
补：100 + 100 + 5 + 0
总结：dp 太难了。

P130015 项链 (necklace)

sol1

二分答案，分成 <k<k 的和 ≥k\ge k 的，<k<k 的一定要选，两个 <k<k 之间最多夹一个 ≥k\ge k，线性检查即可。

sol2

两两成对的插入堆中，堆头是瓶颈，一定是要被调整的，调整的一对一定会删去较大的，直接拿链表模拟即可。
code

P130016 计树 (tree)

神秘的插空 dp。
由于题目的限制，钦定一个 1∼n1\sim n 的加点顺序。
fi,j,kf_{i,j,k} 表示考虑前 ii 个数，形成了 jj 棵树，且留有 kk 个空位的方案数。
  1. 当前节点儿子个数可以取 00。 fi,j+1,k←fi−1,j,kfi,j,k−1←fi−1,j,k×kf_{i,j+1,k} \gets f_{i-1,j,k}\\ f_{i,j,k-1} \gets f_{i-1,j,k} \times k 代表为该节点开一棵树，或者把该节点放在一个空位。
  2. 当前节点儿子个数可以取 11。 fi,j+1,k+1←2×fi−1,j,kfi,j,k←2×fi−1,j,k×kf_{i,j+1,k+1} \gets 2\times f_{i-1,j,k} \\ f_{i,j,k} \gets 2\times f_{i-1,j,k} \times k 这个转移是一样的，只不过要钦定它接的是左儿子还是右儿子。
  3. 当前节点儿子个数可以取 11。 fi,j+1,k+2←fi−1,j,kfi,j,k+1←k×fi−1,j,kfi,j,k+1←2×fi−1,j,k×jfi,j,k←k×2×(j−1)×fi−1,j,kf_{i,j+1,k+2} \gets f_{i-1,j,k} \\ f_{i,j,k+1} \gets k\times f_{i-1,j,k} \\ f_{i,j,k+1} \gets 2\times f_{i-1,j,k}\times j \\ f_{i,j,k} \gets k \times 2 \times (j-1) \times f_{i-1,j,k} 分别代表：新开一棵树产生两个空位，直接接在一个空位，新开一棵树并接一棵树上去，接在一个空位并在该节点上接一棵树。
code

mx9

赛：100 + 0 + 0 + 0
补：100 + 0 + 0 +0
总结：在补。

mx10

没打。
补：0 + 100 + 0 + 0
总结：在补。
min-max 容斥。
max⁡(S)=∑min⁡(T)\max(S) = \sum \min(T)

mx11

赛：0 + 0 + 0 + 0
补：100 + 0 + 0 +0
总结：文件读写要写对。

mx12

赛：60 + 40 + 60 + 10
补：100 + 40 + 100 + 10
总结：对拍，根号分治太强了。

P130032 距离

floyd 本质是 dp，可以求出 i,ji,j 之间编号不超过 kk 的最短路。
考虑分块，ft,i,jf_{t,i,j} 表示不使用编号为 [lt,rt][l_t,r_t] 之间的点，i,ji,j 的最短路。这一部分处理时间是 Θ(n4B)\Theta(\frac{n^4}{B})。
然后对每个 pp 求出全源最短路数组。
对于一个 pp 在 tt 块内，只需要加入 [lt,rt][l_t,r_t] 的其他元素即可，时间复杂度 Θ(Bn3)\Theta(Bn^3)。
取 B=nB=\sqrt n 得到最优复杂度 Θ(n3.5)\Theta(n^{3.5})。
code

mx13

赛：50 + 20 + 30 + 0
补：100 + 100 + 30 + 0
总结：≤≠=\le \not = =，需要仔细分析性质。

mx14

赛：100 + 10 + 0 + 25
补：100 + 10 + 0 + 25
总结：在补。

mx15

赛：40 + 0 + 25 + 0
补：100 + 0 + 25 + 10
总结：在补。

P130051 玲珑宝塔

先二分答案，检查可以贪心，开 midmid 个位置。每次肯定顺着填下去。
code

mx16

赛：100 + 70 + 45 + 0
补：100 + 100 + 45 + 0
总结：在补。

P130067 删数游戏

由于单调递增，从最后的数开始删一定是对的。
赛时发现问题转化为求 ai≡0(modi)a_i \equiv 0\pmod i 位置的最大值，同时动态删点，直接打了分块维护。
实际上找到最后满足的位置后直接把之后的加进来就行。
code

P130068 货币改革

同于最短路，考虑使用 c2∼cic_2\sim c_i 凑出 m=c1m=c_1 的每个剩余系最小价值，那么 disi−mdis_i - m 都是不能被表示的。
然后就是加边最短路，但这题有特殊性质，每次只用考虑新加的边即可。
因为松弛过后假设这个点变为 x2c2+x3c3+⋯+xi−1ci−1+cix_2c_2 + x_3c_3 + \dots+x_{i-1}c_{i-1} + c_i，那么此时不需要 c2∼i−1c_{2\sim i-1} 的边进行松弛，因为最终都可以表示为 xicix_ic_i 的形式，可以直接由这个点更新。
使用类似归并的方法用双端队列实现迪杰。
code

mx17

赛：100 + 36 + 30 + 10
补：100 + 100 + 30 + 0
总结：在补。

mx18

赛：100 + 20 + 50 + 20
补：100 + 100 + 100 + 20
总结：在补。

P130078 染色（paint）

一个颜色的刷子肯定用来刷 [li,ri][l_i,r_i]，li,ril_i,r_i 代表了该颜色的左右边界。
从 11 开始往后刷 solve(l,r) 代表将 [l,r][l,r] 染色，递归处理即可。
code

P130079 交换（swap）

最难做的情况是最小值在右儿子处取到，可以记忆化搜索。
fu,valf_{u,val} 表示以 uu 为根的子树将 uu 改成 valval，这个值最终变到哪里。
直接记忆化搜索，一个点的取值只能是其祖先或者祖先的兄弟。

mx19

赛：100 + 0 + 10 + 4
补：100 + 0 + 10 + 4
总结：在补。

mx20

赛：80 + 30 + 0 + 0
补：100 + 100 + 100 + 0
总结：vector 使用要注意效率问题，数组要算空间。

mx21

赛：100 + 70 + 44 + 10
补：100 + 100 + 100 + 10
总结：数论分块忘记了，本场未挂分。

P130109 新站长 (webmaster)

先把所有 B 变成 A，然后从后往前考虑，能变回来就变，直接贪心。
code

P130110 小粉兔不想挂科 (failure)

数论分块复习。
对于 i=1∼ni=1\sim n，⌊ni⌋\lfloor \frac{n}{i} \rfloor 的值只有 Θ(n)\Theta(\sqrt n) 个。
如果 i≤ni \le \sqrt n，由于 ii 只有 Θ(n)\Theta(\sqrt n) 个，⌊ni⌋\lfloor \frac{n}{i} \rfloor 的值只有 Θ(n)\Theta(\sqrt n) 个.
如果 i>ni > \sqrt n，⌊ni⌋≤n\lfloor \frac{n}{i} \rfloor \le \sqrt n，只有 Θ(n)\Theta(\sqrt n) 个。
所以 ⌊ni⌋\lfloor \frac{n}{i} \rfloor 的值只有 Θ(n)\Theta(\sqrt n) 个。
满足 ⌊ni⌋=k\lfloor \frac{n}{i} \rfloor = k 的 ii 的取值范围为 [⌊nk+1⌋+1,⌊nk⌋][\lfloor \frac{n}{k+1} \rfloor +1,\lfloor \frac{n}{k}\rfloor]。
由不等式 k≤ni<k+1k \le \frac{n}{i} < k+1 推得。
回到原题，依次求 cic_i。
ci=∑j=1ia⌊ij⌋×bi mod jc_i = \sum_{j=1}^{i} a_{\lfloor \frac{i}{j} \rfloor \times b_{i \bmod j}}
数论分块，计算 ⌊ij⌋=k\lfloor \frac{i}{j} \rfloor = k 的一段。
此时 a⌊ij⌋a_{\lfloor \frac{i}{j} \rfloor} 固定，要算 bb 在这一段的和。由于 i mod j=i−⌊ij⌋×ji \bmod j = i - \lfloor \frac{i}{j} \rfloor \times j，所以下标是一个 ii 结尾的一段等差数列，公差为 kk。
由于 i mod j<j=⌊ik⌋i \bmod j < j = \lfloor \frac{i}{k} \rfloor，所以只需要预处理以 ii 结尾的公差 kk 前缀等差数列，而且对于一个 ii 最多需要 ni\frac{n}{i} 个。
调和级数，时间复杂度 Θ(nlog⁡n+nn)\Theta(n\log n + n\sqrt n)。
code

P130111 管理组招新 (recruitment)

神秘带派。
fi,j,kf_{i,j,k} 表示考虑前 ii 个人，配好了 jj 组，还有 kk 组只有组员的答案。
先排序，经验从小到大，而且组员要先被考虑。
直接转移即可。
由于 k≤n2k \le \frac{n}{2}，所以 k=Θ(n)k = \Theta(\sqrt n)，Θ(nlog⁡n+nk2)\Theta(n\log n+ nk^2) 可以过。
code

mx22

评论

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

正在加载评论...