CF730I
共有 \(n\) 个元素和 \(A,B\) 两个集合。每个元素在 \(A\) 集合和 \(B\) 集合的贡献分别为 \(a_i,b_i\) 。现将 \(n\) 个元素放入两个集合中，每个元素只能在一个集合中，\(A\) 集合要 \(p\) 个元素，\(B\) 集合要 \(s\) 个元素。最大化贡献和并输出方案。
\(2\le n\le 3\times 10^3\;\;p+s\le n\)
经典反悔贪心题目。我们假设先选上 \(a\) 最大的 \(p\) 个元素，然后我们做 \(s\) 次操作，每次选一个元素放入 \(B\) 中。我们可以直接从剩下的当中直接选 \(b\) 最大的，也可以考虑反悔，如果我们要将一个元素从 \(A\) 集合挪到 \(B\) 集合中，其贡献的变化为 \(b_i-a_i\) ，然后我们再选一个剩下的 \(a\) 最大的元素放入 \(A\) 集合中，我们比较一下两种选择的贡献大小即可。发现这样我们只需要维护三个大根堆，维护的值分别为 \(a_i,b_i,b_i-a_i\) 。至于输出方案，我们更新答案时同时记录每个元素的归属即可。时间复杂度为 \(O(n\log n)\) 。
ARC076F
数轴上从 \(1\) 到 \(m\) 有 \(m\) 个位置。现在有 \(n\) 个元素，每个元素要占一个位置，每个元素有 \(l_i,r_i\) ，表示它的位置 \(\le l_i\) 或 \(\ge r_i\) 。为了使这 \(n\) 个元素都占到位置，可能需要在左面或右面添加几个新位置，最小化添加的新位置数量。
\(n,m\le 2\times 10^5\;\;0\le l_i<r_i\le m+1\)
对于 \(l_i,r_i\) 这两个限制，我们有一个很朴素的想法，就是按照它们的 \(l\) 值作为第一关键字，\(r\) 值作为第二关键字，将它们从小到大排序。然后我们枚举看是否可以满足 \(l\) 的要求，如果出现了冲突，我们可以考虑反悔，删去之前选择的一个 \(l\) ，让它去满足 \(r\) 的要求，同时容易发现删去 \(r\) 值较小的那个更优，所以我们开一个小根堆维护 \(r\) 值，最终我们处理完了所有的 \(l\) ，得到所有要满足 \(\ge r\) 的元素序列。对于它们的处理，与 \(l\) 类似地做即可，不同的是此时起冲突了就只能添加新位置去满足要求了。时间复杂度为 \(O(n\log n)\) 。
CF1165E
给定两个长度为 \(n\) 的序列 \(a,b\) ，设 \(f_{l,r}=\sum_{l\le i\le r}a_i\times b_i\) 。现对 \(b\) 序列中的元素进行重排，使 \(\sum_{1\le l\le r\le n}f_{l,r}\) 的值最小。输出最小值对 \(998244353\) 取模后的结果。
\(n\le 2\times 10^5\;\;1\le a_i,b_i\le 10^6\)
我们先考虑排序不等式，若有两个升序排列的序列 \(a,b\) ，序列 \(c\) 为 \(b\) 的乱序排列，根据排序不等式有
\[\sum_{i=1}^{n}a_ib_{n-i+1}\le \sum_{i=1}^{n}a_ic_i\le \sum_{i=1}^{n}a_ib_i \]我们假设 \(c\) 为 \(b\) 重排后的序列。我们先考虑最后要求的那个式子，我们考虑对于每个 \(a_i\times c_i\) 对答案的贡献，发现当 \(1\le l\le i,i\le r\le n\) 的时候会产生贡献，所以对答案的总贡献为 \(a_i\times c_i\times i\times (n-i+1)\) ，然后考虑如何最大化答案，如果我们直接对 \(a\) 和 \(b\) 进行排序，那么 \(i\times (n-i+1)\) 的贡献是没有考虑进去的。所以我们让 \(a_i=a_i\times i\times (n-i+1)\) ，再对 \(a\) 从小到大排序，\(b\) 从大到小排序，这样就可以得到答案最小值了。时间复杂度为 \(O(n\log n)\) 。
CF1019A
有 \(n\) 个人和 \(m\) 个候选者，每个人有一个选举的人的编号 \(id\) 以及贿赂这个人去选其他任何候选者的代价 \(w\) 。现想要 \(1\) 号候选者的票数最多，问需要的最小代价。
\(n,m\le 3000\)
直接贪心发现比较难做，不如换一个思路。我们直接枚举 \(1\) 号候选者的最终票数，然后不断去调整其余候选者的票数。具体地，我们先按照代价对所有人从小到大排序。假设当前枚举到的最终票数为 \(x\) ，我们枚举所有人，看它原来选择的候选者的票数是否大于 \(x\) 从而进行调整。若枚举结束后 \(1\) 号候选者的票数仍然没到 \(x\) ，我们就直接贪心地从小到大选取剩下的人将票给 \(1\) 号候选者即可，最后不断更新答案。时间复杂度为 \(O(nm)\) 。
CF436E
有 \(n\) 个关卡，可以花 \(a_i\) 的代价得到一颗星，也可以花 \(b_i\) 的代价得到两颗星，也可以不玩这一关。问得到 \(m\) 颗星的最少代价。
\(n\le 3\times 10^5\;\;m\le 2n\;\;a_i<b_i\)
又是经典的反悔贪心。从 \(i\) 颗星变为 \(i+1\) 颗星共有四种情况：以 \(a_i\) 的代价直接得一颗星，以 \(b_i-a_i\) 的代价将之前的一颗星变为两颗星，以 \(b_i-a_j\) 的代价将关卡 \(i\) 从得一颗星变为不玩并得到关卡 \(j\) 的两颗星，以 \(-b_i+a_i+b_j\) 的代价将关卡 \(i\) 从得两颗星变为得一颗星并得到关卡 \(j\) 得两颗星。所以我们维护五个堆，分别为 \(a_i\) \(b_i-a_i\) \(b_i\) \(-a_i\) \(-b_i+a_i\) 即可。最后四种情况依次取最小值即可。时间复杂度为 \(O(n\log n)\) 。
AGC034C
给定长度为 \(n\) 的序列 \(b,l,r\) ，以及正整数 \(x\) ，求最小的 \(sum\) 使得存在非负整数序列 \(a,c\) 满足 \(\forall 1\le i\le n,a_i\le x,l_i\le c_i\le r_i\) ，\(\sum_{i=1}^{n}a_i=sum\) 且 \(\sum_{i=1}^{n}c_i(a_i-b_i)\ge 0\) 。
\(n\le 10^5\;\;b_i\le x\le 10^5\;\;1\le l_i\le r_i\le 10^5\)
我们考虑去二分答案 \(sum\) ，我们要让 \(\sum_{i=1}^{n}c_i(a_i-b_i)\) 的最大值 \(\ge 0\) ，假设我们已经得到了序列 \(a\) ，我们有显然的贪心策略：当 \(a_i>b_i,c_i=r_i\) ，当 \(a_i\le b_i,c_i=l_i\) 。我们考虑序列 \(a\) ，我们发现序列 \(a\) 只有一个位置可以取 \(0\) 和 \(x\) 以外的值，考虑证明：假设我们现在有两个位置 \(i,j\) 均没取 \(0\) 或 \(x\) ，
-
当 \(a_i>b_i\) 时，我们将 \(a_i+1\) ，\(a_j-1\) ，可以使答案增加 \(r_i-c_j\) ，显然不劣。
-
当 \(a_i\le b_i\) 时，我们将 \(a_i-1\) ，\(a_j+1\) ，可以使答案增加 \(c_j-l_i\) ，显然不劣。
综上，只需有一个位置去满足和为 \(sum\) 的限制即可。所以我们可以枚举那个不是 \(0\) 和 \(x\) 的位置，剩下直接贪心计算答案即可。用排序加前缀和进行优化，时间复杂度为 \(O(n\log n)\) 。
CF351E
给定一个长度为 \(n\) 的序列 \(a\) ，可以改变每个数的正负，求最小逆序对数。
\(n\le 2000\;\;|a_i|\le 10^5\)
我们不妨先把所有数取绝对值，容易发现这没有影响。我们先找到那个最大的数，容易发现，当它取正的时候，是最大的数，会和后面的数全部产生逆序对；当它取负的时候，是最小的数，会和前面的数全部产生逆序对。假设其位置为 \(pos\) ，那么贡献为 \(min(pos-1,n-pos)\) ，发现这与其他数无关。由于其贡献已经计算完毕，此时我们就可以把它删掉了。同理我们考虑剩下的数中的最大数，以同样的方式不断计算即可。事实上，由于之前删去的数是大于现在序列中的数，所以不会影响每个数左边和右边小于它的数字数量，所以简化之后就是求每个数左边和右边有多少个比它小的数，然后取 \(min\) 相加即可。直接暴力是 \(O(n^2)\) ，用权值线段树统计可以做到 \(O(n\log n)\) 。
CF1421E
给定一个长度为 \(n\) 的序列 \(a\) ，进行 \(n-1\) 操作，每次操作选择两个连续的数 \(a_i,a_{i+1}\) ，然后从序列中删掉这两个数，并将 \(-(a_i+a_{i+1})\) 插回到原位置。最大化剩下的唯一那个数。
\(n\le 2\times 10^5\)
考虑发掘一些性质。发现本质上就是给每个数确定正负号，我们不妨寻找正负号的规律。具体地，设当前序列中有 \(x\) 个负号，\(y\) 个正号，那么满足 \(2x+y\equiv 1\pmod{3}\) ，考虑归纳证明。
假设 \(n\) 满足性质， 那么对于得到 \(n+1\) ，第一种是直接合并一个新的数，此时它会将原来 \(n\) 个数的符号全取反，并再加入一个负号，为 \(2(y+1)+x\) ，再设 \(y=3k+1-2x\) ，则 \(2(y+1)+x=6k-3x+4\equiv 1\pmod{3}\) ；第二种是由两个满足性质的状态合并得到，此时它会把所有符号取反。不妨设一个是 \(2x_1+y_1\equiv1\pmod{3}\) ，另一个是 \(2x_2+y_2\equiv1 \pmod{3}\) ，设 \(y_1=3k_1+1-2x_1,y_2=3k_2+1-x_2\) ，那么有 \(2y_1+x_1+2y_2+x_2=6(k_1+k_2)-3(x_1+x_2)+4\equiv1\pmod{3}\) ，证毕。
同时还有一个小的细节，由于第一次操作一定会将两个连续的位置同时变为负号。此后无论怎么操作，这两个位置的符号肯定是一直相同的。所以还要保证存在两个位置的符号相同。发现满足这两个性质就可以表示一种操作序列了。
到这里我们就可以设计一个 \(dp\) 了，设 \(f_{i,0/1/2,0/1,0/1}\) 表示当前考虑前 \(i\) 个数，\(2x+y=x+i\equiv j\pmod{3}\) ，第 \(i\) 个数取正或负，是否存在两个位置的符号相同的最大值。转移直接枚举枚举余数和 \(a_i\) 的正负号进行转移即可。初始化为 \(f_{1,1,0,0}=a_1,f_{1,2,1,0}=-a_1\) ，答案为 \(max(f_{n,1,0,1},f_{n,1,1,1})\) 。时间复杂度 \(O(n)\) 。
AGC030E
给定两个长度为 \(n\) 的 \(01\) 串 \(s,t\) ，串的连续段长度不超过 \(2\) ，每次操作可以反转 \(s\) 的一个位置，要求操作后连续段长度仍不超过 \(2\) ，求使两个串相等的最小操作次数。
\(n\le 5000\)
我们在相邻的 \(0\) 和 \(1\) 之间画一条竖线，则两个串相等当且仅当两个串第一个位置相同且竖线位置相同（第一个位置相同是防止出现与目标串全部相反的情况）。对于反转操作，本质上就是移动了竖线的位置，并且要求移动前后相邻两条竖线的距离均小于等于 \(2\) 。
同时最左端和最右端也能提供或删除若干条竖线。那么我们直接枚举最左端提供或删除的竖线数，由于竖线对应相等，最右端提供或删除的竖线数也是知道的。此时我们将竖线一一对应上计算移动距离即可。同时为了保证满足第一个位置相同，最左端提供或删除的竖线数对奇偶性存在限制，因为提供或删除偶数个第一个位置不会改变，而奇数个会改变，所以直接判断 \(s\) 与 \(t\) 的第一个位置是否相同来确定奇偶性即可。时间复杂度为 \(O(n^2)\) 。
CF468C
设 \(f_x\) 表示 \(x\) 的数位和。给定模数 \(a\) ，构造一组 \(l,r\) 使得 \(\sum_{i=l}^{r}f_{i}\equiv 0\pmod{a}\) 。
\(1\le a\le 10^{18},1\le l\le r\le10^{200}\)
发现对于数字 \(x<10^{18}\) ，\(f_{x+10^{18}}=f_x+1\) 。那么我们考虑设 \(\sum_{i=0}^{10^{18}-1}f_i=x\) ，则 \(\sum_{i=1}^{10^{18}}=x+f_{10^{18}+0}-f_0=x+f_0+1-f_0=x+1\) 。依次类推，
\[\sum_{i=2}^{10^{18}+1}=x+1-f_1+f_{10^{18}+1}=x+1-f_1+f_1+1=x+2\\ \sum_{i=k}^{10^{18}+k-1}=x+k \]那么我们只需要找到 \(k= a-x\,mod\,a\) ，然后使 \(l=k,r=10^{18}+k-1\) 即可，那我们现在只需要计算 \(x\) 。
\[\begin{aligned} \sum_{i=0}^{10^{18}-1}f_i&=45\times 10^{17}+10\times \sum_{i=0}^{10^{17}-1}\\ &=45\times 10^{17}+10\times 45\times 10^{16}+10\times 10\times \sum_{i=0}^{10^{16}-1}\\ &=18\times 45\times 10^{17}\\ &=81\times 10^{81} \end{aligned} \]直接对 \(a\) 取模即可。
CF1404D
交互题。给定 \(1\) 到 \(2n\) 共 \(2n\) 个数，\(A\) 和 \(B\) 进行交互。\(A\) 要将这 \(2n\) 个数分成 \(n\) 个二元组，\(B\) 要从每个二元组中选择一个元素，如果和为 \(2n\) 的倍数则 \(B\) 胜，否则 \(A\) 胜。现在给定 \(n\) ，你需要选择成为 \(A\) 或 \(B\) ，交互库会自动选择另一个。你要取得胜利。
\(n\le 5\times 10^5\)
考虑构造，假如我们选择 \(A\) ，我们将所有的 \(i\) 和 \(i+n\) 分成一组。考虑这样分组后，无论怎么选，和一定为 \(kn+\sum_{i=1}^{n}i=kn+\frac{n(n+1)}{2}=n\times (k+\frac{n+1}{2})\) 。发现当 \(n\) 为偶数的时候，这个东西模 \(n\) 一定不为 \(0\) ，则模 \(2n\) 也一定不为 \(0\) ，所以 \(n\) 为偶数时直接选 \(A\) 这么分组即可。当 \(n\) 为奇数时，它模 \(n\) 等于 \(0\) ，此时我们可以尝试选择 \(B\) 来进行构造。对于它给定的 \(n\) 个二元组 \((x,y)\)，我们要满足 \(x\) 和 \(y\) 只能选一个，并且对于 \(1\le i\le n\) ， \(i\) 和 \(i+n\) 也只能选一个。我们可以直接将其进行连边，即 \(x\) 与 \(y\) ，\(i\) 和 \(i+n\) 均连一条双向边，然后对其进行黑白染色，这样所有白色或所有黑色就是一组满足要求的解。但前面我们发现它只是满足模 \(n\) 等于 \(0\) ，不一定满足模 \(2n\) 等于 \(0\) 。我们不妨假设一个模 \(2n\) 不等于 \(0\) ，即和可以写成 \((2k+1)n\) ，我们发现所有数的总和是 \(\sum_{i=1}^{2n}i=n(2n+1)\) ，我们此时可以惊奇地发现，\(n(2n+1)-n(2k+1)=2n(n-k)\) 满足模 \(2n\) 等于 \(0\) 了！所以这么做必有一组能满足模 \(2n\) 等于 \(0\) ，而我们只需最后判断一下，黑色的数和白色的数哪个模 \(2n\) 等于 \(0\) 即可。时间复杂度为 \(O(n)\) 。
CF949E
给定 \(n\) 个数，你要用最少的 \(2^x\) 或 \(-2^x\) \((x\ge 0)\)，使得能表示出所有的数。求方案。
\(n\le 10^5\;\;a_i\le10^5\)
考虑最优方案中，不会出现相同的数，\(2^x\) 和 \(-2^x\) 也不会同时出现。例如：选择 \(x\) 和 \(x\) 不如选择 \(x\) 和 \(2x\) 优，因为后者还能额外表示出 \(3x\) ；选择 \(-x\) 和 \(x\) 不如选择 \(2x,-x\) 优，因为后者还能额外表示出 \(2x\) 。至此，我们从低到高去考虑每一位，如果是奇数 ，那我们必须从 \(-1\) 和 \(1\) 之间选一个。我们考虑枚举选 \(1\) 还是 \(-1\) ，然后我们将奇数全部变成对应的偶数，选正则减，选负则加，然后把所有的数再除以二，然后递归处理下一位即可，最终比较数的多少来决定答案，注意每次还需要去重来节约时间。由于每次递归值域会除以二，所以时间复杂度为 \(O(n\log n)\) 。
AGC028B
给定一个长度为 \(n\) 的序列 \(a\) ，要将所有元素删除。删除元素 \(i\) 时，设包括 \(i\) 的极长未删除区间为 \([l,r]\) ，则代价为 \(\sum_{i=l}^{r}a_i\) 。求 \(n!\) 种删除顺序的代价和对 \(10^9+7\) 取模的结果。
\(n\le 10^5\)
考虑如果我们随机一个排列，它的期望代价乘上 \(n!\) 就是结果。我们考虑求期望代价，我们按照删除时间去建立一棵小根笛卡尔树，则 \(x\) 比 \(y\) 先删除当且仅当 \(x\) 是 \(y\) 的祖先。所以对于某个位置对答案的贡献，就是它的期望深度乘上 \(a\) 的值。即 \(ans=\sum_{i=1}^{n}h_ia_i\) 。我们现在考虑如何求出 \(h_i\) 。对于 \(i\) 前面的元素 \(x\) ，删除 \(x\) 时 \(i\) 能贡献的概率是 \(\frac{1}{i-x+1}\) ，即 \(x\) 是 \([x,i]\) 中第一个删除的，同理对于 \(i\) 后面的元素 \(x\) ，删除 \(x\) 时 \(i\) 能贡献的概率为 \(\frac{1}{x-i+1}\) ，即 \(x\) 是 \([i,x]\) 中第一个删除的。那么 \(i\) 的期望深度就是 \(\sum_{x=1}^{i-1}\frac{1}{i-x+1}+\sum_{x=i+1}^{n}\frac{1}{x-i+1}+1\) ，我们设 \(s_x=\sum_{i=1}^{x}\frac{1}{i}\) ，则 \(h_i=s_i-1+s_{n-i+1}-1+1=s_i+s_{n-i+1}-1\) 。线性递推预处理逆元可以做到时间复杂度为 \(O(n)\) 。
AGC006E
有一个三行 \(n\) 列的初始矩阵，第 \(i\) 行第 \(j\) 列的数为 \(3j+i-3\) 。每次操作可以选择一个 \(3\times 3\) 的子矩形并将其旋转 \(180\) 度。给出最终局面，问能否通过若干次操作将初始矩阵变为目标矩阵。
\(5\le n\le10^5\)
容易发现任意一列内的三个数不会改变，只会改变上下顺序，并且只会变成形如 \(1,2,3\) 和 \(3,2,1\) 这两种，我们先判掉目标序列的某一列不是这两种形式中的一种的情况。我们将每一列的值设定为这三个数中的最大值除以 \(3\) ，同时若这一列是正好颠倒的，我们将其设定为负值。那么初始序列就是 \(1,2,3,\cdots,n\) ，目标矩阵也被转化成了目标序列。我们考虑每次操作的影响，容易发现，对于 \(pos\) 到 \(pos+2\) 这连续三个位置， \(pos\) 和 \(pos+2\) 进行了交换，同时这三个位置上的数全部取反，如 \(1,2,3\) 会变成 \(-3,-2,-1\) 。那我们不妨找一些性质。
-
一是可以将 \(pos\) 和 \(pos+2\) 两个位置进行取反，其中 \(2\le pos\le n-3\) 。对于序列 \(1,2,3,4,5\) ，有过程：\(-3,-2,-1,4,5\) ，\(-3,-2,-5,-4,1\) ，\(5,2,3,-4,1\) ，\(5,2,-1,4,-3\) ，\(1,-2,-5,4,-3\) ，\(1,-2,3,-4,5\) 。我们将 \(2\) 和 \(4\) 进行了取反。
-
二是可以将四个相邻的数全变为相反数。对于序列 \(1,2,3,4,5\) ，有过程： \(-3,-2,-1,4\) ，\(-3,-4,1,2\) ，\(-1,4,3,2\) ，\(-1,-2,-3,-4\) 。
结合以上两个性质，我们发现可以将任意的 \(pos\) 和 \(pos+2\) 两个位置同时取反。那我们考虑奇数位和偶数位，只有这两位上的负数个数均为偶数时才可能有解。
我们现在解决了正负号的问题，我们再来考虑绝对值大小的问题。我们重新考虑操作，它可以交换两个位置上的值，也就是可以单独对奇数项和偶数项做冒泡排序，但由于取反的问题，奇数项每交换一次中间的偶数项就会取反一次，这两个奇数项会取反两次，同理偶数项每交换一次中间的奇数项也会取反一次，这两个偶数项会取反两次。所以对于排序完的序列，奇数项和偶数项的负数个数发生改变，并分别与偶数项和奇数项的交换次数的奇偶性有关，为奇数改变，为偶数不变。同时交换次数的奇偶性和逆序对的奇偶性相同，所以我们单独对于奇数位和偶数位都求一下逆序对数量，就分别得到了偶数位和奇数位负数个数变化的奇偶性。再结合上初始时偶数位和奇数位的负数数量，判断按绝对值排完序后奇数位和偶数位的负数个数是否均为偶数即可。时间复杂度为 \(O(n\log n)\) 。
CF1364E
交互题。给定 \(n\) ，交互库会生成一个长度为 \(n\) 的排列 \(p\) ，值域为 \([0,n-1]\) 。每次你可以向交互库询问两个位置 \(a,b\) ，交互库会返回 \(p_a|p_b\) 的值。你需要求出这个排列，要求询问次数 \(\le 4269\) 。
\(3\le n\le 2048\)
考虑当我们知道 \(0\) 的位置后就可以通过 \(n-1\) 次询问得到整个排列。所以我们考虑如何找到 \(0\) 的位置。假设我们已经知道 \(pos\) 位上的值 \(x\) ，我们可以不断查询 \(pos\) 位和别的位置 \(i\) ，若结果仍然为 \(x\) ，说明 \(p_i\) 的二进制位是 \(x\) 的真子集，此时我们将 \(pos\) 变成 \(i\) ，\(x\) 变成 \(p_i\) ，重复做下去，容易发现最终得到的 \(x\) 一定是 \(0\) ，即最终的 \(pos\) 一定对应排列中 \(0\) 的位置。现在我们只需要考虑如何求出一个位置上的值，这帮助我们在刚开始求 \(x\) 以及过程中求 \(p_i\) 。我们随机大约 \(20\) 个位置，不断查询这个位置和随机到的位置，并将得到的结果全部与起来，容易发现将某个位算错的概率仅为 \(2^{-20}\) ，答案算错的概率会很低，可以忽略不计。我们现在来算一下询问次数，初始我们得到 \(x\) 会求一个位置上的数，每得到一个新的 \(pos\) 二进制 \(1\) 的个数至少会减少 \(1\) ，最多需要求 \(11\) 次某个位置上的数，总共需要求 \(12\) 次某个位置上的数，即询问 \(12\times 20=240\) 次，再加上 \(2n\) ，超出了限制。事实上我们只需要再刚开始将排列随机打乱，这样初始的 \(x\) 中 \(1\) 的个数就不会被卡满，每次得到的新的 \(x\) 减少的 \(1\) 的数量也不会被卡成 \(1\) ，就可以过了。
CF1227G
给定长度为 \(n\) 的序列，每一项都在 \(1\) 到 \(n\) 之间。需要进行最多 \(n+1\) 次操作使得所有数变成 \(0\) ，每次操作可以把一些位置上的数都减去 \(1\) ，并且每次操作选择的一些位置互不相同。输出方案。
\(n\le 1000\)
发现题目就是要我们构造一个 \(n+1\) 行 \(n\) 列的 \(01\) 矩阵使得每列的 \(1\) 的个数是 \(a_i\) 。我们对于序列 \(a\) 先从大到小排序，对于第 \(i\) 个元素，我们找到第 \(i\) 列，直接从第 \(i\) 行开始往下填 \(a_i\) 个 \(1\) ，到最下端后再回到最上端继续填即可。考虑这样构造的正确性，假设第 \(i\) 行和第 \(j\) 行 \((i<j)\) 这两行是相同的，由于元素都 \(\le n\) ，\(a_{i+1}\) 从第 \(i+1\) 行第 \(i+1\) 列开始填，显然有第 \(i\) 行第 \(i+1\) 列的元素为 \(0\) ，那么第 \(j\) 行第 \(i+1\) 列的元素为 \(0\) ，即向下填充不到第 \(j\) 行。由于 \(a_{i+2}\le a_{i+1}\) ，那么第 \(i\) 行和第 \(j\) 行第 \(i+2\) 列的两个元素无法做到全是 \(0\) ，则两个仍然都为 \(0\) 。依次类推，第 \(j\) 行和第 \(i\) 行第 \(j\) 列的两个元素也全是 \(0\) ，但由于 \(a_j\ge 1\) ，则第 \(j\) 行第 \(j\) 列的元素一定为 \(1\) ，矛盾，所以假设不成立，构造方案正确。
CF1129E
交互题。给定 \(n\) ，交互库会生成一个 \(n\) 个点的树，你需要用不超过 \(11111\) 次询问得出这棵树的形态，每次询问包括两个非空点集 \(S,T\) 和一个点 \(u\) ，交互库会返回对于所有的 \(i\in S,j\in T\) ，\(i\) 到 \(j\) 的路径经过点 \(u\) 的二元组 \((i,j)\) 数量。
\(n\le 500\)
我们先假设以 \(1\) 为根，先令 \(S=\lbrace1 \rbrace,T=\lbrace2,3,4\cdots,n\rbrace\) ，这样我们每次询问就能得到 \(u\) 的子树大小。我们在得到每个点的子树大小后，将其按照子树大小从小到大排序，那么每个点的儿子会在它前面。我们从前往后做，先将还没确定父亲的点放入一个集合 \(A\) 中，初始就是将叶子节点全部放入。对于一个新点，我们令 \(S=\lbrace1\rbrace,T=A\) 查询这个点，就可以得到这个点的儿子数量设为 \(p\) ，接下来我们进行 \(p\) 次二分，对于单次二分，我们二分最小的 \(x\) ，使得我们令 \(S=\lbrace1\rbrace,T=\lbrace A_1,A_2\cdots,A_x\rbrace\) 再次查询，得到的结果不为 \(0\) ，这样我们可以得到这个点的一个儿子 \(A_x\) ，我们将 \(A_x\) 的父亲设为这个点，然后将其从 \(A\) 中删除，最终我们就能找到这个点的所有儿子，我们此时再将它放入 \(A\) 中即可。最终询问次数约为 \(2n+2n\log n\) 。
CF1221G
给定一个 \(n\) 个点 \(m\) 条边的无向图，每个顶点上写 \(0\) 或 \(1\) ，定义边的权值是两个顶点的数字之和。求使得最终至少有一条边的权值是 \(0\) ，至少有一条边的权值是 \(1\) 且至少有一条边的权值是 \(2\) 的写数方案。
\(n\le 40\)
正着求显然不好求，于是我们考虑容斥。\(ans\) 为总方案数，减去没有 \(0\) 的方案数，减去没有 \(1\) 的方案数，减去没有 \(2\) 的方案数，加上没有 \(0\) 和 \(1\) 的方案数，加上没有 \(1\) 和 \(2\) 的方案数，加上没有 \(2\) 和 \(3\) 的方案数，减去没有 \(0,1,2\) 的方案数。
-
总方案数：显然就是 \(2^n\)
-
没有 \(0\) 的方案数：填 \(0\) 的形成独立集，就转化为经典的独立集计数问题，折半搜索即可。
-
没有 \(1\) 的方案数：对于每一个联通块里的所有点（此处孤立点也算联通块），它们上面的数必须相同，可以为 \(0\) 也可以为 \(1\) ，即 \(2^{x}\) ，其中 \(x\) 表示图的联通块个数。
-
没有 \(2\) 的方案数：填 \(1\) 的形成独立集，和没有 \(0\) 的方案数相同。
-
没有 \(0\) 和 \(1\) 的方案数：所有联通块里的所有点只能填 \(1\) （此处孤立点不算联通块），但是孤立点可以随便填，即 \(2^y\) ，其中 \(y\) 表示图的孤立点个数。
-
没有 \(1\) 和 \(2\) 的方案数：与没有 \(0\) 和 \(1\) 的方案数相同。
-
没有 \(0\) 和 \(2\) 的方案数：一条边上必须一个为 \(0\) 一个为 \(1\) ，也就是将原图黑白染色的方案数。若原图可以黑白染色，对于每个联通块，就有两种相反的染色方案，那么总方案数为 \(2^x\) ，其中 \(x\) 表示图的联通块个数；否则方案数为 \(0\) 。
-
没有 \(0,1,2\) 的方案数：发现不可能存在，为 \(0\) 。
时间复杂度为 \(O(2^{\frac{n}{2}}n^2)\) 。
AGC010D
有一个长度为 \(n\) 的序列 \(a\) ，初始时所有数的 \(gcd\) 等于 \(1\) 。两个人轮流进行操作，每次操作可以先选择一个大于 \(1\) 的数将其减 \(1\) ，然后令现在所有数的 \(gcd\) 等于\(g\) ，则每个数都会除以 \(g\) 。当序列中的所有数变成 \(1\) 时，不能再进行操作的人输。假设两个人都足够聪明，则先手必胜还是后手必胜。
\(n\le 10^5 ,1\le a_i\le 10^9\)
我们先考虑当序列中存在 \(1\) 的时候的胜负情况。此时 \(gcd\) 恒为 \(1\) ，那么发现操作次数为 \(\sum_{i=1}^{n} a_i-1\) ，当 \(a_i\) 为偶数且数量为奇数个，则总操作次数也为奇数次，那么此时先手必胜；否则后手必胜。
我们将其扩展到更一般的情况，就是初始有奇数个偶数，此时先手一定是想要维持住这个局面的。先手可以考虑让一个偶数减 \(1\) ，那么此时有偶数个偶数，同时会产生一个奇数，再加上序列中一定还存在一个奇数（否则初始 \(gcd\) 无法为 \(1\) ），序列中会有至少两个奇数，\(gcd\) 为 \(1\) 。此后无论后手怎么操作，先手都可以保持轮到自己时有奇数个偶数（对方动偶数偶数个数减 \(1\) ，动奇数偶数个数加 \(1\) ）并且 \(gcd\) 一直为 \(1\) 。这样直到序列中产生一个 \(1\) ，先手就赢了。
那么对于初始有偶数个偶数，此时先手这一步只能尽力去将偶数个数变为奇数个，那么唯一的希望就是，序列中只有 \(1\) 个奇数。如果序列中有至少两个奇数，那么先手拿到的就相当于上一种情况中的后手，对方是可以完全控制你的，此时后手必胜。那么序列中只有 \(1\) 个奇数的时候，先手只能将那个数减 \(1\) ，此时序列中全是偶数，每个数都会除以 \(gcd\) ，这样数量可能会发生改变。由于此时操作是唯一的，所以我们暴力修改序列，然后递归地去判断新序列的胜负情况。由于每次 \(gcd\) 至少除以 \(2\) ，那么时间复杂度为 \(O(n\log a)\) 。
AGC024E
给定 \(n,k,p\) ，问有多少个序列组 \(\lbrace A_0,A_1,A_2\cdots,A_n\rbrace\) ，满足：序列 \(A_i\) 有 \(i\) 个元素，每个元素均在 \([1,k]\) 间，对于所有的 \(0\le i<n\) ，\(A_i\) 是 \(A_{i+1}\) 的子序列，且 \(A_i\) 的字典序小于 \(A_{i+1}\) 。对 \(p\) 取模。
\(1\le n,k\le 300,2\le p\le 10^9\)
先考虑转化：\(n\) 次操作，每次在序列中插入一个值域为 \([1,k]\) 的数，同时要求后一个序列的字典序严格大于前一个序列。相同的数字显然是可以合并的，对于字典序的问题，其实就是说，你只能在一个小于 \(x\) 的数前面插入 \(x\) 或者直接在序列末尾插入。
此时还是有点不好做，我们把序列转化成一棵树。树上的每个节点都表示一个二元组 \((a,b)\) ，表示第 \(a\) 次操作插入了 \(b\) 这个值。假如第 \(i\) 次操作在第 \(j\) 次插入的值 \(v\) 前面插入了 \(w\) ，那么节点 \((i,w)\) 为节点 \((j,v)\) 的儿子。也就是说，若 \(x\) 为 \(y\) 的儿子，那么 \(a_x>a_y,b_x>b_y\) 。同时我们再新建一个虚拟节点 \((0,0)\) ，若在序列末尾插入数，那就是虚拟节点的儿子。容易发现，此时操作序列和树是一一对应的关系，那么我们转化为对这样的树进行计数。
我们设 \(f_{i,j}\) 表示子树大小为 \(i\) ，根节点的权值为 \(j\) 的方案数。我们考虑枚举 \(a\) 值最小的儿子 \(u\) 的子树大小 \(siz\) 和 \(b\) 值 \(v\) ，\(u\) 在子树内的 \(a\) 值一定为 \(2\)，\(b\) 值一定大于 \(j\) ，那么 \(u\) 的子树内的所有点的 \(a\) 值选择方案就是从 \(i-2\) 个值中选出 \(siz-1\) 个。于是有转移：
\[ f_{i,j}=\sum_{siz=1}^{i-1}f_{i-siz,j}\cdot\binom{i-2}{siz-1}\cdot\sum_{v=j+1}^{k}f_{siz,v} \]预处理一下组合数和 \(f\) 数组的后缀和，时间复杂度为 \(O(n^2k)\) 。
AGC023E
给定一个长度为 \(n\) 的序列 \(a\) ，求所有满足 \(\forall 1\le i\le n,P_i\le a_i\) 的排列 \(P\) 的逆序对数之和对 \(10^{9}+7\) 取模后的结果。
\(1\le n\le 2\times 10^5\)
我们先考虑满足要求的排列 \(P\) 的个数，我们将 \(a\) 从小到大排序后得到序列 \(b\) ，那么答案其实就是：
\[tot=\prod_{i=1}^{n}b_i-i+1 \]排完序后从前往后填数，对于第 \(i\) 个位置有 \(b_i\) 种可选的数，再算上前 \(i-1\) 个用过的数，就有 \(b_i-i+1\) 种选法。全部乘起来即可。
而对于逆序对数的统计，我们可以考虑原序列 \(a\) 中的两个位置 \(i,j(i<j)\) 对答案的贡献。此时我们要对 \(a\) 的大小关系分类。以下 \(c_i\) 表示 \(a_i\) 在排完序后的排名。
-
\(a_i<a_j\)
我们统计 \(p_i>p_j\) 的方案数。方案数为：
\[\frac{(a_i-c_i+1)(a_i-c_i)}{2}\times \frac{tot}{(a_i-c_i+1)(a_j-c_j+1)}\times \prod_{a_i<a_k<a_j}\frac{a_k-c_k}{a_k-c_k+1} =\frac{tot(a_i-c_i)}{2(a_j-c_j+1)}\times \prod_{a_i<a_k<a_j}\frac{a_k-c_k}{a_k-c_k+1} \]
第一项表示选出 \(p_i,p_j\) 的方案数，第二项表示其它项的方案数，第三项表示由于 \(p_j\) 在 \(<a_i\) 中选了从而使满足 \(a_i<a_k<a_j\) 的 \(k\) 的选法减少了 \(1\) 。
-
\(a_i>a_j\)
发现这种情况就是总的方案数减去 \(p_i<p_j\) 的方案数，\(p_i<p_j\) 的方案数显然与上面类似，其实就是将 \(i,j\) 互换，得到：
\[tot-\frac{tot(a_j-c_j)}{2(a_i-c_i+1)}\times \prod_{a_j<a_k<a_i}\frac{a_k-c_k}{a_k-c_k+1} \]
我们只需要考虑如何求这个式子。我们考虑让排序后的 \(a_i\) 从小到大插入，然后分别计算位置 \(<i\) 和位置 \(>i\) 的贡献。我们开一棵线段树，下标为原序列的下标，对于 \(a_i\) ，我们先区间查询 \([1,c_i-1]\) 已经插入的数的区间和，再减去 \([c_i+1,n]\) 的区间和。让结果同时乘上 \(tot\) ，再乘上 \(2(a_i-c_i+1)\) 的逆元，最后再加上第二种情况中 \(tot\) 的个数，这个在线段树上再维护一个 \(cnt\) 查询 \([c_i+1,n]\) 即可。贡献已经计算完毕，此时我们将 \(i\) 插入线段树中，全局要先乘上一个 \(\frac{a_i-c_i}{a_i-c_i+1}\) ，再将 \(a_i-i\) 插入到位置 \(c_i\) ，这样就可以对后面的查询起到该有的贡献了。时间复杂度为 \(O(n\log n)\) 。
AGC022D
有 \(n\) 个地点，第 \(i\) 个地点的坐标为 \(x_i\) ，需要连续呆的时间为 \(t_i\) 。现有一辆车从 \(0\) 出发到 \(L\) 往返行驶，每行驶一单位距离时间为 \(1\) 。起始从 \(0\) 处上车，只能在某个地点、\(0\) 处和 \(L\) 处下车，求最少花费多少时间能在每个地点都连续呆到 \(t_i\) 的时间并最终返回 \(0\) 处。
\(n\le 3\times 10^5\)
发现最终走的距离一定是 \(2L\) 的整数倍，所以以下我们只考虑 \(2L\) 前面的系数。
首先我们将所有 \(t_i\) 模上 \(2L\) ，并将答案加上 \(\lfloor\frac{t_i}{2L}\rfloor\) ，这样答案显然是不会变的。容易发现此时最劣情况就是每到一个地点都等一个 \(2L\) 的来回，所以答案上界为 \(n+1\) 。
我们考虑如何优化方案。我们设 \(l_i\) 表示从左面到达地点 \(i\) ，车下次从右面到达地点 \(i\) 时是否能够呆 \(t_i\) 的时间，同理设 \(r_i\) 表示从右面到达地点 \(i\) ，车下次从左面到达地点 \(i\) 时是否能够呆 \(t_i\) 的时间。\(l_i\) 和 \(r_i\) 显然是很好求的，具体地，我们有 \(l_i=[2(L-x_i)\ge t_i],r_i=[2x_i\ge t_i]\) 。对于 \(l_i=0\) 且 \(r_i=0\) 的地点，显然我们只能等下一个来回了。而对于 \(i<j\) ，若 \(r_i=l_j=1\) ，我们可以从 \(i-1\) 走到 \(i\) 的过程中，先走到 \(j\) ，从右边回来后再上车到 \(i\) ，从左边回来后再上车到下一个地方，容易发现这样我们用了一个来回完成了两个地点 \(i\) 和 \(j\) 。形象化地，我们令 \(r=1,l=0\) 的为左括号，\(l=1,r=0\) 的为右括号，\(l=r=1\) 的为通配符，既可以和左括号匹配也可以和右括号匹配。上面就是一个左括号和右括号匹配的过程。这样我们可以将原序列转化成一个括号序列，而且这个括号序列还有一个很优美的性质，就是说：左括号的右边永远不可能存在右括号，考虑证明：
- 左括号表示 \(r=1,l=0\) ，求解两个关于 \(x\) 的不等式，可以得到 \(x>max(\frac{t}{2},L-\frac{t}{2})\ge \frac{L}{2}\) 。
- 右括号表示 \(r=0,l=1\) ，仍然求解两个关于 \(x\) 的不等式，可以得到 \(x<min(\frac{t}{2},{L-\frac{t}{2}})\le \frac{L}{2}\) 。
- 所以一旦出现左括号，\(x>\frac{L}{2}\) ，已经不符合右括号存在的条件，故右边不会出现右括号，证毕。
所以括号序列一定是形如，前面一堆通配符和右括号，第一个左括号，后面一堆通配符和左括号。我们要让匹配数最大。这是一个很显然的贪心，我们左边枚举到第一个左括号的位置，让通配符和右括号直接匹配，然后再从第一个左括号到第 \(n-1\) 位，让通配符和右括号进行匹配。最后可能左边和右边各剩下一些通配符，再让那些通配符直接匹配即可，注意若剩下的是括号则无法匹配，因为前面是右括号而后面是左括号。
这题同时还有一些细节，对于 \(t_i=0\) 的地点我们可以将其忽略，因为只需要到时候坐上车即可，可以减一个来回。若 \(l_n=1\) ，也可以减一个来回。最终再减去匹配的数量，就能得到答案的系数了。时间复杂度为 \(O(n)\) 。
CF1612G
给定一个长度为 \(m\) 的序列 \(a\) ，还有一个序列 \(A\) 满足：\(\forall 1\le i\le m\) ，\(i\) 在序列 \(A\) 中出现了 \(c_i\) 次。定义序列 \(A\) 的权值为：
\[\sum_{1\le i<j\le n,A_i=A_j} j-i \] 最大化序列 \(A\) 的权值，并求出在权值最大化的前提下序列 \(A\) 个数量。对 \(10^9+7\) 取模。
\(1\le m\le 5\times 10^5,c_i\le 10^6\)
我们对于每一个 \(c_i\) ，考虑其贡献。设 \(i\) 在序列 \(A\) 中出现的下标分别为 \(x_1,x_2,\cdots,x_{c_i}\) （从小到大），那么它对权值的贡献为：
\[\sum_{1\le j<k\le c_i}(x_k-x_j) \]考虑化简，考虑单个位置对权值的贡献，对于下标 \(x_j\) ，它会在所有的 \(k>j\) 被减去，会在所有的 \(k<j\) 被加上，所以其系数为 \(j-1-(c_i-j)=2j-c_i-1\) ，总共就是：
\[\sum_{j=1}^{c_i}(2j-c_i-1)x_j \]我们可以将总共 \(\sum_{i=1}^{m}c_i\) 个元素的贡献系数从大到小排序，然后从大到小依次分配下标，就是让大的乘大的，显然这是最优的。但是 \(\sum_{i=1}^{m}c_i\) 的值特别大，我们不可能完全将序列建立出来。此时我们可以使用一个差分桶，储存每个贡献系数的出现次数。对于一个 \(c_i\) ，其贡献系数写出来是 \(1-c_i,3-c_i,\cdots,c_i-3,c_i-1\) ，那我们直接差分，将 \(1-c_i\) 的位置加一，\(c_i+1\) 的位置减一，每次将下标加二来计算前缀求出原来的值。假如我们已经处理好所有的 \(c_i\) 得到了这个差分桶，设值为 \(p\) 的系数出现 \(x\) 次 ，我们就要拿 \(x\) 个下标去分配给它们，假设下一个该分配的下标是 \(tot\) ，那么对权值的贡献就是 \([tot+1,tot+x]\) 里的数求和乘上 \(p\) ，对数量的贡献就是 \(x!\) ，因为下标可以随意排列去分配，然后 \(tot+=x\) 继续求解下一个值即可。由于系数可能为负数，所以我们同时加上一个数让它们变成正数。时间复杂度为 \(O(n)\) 。
CF1615F
对于两个长度为 \(n\) 的 \(01\) 串 \(s,t\) ，一次操作可以将 \(s\) 中相邻两个 \(0\) 全变成 \(1\) 或把相邻两个 \(1\) 全变成 \(0\) ，定义 \(s\) 到 \(t\) 的距离为 \(s\) 变成 \(t\) 的最小操作步数。现给定两个长度为 \(n\) 由 0,1,? 组成的串，其中 ? 可以为 \(0\) 或 \(1\) ，求所有情况下得到的两个 \(01\) 串的距离之和，对 \(10^9+7\) 取模。
\(n\le 2000\)
我们先考虑如何求出两个确定的 \(01\) 串的距离。我们将两个串下标为偶数的字符取反，得到新的字符串 \(ss,tt\) 。容易发现交换 \(ss\) 中两个相邻的不同字符与原操作等价，此时我们就转化为将 \(ss\) 变为 \(tt\) 的最小操作次数。
显然 \(ss\) 可以变成 \(tt\) 的充要条件是 \(1\) 的个数相同，我们设 \(x_i\) 表示 \(ss\) 中第 \(i\) 个 \(1\) 的下标，\(y_i\) 表示 \(tt\) 中第 \(i\) 个 \(1\) 的下标，那么最小操作次数为 \(\sum_{i=1}^{m}|x_i-y_i|\) 。事实上这个还是有点不方便计算，所以我们再次转化：设 \(a_i\) 表示 \(ss\) 中前 \(i\) 个字符中 \(1\) 的个数，\(b_i\) 表示 \(tt\) 中前 \(i\) 个字符中 \(1\) 的个数，那么最小操作次数为：\(\sum_{i=1}^{n}|a_i-b_i|\) 。至此我们就有一个比较显然的做法了。我们设 \(pre_{i,j}\) 表示确定了 \(ss,tt\) 的前 \(i\) 个字符，\(a_i-b_i=j\) 的方案数，转移时枚举 \(ss,tt\) 第 \(i\) 位的字符从 \(f_{i-1,j}\) 转移到 \(f_{i,j-1/j/j+1}\) 。同理设 \(suf_{i,j}\) 表示确定了 \(ss,tt\) 的第 \(i\) 个字符到第 \(n\) 个字符，其中 \(ss\) 中 \(1\) 的个数与 \(tt\) 中 \(1\) 的个数相差 \(j\) 的方案数，转移同理。最终答案就是：
\[\sum_{i=1}^{n}\sum_{j=-n}^{n}pre_{i,j}\times suf_{i+1,-j}\times |j| \]时间复杂度为 \(O(n^2)\) 。
AGC019F
有 \(n+m\) 个问题，其中 \(n\) 个问题的答案是 Yes，\(m\) 个问题的答案是 No。当回答完一个问题的时候会知道这个问题的正确答案，求最优策略下期望能对多少题，对 \(998244353\) 取模。
\(n,m\le 5\times 10^5\)
先考虑什么是题目所说的 "最优策略" ，假如现在你知道选 Yes正确的概率更高，那么你不会的题肯定会选 Yes。事实上就是这个道理，假设现在 \(a\) 个题答案为 Yes，\(b\) 个题答案为 No，当 \(a>b\) 回答 Yes，当 \(a<b\) 回答 No ，当 \(a=b\) 回答哪个都可以。
我们假设 \(n>m\) ，初始我们肯定回答 Yes，正确则 \(ans+1,n-1\) ，否则 \(m-1\) 。容易发现让 \(n\) 减少的唯一条件就是回答正确，答对了能让较大数减少，所以至少能答对 \(max(n,m)\) 道。但是当 \(n=m\) 时无论回答 Yes 还是 No 都会变成 \((n,n-1)\) 的状态，就是这一步无论正确还是错误，都不影响后面继续答对，所以会对答案可能产生额外的贡献。
我们考虑把它放入一个坐标系中，横坐标表示还有题目答案为 Yes的数量，纵坐标表示还有题目答案为 No的数量，起始点为 \((n,m)\) ，然后再画一条直线 \(y=x\) 。剩下我们就要考虑直线上的点的额外贡献，因为直线上的点满足 \(y=x\) ，那么它会随机选择一个答案去回答，回答正确的概率为 \(\frac{1}{2}\) ，从而对答案产生贡献。我们考虑统计经过直线 \(y=x\) 上的点的方案数，对于直线 \(y=x\) 上一点 \((i,i)\) ，从 \((n,m)\) 走到 \((i,i)\) 的方案数为 \(\binom{n+m-2i}{n-i}\) ，从 \((i,i)\) 走到 \((0,0)\) 的方案数为 \(\binom{2i}{i}\) ，所以经过它的方案数为 \(\binom{n+m-2i}{n-i}\times \binom{2i}{i}\) 。我们求出这条直线上所有点的总方案数，除以从 \((n,m)\) 走到 \((0,0)\) 的总方案数，乘上 \(\frac{1}{2}\) 的概率即可。最终答案为：
时间复杂度为 \(O(n)\) 。
标签：10,le,sum,times,序列,杂题,我们 From： https://www.cnblogs.com/LYT0122/p/17478807.html