联合省选 2021 A 卷 D1T1 卡牌游戏
把两个序列合并起来排序后双指针即可。复杂度 \(O(n\log n)\)。
联合省选 2020 B 卷 D2T1 消息传递
等价于求与 \(x\) 距离恰好为 \(k\) 的节点个数。点分治/点分树均可，每组数据复杂度 \(O((n+m)\log n)\)。
联合省选 2020 A 卷 D2T2 树
把每个数的二进制倒着插入 01trie，发现全局 \(+1\) 相当于交换一条链上点的左右子树。
注意 01trie 的高度只有 \(O(n\log n)\)，因此每次操作暴力交换即可。还需要合并，由于 01trie 本质上是动态开点权值线段树，本身就支持合并，正常写就行了。总的复杂度 \(O(n\log n)\)。
- 本题其实有其他做法QAQ
- 注意到一个数 \(x\) 在第 \(r\) 位上有值当且仅当 \(x\bmod 2^{r+1}\ge 2^{r}\)，因此相当于统计子树内有多少个点满足 \((dep+val)\bmod 2^{r+1}\ge 2^r\)，对每一位开个树状数组，用 dsu on tree 维护这个东西，就可以做 \(O(n\log ^3n)\)。这种做法支持边权任意的情形（但 01trie 似乎不支持！）。
- 似乎可以改用长剖优化至 \(O(n\log ^2n)\)。（我不太理解，如果有好哥哥路过能教教我吗/kel）
联合省选 2020 A/B 卷 D1T1 冰火战士
把冰火双方的能量、温度全都写出来，火是 \(A,B\)，冰是 \(C,D\)，那么相当于要找一个 \(k\)，最大化
考虑二分答案 \(mid\)，把两边分别按照 \(A,C\) 排序，再一次在线段树上二分出能够使 \(D\) 那边的前缀和 \(\ge mid\) 的最小 \(k_1\)，与 \(B\) 那边的后缀和能够 \(\ge mid\) 的最小 \(k_2\)，判断 \(k_1\le k_2\) 是否成立即可。
发现复杂度是 \(O(n\log n\log V)\)，要跑 \(2\times 10^6\) 有点困难。
发现其实不需要两次二分，设 \(X_i=\sum_{j\le i}D_j-\sum_{j\ge i}B_j\)，那么只需要找到第一个 \(X_i>0\) 的位置就可以了。一次操作会把 \(X_i\) 做一个区间加，这同样是容易维护的。这样就只需要 1log 了。
代码......暂时还没写。（太懒了QAQ）考场上估计会写 2log，1log 感觉有不少细节！
联合省选 2020 A/B 卷 D2T1 信号传递
他们真的很喜欢传递信息
相当于确定一个排列 \(p\)，使得这个式子最大：
其中 \(f(x,y)\) 表示从 \(x\) 传递到 \(y\) 的代价，也即，当 \(x\le y\) 时 \(f(x,y)=y-x\)，否则 \(f(x,y)=k(x+y)\)。
我们考虑把 \(f\) 拆开，即认为每个 \(S_i\) 会在左右两侧各造成一次贡献；在右侧造成贡献时，若 \(p[S_i]<p[S_{i+1}]\)，则 \(S_i\) 的贡献为 \(-p[S_i]\)，否则为 \(k\times p[S_i]\)；左侧恰好相反。
使用状压，设 \(g(T)\) 表示：将 \(T\) 以内的信号站分配到 \(1,2,\cdots,|T|\) 这些位置，并且只考虑 \(T\) 以内信号站的贡献，把 \(T\) 以外的位置都看作 \(m+1\) 信号站（但不计算它们的贡献）时，的最小贡献和。转移时，我们考虑将 \(|T|\) 分配给信号站 \(x\in T\)，那么它的贡献实际上是确定的，这取决于 \(x\) 在序列中出现的每个位置前后的值是否在 \(T\) 内。
考虑如何计算这个贡献。若 \(S_i=x\)，考虑 \(S_{i-1}\)，如果 \(S_{i-1}=x\) 则不可能造成贡献；否则会对所有 \(S_{i-1}\in T\) 造成 \(|T|\) 的贡献，对所有 \(S_{i-1}\not\in T\) 造成 \(k|T|\) 的贡献；同理会对所有 \(S_{i+1}\in T\) 造成 \(k|T|\) 的贡献，对所有 \(S_{i+1}\not\in T\) 造成 \(-|T|\) 的贡献。
把 \(S_{i-1}\) 相同的分成一类贡献，那么一共只有 \(m\) 类；当然可以 \(O(m^22^m)\) 预处理。可以简单优化至 \(O(m2^m)\)。总的时间复杂度为 \(O(m2^m)\)。空间上需要卡常。实在卡不过去，看了题解才卡过去的。
联合省选 2020 A 卷 D1T2 组合数问题
直接算是 \(O(nm)\) 的，当然不行。
注意到 \(m=0\) 的时候，只需要算 \(\sum_{k=0}^nx^k\binom{n}{k}=(x+1)^n\)，容易计算。
考虑 \(\sum kx^k\binom{n}{k}\) 怎么算。考虑两边同时求导：
因此 \(\sum_{k=0}^nkx^k\binom{n}{k}=nx(x+1)^{n-1}\)。这样一直求导，我们理论上就可以得到 \(\sum k^mx^k\binom{n}{k}\) 的公式；但手算当然是不太现实的。
考虑 \(k^m\binom{n}{k}\) 的组合意义，发现考虑不出来！我知道你很急但是你先别急，先从 \(m=1\) 开始，从左侧 \(nx(x+1)^{n-1}\) 猜测，发现应该是：钦定某个元素必须选中，其余随意，且恰好选了 \(k\) 个元素的方案数。
再多算一项
发现我们其实应该考虑 \(k^{\underline m}\binom{n}{k}\)。它的组合意义是：钦定某 \(m\) 个数必须选中，且选出的数恰好有 \(k\) 个的方案数。有 \(\sum_{k=0}^nk^{\underline m}\binom{n}{k}x^k=m!\sum_{k=0}^n\binom{k}{m}\binom{n}{k}x^k\)，注意到 \(\binom{n}{k}\binom{k}{m}=\binom{n}{m}\binom{n-m}{k-m}\)，因此只需要求
其实这个和上面组合意义得到的结果是一致的！
现在我们知道下降幂了，如果能找到某个 \(a\) 使得 \(\sum_{i\le m} a_{i,m}k^{\underline i}=k^m\) 就好了。发现就是第二类斯特林数，直接做就行了。复杂度 \(O(m^2)\)
联合省选 2020 B 卷 卡牌游戏
他们真的很喜欢卡牌游戏
记 \(S_i\) 为原序列前缀和，答案即为 \(2,3,\cdots,n\) 种所有 \(>0\) 的 \(S_i\) 之和。
联合省选 2020 B 卷 幸运数字
每个条件相当于一次区间异或。离散化后差分维护每个值最终会变成啥就行了。
因为要离散化，复杂度 \(O(n\log n)\)。
<1min 就会了，但是目测要写 >1min。不想写
联合省选 2020 B 卷 丁香之路
呜呜，第一眼发现不会
先写个状压 DP 压压惊，\(f(i,S,0/1)\) 表示走遍 \(S\) 内特殊边，最后留在 \(u_i/v_i\) 的最小代价
写到一半好像有了点思路！考虑对 \(m\) 条特殊边建图，考虑对于一个连通块，从连通块内某个点开始走遍连通块内所有边的最小代价。显然，如果图中存在欧拉回路，那么最优方案就是沿着欧拉回路走一遍。
如果没有欧拉路径呢？我们发现此时相当于有 \(2k\) 个度数为奇数的点，其中 \(k>1\)。尽管此时不存在欧拉路径，但是我们可以在两个点 \(i,j\) 之间进行 “ 跳跃 “，需要花费 \(|i-j|\) 的代价。那么我们只需跳跃 \(k\) 次，即可得到一条欧拉回路。
现在我们要用 \(k\) 条边连上 \(2k\) 个点，不过图不是二分图。把这 \(2k\) 个点按照编号排序，那么最优方案一定是将 \((x_1,x_2),(x_3,x_4),\cdots,(x_{2k-1},x_{2k})\) 这样两两配对。
似乎漏掉了什么！为什么不可能从某个点不进行跳跃，而是沿着某些别的路径直接遍历剩下的边呢？我们注意到这张图的性质非常好，它满足任意两个点之间的所有简单路径上边权和相等！因此，感性理解一下，不管是什么方案，其实和我们的方案基本是等价的。
现在图中可能有多个连通块，还有从 \(s\) 开始，到 \(i\) 结束的限制，怎么做呢？简单思考一下，发现相当于要加若干边，使得 \(s,i\) 的度数都变成奇数，其他的均为偶数；我们只需检查 \(s,i\) 的度数的奇偶性，据此判断是否要将 \(s,i\) 加入序列一起排序，即可。
加完边之后可能原图仍然不连通，首先如果我们新加了一条边 \((x,y)\)，那么我们完全可以在从 \(x\to y\) 的时候跳到某个中间点，从这里遍历它的连通块，再返回 \(y\) 点；因此 \((x,x+1),(x+1,x+2),\cdots,(y-1,y)\) 这些边都被我们加上了；如果此时原图仍然不连通，考虑求个最小生成树使图联通，即可。注意到最小生成树的可行边只在相邻的连通块之间，因此复杂度仍然有保证。
但有一个问题，为什么不可能是在先前满足每个点的度数约束的时候，改变一些方案，使其满足连通性的限制呢？考虑四个点 \(a<b<c<d\)，一开始的方案是连边 \((a,b),(c,d)\)，如果不连通，我们还会补上边 \((b,c)\)，代价是 \(b-a+d-c+2(c-b)=d-a+c-b\)；如果改变方案为 \((a,d),(b,c)\)，发现此时的代价仍然是 \(d-a+c-b\)。感性理解一下，这两种方案本质是相同的。
至此本题得到完全解决，时间复杂度显然可以做到 \(O(n^2\log n+m)\)，注意到最小生成树的边权不超过 \(n\)，因此可以做到 \(O(n^2+m)\)。
联合省选 2020 A 卷 作业题
首先套路反演一波，设 \(W(T)\) 表示生成树 \(T\) 的边权集合，\(\gcd(S)\) 表示 \(S\) 以内所有数的 \(\gcd\)，\(\text{sum}(S)\) 表示 \(S\) 以内所有数之和
相当于保留所有边权为 \(d\) 的倍数的边，求所有生成树的权值和。
直接暴力算就行了，复杂度大概是 \(O(n^3\sum d(w_i))\)，不会超过 \(n^4\times \max d(w_i)\le 2\times 10^8\)。
联合省选 2020 A 卷 魔法商店
摆
卡牌游戏
把两个序列合并起来排序后双指针即可。复杂度 \(O(n\log n)\)。
矩阵游戏
不难发现确定第一行第一列就可以确定整个矩阵。这启发我们把这 \(n+m-1\) 个数当作自由元，尝试去解出所有的 \(a\)。考虑 \(a_{i,j}\)，可以归纳证明：
其中，\(D_{i,j}=b_{i-1,j-1}-D_{i-1,j-1}-D_{i-1,j}-D_{i,j-1}\)。两边同时乘上 \((-1)^{i+j-1}\) 得到
设 \(c_{i,j}=(-1)^{i+j}a_{i,j}\)，重新定义 \(D_{i,j}=(-1)^{i+j-1}D_{i,j}\)，则有 \(-c_{i,j}=c_{1,1}-c_{i,1}-c_{1,j}+D_{i,j}\)
于是，我们的约束就是：
- \(\forall i,j,c_{1,j}\in[0,(-1)^{j+1}\times 10^6],c_{i,1}\in[0,(-1)^{i+1}\times 10^6]\)。
- \(\forall i,j, c_{1,1}-c_{1,j}-c_{i,1}+D_{i,j}\in[0,(-1)^{i+j-1}\times 10^6]\)。
发现条件涉及到三个变量，不是很好做。但是你注意到上面那个只涉及到一个变量，考虑做变换 \(f_{1,j}=-c_{1,j}+c_{1,1}\)，则条件变为
- \(\forall i,j,c_{1,1}-f_{1,j}\in[0,(-1)^{j+1}\times 10^6],c_{i,1}-f_{1,1}\in[0,(-1)^{i+1}\times 10^6]\)
- \(\forall i,j,f_{1,j}-c_{i,1}\in[-D_{i,j},(-1)^{i+j-1}\times 10^6-D_{i,j}]\)
- \(f_{1,1}=0\)
就变成差分约束的形式啦
图函数
这题比 matrix 简单一万倍好吧
考虑对每个 \(u,v\) 算贡献，发现一定是对一段前缀的 \(f(G_i)\) 有贡献。
具体来说，\(u,v\) 能贡献到 \(f(G_x)\)，当前仅当：存在 \(u\to v,v\to u\) 的路径 \(P\) 满足：
- \(P\) 只包含编号 \(\ge u\) 的点，只包含编号 \(>x\) 的边。
现在有两种做法：
- 枚举编号最小的点 \(u\)，用最短路求出他到每个其他点的最大瓶颈路，复杂度 \(O(nm\log n)\)
- 从大到小加点，同时维护 Floyd， 复杂度 \(O(n^3)\)
据说有 bitset 优化的 \(O(n^3/w)\) 做法，额我暂时不是很懂啊
最短路求最大瓶颈路：考虑仿照 dij，每次取出最大瓶颈路最大的一个点，认为他的最大瓶颈路是对的，并进行扩展。堆优化要 \(m\log\)，暴力做也是 \(O(n^2+m)\)。
宝石
点分治。设当前分治中心为 \(\text{rt}\)，考虑设 \(f_u(x)\) 表示从点 \(u\) 开始走，从 \(P_x\) 开始收集，一路向上走到 \(\text{rt}\)，最多能收集到哪个宝石。我们发现不同的 \(u,x\) 有 \(O(nm)\) 对，但写出转移发现，只有当 \(P_x=w_u\) 的时候，才有 \(f_u(x)=f_{v}(x+1)\)（其中 \(v=fa_u\)），其余情况均有 \(f_u(x)=f_v(x)\)。因此，我们可以使用可持久化线段树来维护 \(f_u\)。由于 \(P\) 互不相同，每次只会修改一个位置。
另一方面，我们尝试设 \(g_u(x)\) 表示从 \(\text{rt}\) 走到 \(u\)，从 \(P_x\) 开始收集，最多到哪个；那么当 \(w_u=P_{g_v(x)+1}\) 时，有 \(g_u(x)=g_v(x)+1\)，否则 \(g_u(x)=g_v(x)\)。但问题在于，可能有很多个 \(g_v(x)\) 符合这个条件，复杂度不能得到保证。
考虑二分答案，重新设 \(g_u(x)\) 表示从 \(u\) 开始走，从 \(P_x\) 开始收集，但是倒着收集，最多能收集到哪个宝石（实际上是收集到的最小宝石的编号）；那么 \(g\) 同样容易计算，判定答案 \(mid\) 是否符合条件只需要 \(f_u(1)+1\ge g_v(mid)\) 即可。
注意 \(g\) 不一定递增，还需要维护后缀最小值；查询时在线段树上二分即可。
总的复杂度看上去是 3log，但你冷静一下发现，实际上点分部分是 \(O(n\log n\log m)\)，询问的二分部分是 \(O(q\log m)\)，因此总的复杂度为 \(O(n\log n\log m+q\log m)\)。由于可以离线，空间复杂度只需要 \(O(n\log m)\)。
我觉得考场上写这种东西需要一些勇气，我先试着写写！/fendou
UPD：自信即巅峰。其实没有那么难写！ac link
- 看题解之后才发现，其实直接倍增就行了。。。一开始我以为要设 \(f(u,i,k)\) 表示从 \(u\) 开始跳，下一个要找的是 \(P_i\)，跳 \(2^k\) 步；但实际上由于 \(P\) 互不相同，我们知道 \(w_u\) 就可以直接推出下一个应该到哪里。。。。
滚榜
考虑暴力枚举 \(n!\) 种排列，发现只需要把最开头那个补到最大值的大小，剩下的用尽可能少的代价补到上一个的大小即可。
考虑这个过程，发现是先把 \(x_1\) 补到最大值（可能还要 \(+1\)，取决于他和最大值的位置关系），对于下一个，如果当前填了 \(b_i\)，原来是 \(a_i\)，那么下一个的 \(b_j\) 应该尽可能小地填。实际上填的值就是 \(b_i+\max(0,a_i-a_j+[i<j])\)
你发现这个 \(b_i\) 不管怎么都要加上去，考虑提前计算贡献，加进来一个就把系数乘上 \(n-i\)
然后考虑状压，\(f(S,x,k)\) 表示考虑了 \(S\) 以内的元素，一共用了 \(x\) 的代价， 最后一个元素是 \(k\) 的方案数。转移时，枚举 \(y\not\in S\)，转移至 \(f(S,x+\text{cost}(k,y)\times (n-|S|),y)\) 即可，其中
复杂度是 \(O(n^22^nm)\)，额，怎么算出来又是 \(6\times 10^8\)，冲了
支配
摆
预处理器
不难发现只需要实现展开某个单词的过程，以及把一行普通代码分割成若干单词的过程。
前者可以用两个 map 记录是否在展开以及展开结果，后者是好做的。
以前一直觉得这个很麻烦，结果写起来发现很简单啊。20min 就写完过了。
填树
摆
卡牌
貌似我把这题做难了......
做过寿司晚宴就容易想到根号分治，对 \(\le \sqrt{v}\) 的质因子状压，同时对每个 \(>\sqrt{v}\) 的质因子 \(p\) 存一个 \(f(p,S)\) 表示只考虑 \(\ge \sqrt{v}\) 的质因子恰好是 \(p\) 的这些数，他们小的那些质因子的并集为 \(S\) 的方案数。
对于一次询问，设 \(U\) 为本次询问中 \(\le \sqrt{v}\) 的质因子构成的集合，\(p_1,\cdots,p_k\) 是本次询问中 \(>\sqrt{v}\) 的质因子，那么要求的就是在每个 \(f(p_i,\cdot)\) 中选择 \(S_1,\cdots,S_k\) 使得 \(U\subseteq \bigcup_{i=1}^k S_i\)，且某些 \(S_i\neq \varnothing\)；对于一种选择集合的方案，其贡献为 \(\prod f(p_i,S_i)\)。
发现只需要做位或卷积，FMT 即可；\(S_i\neq \varnothing\) 这个限制相当于给 \(f(p_i,\cdot)\) 的 FMT 全局减一。总的时间复杂度大概是 \(O(\pi(v)\times r2^r+\sum c_i2^r+m\times r2^r)\)，其中 \(r\) 是 \(\le \sqrt{v}\) 的质数个数，即 \(\pi(\sqrt{v})\)。
LOJ 上很容易过，洛谷上需要卡常。
还是说一下容斥做法吧！对于询问集合 \(S\)，考虑钦定某个子集 \(T\subseteq S\)，令 \(T\) 内质因子都不被包含，则容斥系数为 \((-1)^{|T|}\)；接下来枚举每个大的质因子，设 \(C_{p,S}\) 表示从这个大质因子 \(p\) 的集合中选出若干数使得小质因子并集恰好为 \(S\) 的方案数，如果这个质因子被钦定了就令 \(\text{ans}\leftarrow \text{ans}\times (C_{p,S}-1)\)，否则令 \(\text{ans}\leftarrow \text{ans}\times C_{p,S}\)。\(C\) 当然是可以预处理的，总复杂度 \(O((m+\sum c_i)2^r+v\times r2^r)\)。
别的全摆了