11 月 gogogo

xcyyyyyy · 2025-11-05 19:49:59 · 题解

没题做了，托 11d10xy 和 rizynvu 的福做一下泛做。

QOJ833

www 完全偏了，转化成从右上到左下存在路径，但是这样并不等价于题目条件，这是因为题设只能下或右走。

然后正解是，维护能往下走就往下走的路径和能往右走就往右走（不是 free 就走，而是能走到终点的）的路径，那么这两个路径必然形如前后缀一段相等，然后中间分岔的形式。

如果堵前后那么必然不能到达，否则必然堵 A，然后维护出新的 A,B，剩下堵的就必须是 A\cap B 了。

核心思想是，做只堵一个点时，发现可以通过这两条路径进行刻画。

QOJ837

看错题了。

但是肯定要建立点分树。

建完后，对于不同子树间，必然经过 u，或者经过 u 的那些边，所以对这 2k 个点跑最短路后即可。

QOJ856

第一个字符相等则删掉。

否则不同，删掉或者修改或者插入，重复这个操作就能匹配上。

将这些删掉的匹配拉来，对于相邻两个匹配，假设他们的长度为 len1,len2，则需要的修改次数为 \max(len1,len2)。当然可以通过这个发现删除和添加我们任意保留一个操作即可。

感觉是缩小 dp 状态数量吧。

怎么是换维，换完维后就好做了。

QOJ857

过程必然形如，先把所有点往下面放，然后再一个一个匹配，对于一组匹配将 s 放到 t 的下面，最后再调整上来即可。

对于一颗子树，有如下一些过程：子树内一些匹配，出去，进来。这几种顺序并不好直接钦定啊。

然后对于第一次出现 s,t 共有的 u，一开始先把 s 全部往下调整，对于深度最浅的 s，将其往上走（走不到 u 就炸了），走到 u 子树内存在 t，然后将其安排到 t 下面，若发现安排到 u 邻点了，那么先将其他点排出去，然后再自己走。

但是如果采取递归结构似乎很难对子树结构合并，从上往下又不好确定子树怎么放好。

不过我们的目的还是将所有 s 放到 t 的子树内，完成这个目标的话，再将 s 往上调整必然能成功。

记 siz_x=snum-tnum，合法状态必然是 \forall siz\geq 0。

每次找到一个最深的 siz_x\lt 0 的点，则其所有儿子满足 siz=0，但是它这里会有一个 t 没有被满足。

如果父亲是一个点，则直接移动下来。否则就是找到一个到这条链路径上全部 siz\gt 0 的一个 s，且能走过来的，直接走过来，然后往下面走。

关于“能走过来的”可以进行调整。首先将要移动的 s 尽量往下靠，然后其他点使劲把这条路让出来，然后最后还原即可。

不过最后 s 如果占据了某个位置可能时的这些点完全无法还原，这种情况主要发生在 t 子树内只能放 t 的情况。

找代表元啊我炸了。

代表元的钦定也比较有意思，找某个根然后按照深度从大到小编号，这样我们取字典序最小的时候前面确定的点就不会动了。

然后构造一条合法路径时，只需要其他点动一格即可，所以合法啦啦啦啦。

QOJ862 听说太简单了

QOJ887 听说是阴间题，先不做。

QOJ888

直接分治，拆掉 min，分治外面的多加一条边就行。

\min(a_1+b_1,a_2+b_2,a_3+b_3)

QOJ962 红太阳提醒 01，所以我们要想 01。 01 排序可以用归并，左侧 11111000000，右侧 0000001111111，然后就一遍归并了。然后分治中间的断点即可。但是操作 mx 为奇数时可能左右会交换，对于 01 排序时我们发现 0011100 和 000111000 都可以弄成 000011111 或者 1111000；而外层分治的时候可以提前计算好下面的次数然后提前规定好。我这个做法还是比较牛，但是更牛的是把操作转化成一个区间 reverse + 整体 reverse，区间 reverse 就好做了。 --- lrs 讲题。 #1 $O(deg)$ 算一条边，说白了就是快速锁定每一条边。每次找两个连通块间最小的边，可以枚举小的一边，在大的一边查前驱后继，单次的话 $O(n\log ^2n)$。从 brouvka 的角度来看似乎只会连接 $|a-b|=1$ 的边。因为总能找到一条边代价为 $1$，所以答案就是 $|E|$。至于构造方案，维护一下每个连通块的 $[L,R]$，然后找到一个 $L\neq 1$ 或者 $R\neq n$ 的连通块，直接合并即可，更新 $L,R$ 是不难的。突然发现 $i$ 也要删掉，不过不重要。 #2 不妨设 $X\leq Y$。两个栈的意义是，我们得以将不连续的 c 也同时删。而这些 c 必然不交，所以直接考虑 dp，设 $f_{i,j}$ 表示前 $i$ 个，钦定数字为 $j$ 的最小代价，复杂度是 $O(n^2)$ 的？是不是有什么没考虑到的。经大佬 lhz 提醒，有可能有嵌套关系，所以我们区间 dp 一下，$f_{l,r}$ 表示答案，然后从左往右扫，$g_{i,j}$ 表示当前到 $i$ 钦定 $j$，然后里面的自然就用 $f$ 算，随意 $O(n^3)$ 吧。经过讲解发现还有可能从栈跑回来，不过也不重要。 #3 似乎做过？满足 1. 条件的，就搞一颗点最大生成树，然后答案为深度和。然后随便建立一颗树，答案就是 dep 和了。加一个点的话，就是数以它为开头的方案数了，也就是另一个端点取不到最小值的情况，考虑重新建立最小树的过程，那么其一定是最后加入的，所以问一下 dep 和就行。没听。 #4 倒着加数，这样的话后面不管是不是 mx 都要整体加一/减一。没听，反正做过。 #5 ~~直接直接，所以直接就直接了~~ 建立 ACAM，处理出 t 每个前缀在哪里，然后我们要做的类似于是一种数组复制？但是复制的是长度也没办法直接出 l 啊？有点难。 #6 每次如果将最小值减到 0 的话，这个序列的最大值不会超过 $mx$。设次小当前为 $cmn$，最大为 $mx$，则序列不变当且仅当 $2cmn\geq mx$。其他的不知道的。证明思路可以学习。 #7 $k=1$ 时我们要最小化 $x+y-\gcd(x,y)$，这个式子至少减去了 $\max(x,y)$，至多减去了 $x+y$。若 $(a,b)$ $(c,d)$ 满足 $a+b\leq \max(c,d)$，则必然不会删掉 $(c,d)$。因此考虑最小的两个数 $x,y$，我们只考虑 $z\leq x+y$ 的对子。然后如果固定 $a\lt b$，且固定 $b$ 时，若存在 $a$ 为 $b$ 因数则最优。对于剩下的可能的对都满足 $a \nmid b$。好难，直接开始猜，我们只需要考虑排序后的相邻对，证明思路可以学习。 #8 肯定得容斥吧。如果钦定了若干个区间是一个 $[l,r]$ 的排列，那么最后方案数自然就是划分的每个段长的阶乘，以及外面没有钦定的阶乘。这个 trick 似乎见过，不过还是可以学习。下面是正文部分： --- CF1801G 有点奇思妙想了，本来以为要用某种计数手段。找到最大 $R$ 使得存在以 $R$ 右端点，跨过 $l$ 的字符串，以 $[R+1,r]$ 为结尾的子串都一定不会跨过 $l$。对于 $[l,R]$ 内的串，其结尾的就有可能超出去了，不过此时这个串一定是某个串的后缀，可以提前预处理出来。本质上还是一个预处理的过程，不过讨论得这么细是真逆天。 CF1805F2 减去 0 的性质是可以发现的。根据 lrs 的说法， $a_n$ 活下来的条件是很苛刻的，所以我们仔细探索一下。如果其活下来了，那么 $0+a_2,...,0+a_n$ 都活下来了，这个时候就已经有 $n-1$ 个数了，而其他数中最小的就是 $b_2+b_3$，这表明 $b_2+b_3\gt b_n$。不妨多做几轮，如果再次苟活，那么序列变成 $0,b_4-b_3,...,b_n-b_3$ 注意到此时 $b_n$ 已经砍掉一半了，也就是其最多活 $O(\log V)$。 **活不了，说明其对最终答案无影响，我们可以不用维护它**。那么不妨推广到其他数，假设我们只需要维护 $L$ 个数就能将最后答案算出来，我们进行证明。这里的证明思路是，我们可能在某些时候无法维护出正确的值，所以不得不退而求其次，不过只会退很少次，所以我们也只需要维护很少个数。 $b_2+b_3\leq b_L$，那么再算一次还是正确的。否则 $b_2+b_3\geq b_L$，根据刚刚的说法，我们此时不一定能维护出正确的值，因为我们不知道 $b_{L+1}$ 能不能冲进来，不过至少 $L-1$ 个数是合理的，再做一次 $L-2$ 个数是合理的。而每做一次，最后一个数都会砍一半，砍到后面就不会出现 $b_2+b_3\geq L$ 的情况了（$n=2$ 特判），所以只需要维护 $2\log V$ 个数的变化。 CF1806F2 感觉有点没想懂啊。直接猜想只会选择一个集合的数（lrs：你要对自己的猜想负责），尝试证明一下：对于两个集合 $S,T$，假设 $x\geq y$，且 $S$ 中存在 $\geq 2x$ 的数，那么将 $2x$ 提出来一定不劣。不过只存在 $x$ 就炸了。~~所以确实要对猜想负责~~。不过这个时候至少说明，不会有 $\geq 2$ 个存在不同元素的集合。而且我们可以钦定 $S$ 里没有相同元素，否则可以当做相同元素的合并。因此提前处理好如果要求 $x$ 个数合并，最小的那几个是谁，然后枚举 $\gcd$ 以及选择数的数量，可以过 easy version，做到复杂度 $O(m\log m)$。 hard version 生怕我们枚举 $\gcd$，所以需要进一步发现性质。因为 $S$ 中再怎么都是 $d$ 的倍数，如果我们将其中的数往下调的话，实际上能变大很多，而 $\gcd$ 的减少无非也就 $d$。也就是说，如果选择了 $x$ 个数为 $S$ 中的数，那么第 $x-1$ 个数前面的数全部都选择了。把不重复的数拉出来，则选择的是一个前缀，这个前缀 $\text{gcd}$ 下降次数为 $j$，我们相当于枚举一个数 $len$，再多选一个数，求解 $\max(b_{m-len}+\gcd(a_{len-1},x))$。 $\gcd$ 只会有 $O(\log m)$ 个，暴力求解就行。 CF1874F 考虑到相交的情况下，对于 $[l,r],[L,R]$，其 $[L,r]$ 必然也是包含在题目所要求的区间下的，所以如果容斥的话必然可以抵消，所以只需要对树形态的进行统计，这个自然不难的。 QOJ964 可以随便铺一下，在值域上体现出来，就是不断往下接，接上后又不断往上走。也就是从 $i=n \rightarrow 1$，找到第一个 $num_i=i$ 的位置。有点高妙，在莫队的上面可以搞一个并查集和一个链表找第 $k$ 个后缀最大值，用以维护后缀加一和最大值查询。更牛的是直接扫描答案，维护每个询问内 1 数量。希望找到当前 sum $\rightarrow $ 希望维护找最大值的数据结构。区间具有单调性 $\rightarrow $ 只用维护每个 $l$ 最大 $r$。将 $x$ 减一 $\rightarrow $ 区间减一。不过最后维护的时候，可以将 $l$ 升序，$r$ 降序的顺序来放。 QOJ970 这个性质没发现啊。二分答案，则 $\leq W/2$ 的必然选中，因为将其插入，然后将可能的旁边的 $\gt W/2$的删掉，显然答案更优。有时候真的想不清楚这种区间询问该怎么做，直接一点的，有对 $r$ 从左往右，也有 $l$ 从左往右；然后还有对答案进行枚举处理；或者分治进行全局处理；或者直接处理；或者移动指针进行求解；或者整体二分；或者猫树处理；差分处理。考虑对于多个区间快速判断一个 $W$，对于相邻的 $W/2$，显然其最左最右中的已经确定，而对于更中间的也就是两个最小值询问了。 $W$ 具有单调性，$k$ 也具有单调性。整体二分？我们并不能找到很好的数据分治方法。如果 $W$ 的可能值很少的话我们是可以考虑扫答案的。对于 $0/1$ 状态的改变只会经历 $O(n)$ 个 $W$，我们不妨从这里进行入手。对于 $W\in[l,r]$，相邻两个 00 状态可以表示为：如果 $W\geq$ 多少，那么 00 中可以再插入一个值。然后问题是一个区间我们不可能去扫多次，不过哪怕不考虑循环区间的影响，其他位置也是递增的，我们可以分别在 $k-1,k,k+1$ 的时候进行扫描。那么就是怎么设置警报器了，可以理解为一个前缀减的警报器？不过并不是一个相加的形式。可以用分治搞成相加的形式，当 $l,r$ 其中一端达到 $k/2$ 时报警，否则设置更小。不过分治和答案枚举并不能同时用。 --- 每次加入一个数 $x$，考虑两侧的最小值，如果在 $[x+y,2y)$ 间就放到 $x$ 的上，否则放到 $y$ 上，可以主席树做到 $O(n\log n)$。如果不要求左右侧的话，可以直接在主席树上二分了（这一点很困难了），然后一步步调整即可。 tomorrow。 QOJ971 一个 bst 怎么做？这个 bst 的性质很好，其实就相当于是将这些值排成一列，然后在上面按照时间建立小根笛卡尔树。找到两侧中第一个比它小的，那么其父亲必然是其中较大的一个。然后我们要做的就是询问到根的和，扫描线后就是：维护一个序列，每次会将一个值改成 $w$，然后询问一个位置建立笛卡尔树后往上链的和。一个点 $x$ 是另一个点 $y$ 的祖先，当且进当 $a_x\lt a_y$，且 $(x,y)$ 中的数 $\gt a_x$。那么修改一个点的值的时候，如果是从 $\inf$ 修改成 $w$，首先其对别人的贡献是好做的，不必多说。而其他点可能本来跨过它的，然后被它挡住了。似乎不是很好算啊。 --- 我是傻逼。如果不能很好的维护祖先对儿子的贡献，那就直接从儿子问，那么显然这是一个前后缀最大值的模型，楼房重建就行了。 QOJ975 想了半天，好像迭代是一个很好的刻画方法，不断迭代到后面肯定就是取其凸包了。 QOJ977 jsy 说这是儿子题。 $n\times m$ 必然最大，然后 $n\times m-1$ 必须和他同行或者同列，然后下一个数继续填。实在刻画不出来了，还是用容斥吧。假设钦定了 $|a| $ 个数，从小到大依次排成 $[a]$。对于 $a_1$，取到了 $2n-1$ 个数 $\leq a_1$，那么对于 $a_i$，取到了 $2(n-i)+1$ 个数。不过每一次取到的数有很多，或许很多情况下并没有值？ $f_{i,j}$ 表示考虑前 $i$ 个数，已经钦定了 $j$ 个数。那么显然需要保证 $i\geq O(j^2)$。合法 $j$ 是根号级别的。 --- 不需要 dp 具体的数，直接连边后是一个拓扑序直接算就行了。 QOJ993 假如有一个元素特别少，为 $x$ 个。对于两个箱子，我们任意选择两个颜色不断维护，那么只需要 3x+1 步就能确定出一个多的元素，对于剩下两种颜色，我们还是不断加，2x+1 个。其中最多浪费多少呢？是不是选择的两个颜色中有一个少元素，这样我们可能会扔掉 2x+1 个元素。那么 $x\leq 28$ 都能做。事实上我们完全有可能在确定前一个都没有保留，不妨就记成 $3x$，我们会丢掉这么多箱子，那么剩下 $100-3x\geq43$，那么 $x\leq 19$。最小加次小 $\geq 43$ 也很好。否则我们再那么想要取两个次大的已经很不优了，其实只要把最大的那个选了就好，显然这个东西用类似摩尔投票的方法即可，反正差值特别大。 QOJ1166 一个点不能被上下包含。一个颜色有这样几种想法：可以双左，双右，直接连接（均两侧）。要求就是不能相交。 --- 虽然看起来是 4-sat，但是这四个维度仔细分析一下，其实只需要两个线段的方向确定后，其连线就确定了，我们对方向进行 2-sat 即可。还是一个简化的一个过程，其实我也想到了，不过没有深究，下次注意点。长度取 $R_i$ 好，有点 666。 QOJ1173 没有什么有效的思路，不妨直接对本质问题研究。将所有不能一起做的区间相连，那么这个问题可以怎么解决？ ---- 这是题吗这是题吗这是题吗？？？？？？？？？？？？？？？？问题类似于匹配，不断加入区间，考虑当前最优的决策。按照右端点从大到小进行加入，当加入一个区间的时候：如果能匹配，那么直接匹配；否则我们希望可以替换前面的一些匹配使得待匹配的区间的 $l$ 尽可能大，这时按照右端点从大到小加入的好处就来了，这些区间我们都能替换，直接选择 $l$ 最大的那个进行替换即可；此时可能对前面直接匹配进行质疑，不会选择 $l$ 可以中最小的那个吗？实际上，因为是按照 $r$ 从大到小排序，所以可以的区间以后都可以。这个解法应该是实在没有办法的情况下直接考虑一个个加，然后逐步构造封闭贪心的结果。 QOJ1174 又是这种不是题的题。安装的灯可以当做从 $1/2$ 开始走路，每次走 $1/2$ 步长，安装对应的灯。方案数拿脚算，关键是将这些方案排序是个什么鬼。还是尝试构造拓扑序，最小的方案可以用 dp 求解。（不过一个拓扑序就已经是 $O(n)$ 的了，就算真的取这么多次不就炸了吗，如果用哈希就不好找下一个了啊）不过除此之外我们并没有其他方法了呢，所以硬着头皮构造吧。 --- 前 k 大可以构建，前 k 小不行了捏。可持久化可并堆不会，咕咕咕。 nbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnb 谁发明的 K 短路！！！真的是厉害，首先可以构建一颗指向 t 的最短路树，从 $s$ 到 $t$ 的路径可以刻画为若干非树边组成的路径，因此我们定义一个非树边 $(u,v,w)$ 偏移量为 $d_v-d_u+w$，那么答案就是 $d_s+\sum w_e$。一股 johnson 最短路的味道对不对？从 $u$ 我们可以走任意一个祖先的非树出边，这样的话 k 短路就变成了在这个图上的一条路径。不过此时边数太多，不过走路必然是按照边权从大到小走，所以同样可以用类似拓扑序的方法求解 $k$ 短路。一个状态为 $(dis,heap)$，然后每次走一条边后，就对应放入新的持久化可并堆。被 0 边爆了，以后排序来或取树顺序时一定要多留意一下。 QOJ1351 找到一个在 $2$ 以内尽可能小的边集，使得割掉后图变成二分图，统计数量。 $|S|=0$，就是判定问题。 $|S|=1$，抽取生成树，如果只存在一条奇边，那么直接删掉这个环上的任意一条边都可以；否则多条奇边我们必须删除其覆盖的树边交集。证明的话可以单独再取一条边题换掉这个边，然后在新的生成树上进行分析。-+ $|S|=2$，似乎就有点困难了，删掉至少一条非树边是很好进行计算的，关键是删掉两条非树边。根据刚刚的分析，如果一个奇边中间的边被删掉了，就已经可以将其当做偶边抛开了，所以我们的任务是去覆盖所有的奇边。 --- 错了，不是覆盖所有奇数边。可以从这个角度来理解：因为我们是要求删掉最少的边，所以每一次删掉的边必然被一个奇边经过，既然存在一条奇边，其实可以当成这个边有个边权 1，被翻转成 0 了。然后转化成翻转边权的话就好做了，而且注意到在这个问题背景下，偶边并没有那么不重要，甚至是完全融入这个体系中的。这个描述方法真的好厉害，就是通过最少的条件，使得删边必然存在奇边，然后就转化为了翻转边权。 QOJ14579 普通 dp 转移：$f_{i,j,k}$ 表示 dfn 序到 $i$，钦定子树内有 $j$ 个取点，还可以取至多 $k$ 个点的最大值。既然是钦定，进入的时候我们直接取 $c_i-j$ 个的 $v_i$ 进行转移，然后看 $i$ 这个点要不要取，然后直接进入子树。但是进入子树的时候需要再钦定一个 $j'$ 表示子树内需要这么多，但是由于转移顺序的钦定，我们无法得知之前的 $j$，也无法得知后面还剩下多少 $(j-j')$。不过我们相当于要 dp 一个取链序列，然后子树点数做前缀和就是 $t_{out}-t_{in}$，那么可以取的点数就是 $c_i-(t_{out}-t_{in})$，由于题目保证了 $c_i\gt t_{any}$，所以可以拆成 $c_i-t_{out}+t_{in}$，这样我们分拆成两步进行转移即可。对于不选子树，这就是卷上一个子树内的选择若干条最大链的方式，红太阳说这个可以四边形不等式。 --- queue 似乎有点慢，红太阳说的。 basic_string 似乎有点快，红太阳说的。 stable_sort 在比较次数上比 sort nice 一点。 --- QOJ1357 看起来好有意思！如果只有一个黑子需要特判一下，因为这个情况下黑子不能抵消步数。一个黑子的话，记 $x,y$ 为在对应维上的差，若 $x\neq y$，则 yuto 直接选择短的一边逃逸即可，否则可以一直维持这样的形态直到最后一步被逮捕。而且通过这个特判我们发现这个距离是很重要的，只要存在 yuto 就完蛋了，否则还能争。问题可以转化为若干 $(x,y)$，每次 yuto 可以选择一个维度全部减一，Platina 可以选择一个棋子的一个维度减一，减到负一就炸掉一个棋子。从感觉上来说，yuto 会操作一侧后再操作另一侧。如果这样都不行，那么半途而废也不行啊。也不对，反正好难。会做了。 QOJ1359 $k=1$ 就很像最小割了，但是这个要求我做多层最小割？？？显然不可能考新算法，所以不要慌张。感受了一下，好像要建多层图，问了下红太阳说是，那就尝试建一下。建立 $K-1$ 层图，第一层我们肯定需要一些点去将从 $s$ 到 $t$ 的一系列点拦住，不过拦住后，我们可以通过消耗一次免费次数到达下一层。所以正解呼之欲出了，层与层之间建立无穷大的边即可。 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\nrightarrow i+1$ 的状态必然经过，对两侧分别求解后直接合并即可。还好我比较机智，在前后多加了两个点。 CF1630F 图传递，所以一个点有三种状态（对点的状态讨论）：小的，大的，或者不选。令一个边从小到大。可以建立图，如果说一个点是小的，那么所有指向它的边都不行，如果一个点是大的，那么它指向的都不行。左右不能选，这变成了一个最大独立集。然后这个图并不是二分图，但是边很有性质。定向后是一个 DAG，所以变成了最长反链。 CF1338E 最好别觉得 vector().size() 是 ull 的。 CF1305G 本来是最小树形图，但是边双向，可以添加对点的权值后变成最小生成树，每个点多算了一个权值。如果树形图是森林的话可以考虑加一个权为 0 的超级原点来去掉对根点的特判。 QOJ4898 $n$ 小的时候可以用 st 表优化建图。首先计算若干组边后的代表元，对于 $(d1,d2)$，对于最后 $d1$ 个点，他们一定和 $v-d1$ 相连。尝试递归下去，发现剩下的点距离为 $d2-d1$ 就相连，而且信息没有丢失，所以可以递归下去。多组边同理，这样我们得到了一组组边对这个图的方法。在辗转相除过程中，对 $n$ 的修改只用了 $O(\log n)$ 个 $d$，只有这些 $d$ 是有用的。加上 $b$，其实就是在这些 $u_i,v_i$ 只用一组组边构成的 kruskal 重构树上的虚树的边拿出来一起跑一个 kruskal 即可。不过这个时候有点黑暗了，因为我们每加入一组边后都要尝试去对每个 $u$ 跑，这很不好。既然是连通性，就和强连通一样的，我们直接做整体二分。当前就是 $[L,R,S]$ 表示加入这里面的边后这些点就合并起来。然后加入 $M$ 组边，对这些点求解合并状态为 $S_1,S_2,S_3..S_m$，那么在 $M$ 后面我们取代表点，在 $M$ 前面取做每个 $s$ 中的点即可。这样复杂度就对了。 P8520 对于横向边，先全部加上。然后从下往上扫，每次扫一个横线，然后将能和下面连接的情况统计一下，此时能连必然连，只是连谁的问题。 --- 神秘，黑白染色的动机应该是提前钦定好某一个 belong 的原因。 AGC073B 建图，将可达点之间互建边，那么要求就是在一个范围内 $0$ 连通块内的边有环。其实这些边可以平移，所以平移到 $0$ 上就是一个方案。二分答案，然后要求 $0$ 走回来。强行把上一道题套过来，还是考虑 $d_1$，在 $(n-d_1,n]$ 直接删掉，然后递归到 $\set {d_1,d_2-d_1,...,d_n-d_1}$。出现了 $0$，就说明成功了。不过似乎并没有必要二分答案，反正就是一直递归，递归到出现一个 $0$ 的时候直接计算走了多少步就行。证明可以考虑，对于前 $d_1$ 个点，和他们相关的 $d_2...d_n$ 一定可以拼上一个 $d_1$ 从而和这个里面无关。 P5811 $a\leq b\leq c$，若 $c$ 可以连通，换成小的也可以。一颗树，就是考虑重心，如果说没有容纳下 $a$ 的子树，那就必然占用两次重心。否则可以构造。一个图，考虑重心，然后如果作为一颗树不行，由 dfs 树的性质，再考虑重心父亲的儿子们加起来是否可行。所以放点问题一般考虑重心，这都多少次了。 QOJ1812 一条链就是 121212，如果遇见菊花就 12->13456... 以此定目标，使得每个点到根路径颜色数不超过 $7$，构造就是，优先选择大子树选择已经用的颜色，更多的就直接新颜色。证明可以 dp，转移形如 $f_{i+1}i+1\rightarrow f_i$。 QOJ14711 如果只用 $L,R$ 的 $N=1$ 格子能怎么构造?（考虑对一个仅包含 $L,R$ 的统计步数，找到其表达式后对着构造。）对于第一个位置，往左边后，其格子上一定是 $L$。其实意味着，当我们当前在 $i$ 时，$[1,i-1]$ 一定全部都是 $L$。而如果我们到达了一个全 $L$ 的左侧，那么只需要 $O(len)$ 步就能走出来，这就很地狱了，我们构造的上界只有 $O(n^2)$。不过其是连续的，$R$ 就是不要这一个位。还是严谨一下。一个 $L$：1 两个 $LL$：3 然后一个 $L$ 占一步，还要基础步 len-1 步。然后样例就是：LLRLLR，算一下就是，1+3+7+9+5=25，正确！加上 UD 后，分析一下，感觉也不会加很多啊？主要是，如果 D 接一个 R，那么 R 实际上也不会往 D 走，反而是向另一个地方走。不过这也有可能是构造的一个方法。突然发现一个很好的结构： ``` LLU DUR DLL ``` 首先我们发现，这个图很有意思。对于一段路径而言，我走过它了，然后再回到中间的某个时刻，它一直都是以最坏的次数走相同的路径。不考虑恰好这个限制，那么我们只需要构建一条路径，使得其每一个位置的反方向所对应的正路径和尽量大。太难了不想了。 CF2164F2 这相当于 $u$ 在祖先中指 $a_u$ 个点，然后剩下的指向 $u$，然后问其拓扑序之和。这样看来其实祖先儿子之间的比较关系还是比较充分的，如果只有一条链，那么在不存在环的情况下必然只有一个方案，因为是一个完全图。进一步发现，从上往下确定 DAG 可以更好刻画这个过程！对于 dis=2 的点，其和祖先的关系是确定的。不断递归就是在前面已经确定的链上可以恰好找到第 $a_u$ 个点，然后把这个点插到中间。这样我们将边的数量缩小到了 $O(n)$ 级别，不过还需要统计拓扑序。这些边画出来是一个一个三角形构成，而且对于： ``` /\ / \ / \ \ / \ / \/ ``` 这样的图，中间的两个点是能缩起来的。而对于一个出点入点都是一度的点，其可以将两边的点合起来变成一个点，不断这样做一定可以合起来。这个做法应该有一个名字：广义串并联图方法。维护的话，可以考虑加入一个点时，将其对应的边权值放到这个点上，这样的话就不用再单独再算一遍了。 CF2164G 太难了 QOJ9870 一脸论文题的样子，我们尽可能的想出一些有用的做法吧。同余最短路，在 $w_1\leq 1e4$ 还能做，接下来默认 $w_1\geq 1e4$。此时选择的数量小于等于 $n^2/1e4$，直接枚举数量，归到选择 $x$ 个数和为 $y$，新序列为 $[w_1-w_1,...,w_n-w_1]$。有 $0$ 的存在，因此只需要 $\leq x$ 个数即可。不过减去 $w_1$ 并没有使得这个问题有任何本质变化，甚至我们多添加了条件，这个思路是行不通的。在模 $w_1$ 的意义下尝试缩小一下决策数量，如果说一个 $(d,w)$ 能够被若干完美替代，那么让他再跑一遍最短路没有任何意义。这个倒是莫名的简单，直接跑最短路的时候顺手判一下即可。 --- 看错题了。首先可以减去 $nw_1$ 使得条件变成 $\leq n$ 个。然后对于现在的最小值，可以再枚举一个数量，然后进一步递归。 QOJ9691 尝试将这些合法位置划分为若干矩形。似乎有点困难，如果我们用前两种标记铺满，然后若干次对角线，这样的话甚至是若干对位乘加法，这个方法显然不行。所以我们只能思考对于每个 $a$ 统计其 $b$ 的和。 QOJ14583 钦定全部为 C，然后进一步调整。对于一个点已经是固定值的就不纳入考虑范围，那么对于边 2，若一侧为 A，则变 A 为 -1，变为 B 为 +1，若两个都没有确定，那么如果变成。 QOJ14584 直觉告诉我们这个并不是环。这些点构成的边缘会不断的缩小，这意味着轮数只有 $O(n)$。发现这个就是直径，那么直径两端的点就确定了，然后再来考虑喜欢这些点的点。发现他们也确定了！就是往直径靠，然后往对应方向走。进一步确定路径，我们会发现，一定是往直径靠，然后往中心走。再考虑这个点被喜欢的点，如果在这个点上面，那么就是往下再跟着走，否则就是往直径上走后就往喜欢的点走，如果没有浓缩到直径里就进一步走。再递归，如果一个点的路径是这样的话，对于喜欢它的点，在下面就往上走。差不多就是，首先到达和喜欢的点同子树，然后上下上下上，然后就往直径走，然后往中心走。 OK 会了。求解直径中点，求解每个点的 dis，从大到小考虑。如果喜欢点 dis 大，那么直接在前面建的树上二分，算出最终相遇点，那么可以表示为，走一段路，然后和 $u$ 这一段时间相同。如果喜欢点 dis 小，那么我们一直往上走必然是遇得到这个 dis 小的点的。只是一个问题是遇见后该干什么。换个角度，直接从两个最长点开始往前走，那么喜欢的点路径一定确定。其实我们只需要位置就行，这个东西可以直接倍增吧。所以我们要求解的：直径，然后一遍建立。 upd：不是按照 dis，而是直接从确定的点往前扫。 --- jly 听讲： QOJ14711 只差一步，就是最后的那个构造，实际上这样就够了： ``` -------| |------- |------| |||----- |||----| |||||--- |||||--| -|-|-|XX ``` QOJ14713 很少看到 $n$ 开 3000 还不是 dp 的题。首先，重量轻的优先是一个突破口，这个决策简洁，在排序后取的一定是一个前缀。那么对于已经确定了 $w$ 的物品，我们将其排序后，枚举一个前缀 $i$。那么对于 $j\leq i$ 的物品，如果其价值没有确定，那么肯定是弄成 $1$；$j\geq i$ 的物品，如果其价值没有确定，那么肯定弄成 $10^9$。（此时我们还没有考虑那些 w 没有确定的物品）然后考虑按照价值排序的情况，此时对于重量确定的物品而言，其选不选我们是知道的，而对于重量不确定的物品还没有确定其选不选。剩下的随便写写就会了。不过对于 $w$ 没有确定的物品，如果说设置成 1e9，这不意味着它就选不了。在我们设计的算法下，如果说枚举的前缀是 $0$，我们还是有可能会选上这个 $1e9$ 的物品。 CF2164H 如果两个出现位置相交，则其并集一定是一个回文串。找到 $l=1$ 的最长回文串，$r=n$ 最长回文串，首先把他们的贡献算了。那么我们只需要考虑回文中心在 $[L,R]$ 中的回文串即可，且此时其一定不会超出去。不相交的很少，反正至少能分析到 $O(n\log n)$。 CF2164G 得到度数的情况下，可以考虑剥叶，不过我们需要统计一下周围点的信息。这个可以直接统计异或和。然后把底数换成 3 就 OK 了。 QOJ1817 可以使用 s1 里的每个 $u$ 必然有 u-2^d 精确刻画条件。然后对 s0 递归构造，然后对于 s1 匹配上 s0 匹配的，然后剩下的一些 s0 再匹配。 QOJ1823 不懂就问，这个题是拿来给作者训练论文怎么写的吗？将 $a$ 分成若干整的分解数，然后找它的过程可以用线段树解决。 QOJ1824 如果走到了一个点，其存在关键边，则我们一定会走出去。提前处理了，如果说一个点有两个关键边，然后将这个点连接的两端缩起来，则可以将其他边全部删掉。三个就可以直接将这个点和旁边的点删掉。一条关键边就可以将两个点缩起来。这样这个图有环就 OK，否则 gg。如果说缩小的过程中出现将两个一样的点缩了，此时要求其旁边没有特殊边。如果成功就 output，否则直接将连通块干掉。其实整体看来就是，保留下来的只有：一个整环，一个链，其他的情况一旦存在死点就直接死。现在的问题是存在链的强行边。不过可以考虑对每个链合并，直接枚举两侧的边，强行合并，最后无非也就一个 $O(n^3)$ 的边。不过要存走过的点，不管了，直接存还是 $O(n^4)$，或者用可持久化的平衡树做到 $O(n^3\log n)$。不过可能会重边啊，这样似乎又不行了。看了下题解，其必要性比较好，充分性其实并不显然，尝试用 dfs 树证明了一下发现可能用多条非树边。 QOJ1839 考察什么样的 $f(p,q,s)$ 是合法的，首先可以将 $p$ 去掉，那么就要求连出来的边没有环，也就是不存在 $i\lt j,s_i=1,s_j=0,q_i\gt q_j$。从确定 $q$ 算 $s$ 的角度已经尝试不好做，考虑确定 $s$ 算 $q$ 方案数。这相当于对于前缀 $s_i=1$ 的最大 $q_i$，$s_j=0$ 时要 $q_j\gt q_i$。用延迟放置的思想，设 $f_{i,j,k}$ 表示，已经考虑了前 $i$ 个数的 $s,q$ 放置，当前最大 $q_i$ 的为 $j$，有 $k$ 个 $s_i=0$ 的大于 $j$ 还没有放。通过这个状态我们同样可以计算出 $\leq j$ 的有多少个数，转移：如果 $s_i=0$ 时，可以放大一点。 $s_i=1$ 时，如果往下放，那么一个组合数；往上放，那么枚举放到哪里，以及放了多少个数在中间，复杂度 $O(n^5)$？其实可以从 $j$ 往上每走一步，决定一下填不填，$k$ 中的谁来填，这样就好了，这样就是 $O(n^3)$ 了！ www 居然自己做出来了。 QOJ1844 环是好做的。但是不好消环，因为可能出现某个点是奇数。可以先不断操作，没有奇点时一定没有割边，此时就能用这个方法剥环了。 QOJ1854 必要是 $\gcd(p,q)=1$。玩一下 $p=2,q=1$。好像都是模一个数等于某两个数。 “归纳”一下就是，模 $p+q$ 等于 $0/1$ 的时候合法，否则不行，当然要求 $\gcd(p,q)=1$。虽然炸了，但是至少说明我们可以凑出起点为 0 终点为 p+q 的路径，而且首尾都是。 o，原来是 p=1,q=1 没有判。必要性证明的话，每次 $x$ 只能到达 $x+p,x-q$，按照 $\bmod p+q$ 分类每次走一步 $p$。然后按照同余类分的话可以是 $v_{0,1,...,p+q-1}$，那么分类讨论就发现其绝对值之差不能过大。然后为什么我们能构造出来呢？对于一个 $n=p+q$ 内的边形成是一个环。就是在 $\gcd(step,n)=1$ 时一直走 $step$ 一定会遍历整个环。根据裴蜀定理一定走得到每个点对吧，而且不会提前走。 QOJ1874 前几天做过一个更难点的，感觉这个不会很难吧。我错了，先咕咕了。 QOJ1875 应该会做啊，主要是突然搞忘了 999999 能整除的性质了。然后数位 dp 一下即可。具体的，从高到低决定有哪些位，然后计算方案数。决定数量的话就是有若干个长度为 $k$ 的和一个不超过 $k$ 的，要他们的和和某个 $r$ 模 $99999$ 同余。直接枚举和 $BM+r$ ，然后数位 dp 一下。 QOJ1876 QOJ1884 CF38H 判定一个方案是否合法，拿金牌的取最长路，拿铜牌的取最短路，中间判断有没有即可。枚举最长路中最短的，最短路中最长的，剩下的话一个人可以分给三个区域中的一个，直接 dp 做到 $O(n^5)$。 CF1696H 选择绝对值最大的 $k$ 个，看情况调整一下正负。所以先排序，随便讨论一下应该不难。 UOJ390 wc 我不会 minmax 容斥了！！！ $\max(S)=\sum (-1)^{|T|+1}\min(T)$。最大的元素会被算 1 次，而其他元素取或者不取最大值系数相反得证。所以枚举一个包含 $i$ 的 $S$，看一下最小值等于 $i$ 的方案数。也就是计算 $i$ 第一个被干死的概率。然后就是先插入 $a_i$ 个小球，然后在前面依次插入 $\lt a_j$ 个小球。枚举 $i$，$f_{i,j,k}$ 表示前 $i$ 个数，$s$ 大小为 $j$，已经有 $k$ 个小球了，直接算 $O(n^6)$。主要是，$j,k$ 是必要的，且合并代价比较大。不过这个顺序是不是可以撤销？直接从里面撤销 $i$ 的影响，然后再插入是不是就可以了，复杂度的话，插入撤销都是 $O(n^4)$，做 $O(n)$ 次就是 $O(n^5)$。 QOJ8147 jsy 大佬神秘观察力，发现这个序列是一个栈，所以问题变成了每次加一个数，或者删掉一个数。或者令 $b_i=\frac{|a_i+1|}{2}$，发现可以构成双射。 oooj 某神秘题目给定长度为 $n$ 的序列 $a$，共 $q$ 次询问，每次给定 $l_j,r_j$，询问，有多少个长度为 $n$ 的序列 $b$，满足：对于所有 $1\leq i \leq n$ 有 $b_i\in [0,a_i]$，且 $b_1\oplus b_2 \oplus ... \oplus b_n \in [l_j,r_j]$，答案对 998244353 取模。发现当固定了随意位小于等于某个值时，高位已经确定，因此可以统计每一个位的信息后直接算即可。 QOJ14816 Sequence Covering Problems：差分序列，正的 $l$ 位置用 $b_l$，负的 $r$ 用 $c_{r-1}$。 Many Sequence Covering Problems： $b_i$ 增大会令 $P$ 增加 $[z_l\geq 0]z_l$，$c_i$ 增大会令 $P$ 增加 $-[z_{r+1}\leq 0]z_{r+1}$，而如果能加则会一直加，所以其限制等价于 $z_l\leq d_l$，$z_{r+1}\geq -e_{r}$，而对应代价就是对应 $a,b$ 之和。现在最地狱的事情来了，$A,B,C,D,E$ 都可以决定区间。不过 $D,E$ 看起来比较小丑，实际上决定 $A$ 后其只是乘上一个数而已，而对于 $B,C$ 就是给差分序列一个加权。暴力 $f_{i,j}$ 表示考虑了 $i$ 个，上一个为 $j$，枚举下一个数的话复杂度有点炸裂。考虑同时所有 $j$ 的贡献。 $j= k$ 直接做。 $j\lt k$，此时 $z_{i+1}\gt 0$，那么 $c$ 无贡献，$e$ 直接化为定系数，$b$ 的贡献是 $(k-j)b$ 可以拆开进行贡献，$d$ 就是 $\max(d-(k-j)+1,0)$，直接当做 $d-k+j$ 的系数。分析完贡献后，首先统计方案数，这个方案数就和 $b,c$ 无关了，而这个乘法可以拆开贡献。放这种题和溢位？ QOJ14817 分成若干组，使得同组内最小值最大。首先考虑单次询问，可以二分 $D$。这个贪心似乎并没有那么简单，首先找到第一个数的可能后继中最靠前的。如果这个位置超过了 $\frac{r-l+1}{k}+2$ 就炸了，因为剩下的会出现问题。然后继续看下一个数匹配。然后考虑这样一个问题 $-----,-----,-$ 这样情况下前两个先匹配了不一定很好，所以需要加上更多决策。记一些可接点集合 $p_1,...,,p_k$，每次扫一个点，首先将可接点加进去，然后在剩下的这些可接点中，选择剩下长度最长的接上来。因为两种留下来的长度分别是 $l_1,l_2$ 和 $l_1-1,l_2+1$，感觉上来说越靠中越好。不过这个似乎很难优化，主要是信息太多了，而且不能划层。不过根据刚刚的想法，我们可以尝试将这些序列划分成若干极长链，然后长的都可以了短的一定也可以。而且刚刚的决策是不是也行了？直接划分是 $2,1,1$，划分的策略还是需要调整。 --- 最优策略一定是模 $k$ 同余的一组，问题转化为 $k=1$。然后我们取的位置是 $\max(l_i,x_{i-1}+D)\leq r_i$，可以拆开变成对于任意 $i\lt j,l_i+(j-i)D\leq r_j

采用分治结构线段树，分成若干区间，每个区间内部的 D 是能求解的。而对于段之间，可以把这些询问一起二分，然后在上面一起做双指针，然后逐一判断即可。

复杂度是 O(\log V(n\log n+q\log n))。

第一个做法还是利用了 3\log n \rightarrow 2\log 方法。

我是傻逼，题目给了 D。

而且凸包切凸包只有部分单调性，就是有两段单调，就是凸包之间的切线两段单调性不同。

QOJ14804

吓人题目。

好吧其实是高妙题目。

首先对一条链进行考虑，我们最优的方法一定是每次选择最浅的点，往上面走。直接做的话可以每次选择最浅的，然后往上走，要么走到 1 要么更劣考虑下一个。

这暗示了这些树之间的局面有某种全序关系，因此我们认为有全序关系，那么我们去考虑如何比较两个局面的优劣。

不妨这样想，对于 A,B 两个局面，我们可以令有无限个 A 和无限个 B，那么因为他们之间有全序关系，所以我最优策略一定是不断走某个决策，可能中途劣了，但是一定又会去走下一个 A。这个东西相当于走到 1 为止，或者重开。

因此我们现在要求对于一个点，可以重开的情况下的期望最优步数。似乎并不好求（迭代也不行），不过最劣的点是可以求的，也就是满足无论走到谁都比重开优的点，也就是到 1 期望步数最大的点。

所以我们可以考虑从大到小求这个值，而且还是因为全序关系，前面已经判定更劣的点我们是不会走的，而当前我们要求解的点集之间还没有确定。

不过无论怎么说，我们只钦定这些点，然后取期望步数最大的那个点，还是能求解出最劣的点，反正其他点在值上一定比它好。

（这个启示了我们一类方法，在遇见 \max E 的时候，可以通过求解最劣点来做，也许我们策略考虑不周全，但是把当前能做的策略发现它已经最劣的时候，就可以把它踢掉。可以类比 dijkstra 的思想。或者像上周我做的那个胡策一样，都是找到某个解后往前推）

然后我们求解出每个点的权后，我们的策略就已经确定了，但是还是不好 dp，怎么办？

首先我们将这些路径独立出来，假设我们已经确定了每个点是走怎样的路径，那么最后到达 1 的一定是最大值最小的那个。然后进一步确定，我们的路径一定形如，一个点走到最大值，然后其他点都越过了这个最大值，不过后面再也没有动，然后这个点不断走走到了 1。

很高妙的思想，避免了每时每刻都去取最优的，直接从最大点开始分析。而且很多比较权值走路也能这样分析（我可能以前做过）每次走权值最小的，不如直接枚举他们的最终的值。不过这个还要复杂一点，走的路甚至不是单调的。

剩下的应该是统计基本功了。

QOJ14807

可以不用管水漏光的情况，如果被算成负数了还不如给别人合并了。只需要判断全部合起来都要漏光的情况即可。

合并 \set{v1,v2},\set{l1,l2} 优，当且仅当 v1\leq tl1，不过这个并不是操作了就更优。可以放缩成选择两个 v,tl 抵消，反正最后我们也只会选择最优的那一种。

不过选择最大的 l 和最小的 v 抵消一定在最优解中，将这个两个抵消后再进一步抉择。合并后的 l/v 序列并没有，将抵消合并的操作弄得好看一点应该是能维护的。

好像不需要怎么弄，直接排序做就行，如果删到一样的了就当这个数合并了就行。

QOJ14808

对着名字出的题应该不会多难。

首先来找到中间的两个串的 [L,R]，可以先找到 [l,R] 的border 数量，然后从 l 开始扩展就能扩展到所有 [L,R]。

然后枚举两侧的 [R,L]，统计其 ”border“。

不过没必要，直接找到一个子串的所有出现位置，对应贡献一下即可。

QOJ14810

有点神秘啊。

如果一个点本来是割点，不过割掉出来的第一个连通块如果是指向了 u 的父亲，那么暂时还看不出来；但是如果后面的点指向了 u，那么算 low u 的时候就会算错从而导致看不出来。

充要条件就是每个点双至少和它有两个边，且其本身是割点。

OIWIKI 树状数组。

因为要学习二分所以重修一下。

相当于构造一颗树，i 的父亲是 i+lowbit(i)。

然后我直接狂暴膜拜 11d10xy and rizynvu 顺手把这个方法教给我了。

QOJ8049

暴力的话就是直接 f_{i,j,k} 表示考虑前 i 个 x 和前 j 个 y，和为 k 的方案数，转移枚举一个数 O(n^5)。

这是一个求和为 0 的过程，而且 x,y 谁走下一步我们是能决定的，我们钦定在和为 \leq 0 时走 x，和 \gt 0 时走 y。

这样我们就将 dp 范围压缩到了 O(n) 范围内，复杂度 O(n^4)。然后转移用前缀和优化即可做到 O(n^3)。

CF2085F2

选择 k 个互不相同的数，将其移动到一起的最优步数一定是前半部分往右，后半部分往左。

现在需要尽量优秀的选择，那么对于左半部分，一定是能往右就往右。

不妨枚举中心位置，先全部钦定为左边，然后调整一部分去右边即可，线段树维护即可。

CF2084F

首先判断两个的可达性，但是第一个操作也太逆天了，直接把 b_r 这个数抹掉了，感觉是诈骗。

而循环移位是不是太强了？直接移动就能做到 n 步啊？

ooo 原来是同时做啊，我无语了。

那么限制等价于 r 是最小值，我们每次只能将一个数往前面交换，且满足前面的数更大。

不妨看作一个排列要移成某个 [1,...,n]，且每个数带一个权。

那么就是不存在 i\lt j,p_i\gt p_j,q_i\gt q_j。

不过这个题的 (p,q) 是绑定的，那么我们就是要找一种方式使得不存在这样的双逆序对。

首先跑一个拓扑序出来，那么就是顺取数，那先把后继确定的时间短的取掉一定是对的。

at_agc059_d

怎么刻画这个出现的数的数量呢？

$A_i=A_{i+1}-1$ 就要求 $B_{i+k}$ 没有出现过，然后添加一个出现过的数。 $A_{i}=A_{i+1}$，就是要求 $B_{i}$ 和 $B_{i+k}$ 在 $[i+1,i+k-1]$ 中的出现情况一致，那么直接令 $B_{i}=B_{i+k}$ 即可。归纳上面三种情况，发现就是要求 $i+k$ 是否在 $[i+1,i+k-1]$ 出现，同时给 $B_i$ 一个值。那么我们有对 $i$ 在 $[i-k,i)$ 和 $(i,i+k]$ 中的出现情况做要求。可以转化为匹配问题，这样一定能覆盖最终答案。然后在最终答案的角度上考虑的话，只要 $B_i\neq k$ 的时候，如果说不钦定 $r_i=l_{i+k}=1$ 的有答案，那么加上这一对也合法，且可能将某一对反的搞成正的。否则只能钦定 $r_i=l_{i+k}=0$。 --- $l,r$ 的我知道，但是为什么这个东西是一个匹配啊？我们的主要疑惑是，为什么这个东西是一度的，为什么不能是，一个数匹配上两个。不过我们这样推，就是，最后反正也是找到一个数相等，然后另外一边同理。从最后的角度来看，我们可以始终选择相邻的进行匹配，使得我们的模型可以成功刻画。 QOJ10404 $l_i+l_j\leq s$，$r_i+r_j\geq s$ 就一定能选 $(i,j)$。怪糟糟的，和上次那个逆天贪心题可能差不多。构造一个扫描顺序使得能匹配的中有优劣即可。 QOJ14943 首先可以算出 $3^7$ 种情况下，可以表示的数字个数。不太懂 0 和其他数的区别啊。原来是空的意思啊，不重要。 QOJ14944 有点意思的题目。太奇怪了。我们可以这样做：如果说有任务中的点，那么就打，否则就打出下一次出现最远的位置。此时这个位置至少打了 $n$ 次，我们在这个策略出现前一定是能捏到这个牌的。在这样的策略下，我们发现只要取出了某个牌，那么它下一次出现的时候就不需要花费额外的次数，所以一定是最优秀的。对于一个排列以及任务列表，我们来计算其次数。所以求解的时候我们只关心第一次取出来的时间即可。 $f_i$ 表示将第 $i$ 张牌打出后的最小次数。那么对应的 $f_i=1+\max(f_{i-1},f_{j}+n)$。现在要考虑统计每种排列下这个的答案。实际上可以统计 $\leq k$ 的答案，然后转而对 $pos$ 进行限制，显然 $k$ 减少一则所有 $pos$ 减少一，因此有用的 $k$ 仅 $O(n)$ 个，至于锁定位置的话可以任取一个排列求 $k$，然后上下 $n$ 即可。 QOJ14949 同一方向进入，就是求 $v$ 两侧距离。不同方向进入，则存在分界线；如果分界线对应两侧过环，则求解 $[0,m-1]$ 最靠边距离，否则就是算相邻 $1$ 之间的距离最大值，同时要强制加入 $v$ 这个值。删除好做，直接回滚，如果加上 $v$，只要保证每一个块内询问个数不多，那么我们也可以将所有 $v$ 加入到分割点，到某单个 $v$ 的时候将其他的删掉即可。可以对询问进行排序。 QOJ14947 好吧不是我想象中的 young diagram。首先发现对应杨表的反对角线的格子数量相同。这也是充分的，因为操作可逆，我们令代表元为第一行最大，然后第二行最大（符合直觉）构造的话，考虑找到 $(1,\lambda_1)$ 这条线上，往下多延伸的距离最大值，操作过来，此时一定合法。递归构造。因此我们只需要证明在条件下 $\lambda_1$ 最大值相等即可，当然这是显然正确的，因为我们只需要找到斜对角线最靠外的一个移动过来即可。后面的统计太逆天了，反正理解就行。好吧还是写一下，最后的对角线和一定是先若干个 1，2，3，4，5，然后开始递减，这是因为每次都是从刚刚可以延伸的地方再延伸，不可能更多。进一步观察，每次如果“丢失”了一些延伸的位置，那么在对角线上体现出来就一定是，本来有 $a_i+2$ 个线，结果被搞出去 $2a_{i+1}$ 条线，中间就有 $a_{i}-a_{i+1}+1$ 条右线和下线。然后当做每次往中间插入下一层的线即可。 QOJ14819 本来不想做这个题的，但是似乎没有其他题做，那就做吧。如果没有 $3$ 的情况，就是每一个段可以收缩。如果有 $3$，那么对于中间的段，取的是一个子段的收缩，左边是前缀，右边是后缀。首先可以将序列倒转，此时长度递减，那么我们就求解出尽量靠前的 $3$ 位置，给后面留的位置就比较多了。对于钦定内部，首先 3 吃掉了第一段。如果颜色和第一段相同如果长度为 $len_1$，那么如果说下下段满足，就从下一段开始继续钦定；否则不合法。如果说 $\lt len_1$，那么第一段钦定完了。如果颜色不同，那么从第二段开始即可。如果说钦定的长度使得还剩下一些位置（或者根本没有钦定），可能可以钦定 $3$。归纳出来就是 $f_{i,0/1}$ 表示第一个位置是否被吃掉。对于最后一段，可以这样处理，最后取的是一个后缀，不过这个是简单的。对于第一段，如果钦定的是 0/len-1 都可以为 3，否则只能继续下去。完了我寄了，虽然我们可以钦定 0 的长度，但是那是建立在上一个段没有补满的情况下的。 P11831 这个题实际上要教会我们的是换维。 CF2157H $n\leq 26$ 都能搜。而且更大的情况下，对于 $n-m\leq 10$ 的部分，$g_{n-m}$ 也不会变，所以不需要刻画也知道是从 $n$ 小的地方直接加上来的。问题就在于，$n$ 大，$m$ 小的时候，我们需要构造一种 $m$ 不加，$n$ 加的方法，而且对不同方案最后构造的也要不同。插入一个数整体加，还不如考虑缩环，也就是交换两个不在同一个环内的数，且其上升下降序列仍然满足。其实这个也挺难的，不过可以首先同时减，一直减到 $m=1$ 的情况。 --- 打表大胜利，但是还是不会构造 $(n,m)\rightarrow (n+1,m)$，实际上关注特殊点（最后一个）即可。至于为什么 $g_{n-m}$ 不变，我们已经拥有了 $(n,m)\rightarrow(n+1,m)$ 的映射，那么再加上一个 $(n,m)$ 到 $(n-1,m)$ 的映射即可，发现 $m\gt n/2+eps$ 的时候，一定形如一段前缀自环，那么反着来即可。 qoj2550 qoj2548 qoj2214 qoj2210 CF2118F 从高到低考虑相对顺序，可以刻画成一颗树（虽然说有一些关系没考虑完，但是在树的判断上没有问题） qoj2554 构造支配对，https://www.luogu.com.cn/article/s5cutdhn。 ~~我还可以出一个四边形不等式的题~~。 qoj2563 差不多无限之环，不过这个题的考虑手段比较高妙。就是对横竖单独考虑，对相邻两个限制，看他们的奇偶性是否正确，如果正确就没有限制，否则就要求中间一个格子不选。进一步处理同时选的情况，也就是二分图匹配。 qoj2570 转最小割，再转最多选多少不交最长上升子序列，然后贪心即可。 qoj2601 被诈骗了，分析到最后只剩下一个 $a_1a_2...a_q$，其实对于颜色 $i$ 确定数量为 $c_i$ 时，必须要求某个 $c_i=q$ 组合数才不是 $q$ 的倍数。 qoj2605 先保证有 $KN$ 条异色边，然后再对不超过 $K$ 条的点删掉，这样调整后 $E\geq KN$，且一定不会删空。 $KN$ 条异色边可以看到题目的 $M$ 上，只要保证有一半的边是即可，那么也可以对点进行调整。