专栏文章

11 月 gogogo

xxcyyyyyy
题解参与者 3已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@mindaxww
此快照首次捕获于
2025/12/02 00:32
3 个月前
此快照最后确认于
2025/12/02 00:32
3 个月前
查看原文
没题做了，托 11d10xy 和 rizynvu 的福做一下泛做。
QOJ833
www 完全偏了，转化成从右上到左下存在路径，但是这样并不等价于题目条件，这是因为题设只能下或右走。
然后正解是，维护能往下走就往下走的路径和能往右走就往右走（不是 free 就走，而是能走到终点的）的路径，那么这两个路径必然形如前后缀一段相等，然后中间分岔的形式。
如果堵前后那么必然不能到达，否则必然堵 AA，然后维护出新的 A,BA,B，剩下堵的就必须是 A∩BA\cap B 了。
核心思想是，做只堵一个点时，发现可以通过这两条路径进行刻画。
QOJ837
看错题了。
但是肯定要建立点分树。
建完后，对于不同子树间，必然经过 uu，或者经过 uu 的那些边，所以对这 2k2k 个点跑最短路后即可。
QOJ856
第一个字符相等则删掉。
否则不同，删掉或者修改或者插入，重复这个操作就能匹配上。
将这些删掉的匹配拉来，对于相邻两个匹配，假设他们的长度为 len1,len2len1,len2，则需要的修改次数为 max⁡(len1,len2)\max(len1,len2)。当然可以通过这个发现删除和添加我们任意保留一个操作即可。
感觉是缩小 dp 状态数量吧。
怎么是换维，换完维后就好做了。
QOJ857
过程必然形如，先把所有点往下面放，然后再一个一个匹配，对于一组匹配将 s 放到 t 的下面，最后再调整上来即可。
对于一颗子树，有如下一些过程：子树内一些匹配，出去，进来。这几种顺序并不好直接钦定啊。
然后对于第一次出现 s,t 共有的 u，一开始先把 s 全部往下调整，对于深度最浅的 s，将其往上走（走不到 u 就炸了），走到 u 子树内存在 t，然后将其安排到 t 下面，若发现安排到 u 邻点了，那么先将其他点排出去，然后再自己走。
但是如果采取递归结构似乎很难对子树结构合并，从上往下又不好确定子树怎么放好。
不过我们的目的还是将所有 s 放到 t 的子树内，完成这个目标的话，再将 s 往上调整必然能成功。
记 sizx=snum−tnumsiz_x=snum-tnum，合法状态必然是 ∀siz≥0\forall siz\geq 0。
每次找到一个最深的 sizx<0siz_x\lt 0 的点，则其所有儿子满足 siz=0siz=0，但是它这里会有一个 t 没有被满足。
如果父亲是一个点，则直接移动下来。否则就是找到一个到这条链路径上全部 siz>0siz\gt 0 的一个 s，且能走过来的，直接走过来，然后往下面走。
关于“能走过来的”可以进行调整。首先将要移动的 s 尽量往下靠，然后其他点使劲把这条路让出来，然后最后还原即可。
不过最后 s 如果占据了某个位置可能时的这些点完全无法还原，这种情况主要发生在 t 子树内只能放 t 的情况。
找代表元啊我炸了。
代表元的钦定也比较有意思，找某个根然后按照深度从大到小编号，这样我们取字典序最小的时候前面确定的点就不会动了。
然后构造一条合法路径时，只需要其他点动一格即可，所以合法啦啦啦啦。
QOJ862 听说太简单了
QOJ887 听说是阴间题，先不做。
QOJ888
直接分治，拆掉 min，分治外面的多加一条边就行。
min⁡(a1+b1,a2+b2,a3+b3)\min(a_1+b_1,a_2+b_2,a_3+b_3)
a1+b1≤a2+b2,a3+b3a_1+b_1\leq a_2+b_2,a_3+b_3——a1−a2≤b2−b1,a1−a3≤b3−b1a_1-a_2\leq b_2-b_1,a_1-a_3\leq b_3-b_1。
QOJ962
红太阳提醒 01，所以我们要想 01。
01 排序可以用归并，左侧 11111000000，右侧 0000001111111，然后就一遍归并了。
然后分治中间的断点即可。
但是操作 mx 为奇数时可能左右会交换，对于 01 排序时我们发现 0011100 和 000111000 都可以弄成 000011111 或者 1111000；而外层分治的时候可以提前计算好下面的次数然后提前规定好。
我这个做法还是比较牛，但是更牛的是把操作转化成一个区间 reverse + 整体 reverse，区间 reverse 就好做了。
lrs 讲题。
#1
O(deg)O(deg) 算一条边，说白了就是快速锁定每一条边。
每次找两个连通块间最小的边，可以枚举小的一边，在大的一边查前驱后继，单次的话 O(nlog⁡2n)O(n\log ^2n)。
从 brouvka 的角度来看似乎只会连接 ∣a−b∣=1|a-b|=1 的边。因为总能找到一条边代价为 11，所以答案就是 ∣E∣|E|。
至于构造方案，维护一下每个连通块的 [L,R][L,R]，然后找到一个 L≠1L\neq 1 或者 R≠nR\neq n 的连通块，直接合并即可，更新 L,RL,R 是不难的。
突然发现 ii 也要删掉，不过不重要。
#2
不妨设 X≤YX\leq Y。
两个栈的意义是，我们得以将不连续的 c 也同时删。而这些 c 必然不交，所以直接考虑 dp，设 fi,jf_{i,j} 表示前 ii 个，钦定数字为 jj 的最小代价，复杂度是 O(n2)O(n^2) 的？
是不是有什么没考虑到的。
经大佬 lhz 提醒，有可能有嵌套关系，所以我们区间 dp 一下，fl,rf_{l,r} 表示答案，然后从左往右扫，gi,jg_{i,j} 表示当前到 ii 钦定 jj，然后里面的自然就用 ff 算，随意 O(n3)O(n^3) 吧。
经过讲解发现还有可能从栈跑回来，不过也不重要。
#3
似乎做过？
满足 1. 条件的，就搞一颗点最大生成树，然后答案为深度和。
然后随便建立一颗树，答案就是 dep 和了。
加一个点的话，就是数以它为开头的方案数了，也就是另一个端点取不到最小值的情况，考虑重新建立最小树的过程，那么其一定是最后加入的，所以问一下 dep 和就行。
没听。
#4 倒着加数，这样的话后面不管是不是 mx 都要整体加一/减一。
没听，反正做过。
#5
直接直接，所以直接就直接了
建立 ACAM，处理出 t 每个前缀在哪里，然后我们要做的类似于是一种数组复制？但是复制的是长度也没办法直接出 l 啊？
有点难。
#6
每次如果将最小值减到 0 的话，这个序列的最大值不会超过 mxmx。
设次小当前为 cmncmn，最大为 mxmx，则序列不变当且仅当 2cmn≥mx2cmn\geq mx。
其他的不知道的。
证明思路可以学习。
#7
k=1k=1 时我们要最小化 x+y−gcd⁡(x,y)x+y-\gcd(x,y)，这个式子至少减去了 max⁡(x,y)\max(x,y)，至多减去了 x+yx+y。
若 (a,b)(a,b) (c,d)(c,d) 满足 a+b≤max⁡(c,d)a+b\leq \max(c,d)，则必然不会删掉 (c,d)(c,d)。因此考虑最小的两个数 x,yx,y，我们只考虑 z≤x+yz\leq x+y 的对子。
然后如果固定 a<ba\lt b，且固定 bb 时，若存在 aa 为 bb 因数则最优。对于剩下的可能的对都满足 a∤ba \nmid b。
好难，直接开始猜，我们只需要考虑排序后的相邻对，
证明思路可以学习。
#8
肯定得容斥吧。
如果钦定了若干个区间是一个 [l,r][l,r] 的排列，那么最后方案数自然就是划分的每个段长的阶乘，以及外面没有钦定的阶乘。
这个 trick 似乎见过，不过还是可以学习。
下面是正文部分：
CF1801G
有点奇思妙想了，本来以为要用某种计数手段。
找到最大 RR 使得存在以 RR 右端点，跨过 ll 的字符串，以 [R+1,r][R+1,r] 为结尾的子串都一定不会跨过 ll。
对于 [l,R][l,R] 内的串，其结尾的就有可能超出去了，不过此时这个串一定是某个串的后缀，可以提前预处理出来。
本质上还是一个预处理的过程，不过讨论得这么细是真逆天。
CF1805F2
减去 0 的性质是可以发现的。
根据 lrs 的说法， ana_n 活下来的条件是很苛刻的，所以我们仔细探索一下。
如果其活下来了，那么 0+a2,...,0+an0+a_2,...,0+a_n 都活下来了，这个时候就已经有 n−1n-1 个数了，而其他数中最小的就是 b2+b3b_2+b_3，这表明 b2+b3>bnb_2+b_3\gt b_n。
不妨多做几轮，如果再次苟活，那么序列变成 0,b4−b3,...,bn−b30,b_4-b_3,...,b_n-b_3 注意到此时 bnb_n 已经砍掉一半了，也就是其最多活 O(log⁡V)O(\log V)。
活不了，说明其对最终答案无影响，我们可以不用维护它。那么不妨推广到其他数，假设我们只需要维护 LL 个数就能将最后答案算出来，我们进行证明。这里的证明思路是，我们可能在某些时候无法维护出正确的值，所以不得不退而求其次，不过只会退很少次，所以我们也只需要维护很少个数。
b2+b3≤bLb_2+b_3\leq b_L，那么再算一次还是正确的。
否则 b2+b3≥bLb_2+b_3\geq b_L，根据刚刚的说法，我们此时不一定能维护出正确的值，因为我们不知道 bL+1b_{L+1} 能不能冲进来，不过至少 L−1L-1 个数是合理的，再做一次 L−2L-2 个数是合理的。
而每做一次，最后一个数都会砍一半，砍到后面就不会出现 b2+b3≥Lb_2+b_3\geq L 的情况了 （n=2n=2 特判），所以只需要维护 2log⁡V2\log V 个数的变化。
CF1806F2
感觉有点没想懂啊。
直接猜想只会选择一个集合的数（lrs：你要对自己的猜想负责），尝试证明一下：
对于两个集合 S,TS,T，假设 x≥yx\geq y，且 SS 中存在 ≥2x\geq 2x 的数，那么将 2x2x 提出来一定不劣。不过只存在 xx 就炸了。所以确实要对猜想负责。
不过这个时候至少说明，不会有 ≥2\geq 2 个存在不同元素的集合。
而且我们可以钦定 SS 里没有相同元素，否则可以当做相同元素的合并。
因此提前处理好如果要求 xx 个数合并，最小的那几个是谁，然后枚举 gcd⁡\gcd 以及选择数的数量，可以过 easy version，做到复杂度 O(mlog⁡m)O(m\log m)。
hard version 生怕我们枚举 gcd⁡\gcd，所以需要进一步发现性质。
因为 SS 中再怎么都是 dd 的倍数，如果我们将其中的数往下调的话，实际上能变大很多，而 gcd⁡\gcd 的减少无非也就 dd。
也就是说，如果选择了 xx 个数为 SS 中的数，那么第 x−1x-1 个数前面的数全部都选择了。
把不重复的数拉出来，则选择的是一个前缀，这个前缀 gcd\text{gcd} 下降次数为 jj，我们相当于枚举一个数 lenlen，再多选一个数，求解 max⁡(bm−len+gcd⁡(alen−1,x))\max(b_{m-len}+\gcd(a_{len-1},x))。
gcd⁡\gcd 只会有 O(log⁡m)O(\log m) 个，暴力求解就行。
CF1874F
考虑到相交的情况下，对于 [l,r],[L,R][l,r],[L,R]，其 [L,r][L,r] 必然也是包含在题目所要求的区间下的，所以如果容斥的话必然可以抵消，所以只需要对树形态的进行统计，这个自然不难的。
QOJ964
可以随便铺一下，在值域上体现出来，就是不断往下接，接上后又不断往上走。
也就是从 i=n→1i=n \rightarrow 1，找到第一个 numi=inum_i=i 的位置。
有点高妙，在莫队的上面可以搞一个并查集和一个链表找第 kk 个后缀最大值，用以维护后缀加一和最大值查询。
更牛的是直接扫描答案，维护每个询问内 1 数量。
希望找到当前 sum →\rightarrow 希望维护找最大值的数据结构。
区间具有单调性 →\rightarrow 只用维护每个 ll 最大 rr。
将 xx 减一 →\rightarrow 区间减一。
不过最后维护的时候，可以将 ll 升序，rr 降序的顺序来放。
QOJ970
这个性质没发现啊。
二分答案，则 ≤W/2\leq W/2 的必然选中，因为将其插入，然后将可能的旁边的 >W/2\gt W/2的删掉，显然答案更优。
有时候真的想不清楚这种区间询问该怎么做，直接一点的，有对 rr 从左往右，也有 ll 从左往右；然后还有对答案进行枚举处理；或者分治进行全局处理；或者直接处理；或者移动指针进行求解；或者整体二分；或者猫树处理；差分处理。
考虑对于多个区间快速判断一个 WW，对于相邻的 W/2W/2，显然其最左最右中的已经确定，而对于更中间的也就是两个最小值询问了。
WW 具有单调性，kk 也具有单调性。
整体二分？我们并不能找到很好的数据分治方法。
如果 WW 的可能值很少的话我们是可以考虑扫答案的。
对于 0/10/1 状态的改变只会经历 O(n)O(n) 个 WW，我们不妨从这里进行入手。
对于 W∈[l,r]W\in[l,r]，相邻两个 00 状态可以表示为：如果 W≥W\geq 多少，那么 00 中可以再插入一个值。
然后问题是一个区间我们不可能去扫多次，不过哪怕不考虑循环区间的影响，其他位置也是递增的，我们可以分别在 k−1,k,k+1k-1,k,k+1 的时候进行扫描。
那么就是怎么设置警报器了，可以理解为一个前缀减的警报器？不过并不是一个相加的形式。
可以用分治搞成相加的形式，当 l,rl,r 其中一端达到 k/2k/2 时报警，否则设置更小。不过分治和答案枚举并不能同时用。
每次加入一个数 xx，考虑两侧的最小值，如果在 [x+y,2y)[x+y,2y) 间就放到 xx 的上，否则放到 yy 上，可以主席树做到 O(nlog⁡n)O(n\log n)。
如果不要求左右侧的话，可以直接在主席树上二分了（这一点很困难了），然后一步步调整即可。
tomorrow。
QOJ971
一个 bst 怎么做？
这个 bst 的性质很好，其实就相当于是将这些值排成一列，然后在上面按照时间建立小根笛卡尔树。
找到两侧中第一个比它小的，那么其父亲必然是其中较大的一个。
然后我们要做的就是询问到根的和，扫描线后就是：维护一个序列，每次会将一个值改成 ww，然后询问一个位置建立笛卡尔树后往上链的和。
一个点 xx 是另一个点 yy 的祖先，当且进当 ax<aya_x\lt a_y，且 (x,y)(x,y) 中的数 >ax\gt a_x。
那么修改一个点的值的时候，如果是从 inf⁡\inf 修改成 ww，首先其对别人的贡献是好做的，不必多说。而其他点可能本来跨过它的，然后被它挡住了。
似乎不是很好算啊。
我是傻逼。
如果不能很好的维护祖先对儿子的贡献，那就直接从儿子问，那么显然这是一个前后缀最大值的模型，楼房重建就行了。
QOJ975
想了半天，好像迭代是一个很好的刻画方法，不断迭代到后面肯定就是取其凸包了。
QOJ977
jsy 说这是儿子题。
n×mn\times m 必然最大，然后 n×m−1n\times m-1 必须和他同行或者同列，然后下一个数继续填。
实在刻画不出来了，还是用容斥吧。
假设钦定了 ∣a∣|a| 个数，从小到大依次排成 [a][a]。
对于 a1a_1，取到了 2n−12n-1 个数 ≤a1\leq a_1，那么对于 aia_i，取到了 2(n−i)+12(n-i)+1 个数。
不过每一次取到的数有很多，或许很多情况下并没有值？
fi,jf_{i,j} 表示考虑前 ii 个数，已经钦定了 jj 个数。
那么显然需要保证 i≥O(j2)i\geq O(j^2)。
合法 jj 是根号级别的。
不需要 dp 具体的数，直接连边后是一个拓扑序直接算就行了。
QOJ993
假如有一个元素特别少，为 xx 个。
对于两个箱子，我们任意选择两个颜色不断维护，那么只需要 3x+1 步就能确定出一个多的元素，对于剩下两种颜色，我们还是不断加，2x+1 个。
其中最多浪费多少呢？是不是选择的两个颜色中有一个少元素，这样我们可能会扔掉 2x+1 个元素。
那么 x≤28x\leq 28 都能做。
事实上我们完全有可能在确定前一个都没有保留，不妨就记成 3x3x，我们会丢掉这么多箱子，那么剩下 100−3x≥43100-3x\geq43，那么 x≤19x\leq 19。
最小加次小 ≥43\geq 43 也很好。
否则我们再那么想要取两个次大的已经很不优了，其实只要把最大的那个选了就好，显然这个东西用类似摩尔投票的方法即可，反正差值特别大。
QOJ1166
一个点不能被上下包含。
一个颜色有这样几种想法：
可以双左，双右，直接连接（均两侧）。
要求就是不能相交。
虽然看起来是 4-sat，但是这四个维度仔细分析一下，其实只需要两个线段的方向确定后，其连线就确定了，我们对方向进行 2-sat 即可。
还是一个简化的一个过程，其实我也想到了，不过没有深究，下次注意点。
长度取 RiR_i 好，有点 666。
QOJ1173
没有什么有效的思路，不妨直接对本质问题研究。
将所有不能一起做的区间相连，那么这个问题可以怎么解决？
这是题吗这是题吗这是题吗？？？？？？？？？？？？？？？？
问题类似于匹配，不断加入区间，考虑当前最优的决策。
按照右端点从大到小进行加入，当加入一个区间的时候：
如果能匹配，那么直接匹配；
否则我们希望可以替换前面的一些匹配使得待匹配的区间的 ll 尽可能大，这时按照右端点从大到小加入的好处就来了，这些区间我们都能替换，直接选择 ll 最大的那个进行替换即可；
此时可能对前面直接匹配进行质疑，不会选择 ll 可以中最小的那个吗？实际上，因为是按照 rr 从大到小排序，所以可以的区间以后都可以。
这个解法应该是实在没有办法的情况下直接考虑一个个加，然后逐步构造封闭贪心的结果。
QOJ1174
又是这种不是题的题。
安装的灯可以当做从 1/21/2 开始走路，每次走 1/21/2 步长，安装对应的灯。
方案数拿脚算，关键是将这些方案排序是个什么鬼。
还是尝试构造拓扑序，最小的方案可以用 dp 求解。（不过一个拓扑序就已经是 O(n)O(n) 的了，就算真的取这么多次不就炸了吗，如果用哈希就不好找下一个了啊）
不过除此之外我们并没有其他方法了呢，所以硬着头皮构造吧。
前 k 大可以构建，前 k 小不行了捏。
可持久化可并堆不会，咕咕咕。
nbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnb 谁发明的 K 短路！！！
真的是厉害，首先可以构建一颗指向 t 的最短路树，从 ss 到 tt 的路径可以刻画为若干非树边组成的路径，因此我们定义一个非树边 (u,v,w)(u,v,w) 偏移量为 dv−du+wd_v-d_u+w，那么答案就是 ds+∑wed_s+\sum w_e。一股 johnson 最短路的味道对不对？
从 uu 我们可以走任意一个祖先的非树出边，这样的话 k 短路就变成了在这个图上的一条路径。
不过此时边数太多，不过走路必然是按照边权从大到小走，所以同样可以用类似拓扑序的方法求解 kk 短路。
一个状态为 (dis,heap)(dis,heap)，然后每次走一条边后，就对应放入新的持久化可并堆。
被 0 边爆了，以后排序来或取树顺序时一定要多留意一下。
QOJ1351
找到一个在 22 以内尽可能小的边集，使得割掉后图变成二分图，统计数量。
∣S∣=0|S|=0，就是判定问题。
∣S∣=1|S|=1，抽取生成树，如果只存在一条奇边，那么直接删掉这个环上的任意一条边都可以；否则多条奇边我们必须删除其覆盖的树边交集。证明的话可以单独再取一条边题换掉这个边，然后在新的生成树上进行分析。-+
∣S∣=2|S|=2，似乎就有点困难了，删掉至少一条非树边是很好进行计算的，关键是删掉两条非树边。根据刚刚的分析，如果一个奇边中间的边被删掉了，就已经可以将其当做偶边抛开了，所以我们的任务是去覆盖所有的奇边。
错了，不是覆盖所有奇数边。
可以从这个角度来理解：因为我们是要求删掉最少的边，所以每一次删掉的边必然被一个奇边经过，既然存在一条奇边，其实可以当成这个边有个边权 1，被翻转成 0 了。
然后转化成翻转边权的话就好做了，而且注意到在这个问题背景下，偶边并没有那么不重要，甚至是完全融入这个体系中的。
这个描述方法真的好厉害，就是通过最少的条件，使得删边必然存在奇边，然后就转化为了翻转边权。
QOJ14579
普通 dp 转移：fi,j,kf_{i,j,k} 表示 dfn 序到 ii，钦定子树内有 jj 个取点，还可以取至多 kk 个点的最大值。
既然是钦定，进入的时候我们直接取 ci−jc_i-j 个的 viv_i 进行转移，然后看 ii 这个点要不要取，然后直接进入子树。
但是进入子树的时候需要再钦定一个 j′j' 表示子树内需要这么多，但是由于转移顺序的钦定，我们无法得知之前的 jj，也无法得知后面还剩下多少 (j−j′)(j-j')。
不过我们相当于要 dp 一个取链序列，然后子树点数做前缀和就是 tout−tint_{out}-t_{in}，那么可以取的点数就是 ci−(tout−tin)c_i-(t_{out}-t_{in})，由于题目保证了 ci>tanyc_i\gt t_{any}，所以可以拆成 ci−tout+tinc_i-t_{out}+t_{in}，这样我们分拆成两步进行转移即可。
对于不选子树，这就是卷上一个子树内的选择若干条最大链的方式，红太阳说这个可以四边形不等式。
queue 似乎有点慢，红太阳说的。
basic_string 似乎有点快，红太阳说的。
stable_sort 在比较次数上比 sort nice 一点。
QOJ1357
看起来好有意思！
如果只有一个黑子需要特判一下，因为这个情况下黑子不能抵消步数。
一个黑子的话，记 x,yx,y 为在对应维上的差，若 x≠yx\neq y，则 yuto 直接选择短的一边逃逸即可，否则可以一直维持这样的形态直到最后一步被逮捕。
而且通过这个特判我们发现这个距离是很重要的，只要存在 yuto 就完蛋了，否则还能争。
问题可以转化为若干 (x,y)(x,y)，每次 yuto 可以选择一个维度全部减一，Platina 可以选择一个棋子的一个维度减一，减到负一就炸掉一个棋子。
从感觉上来说，yuto 会操作一侧后再操作另一侧。
如果这样都不行，那么半途而废也不行啊。
也不对，反正好难。
会做了。
QOJ1359
k=1k=1 就很像最小割了，但是这个要求我做多层最小割？？？
显然不可能考新算法，所以不要慌张。
感受了一下，好像要建多层图，问了下红太阳说是，那就尝试建一下。
建立 K−1K-1 层图，第一层我们肯定需要一些点去将从 ss 到 tt 的一系列点拦住，不过拦住后，我们可以通过消耗一次免费次数到达下一层。
所以正解呼之欲出了，层与层之间建立无穷大的边即可。
QOJ1355
把状态设成错过多少个，这样就是按层转移了。
然后发现有四边形不等式，算即可。
P7710
O(n\sqrt n) 空间 dog 会，一眼往上去不好优化，实则将 m 分块后同一个块的先暴力枚举了就能很好 O(n) 空间。
其实说明我们对 O(1)-O(n)/O(n)-O(1) 本质理解不够，它其实就是一个分块，而且这个分块可以拿在外面。这是个二维的东西，不是嵌套。
F1314
双序列拓展差分后是一个 Monster Hunter......
F1315
进制转换似乎并不好线性，不过直接 bitset 类似的复杂度也不错。
CF1616G
判定的时候可以 dp，将到达 x 的和到达 y 的看作 01 后我们只关心分界点。
然后尝试将 xy 独立，发现第一个 i↛i+1i\nrightarrow i+1 的状态必然经过，对两侧分别求解后直接合并即可。
还好我比较机智，在前后多加了两个点。
CF1630F
图传递，所以一个点有三种状态（对点的状态讨论）：
小的，大的，或者不选。
令一个边从小到大。
可以建立图，如果说一个点是小的，那么所有指向它的边都不行，如果一个点是大的，那么它指向的都不行。左右不能选，这变成了一个最大独立集。
然后这个图并不是二分图，但是边很有性质。定向后是一个 DAG，所以变成了最长反链。
CF1338E
最好别觉得 vector().size() 是 ull 的。
CF1305G
本来是最小树形图，但是边双向，可以添加对点的权值后变成最小生成树，每个点多算了一个权值。
如果树形图是森林的话可以考虑加一个权为 0 的超级原点来去掉对根点的特判。
QOJ4898
nn 小的时候可以用 st 表优化建图。
首先计算若干组边后的代表元，对于 (d1,d2)(d1,d2)，对于最后 d1d1 个点，他们一定和 v−d1v-d1 相连。尝试递归下去，发现剩下的点距离为 d2−d1d2-d1 就相连，而且信息没有丢失，所以可以递归下去。
多组边同理，这样我们得到了一组组边对这个图的方法。
在辗转相除过程中，对 nn 的修改只用了 O(log⁡n)O(\log n) 个 dd，只有这些 dd 是有用的。
加上 bb，其实就是在这些 ui,viu_i,v_i 只用一组组边构成的 kruskal 重构树上的虚树的边拿出来一起跑一个 kruskal 即可。
不过这个时候有点黑暗了，因为我们每加入一组边后都要尝试去对每个 uu 跑，这很不好。
既然是连通性，就和强连通一样的，我们直接做整体二分。当前就是 [L,R,S][L,R,S] 表示加入这里面的边后这些点就合并起来。
然后加入 MM 组边，对这些点求解合并状态为 S1,S2,S3..SmS_1,S_2,S_3..S_m，那么在 MM 后面我们取代表点，在 MM 前面取做每个 ss 中的点即可。
这样复杂度就对了。
P8520
对于横向边，先全部加上。
然后从下往上扫，每次扫一个横线，然后将能和下面连接的情况统计一下，此时能连必然连，只是连谁的问题。
神秘，黑白染色的动机应该是提前钦定好某一个 belong 的原因。
AGC073B
建图，将可达点之间互建边，那么要求就是在一个范围内 00 连通块内的边有环。
其实这些边可以平移，所以平移到 00 上就是一个方案。
二分答案，然后要求 00 走回来。
强行把上一道题套过来，还是考虑 d1d_1，在 (n−d1,n](n-d_1,n] 直接删掉，然后递归到 { d1,d2−d1,...,dn−d1 }\set {d_1,d_2-d_1,...,d_n-d_1}。出现了 00，就说明成功了。
不过似乎并没有必要二分答案，反正就是一直递归，递归到出现一个 00 的时候直接计算走了多少步就行。
证明可以考虑，对于前 d1d_1 个点，和他们相关的 d2...dnd_2...d_n 一定可以拼上一个 d1d_1 从而和这个里面无关。
P5811
a≤b≤ca\leq b\leq c，若 cc 可以连通，换成小的也可以。
一颗树，就是考虑重心，如果说没有容纳下 aa 的子树，那就必然占用两次重心。否则可以构造。
一个图，考虑重心，然后如果作为一颗树不行，由 dfs 树的性质，再考虑重心父亲的儿子们加起来是否可行。
所以放点问题一般考虑重心，这都多少次了。
QOJ1812
一条链就是 121212，如果遇见菊花就 12->13456...
以此定目标，使得每个点到根路径颜色数不超过 77，构造就是，优先选择大子树选择已经用的颜色，更多的就直接新颜色。
证明可以 dp，转移形如 fi+1i+1→fif_{i+1}i+1\rightarrow f_i。
QOJ14711
如果只用 L,RL,R 的 N=1N=1 格子能怎么构造?（考虑对一个仅包含 L,RL,R 的统计步数，找到其表达式后对着构造。）
对于第一个位置，往左边后，其格子上一定是 LL。
其实意味着，当我们当前在 ii 时，[1,i−1][1,i-1] 一定全部都是 LL。
而如果我们到达了一个全 LL 的左侧，那么只需要 O(len)O(len) 步就能走出来，这就很地狱了，我们构造的上界只有 O(n2)O(n^2)。不过其是连续的，RR 就是不要这一个位。
还是严谨一下。
一个 LL：1
两个 LLLL：3
然后一个 LL 占一步，还要基础步 len-1 步。
然后样例就是：LLRLLR，算一下就是，1+3+7+9+5=25，正确！
加上 UD 后，分析一下，感觉也不会加很多啊？主要是，如果 D 接一个 R，那么 R 实际上也不会往 D 走，反而是向另一个地方走。不过这也有可能是构造的一个方法。
突然发现一个很好的结构：
CPP
LLU
DUR
DLL
首先我们发现，这个图很有意思。对于一段路径而言，我走过它了，然后再回到中间的某个时刻，它一直都是以最坏的次数走相同的路径。
不考虑恰好这个限制，那么我们只需要构建一条路径，使得其每一个位置的反方向所对应的正路径和尽量大。
太难了不想了。
CF2164F2
这相当于 uu 在祖先中指 aua_u 个点，然后剩下的指向 uu，然后问其拓扑序之和。
这样看来其实祖先儿子之间的比较关系还是比较充分的，如果只有一条链，那么在不存在环的情况下必然只有一个方案，因为是一个完全图。
进一步发现，从上往下确定 DAG 可以更好刻画这个过程！对于 dis=2 的点，其和祖先的关系是确定的。不断递归就是在前面已经确定的链上可以恰好找到第 aua_u 个点，然后把这个点插到中间。
这样我们将边的数量缩小到了 O(n)O(n) 级别，不过还需要统计拓扑序。
这些边画出来是一个一个三角形构成，而且对于：
CPP
  /\
 /  \
/    \
\    /
 \  /
  \/
这样的图，中间的两个点是能缩起来的。
而对于一个出点入点都是一度的点，其可以将两边的点合起来变成一个点，不断这样做一定可以合起来。
这个做法应该有一个名字：广义串并联图方法。
维护的话，可以考虑加入一个点时，将其对应的边权值放到这个点上，这样的话就不用再单独再算一遍了。
CF2164G
太难了
QOJ9870
一脸论文题的样子，我们尽可能的想出一些有用的做法吧。
同余最短路，在 w1≤1e4w_1\leq 1e4 还能做，接下来默认 w1≥1e4w_1\geq 1e4。
此时选择的数量小于等于 n2/1e4n^2/1e4，直接枚举数量，归到选择 xx 个数和为 yy，新序列为 [w1−w1,...,wn−w1][w_1-w_1,...,w_n-w_1]。
有 00 的存在，因此只需要 ≤x\leq x 个数即可。
不过减去 w1w_1 并没有使得这个问题有任何本质变化，甚至我们多添加了条件，这个思路是行不通的。
在模 w1w_1 的意义下尝试缩小一下决策数量，如果说一个 (d,w)(d,w) 能够被若干完美替代，那么让他再跑一遍最短路没有任何意义。
这个倒是莫名的简单，直接跑最短路的时候顺手判一下即可。
看错题了。
首先可以减去 nw1nw_1 使得条件变成 ≤n\leq n 个。
然后对于现在的最小值，可以再枚举一个数量，然后进一步递归。
QOJ9691
尝试将这些合法位置划分为若干矩形。
似乎有点困难，如果我们用前两种标记铺满，然后若干次对角线，这样的话甚至是若干对位乘加法，这个方法显然不行。
所以我们只能思考对于每个 aa 统计其 bb 的和。
QOJ14583
钦定全部为 C，然后进一步调整。
对于一个点已经是固定值的就不纳入考虑范围，那么对于边 2，若一侧为 A，则变 A 为 -1，变为 B 为 +1，若两个都没有确定，那么如果变成。
QOJ14584
直觉告诉我们这个并不是环。
这些点构成的边缘会不断的缩小，这意味着轮数只有 O(n)O(n)。
发现这个就是直径，那么直径两端的点就确定了，然后再来考虑喜欢这些点的点。
发现他们也确定了！就是往直径靠，然后往对应方向走。
进一步确定路径，我们会发现，一定是往直径靠，然后往中心走。
再考虑这个点被喜欢的点，如果在这个点上面，那么就是往下再跟着走，否则就是往直径上走后就往喜欢的点走，如果没有浓缩到直径里就进一步走。
再递归，如果一个点的路径是这样的话，对于喜欢它的点，在下面就往上走。差不多就是，首先到达和喜欢的点同子树，然后上下上下上，然后就往直径走，然后往中心走。
OK 会了。
求解直径中点，求解每个点的 dis，从大到小考虑。
如果喜欢点 dis 大，那么直接在前面建的树上二分，算出最终相遇点，那么可以表示为，走一段路，然后和 uu 这一段时间相同。
如果喜欢点 dis 小，那么我们一直往上走必然是遇得到这个 dis 小的点的。只是一个问题是遇见后该干什么。
换个角度，直接从两个最长点开始往前走，那么喜欢的点路径一定确定。
其实我们只需要位置就行，这个东西可以直接倍增吧。
所以我们要求解的：
直径，然后一遍建立。
upd： 不是按照 dis，而是直接从确定的点往前扫。
jly 听讲：
QOJ14711
只差一步，就是最后的那个构造，实际上这样就够了：
CPP
-------|
|-------
|------|
|||-----
|||----|
|||||---
|||||--|
-|-|-|XX
QOJ14713
很少看到 nn 开 3000 还不是 dp 的题。
首先，重量轻的优先是一个突破口，这个决策简洁，在排序后取的一定是一个前缀。
那么对于已经确定了 ww 的物品，我们将其排序后，枚举一个前缀 ii。
那么对于 j≤ij\leq i 的物品，如果其价值没有确定，那么肯定是弄成 11；j≥ij\geq i 的物品，如果其价值没有确定，那么肯定弄成 10910^9。（此时我们还没有考虑那些 w 没有确定的物品）
然后考虑按照价值排序的情况，此时对于重量确定的物品而言，其选不选我们是知道的，而对于重量不确定的物品还没有确定其选不选。
剩下的随便写写就会了。
不过对于 ww 没有确定的物品，如果说设置成 1e9，这不意味着它就选不了。
在我们设计的算法下，如果说枚举的前缀是 00，我们还是有可能会选上这个 1e91e9 的物品。
CF2164H
如果两个出现位置相交，则其并集一定是一个回文串。
找到 l=1l=1 的最长回文串，r=nr=n 最长回文串，首先把他们的贡献算了。
那么我们只需要考虑回文中心在 [L,R][L,R] 中的回文串即可，且此时其一定不会超出去。
不相交的很少，反正至少能分析到 O(nlog⁡n)O(n\log n)。
CF2164G
得到度数的情况下，可以考虑剥叶，不过我们需要统计一下周围点的信息。
这个可以直接统计异或和。
然后把底数换成 3 就 OK 了。
QOJ1817
可以使用 s1 里的每个 uu 必然有 u-2^d 精确刻画条件。
然后对 s0 递归构造，然后对于 s1 匹配上 s0 匹配的，然后剩下的一些 s0 再匹配。
QOJ1823
不懂就问，这个题是拿来给作者训练论文怎么写的吗？
将 aa 分成若干整的分解数，然后找它的过程可以用线段树解决。
QOJ1824
如果走到了一个点，其存在关键边，则我们一定会走出去。
提前处理了，如果说一个点有两个关键边，然后将这个点连接的两端缩起来，则可以将其他边全部删掉。三个就可以直接将这个点和旁边的点删掉。一条关键边就可以将两个点缩起来。
这样这个图有环就 OK，否则 gg。
如果说缩小的过程中出现将两个一样的点缩了，此时要求其旁边没有特殊边。如果成功就 output，否则直接将连通块干掉。
其实整体看来就是，保留下来的只有：一个整环，一个链，其他的情况一旦存在死点就直接死。
现在的问题是存在链的强行边。
不过可以考虑对每个链合并，直接枚举两侧的边，强行合并，最后无非也就一个 O(n3)O(n^3) 的边。
不过要存走过的点，不管了，直接存还是 O(n4)O(n^4)，或者用可持久化的平衡树做到 O(n3log⁡n)O(n^3\log n)。
不过可能会重边啊，这样似乎又不行了。
看了下题解，其必要性比较好，充分性其实并不显然，尝试用 dfs 树证明了一下发现可能用多条非树边。
QOJ1839
考察什么样的 f(p,q,s)f(p,q,s) 是合法的，首先可以将 pp 去掉，那么就要求连出来的边没有环，也就是不存在 i<j,si=1,sj=0,qi>qji\lt j,s_i=1,s_j=0,q_i\gt q_j。
从确定 qq 算 ss 的角度已经尝试不好做，考虑确定 ss 算 qq 方案数。
这相当于对于前缀 si=1s_i=1 的最大 qiq_i，sj=0s_j=0 时要 qj>qiq_j\gt q_i。
用延迟放置的思想，设 fi,j,kf_{i,j,k} 表示，已经考虑了前 ii 个数的 s,qs,q 放置，当前最大 qiq_i 的为 jj，有 kk 个 si=0s_i=0 的大于 jj 还没有放。
通过这个状态我们同样可以计算出 ≤j\leq j 的有多少个数，转移：
如果 si=0s_i=0 时，可以放大一点。
si=1s_i=1 时，如果往下放，那么一个组合数；往上放，那么枚举放到哪里，以及放了多少个数在中间，复杂度 O(n5)O(n^5)？
其实可以从 jj 往上每走一步，决定一下填不填，kk 中的谁来填，这样就好了，这样就是 O(n3)O(n^3) 了！
www 居然自己做出来了。
QOJ1844
环是好做的。
但是不好消环，因为可能出现某个点是奇数。
可以先不断操作，没有奇点时一定没有割边，此时就能用这个方法剥环了。
QOJ1854
必要是 gcd⁡(p,q)=1\gcd(p,q)=1。
玩一下 p=2,q=1p=2,q=1。
好像都是模一个数等于某两个数。
“归纳”一下就是，模 p+qp+q 等于 0/10/1 的时候合法，否则不行，当然要求 gcd⁡(p,q)=1\gcd(p,q)=1。
虽然炸了，但是至少说明我们可以凑出起点为 0 终点为 p+q 的路径，而且首尾都是。
o，原来是 p=1,q=1 没有判。
必要性证明的话，每次 xx 只能到达 x+p,x−qx+p,x-q，按照  mod p+q\bmod p+q 分类每次走一步 pp。
然后按照同余类分的话可以是 v0,1,...,p+q−1v_{0,1,...,p+q-1}，那么分类讨论就发现其绝对值之差不能过大。
然后为什么我们能构造出来呢？对于一个 n=p+qn=p+q 内的边形成是一个环。
就是在 gcd⁡(step,n)=1\gcd(step,n)=1 时一直走 stepstep 一定会遍历整个环。根据裴蜀定理一定走得到每个点对吧，而且不会提前走。
QOJ1874
前几天做过一个更难点的，感觉这个不会很难吧。
我错了，先咕咕了。
QOJ1875
应该会做啊，主要是突然搞忘了 999999 能整除的性质了。
然后数位 dp 一下即可。
具体的，从高到低决定有哪些位，然后计算方案数。
决定数量的话就是有若干个长度为 kk 的和一个不超过 kk 的，要他们的和和某个 rr 模 9999999999 同余。
直接枚举和 BM+rBM+r ，然后数位 dp 一下。
QOJ1876
QOJ1884
CF38H
判定一个方案是否合法，拿金牌的取最长路，拿铜牌的取最短路，中间判断有没有即可。
枚举最长路中最短的，最短路中最长的，剩下的话一个人可以分给三个区域中的一个，直接 dp 做到 O(n5)O(n^5)。
CF1696H
选择绝对值最大的 kk 个，看情况调整一下正负。
所以先排序，随便讨论一下应该不难。
UOJ390
wc 我不会 minmax 容斥了！！！
max⁡(S)=∑(−1)∣T∣+1min⁡(T)\max(S)=\sum (-1)^{|T|+1}\min(T)。
最大的元素会被算 1 次，而其他元素取或者不取最大值系数相反得证。
所以枚举一个包含 ii 的 SS，看一下最小值等于 ii 的方案数。也就是计算 ii 第一个被干死的概率。
然后就是先插入 aia_i 个小球，然后在前面依次插入 <aj\lt a_j 个小球。
枚举 ii，fi,j,kf_{i,j,k} 表示前 ii 个数，ss 大小为 jj，已经有 kk 个小球了，直接算 O(n6)O(n^6)。
主要是，j,kj,k 是必要的，且合并代价比较大。
不过这个顺序是不是可以撤销？直接从里面撤销 ii 的影响，然后再插入是不是就可以了，复杂度的话，插入撤销都是 O(n4)O(n^4)，做 O(n)O(n) 次就是 O(n5)O(n^5)。
QOJ8147
jsy 大佬神秘观察力，发现这个序列是一个栈，所以问题变成了每次加一个数，或者删掉一个数。
或者令 bi=∣ai+1∣2b_i=\frac{|a_i+1|}{2}，发现可以构成双射。
oooj 某神秘题目
给定长度为 nn 的序列 aa，共 qq 次询问，每次给定 lj,rjl_j,r_j，询问，有多少个长度为 nn 的序列 bb，满足：对于所有 1≤i≤n1\leq i \leq n 有 bi∈[0,ai]b_i\in [0,a_i]，且 b1⊕b2⊕...⊕bn∈[lj,rj]b_1\oplus b_2 \oplus ... \oplus b_n \in [l_j,r_j]，答案对 998244353 取模。
发现当固定了随意位小于等于某个值时，高位已经确定，因此可以统计每一个位的信息后直接算即可。
QOJ14816
Sequence Covering Problems：差分序列，正的 ll 位置用 blb_l，负的 rr 用 cr−1c_{r-1}。
Many Sequence Covering Problems： bib_i 增大会令 PP 增加 [zl≥0]zl[z_l\geq 0]z_l，cic_i 增大会令 PP 增加 −[zr+1≤0]zr+1-[z_{r+1}\leq 0]z_{r+1}，而如果能加则会一直加，所以其限制等价于 zl≤dlz_l\leq d_l，zr+1≥−erz_{r+1}\geq -e_{r}，而对应代价就是对应 a,ba,b 之和。
现在最地狱的事情来了，A,B,C,D,EA,B,C,D,E 都可以决定区间。
不过 D,ED,E 看起来比较小丑，实际上决定 AA 后其只是乘上一个数而已，而对于 B,CB,C 就是给差分序列一个加权。
暴力 fi,jf_{i,j} 表示考虑了 ii 个，上一个为 jj，枚举下一个数的话复杂度有点炸裂。考虑同时所有 jj 的贡献。
j=kj= k 直接做。
j<kj\lt k，此时 zi+1>0z_{i+1}\gt 0，那么 cc 无贡献，ee 直接化为定系数，bb 的贡献是 (k−j)b(k-j)b 可以拆开进行贡献，dd 就是 max⁡(d−(k−j)+1,0)\max(d-(k-j)+1,0)，直接当做 d−k+jd-k+j 的系数。
分析完贡献后，首先统计方案数，这个方案数就和 b,cb,c 无关了，而这个乘法可以拆开贡献。
放这种题和溢位？
QOJ14817
分成若干组，使得同组内最小值最大。
首先考虑单次询问，可以二分 DD。这个贪心似乎并没有那么简单，首先找到第一个数的可能后继中最靠前的。如果这个位置超过了 r−l+1k+2\frac{r-l+1}{k}+2 就炸了，因为剩下的会出现问题。然后继续看下一个数匹配。
然后考虑这样一个问题 −−−−−,−−−−−,−-----,-----,- 这样情况下前两个先匹配了不一定很好，所以需要加上更多决策。
记一些可接点集合 p1,...,,pkp_1,...,,p_k，每次扫一个点，首先将可接点加进去，然后在剩下的这些可接点中，选择剩下长度最长的接上来。
因为两种留下来的长度分别是 l1,l2l_1,l_2 和 l1−1,l2+1l_1-1,l_2+1，感觉上来说越靠中越好。
不过这个似乎很难优化，主要是信息太多了，而且不能划层。
不过根据刚刚的想法，我们可以尝试将这些序列划分成若干极长链，然后长的都可以了短的一定也可以。而且刚刚的决策是不是也行了？直接划分是 2,1,12,1,1，划分的策略还是需要调整。
最优策略一定是模 kk 同余的一组，问题转化为 k=1k=1。
然后我们取的位置是 max⁡(li,xi−1+D)≤ri\max(l_i,x_{i-1}+D)\leq r_i，可以拆开变成对于任意 i<j,li+(j−i)D≤rji\lt j,l_i+(j-i)D\leq r_j
采用分治结构线段树，分成若干区间，每个区间内部的 DD 是能求解的。而对于段之间，可以把这些询问一起二分，然后在上面一起做双指针，然后逐一判断即可。
复杂度是 O(log⁡V(nlog⁡n+qlog⁡n))O(\log V(n\log n+q\log n))。
第一个做法还是利用了 3log⁡n→2log⁡3\log n \rightarrow 2\log 方法。
我是傻逼，题目给了 DD。
而且凸包切凸包只有部分单调性，就是有两段单调，就是凸包之间的切线两段单调性不同。
QOJ14804
吓人题目。
好吧其实是高妙题目。
首先对一条链进行考虑，我们最优的方法一定是每次选择最浅的点，往上面走。直接做的话可以每次选择最浅的，然后往上走，要么走到 1 要么更劣考虑下一个。
这暗示了这些树之间的局面有某种全序关系，因此我们认为有全序关系，那么我们去考虑如何比较两个局面的优劣。
不妨这样想，对于 A,BA,B 两个局面，我们可以令有无限个 AA 和无限个 BB，那么因为他们之间有全序关系，所以我最优策略一定是不断走某个决策，可能中途劣了，但是一定又会去走下一个 AA。这个东西相当于走到 11 为止，或者重开。
因此我们现在要求对于一个点，可以重开的情况下的期望最优步数。似乎并不好求（迭代也不行），不过最劣的点是可以求的，也就是满足无论走到谁都比重开优的点，也就是到 11 期望步数最大的点。
所以我们可以考虑从大到小求这个值，而且还是因为全序关系，前面已经判定更劣的点我们是不会走的，而当前我们要求解的点集之间还没有确定。
不过无论怎么说，我们只钦定这些点，然后取期望步数最大的那个点，还是能求解出最劣的点，反正其他点在值上一定比它好。
（这个启示了我们一类方法，在遇见 max⁡E\max E 的时候，可以通过求解最劣点来做，也许我们策略考虑不周全，但是把当前能做的策略发现它已经最劣的时候，就可以把它踢掉。可以类比 dijkstra 的思想。或者像上周我做的那个胡策一样，都是找到某个解后往前推）
然后我们求解出每个点的权后，我们的策略就已经确定了，但是还是不好 dp，怎么办？
首先我们将这些路径独立出来，假设我们已经确定了每个点是走怎样的路径，那么最后到达 11 的一定是最大值最小的那个。然后进一步确定，我们的路径一定形如，一个点走到最大值，然后其他点都越过了这个最大值，不过后面再也没有动，然后这个点不断走走到了 11。
很高妙的思想，避免了每时每刻都去取最优的，直接从最大点开始分析。而且很多比较权值走路也能这样分析（我可能以前做过）每次走权值最小的，不如直接枚举他们的最终的值。不过这个还要复杂一点，走的路甚至不是单调的。
剩下的应该是统计基本功了。
QOJ14807
可以不用管水漏光的情况，如果被算成负数了还不如给别人合并了。只需要判断全部合起来都要漏光的情况即可。
合并 { v1,v2 },{ l1,l2 }\set{v1,v2},\set{l1,l2} 优，当且仅当 v1≤tl1v1\leq tl1，不过这个并不是操作了就更优。 可以放缩成选择两个 v,tlv,tl 抵消，反正最后我们也只会选择最优的那一种。
不过选择最大的 ll 和最小的 vv 抵消一定在最优解中，将这个两个抵消后再进一步抉择。合并后的 l/vl/v 序列并没有，将抵消合并的操作弄得好看一点应该是能维护的。
好像不需要怎么弄，直接排序做就行，如果删到一样的了就当这个数合并了就行。
QOJ14808
对着名字出的题应该不会多难。
首先来找到中间的两个串的 [L,R][L,R]，可以先找到 [l,R][l,R] 的border 数量，然后从 ll 开始扩展就能扩展到所有 [L,R][L,R]。
然后枚举两侧的 [R,L][R,L]，统计其 ”border“。
不过没必要，直接找到一个子串的所有出现位置，对应贡献一下即可。
QOJ14810
有点神秘啊。
如果一个点本来是割点，不过割掉出来的第一个连通块如果是指向了 uu 的父亲，那么暂时还看不出来；但是如果后面的点指向了 uu，那么算 low u 的时候就会算错从而导致看不出来。
充要条件就是每个点双至少和它有两个边，且其本身是割点。
OIWIKI 树状数组。
因为要学习二分所以重修一下。
相当于构造一颗树，ii 的父亲是 i+lowbit(i)i+lowbit(i)。
然后我直接狂暴膜拜 11d10xy and rizynvu 顺手把这个方法教给我了。
QOJ8049
暴力的话就是直接 fi,j,kf_{i,j,k} 表示考虑前 ii 个 xx 和前 jj 个 yy，和为 kk 的方案数，转移枚举一个数 O(n5)O(n^5)。
这是一个求和为 00 的过程，而且 x,yx,y 谁走下一步我们是能决定的，我们钦定在和为 ≤0\leq 0 时走 xx，和 >0\gt 0 时走 yy。
这样我们就将 dp 范围压缩到了 O(n)O(n) 范围内，复杂度 O(n4)O(n^4)。然后转移用前缀和优化即可做到 O(n3)O(n^3)。
CF2085F2
选择 kk 个互不相同的数，将其移动到一起的最优步数一定是前半部分往右，后半部分往左。
现在需要尽量优秀的选择，那么对于左半部分，一定是能往右就往右。
不妨枚举中心位置，先全部钦定为左边，然后调整一部分去右边即可，线段树维护即可。
CF2084F
首先判断两个的可达性，但是第一个操作也太逆天了，直接把 brb_r 这个数抹掉了，感觉是诈骗。
而循环移位是不是太强了？直接移动就能做到 nn 步啊？
ooo 原来是同时做啊，我无语了。
那么限制等价于 rr 是最小值，我们每次只能将一个数往前面交换，且满足前面的数更大。
不妨看作一个排列要移成某个 [1,...,n][1,...,n]，且每个数带一个权。
那么就是不存在 i<j,pi>pj,qi>qji\lt j,p_i\gt p_j,q_i\gt q_j。
不过这个题的 (p,q)(p,q) 是绑定的，那么我们就是要找一种方式使得不存在这样的双逆序对。
首先跑一个拓扑序出来，那么就是顺取数，那先把后继确定的时间短的取掉一定是对的。
at_agc059_d
怎么刻画这个出现的数的数量呢？
Ai=Ai+1+1A_i=A_{i+1}+1 首先就需要保证 Bi+kB_{i+k} 在前面出现过，然后新的这个数我们可以任意决定，其就独立了。
Ai=Ai+1−1A_i=A_{i+1}-1 就要求 Bi+kB_{i+k} 没有出现过，然后添加一个出现过的数。
Ai=Ai+1A_{i}=A_{i+1}，就是要求 BiB_{i} 和 Bi+kB_{i+k} 在 [i+1,i+k−1][i+1,i+k-1] 中的出现情况一致，那么直接令 Bi=Bi+kB_{i}=B_{i+k} 即可。
归纳上面三种情况，发现就是要求 i+ki+k 是否在 [i+1,i+k−1][i+1,i+k-1] 出现，同时给 BiB_i 一个值。
那么我们有对 ii 在 [i−k,i)[i-k,i) 和 (i,i+k](i,i+k] 中的出现情况做要求。
可以转化为匹配问题，这样一定能覆盖最终答案。
然后在最终答案的角度上考虑的话，只要 Bi≠kB_i\neq k 的时候，如果说不钦定 ri=li+k=1r_i=l_{i+k}=1 的有答案，那么加上这一对也合法，且可能将某一对反的搞成正的。否则只能钦定 ri=li+k=0r_i=l_{i+k}=0。
l,rl,r 的我知道，但是为什么这个东西是一个匹配啊？
我们的主要疑惑是，为什么这个东西是一度的，为什么不能是，一个数匹配上两个。
不过我们这样推，就是，最后反正也是找到一个数相等，然后另外一边同理。
从最后的角度来看，我们可以始终选择相邻的进行匹配，使得我们的模型可以成功刻画。
QOJ10404
li+lj≤sl_i+l_j\leq s，ri+rj≥sr_i+r_j\geq s 就一定能选 (i,j)(i,j)。
怪糟糟的，和上次那个逆天贪心题可能差不多。
构造一个扫描顺序使得能匹配的中有优劣即可。
QOJ14943
首先可以算出 373^7 种情况下，可以表示的数字个数。
不太懂 0 和其他数的区别啊。
原来是空的意思啊，不重要。
QOJ14944
有点意思的题目。
太奇怪了。
我们可以这样做：如果说有任务中的点，那么就打，否则就打出下一次出现最远的位置。此时这个位置至少打了 nn 次，我们在这个策略出现前一定是能捏到这个牌的。
在这样的策略下，我们发现只要取出了某个牌，那么它下一次出现的时候就不需要花费额外的次数，所以一定是最优秀的。对于一个排列以及任务列表，我们来计算其次数。所以求解的时候我们只关心第一次取出来的时间即可。
fif_i 表示将第 ii 张牌打出后的最小次数。那么对应的 fi=1+max⁡(fi−1,fj+n)f_i=1+\max(f_{i-1},f_{j}+n)。
现在要考虑统计每种排列下这个的答案。
实际上可以统计 ≤k\leq k 的答案，然后转而对 pospos 进行限制，显然 kk 减少一则所有 pospos 减少一，因此有用的 kk 仅 O(n)O(n) 个，至于锁定位置的话可以任取一个排列求 kk，然后上下 nn 即可。
QOJ14949
同一方向进入，就是求 vv 两侧距离。
不同方向进入，则存在分界线；如果分界线对应两侧过环，则求解 [0,m−1][0,m-1] 最靠边距离，否则就是算相邻 11 之间的距离最大值，同时要强制加入 vv 这个值。
删除好做，直接回滚，如果加上 vv，只要保证每一个块内询问个数不多，那么我们也可以将所有 vv 加入到分割点，到某单个 vv 的时候将其他的删掉即可。可以对询问进行排序。
QOJ14947
好吧不是我想象中的 young diagram。
首先发现对应杨表的反对角线的格子数量相同。
这也是充分的，因为操作可逆，我们令代表元为第一行最大，然后第二行最大（符合直觉）
构造的话，考虑找到 (1,λ1)(1,\lambda_1) 这条线上，往下多延伸的距离最大值，操作过来，此时一定合法。递归构造。
因此我们只需要证明在条件下 λ1\lambda_1 最大值相等即可，当然这是显然正确的，因为我们只需要找到斜对角线最靠外的一个移动过来即可。
后面的统计太逆天了，反正理解就行。
好吧还是写一下，最后的对角线和一定是先若干个 1，2，3，4，5，然后开始递减，这是因为每次都是从刚刚可以延伸的地方再延伸，不可能更多。
进一步观察，每次如果“丢失”了一些延伸的位置，那么在对角线上体现出来就一定是，本来有 ai+2a_i+2 个线，结果被搞出去 2ai+12a_{i+1} 条线，中间就有 ai−ai+1+1a_{i}-a_{i+1}+1 条右线和下线。
然后当做每次往中间插入下一层的线即可。
QOJ14819
本来不想做这个题的，但是似乎没有其他题做，那就做吧。
如果没有 33 的情况，就是每一个段可以收缩。
如果有 33，那么对于中间的段，取的是一个子段的收缩，左边是前缀，右边是后缀。
首先可以将序列倒转，此时长度递减，那么我们就求解出尽量靠前的 33 位置，给后面留的位置就比较多了。
对于钦定内部，首先 3 吃掉了第一段。
如果颜色和第一段相同
如果长度为 len1len_1，那么如果说下下段满足，就从下一段开始继续钦定；否则不合法。
如果说 <len1\lt len_1，那么第一段钦定完了。
如果颜色不同，那么从第二段开始即可。
如果说钦定的长度使得还剩下一些位置（或者根本没有钦定），可能可以钦定 33。
归纳出来就是 fi,0/1f_{i,0/1} 表示第一个位置是否被吃掉。
对于最后一段，可以这样处理，最后取的是一个后缀，不过这个是简单的。
对于第一段，如果钦定的是 0/len-1 都可以为 3，否则只能继续下去。
完了我寄了，虽然我们可以钦定 0 的长度，但是那是建立在上一个段没有补满的情况下的。

评论

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

正在加载评论...