AGC030D Inversion Sum简单题。难点是容易想歪。 求逆序对数，其实就是求有多少种方案使得对 $i < j$ 满足 $A_i > A_j$ 。 考虑直接设一个矩阵 $G$ ，其中 $G[i][j]$ 表示有多少种使用操作的方案使得 $A_i > A_j$ 。 每次操作 $(x,y)$ 其实就是将 $G[x],G[y]$ 两行以及 $G[.][x],G[.][y]$ 两列加起来放回去，并且将其他位置的值乘二，再特判一下 $G[x][y]$ 和 $G[y][x]$ ...

AGC020E Encoding Subsets申必题，搞了点奇怪做法跑过去了。 其实要做的就是对于每个编码方案，求出每个编码方案最终二的 $1$ 的个数次幂。 现在假设我有一种编码策略，很显然如果所有数都是 $0$ 这种策略一定是合法的，但是该怎么求出这种策略下最多的 $1$ 的个数？ 可以发现对于某个数假设它被嵌套编码了若干层，这些层用来循环的长度分别为 $A_1,A_2,\ldots,A_k$ ，那么可以发现它是否合法只和这些长度有关，和这些编码段在原序列的位置无关。具体来说只需要关心它的 ...

AGC057C Increment or XorFirst 3300! 感觉是个不算太难的 1+1 问题。 首先考察最低位，可以发现加法还是异或对最低位的影响是等价的，那么最低位必须初始就是 $0101\ldots$ 或 $1010\ldots$ ，两者可以通过一次异或互相转换，否则一定无解。 那么可以发现，对于每个数如果我们都不考虑最低位，那么奇数位置和偶数位置的数就分别变成了字问题。因为我们总是可以通过异或最低位来控制让奇数位置还是偶数位置的数加一，而异或的唯一区别就是两个部分必须同时做异或 ...

AGC058D Yet Another ABC String简单计数。 考虑容斥，可以发现钦定若干位置违反限制后这些钦定的长为三的段之间是可以重叠的。因此我们考虑每个极长的连续的被钦定的段，假设长度是 $l$ ，考虑计算它的容斥系数。 可以发现对于这一段，它内部两个相邻被钦定的点之间要么在串中相邻，要么相隔一个空位，不然无法满足整个段是连续被钦定的段。因此类似斐波那契容斥系数的递推可以写作 f_l = -f_{l - 1} - f_{l - 2}其中 $f_3 = -1,f_4 = 1$ ， ...

AGC045C Range Set简单题。 显然初始全零和全一没有区别，可以全部进行一次覆盖，所以如果 $A>B$ 可以交换 $A,B$ 。 首先可以发现，如果打算在结尾放 $B$ 个 $1$ ，那么前面任意放的状态都可以被构造出来。因为总是可以用 $A$ 个 $0$ 去覆盖掉一部分的 $1$ 。 接着考虑，会发现如果在序列中任意存在一段连续 $B$ 个 $1$ ，那么它的左右的构造是互不影响的，都可以用一样的方法造出来。所以只要序列中存在一段连续 $B$ 个 $1$ 就一定可以构造出来。 ...

AGC043D Merge Triplets比这个 C 简单太多了。 我们考虑最终的排列中的一个位置 $P_i$ ，如果有 $P_i < P_{i-1}$ ，那么一定是拿完 $P_{i-1}$ 后立即拿 $P_i$ ，且 $P_{i}$ 一定出现在 $P_{i-1}$ 的序列中的下方。 我们考虑这个序列的前缀最大值序列，很显然两个前缀最大值中间不能间隔超过 $2$ ，因为中间间隔的数必须是选择了上一个数后立即在它对应序列下方选择的。 考虑什么样的序列能够被构造出来。我们假设有 $a_k$ ...

AGC043C Giant Graph神仙题，虽然用垃圾做法过掉了，但是 sol 太神仙了。 Editorial 做法：显然我们会贪心选点，因此对于点 $(x_i,y_j,z_k)$ ，设它是否会被选为状态 $dp[i][j][k]$ ，很显然这只有在 Giant Graph 中与它直接相连的点有关，即若 $dp[a][b][c]$ 中有 $1$ （这里 $a,b,c$ 中有一个是在图中与 $i/j/k$ 有边的点，另外两个就是 $i/j/k$ ），则 $dp[i][j][k] = 0$ ，否则 ...

AGC044C Strange Dance比较简单的一个题。我上来就直接考虑分块了，观察一下可以发现任意进行操作 $\bmod 3$ 之后的序列是三个数不断重复出现，而同理 $\mod 3^k$ 也一样。所以考虑把最后 $3^{n/2}$ 位单独考虑，$3^{\frac {3n}2}$ 是个可以通过的复杂度！ 同时可以发现，在序列中低 $n/2$ 位是一个固定数的高位一定也形成了一个 $3^{n/2}$ 长的序列。我们可以维护这个序列，最后把两部分拼起来就行了。 对每次交换操作，对低 $n/2$ ...

AGC051D C4想了两小时 $O(n)$ 才发现 $O(n\log n)$ 可过。做法非常垃圾。 经过边的次数固定看起来非常复杂，经过点的次数会好考虑很多，假设四个点的次数分别是 $a,b,c,d$ ，那么答案其实就是 $\binom{a+c-1}{a-1} \binom{b+d}{b}$ ，因为总是在 $(a,c),(b,d)$ 之间切换。 如果边的次数给定了，那么其实点的次数是确定的，每个点经过次数分别是 $\frac{a+b}{2},\frac{b+c}2,\frac{c+d} 2,\ ...

AGC051C Flipper可以注意到，我们对 $x$ 和 $x+1$ 两个位置作用 flipper 后，可以对 $(x,y),(x,y+1),(x+3,y),(x+3,y+1)$ 进行翻转，可以称此为一次基本操作。同时，我们只需要不断进行基本操作，可以对任何 $x$ 轴长度为 $3$ 的倍数的矩形的四个端点进行操作。 这提示我们把 $x$ 坐标按模 $3$ 分类，得到三个坐标系。在这三个坐标系中，基本操作可以对任何一个矩形的四个端点进行操作。事实上，如果需要操作的点在每个 $x,y$ 坐标上 ...

AGC047E Product Simulation简单构造，不过做着挺有趣的。 首先可以问 $0 < A$ 造 $1$ ，就算是 $0$ 也没关系，是 $0$ 的话之后得到的所有数都是 $0$ 了。 然后可以造出 $2^0 \sim 2^{29}$ ，放到固定的一些位置中。 然后我们考虑造出对 $k = 0\sim 29$ ，判断 $B$ 在这一位是否有值。从高到低考虑每一位，用一个位置 $x$ 来维护 $B$ 之前的位的和。对于当前位 $t$ ，我们把 $x$ 先加上 $2^t$ ，然 ...

AGC047D Twin Binary Trees非常水的红题，基本上可以说是一眼题！ 对每个第二棵树的叶子，考虑维护根到这个叶子的树形结构，有点像动态开点线段树。 然后对第一棵树的每个叶子，把它和与它连边的点在连边的点的树形结构中记录这两个点到根路径上所有点的权值积。 接下来在第一棵树上做“线段树合并”，具体来讲是之前维护的树形结构的合并，由于是二叉树所以很类似于线段树合并。合并的时候相当于把左儿子和右儿子对应的所有点连边的点在第二棵树的结构拿出来合并。这个时候第一棵树的 LCA 是确定的，第 ...

AGC046D Secret Passage好像我做法比题解做法麻烦。。 我们考虑最终得到的串肯定会有一个子序列和原串结尾的一段子段相同，这些位置是保持不动的，而需要从 $S$ 前面的位置往这些位置插入字符。 现在就有了一个想法：能不能枚举一段原串的后缀和操作次数（通过操作次数可以确定串长），统计可以得到多少种不同的字符串？但是事实上可能会出现重复统计的情况，即一个串可能有多个后缀与之对应。 于是我们可以考虑在最短的、可以得到这个串的后缀处计算它。具体而言，当确定了操作次数和选择不动的后缀时，前 ...

AGC059C Guessing Permutation for as Long as Possible猜结论AC.jpg 我们考虑对两个点 $i,j$ ，如果 $P_i < P_j$ 就连 $i \to j$ ，否则连 $j \to i$ ，边权设置为 $(i,j)$ 出现的时间。 可以发现，对于一个三元组 $(a,b,c)$ ，假设相关的三个二元组出现顺序是 $(a,b),(a,c),(b,c)$ ，那么 $a$ 一定同时比 $b,c$ 小或比它们大。 我们可以猜测所有这样的限制就是合 ...

AGC055C Weird LIS显然，删除一个数后剩下的数的 LIS 长度和原来的差至多为 $1$ ，因此 $A$ 序列一定是由 $x-1$ 和 $x$ 构成的。 我们可以考虑对于任意一个由 $x-1$ 和 $x$ 组成的长为 $n$ 的序列，在 $x$ 取哪些数时可作为合法的 $A$ 序列。很显然，$x-1$ 的个数不超过 $x$ ，因为它们都在 LIS 上，LIS 的长度就是 $x$ 。现在我们考虑 $x$ 最大可以取多少。 我们考虑被 $x-1$ 截开的数组，假设剩下若干段，段长为 $l ...

AGC053C Random Card Game昨晚十点过开题，睡觉时躺床上脑子里全是这个题，两三点的时候想出来了。XD 由于 $2n$ 无论与什么数一起选，均能删掉选择的数，最后留下的一定是 $2n$ 所在的牌组。只有当一个牌组被清空时才会结束，所以最少的操作次数其实就是 $n$ 加上另一个牌组最少需要被删除的数的个数。 设 $2n$ 所在的数组为数组 $B$ ，另一个数组为 $A$ ，仔细分析可以发现结论： 设对 $A$ 数组中从上到下第 $i(1 \le i \le n)$ 个元素 $A ...

Ucup Stage 5 Osijek 部分题解A And Xor Tree我们把贡献拆开，设 $B_i$ 表示与 / 或 / 异或第 $i$ 位的值，那么： \sum_{\text{path}\ P} \left(\sum_{i=1}^b B_i \right)^2\\ \sum_{\text{path}\ P} \sum_{1 \le i,j \le b} B_iB_j\\ \sum_{1 \le i,j \le b} \sum_{\text{path}\ P} B_iB_j\\也就是说对 ...

2022 HDU 多校 2Link A Static Query on Tree把所有 $A,B,C$ 集合中的点拖出来建虚树，然后在虚树上统计每个子树中 $A,B$ 的点的个数和到根的链上 $C$ 的个数即可。 复杂度 $O((\sum |A|+|B|+|C|)\log n + n\log n)$ 。 Submission B C++ to Python去掉 std::make_tuple 即可。 Submission C Copy由于所有查询的位置和复制的区间都不超过 $n$ ，暴力复制即可 ...

2022 HDU 多校 1Link A String开始考虑 KMP 直接做发现相交和模 $k$ 两个条件都难以递推，所求式子也看不出除了直接求 $F$ 外的处理手段。 后来考虑 Z 算法，如果能够求出 Z 数组，即每个后缀和开头的 LCP ，就一定确定了交的起点。 而且，当交的起点固定，每当 border 长度加一，交的大小一定正好增加 $1$ 。同时，border 长度的上限其实就是 Z 数组的值。 因此相当于给定了一个区间，给里面的元素从某个元素开始每隔 $k$ 加一。直接前缀和处理即可。 ...

参考：http://www.algonotes.com/en/counting-matchings/ 和四川省选 D 官方题解。 下午研究 FKT Algorithm 的时候发现了这篇博客，弄明白后觉得非常巧妙，而且实现极为容易！ 仍然有一些只会感性理解不会严格证明的结论… 题目描述给定一个 $n \times m$ 的棋盘，求有多少种在棋盘上放置 $1 \times 2$ 的多米诺骨牌使棋盘密铺的方法。同时，对于每个位置 $(i,j)$ ，分别给出在 $(i,j)\to (i,j+1)$ 和 ...

A [CTSC2010]星际旅行我们考虑每次旅行收益一样，提示我们这题很可能可以贪心。然后考虑每个点有 $H_i \ge deg_i$ ，可以发现这正好是从 $1$ 出发遍历所有点然后回到 $1$ 的代价，于是我们先考虑终点在 $1$ ，直接把这个代价减掉，得到新的 $H_i$ 。此时能够增加答案的方法就是选择相邻的两个点把他们的 $H$ 同时减少 $1$ ，然后路径上就是进行一次左右横跳，会让答案增加 $2$ 。 这个过程显然是可以贪心做的（因为一个点）把 $H$ 留着匹配上面的收益和往下匹 ...

A 大佬的难题首先这题本身是一个裸的三维数点，直接做复杂度 $O(n\log^2 n)$ ，虽然各种卡常导致看起来随机数据是可以进 2.5 的，但是终测性能太差还是卡掉了！ 我们考虑一个容斥。我们考虑对三个序列两两求一次二维偏序问题，这个问题复杂度显然是 $O(n\log n)$ 的。然后考虑对于一对 $i,j$ ，设满足偏序关系的维度数是 $k$ 。如果 $k = 0,k = 3$ ，它的贡献显然都是 $3$ ，也就是三次求二维偏序都把它算进去了。如果 $k = 1,k = 2$ ，那么它的贡 ...

A 哈密顿回路被阴间到了，给了一个 $G_{i,j} < G_{i,k} + G_{k,j}$ 的没用条件看了很久发现确实没用，最后暴搜一下就跑过去了。。 我们折半搜索一下，具体来说，对于 $n = 14$ ，我们搜出 $1$ 出发的所有点的个数为 $7$ 的路径，再搜出所有 $1$ 出发点的个数为 $8$ 的路径，然后拼起来即可。复杂度大概是一个和 $\binom{13}{6}$ 有关的东西。 写完后试了试，发现跑的非常慢。这里写一下我的优化方法： 由于最后只需要合并一次，不需要开 s ...

A 圆圈游戏一道优秀的扫描线题。 我们考虑没有相交和包含，提示我们可以通过包含的关系建立出一棵树，一个点的儿子就是它极大的包含的圆。 如果能够建立出这个树，那么我们可以在树上做一个非常 trival 的 $dp$ 解决问题。转移就是枚举选不选这个点。 我们考虑怎么建立这个树。考虑从左往右进行扫描，到达一个圆的左端点的时候就加入这个圆，到达右端点的时候删掉他。我们考虑在删掉一个圆的时候找出它的父亲。 如果这个圆右端点向上引一条切线，考虑讨论一下这个切线碰到的第一段弧。如果这段弧是一个上圆弧，显然我 ...

A Training相当于是要求保留的非树边和尽量大。 我们考虑所有边 $(u,v)$ ，如果距离为奇数，显然这条边必删。 如果距离为偶数，那么加入后会存在一个奇环。但是如果有两个相交的奇环，那么它们拼起来的大环的大小就是两个环长度和减去共有的部分乘二，这是个偶环。 所以我们相当于需要加入若干个点对，使得两两路径之间无交。 事实上这题还在 CERC 中出现过一个无权值的版本，那个问题由于路径权值是 $1$ ，可以证明局部最优等价于全局最优，因此 $dp$ 更加容易，但在这里行不通。 由于每个点度 ...

6.11 模拟赛A Game我们考虑所有人的初始情况是一样的，所以可以逐一确定每个人的做任务情况。 所以有了一个朴素的想法，我们设 $dp[i][j]$ 表示前 $i$ 个人，一共已经做了 $j$ 个任务，这种情况下最小的天数是多少。不难发现，如果我们可以算出 $f(k-j,t)$ 表示一共 $k-j$ 的体力值，一共用 $t$ 天最多做多少任务的话，就可以直接 $O(nm^2)$ 解决问题。 这个东西看起来需要一个 $O(km^2)$ 的转移，但是事实上我们可以算出 $pd[i][j]$ 表示 ...

A 树考虑先化一下第一个式子，那么就是 \sum_{u\in A} d_u + \binom{|A|}{2} - \sum_{u \in A}\sum_{v \in A} [\text{u 是 v 祖先} ,w_u \le w_v] + \sum_{u\in B} \sum_{v \in B} [\text{u 是 v 祖先},w_u< w_v]然后我们不考虑 $\binom{|A|}{2}$ 。 可以猜测这个式子有特殊含义，所以把第一部分也加进这里面来统计，具体来说，我们把这个 $\sum_ ...

Topcoder 12505 CharacterBoard我们考虑如果能够枚举长度，那么每个字符对应回原串的位置就是固定的了，这样我们就可以直接 $26$ 的剩下字符个数次方得到答案。 但是事实上字符串的长度可能到达 $10^9$ ，这么考虑肯定是不行的。但是仔细想一想会发现，对于多数长度，你的 $n \times m \le 100$ 个字符根本不会有冲突。而有冲突的长度，必然是某两个字符之间差距的约数。因此我们直接枚举每两个字符之间的差距，然后枚举这个差距的约数，然后单独计算这些长度即可。剩 ...

A 宝石开场看错题 1.5h ，一直以为不能拿连续 $k$ 个宝石，然后发现 15pts 都不会，直接导致 T3 暴力都没打。。 我们考虑找出第一个位置，使得这个位置的颜色在之前出现过了，那么如果想继续往后选择，就必须把这个位置丢掉。我们一直重复找这种位置的过程，知道找到了第 $k+1$ 个，此时我们就只会在前面的东西种选择 $k$ 个扔掉。具体来说，对于每个出现了大于等于 $2$ 次的颜色我们只会保留最大的。 由于 $k$ 很小，我们可以考虑暴力做上面那个过程。每次之需要找到后面第一个重复出现 ...

懒得卡空间了！ 我们考虑对于一段区间来说，在全局加 $x$ 后，长度为 $l$ 的段的最优答案是啥。不难发现是 $lx + b$ ，其中 $b$ 为长度为 $l$ 段的和的最大值。因此我们可以对每个 $l = 1\sim n$ ，求出一条直线，然后对这个直线求一个凸包就可以做询问在全局加 $x$ 的情况下的和了。 然后考虑区间询问怎么办。首先我们可以把区间询问拆成 $O(\log n)$ 个线段树节点。然后对每个节点，我们维护出最大的后缀和，最大的前缀和，最大的区间本身子段，以及区间的和。之需要 ...