2023.11.13

CWOI

T1 神奇模拟题，最直接的做法就是每个石头暴力向下滚，有 $60$ 分。但是大样例跑了 $15s$。稍微观察一下，会发现很多次循环都是在重复向下走到一格空位上，于是考虑优化：用 set 维护每一列的那些位置有障碍（包括石头），每次直接 lower_bound 跳到下一个位置，会快很多，大样例 $1.7s$。赛时就写的这个，但还是过不去的。因为反复横跳就会将其卡至 $O(nr \log r)$。

我们发现 $c$ 是很小的，也就意味着会有很多次都是从同一列向下滚。观察发现：同一列的滚动路径只会有后面连续的一段会被改变。也就是说假如这列第一个球的路径是 $p_1,p_2...p_x$ ，那么下一个小球的路径的前半段一定与当前小球相同。因为假设有一个位置 $y$ 使得 $p_y$ 被覆盖而 $p_{y+1}$ 没有被覆盖，那么小球沿着滚动路径一定能放下滚去覆盖 $p_{y+1}$，与假设矛盾。

因此，我们直接维护从当前列开始扔，到第 $x$ 行是在第几列。因为有可能会有一些小球会把当前位置占掉，所以我们在进行操作前要先将被占的位置撤销，找到一个空列再下落。这样时间复杂度就均摊下来了，为 $O(rc^2)$。

T2 ~~World_Ender怎么一年前就做过原题啊。~~ $2 \times 10^3$ 的数据直接 $O(n^2 \log n)$，对每个点二分答案，check 直接从当前点搜索一遍图就好了。$r_i =0$ 相当于找环，记搜一下即可。

正解是贪心+拓扑排序。设 $f_i$ 表示从 $i$ 点开始，至少要拥有多少元才能无限走下去。首先如果要无限走下去，那么从这个点出发一定能走到一个环上，因此那些出度为 $0$ 的点肯定是无解的，先把他们删掉。

再考虑那些没被删的点如何转移。一个直接的想法是 $f_u=\min \{f_u,\max \{r_{u \to v},f_v-p_{u \to v}\}\}$。相当于要么取最大的 $r_i$，要么根据$f_v$ 来倒推出当前值。但是原图是有环的，转移会有后效性，考虑换一种顺序：将边按 $r_i$ 从大到小排序。为什么是对的呢？因为假如说这个点可以走到环上，那么以最大的 $r_i$ 走一定能继续下去，因为 $p_i$ 是正数，只会越走越大，因此一定是对的。

明白这些之后，就可以用一种拓扑排序的思想：每次取出队首，遍历所有出边并更新，同时删掉出边。注意建边时要建反边，因为要用 $v$ 来更新 $u$。如果这样完了一轮后当前边还没删，那就相当于这条边可以走到环上，因此用这条边的 $r_i$ 更新即可。

T3 神秘构造题。咕咕咕。

T4 咕。

2023.11.14

CWOI

T2 冲了两个多小时没冲出来，考试策略还是有点问题，T4就一眼没看，下次要合理分配时间了。

T1 每次找最左上角有 x 的地方盖章，按题意模拟即可。我用了 set 来找最左上的点，实际上不需要，直接按顺序枚举每个点盖章，一共只会盖 x 的数量那么多次，复杂度 $\mathcal {O(nm)}$。

T2 看我写的题解吧。

T3 把每个点按顺序标号后，每个操作就变成了：

$\tt 1$：$x \times 2$
$\tt 2$：$x \times 2 + 1$
$\tt U$：$\left \lceil {\dfrac{x}{2}} \right \rceil$
$\tt L$：$x-1$
$\tt R$：$x+1$

直接用数组维护二进制下位数是 $\mathcal {O(n^2)}$ 的，因为涉及到进位，但是手写一个 bitset 就能 $\mathcal {O(\dfrac{n^2}{w})}$ 草过去，%Kowenxrz。另外一个思路就是线段树维护这个数的变化，就能做到 $\mathcal {O(n \log n)}$，很多人场切，可惜我太蒟了，呜呜呜。

赛后看题解发现一种超级巧妙的思路：可以注意到，如果你先移到父节点再左右平移和先平移再移到父节点的结果是一样的！有了这个性质，就可以不用边操作边进位了，只需把整个数存到最后一起进位就可以 $\mathcal {O(n)}$了。

最后统计答案时，枚举往上跳到了哪一层，更新即可。

for(int i=0;i<=len&&now<=(1ll<<20);++i){
  now=now*2+a[i]-b[i];//跳到当前这层两个数的位置差
  ans=min(ans,(ll)(len-i)*2+abs(now));//算上向上跳的层数
}
cout<<ans+abs(la-lb);//要先到同一层再往上跳

T4 网络流。

2023.11.16

CWOI

本来以为这场能打得很好，不到 $2h$ 就“过”T3了。结果异或和为 $0$ 的情况根本就没考虑对，还手造几组以为对了，也不去对拍。以后该拿的分拿完了一定要去检查前面的题，写对拍，测极限数据，看是否有情况考虑漏，不要再无所事事了。

T1 考虑从下往上删，这样不会对后面的操作产生影响。对于孤立点在删完能删的之后统一考虑，每一对对答案的贡献为 $2$ （先换到一起再删）。$\mathcal {O(n)}$。

T2 要把 $a$ 分为几个连续段使他们的按位或和相同，那么这几段的或和再或起来一定是整个序列的按位或和（因为每一位都一样），同时靠在一起的几段也能合并成一段，因为他们或起来结果是不变的。于是原问题就转化成了有多少个 $a$ 存在一个 $p$，使得 $\mathrm {OR}_{i=1}^{p}a_i = \mathrm{OR}_{i=p+1}^{n}a_i = \mathrm{OR}_{i=1}^{n}a_i$。

此时我们设 $l_i$ 为最左边满足 $a_{l_i}$ 在二进制下第 $i$ 位为 $1$ 的位置，$r_i$ 为最右边的位置。那么要想满足条件，$p$ 就必须 $\in [L,R] = \bigcap_{i=1}^{k-1} [l_i,r_i]$（因为只有这样才能满足或的那个式子，两边同一位相等）。

那此时我们枚举这个分割点 $p$，$p$ 在 $[L,R]$ 这个区间中的方案数即为 $((2^p-1)(2^{n-p}-1)+1)^k$。因为前面的每一位都可以放与不放，但是全放 $0$ 不合法，因此 $-1$，后面同理。每一位 $k$ 种放法，因此如此。但是这样的话 $p$ 可以取到 $[L,R]$ 中的每一个值算重了，于是强制让 $p = L$，减掉多余的方案，得到：$((2^p-1)(2^{n-p}-1)+1)^k - ((2^p-2)(2^{n-p}-1)+1)^k$。

于是，合法序列的个数就出来了：$1+\textstyle \displaystyle\sum_{i=1}^{n}((2^p-1)(2^{n-p}-1)+1)^k - ((2^p-2)(2^{n-p}-1)+1)^k$

其中，$+1$ 是全零序列也是合法的。总情况为 $(2^n)^k$，因此，概率为： $\frac{1+\textstyle \displaystyle\sum_{i=1}^{n}((2^p-1)(2^{n-p}-1)+1)^k - ((2^p-2)(2^{n-p}-1)+1)^k}{(2^n)^k}$

T3 sto BINYU 大佬的简单解法。求有多少种把 $a$ 划分为若干连续段的方案，使得每一段的异或和相同。首先，因为每一段异或和相等，那么我们分分的段数的奇偶讨论：当分了偶数段时，异或和一定为 $0$，所以只有整个序列异或和为 $0$ 时才有结果；当分了奇数段时，可以先把偶数段异或成 $0$，剩下一段的异或和一定等于整个序列的异或和。所以，每段的异或和都等于整段的异或和。

记 $sum_i$表示前 $i$ 个数的异或和，$cnt_i$ 表示前 $i$ 个数中 $sum$ 为 $0$ 的个数，$f_i$ 表示分完前 $i$ 段的方案数。

先考虑 $sum_n$ 不为 $0$ 的情况,设 $v=sum_n$。因为此时每段的异或和都为 $sum_n$，因此，每段末尾的 $sum$ 一定是 $v,0,v,0...$ 交替的，才能满足条件。那么，转移就很显然了,对于每个 $sum_i=v$ 的 $i$ 有：$f_{i} = \displaystyle\sum_{sum_j=v,j<i}^{}f_j(cnt_i-cnt_{j-1})$。这个式子相当于在两个 $sum=v$ 的位置之间选一个 $sum=0$ 的位置让他们连起来，中间 $sum=0$ 的个数就是 $cnt_i-cnt_{j-1}$。把这个式子化一下：$f_i = cnt_i\displaystyle\sum_{sum_j=v,j<i}f_j-\displaystyle\sum_{sum_j=v,j<i}^{}f_j cnt_{j-1}$。前面的一坨前缀和优化，后面的一坨也可以前缀和优化，那我们就能 $\mathcal {O(1)}$ 转移了。时间：$\mathcal {O(n)}$。

这时再考虑 $sum_n$ 为 $0$ 的情况。可以发现，交替规律还是一样，不过最后一个就是以 $0$ 结尾了。而且异或和为 $0$ 时不一定需要 $v=sum_n$ 了，只需要所有 $v$ 相等即可。因此，把所有相等的数的位置存下来。这个时候，先不管最后一个 $0$，把前面的相等数按上一种情况的做法分好，得到方案。最后再补一个 $0$ 即可。同时还要考虑 $v=0$ 的情况，最后一个 $sum_n$ 必须选，前面共有 $cnt_{n-1}$ 个位置为 $0$，每个位置可以选或不选，因此共 $2^{cnt_{n-1}}$ 种分割方法，答案累加即可。

T4 还没看。

2023.11.18

CWOI

暴力确实打满了，但是性质分没打。下次可以多打一点性质。

T1 贪心找后面最大的和前面的换，特判已经降序的序列，可以交换两个相同的数。

T2 计数题。设 $f_{i,j}$ 表示前 $i$ 个数中，最后 $j$ 个数互不相同（也就是倒数第 $j+1$ 个数出现重复）的序列数。转移可以填一个与之前都不相同的数,$f_{i,j} \gets (m-j+1)f_{i-1,j-1}$（$m-j+1$ 就是有这么多个不同的数可以填）；也可以填一个与前面的数重复的数,则 $f_{i,j} \gets \displaystyle\sum_{k\ge j} f_{i-1,k}$。直接转移是 $\mathcal {O(nm^2)}$ 的，用前缀和优化一下 $\sum$ 即可做到 $\mathcal {O(nm)}$，有 $60$ 分。

再观察一下，$m \leq 200$ 而 $n \leq 10^9$ ，猜一下应该是 $\mathcal {O(m^3)}$ 或 $\mathcal {O(m^3 \log n)}$。同时，这个式子非常可以用矩阵优化。因此，写一个矩阵优化即可。$f_{i}$ 只与 $f_{i-1}$ 有关，因此可以滚掉一维。转移矩阵怎么推呢？注意到 $f_{j}$ 会从所有 $k \ge j-1$ 的 $g_{k}$ 转移过来，所以在 $\ge j$ 的位置放 $1$，在 $j-1$ 位置放 $m-j+1$，前面的放 $0$ 即可。

T3 大模拟，还没写过。upd：不写了，艹！大模拟浪费我的时间和青春，现在交全部mle。

T4 Ynoi

2023.11.20

NOIP vp

$100+40+0+36=176$，被一众大佬薄纱。

本来想T2冲一会儿就走的，但是正解没调出来去打暴力时犯了很sb的错误，导致11点过才去看后面的题，匆匆写了个T4暴力 dp 就跑路了。打得一般，考试心态还要放好一点，不要调不出题时乱了阵脚。

T1 把每个字符串的最大，最小字典序先求出来，每次判断一个时用它的最小去比较其它的最大，如果还不合法肯定就为 $0$ 了。

T2 先思考什么时候必须为 $U$，只要根据关系得到当前值 $x=\neg x$，那么 $x$ 只有为 $U$ 时才成立。我们可以用一种并查集思想来做，记一个 $flag_i$ 表示第 $i$ 个数是否需要 $\neg$，对于赋值操作，直接把当前点的父亲变为 $T,F,U$ 三个中的一个，并把 $flag$ 变为 $0$。把一个数赋给另一个数的话直接更新父亲，如果为 $-$ 操作，那么 $flag_x=flag_y xor 1$，否则直接继承。

要满足上面所说的条件，必须要有环出现，于是对于每个点暴力跳父亲判环，在跳的同时路径压缩并且从上至下更新 $flag$，每次 $flag_x xor flag_{fa_x}$。如果最后祖先的 $flag$ 为 $1$，那么说明必定有环出现并且该环上的点都要为 $U$ 才满足条件。因此，对于这些环跑 bfs 打标记即可，最后看有多少点被打上了标记就是答案了。

T3 神秘题。

T4 stO 六楼溜刘。一个普通的 dp 是设 $f_{i,j}$ 表示前 $i$ 天，最后 $j$ 天连续跑步的最大能量。转移时直接看第 $i$ 天有没有奖励，转移即可。这样做是 $\mathcal {O(nk)}$ 的，但是 $n,k$ 都到了 $10^9$ 这一量级，很明显是不好做的。但是 $m$ 只有 $10^5$，因此可以从这里入手。

我们可以先转化一下，把 $x,y$，转换为 $l,r$，$l=x-y+1,r=x$。这样就变成了一个区间问题。再转化一下，因为考虑要选那些点是不太容易的，那么就去看不选那些点。因为如果在一段奖励线段上选了一些点但又不选完，那么不选他们肯定更优(这样少减了一些 $d$，增加的值却没变)。所以，每条线段一定是要么选完要么一点不选。因此我们设 $f_i$ 表示第 $i$ 个分界点不选的最大价值。那么枚举上一个分界点 $j$:$f_i=\displaystyle\max_{j<i}^{p_i-p_j-1\leq k} \{f_j-d\times(p_i-p_j-1)+w(j,i) \}$。其中 $w(j,i)$ 表示覆盖完 $[p_j+1,p_i-1]$ 的价值和。可以发现 $w(j,i)$ 相当于固定右端点 $i$ 去查询左端点的一坨东西。那么我们考虑一条 $[l_i,r_i]$ 会对答案造成什么贡献。当 $r_i$ 等于当前枚举的坐标时，在 $l_i-1$ 之前的分界点到当前点都能将其完全覆盖，因此直接把 $[1,l_i-1]$ 贡献加上就行。

把转移式里面提出来：$f_i=-d\times (p_i-1)+\max \{f_j+d\times p_j+w(j,i)\}$，大括号中用线段树维护即可。同时用一个指针维护，使区间长 $\leq k$，此题就做完了。

喜报：今天喜提陶片一个，禁言 $7$ 天。

2023.11.22

CWOI

今天T2和T4暴力都写挂了，感觉状态不太行。并且签到做得太慢，差不多做了 $1.75h$ 才写完，做法又过于复杂，别人 $30$ 多行贪心，我写了 $100$ 多行线段树。以后要更快更好地想出做法，不能在签到上浪费时间，争取在 $60$ 分钟以内写+调出，把时间留给后面的题。多打暴力和性质，才不至于只拿个大众分。

T1 先写我的写法。因为 $w_i-w_j \ge \lvert x_i-x_j \rvert$，所以 $w_i-w_j$ 一定是 $\ge 0$ 的才可能满足条件。所以可以按照 $w$ 从小到大排序，那么最大的 $w_i$ 一定是要操作的，因为没有更大的 $w_j$ 来使 $i$ 满足条件。于是倒着枚举，哪个点没染黑就删哪个点。但是删了后还会影响其他点，直接维护肯定T飞。于是考虑在枚举到每个点时看他是否会被之前删掉的点带着删掉。分类讨论一下，当 $x_i\leq x_k$ 时（$x_k$ 为先前被删的点的 $x$ 值），因为我们是按 $w$ 从小到大排的序，因此 $w_k \ge w_i$，故：$w_k-w_i\ge x_k-x_i$，移项得：$x_i-w_i\ge x_k-w_k$ 。只需要存在一个 $k$ 满足条件就能让 $i$ 被删了，因此只要 $x_i-w_i \ge (x_k-w_k)_{\min}$ 即可。当 $x_i>x_k$ 时，$x_i+w_i \leq (x_k+w_k)_{\max}$。其实这就是个区间修改，区间查询最值，上线段树就完了。$x_i$ 很大，离散化即可。

题解：根据 $x$ 大小分讨把绝对值去掉（跟上面一样），这样题目就转化成了：二维平面上有 $n$ 点，每个点坐标为 $(x_i-w_i,x_i+w_i)$，删一个点会把它左下角的点全部删除，问最少删几次。那么我们只需要删除右上角没有点的那些点，因为删除任何点都不能连带删除它们，而把它们都删除后，可以连带删除其他所有点。按一维从大到小排序（相同时按另一维从大到小），前缀 $\max$ 的数量就是答案。复杂度 $O(n \log n)$。更详细可见 BIG_CUTE_BUG 大佬的题解。

T2 容斥。可以先把奇偶性去掉，每一行的长度就可以表示为 $2x_i+p_i$。于是就能得到 $2x_i+p_i \in [a_i,b_i]$，解出 $x_i \in [a_{i}^{\prime},b_{i}^{\prime}]$。同理可通过 $\sum 2x_i+p_i \in [S,T]$ 得到 $\sum x_i \in [S^{\prime},T^{\prime}]$。对于 $\sum x_i$ 可以把它转化成 $\sum x_i \leq T^{\prime}$ 和 $ \sum x_i <S^{\prime}$ 的方案进行相减。但对于单独的 $x_i$ 还有两个边界不好处理，这时就可以容斥去掉一个边界。

枚举一个子集 $S$，强制让 $S$ 中的 $i$ 满足 $x_i \ge b_{i}^{\prime}+1$，不在 $S$ 中的 $i$ 需要满足 $x_i \ge a_{i}^{\prime}$
，这时求一个 $sum = \sum l_i$（$l_i$ 为边界之和），若总的上界为 $k \in[S^{\prime},T^{\prime}]$，那么剩下的行数就是 $k-sum$。我们现在要把他们分到 $n$ 个组里，可以为空，那就把空的当成一个新组，就有 $n+1$ 个组。因为可以为空不好处理，我们就再增加 $n$ 组，让他变成不能为空。于是就相当于在 $n+1$ 组中插 $n$ 块板，有 $k-sum+n$ 个空。$C_{k-sum+n}^{n}$ 即可。容斥就是奇数减偶数加，跟集合的求交类似。

还有一点是模数不一定为素数，那就不能求逆元。注意到 $13!$ 是在 long long 范围内的，所以边算边约分就行了。

T3 换根 dp。sto BINYU Zi_Gao orz。对于每条路径都求长度和乘积是不好做的。我们可以考虑枚举两两叶子之间的 lca，再进行答案统计。对于一个 lca，我们可以把原问题变为经过这个点的三条链，从中选两条拼成路径，一条作为高度。贪心地想就是选最大的三条链，但这样容易算重。于是我们可以让高度尽量大，这样去枚举其它点时选择的路径一定不会包含当前点的三条链中的最小路径（用更大的高度那条路径去替换会更优）。于是换根即可。

设 $mx_{u,0}$ 表示从 $u$ 到他子树内的最长链的长度 $1$ 为次长，$2$ 为次次长。再设 $c_{u,0,0}$ 表示能为 $u$ 提供 $1$ 条长为 $mx_{u,0}$ 的链的数量，最后一维为 $1$ 则表示提供两条。第一次 dfs 直接从儿子向上更新即可。第二次换根，则需要考虑 $mx_{u,0}$ 是不是由 $v$ 提供。三种情况：

全部由 $v$ 提供，那么 $v$ 就从 $mx_{u,1}$ 和 $c_{u,1,0}$ 转移。
部分由 $v$ 提供，那么 $v$ 就从 $mx_{u,0}$ 和 $c_{u,0,0}-c_{v,0,0}$ 转移（去掉 $v$ 给 $u$ 提供的部分）。
不由 $v$ 提供，那么 $v$ 从 $mx_{u,0}$ 和 $c_{u,0,0}$ 转移。

最后统计答案就分讨三条链是由 $mx_{u,0},mx_{u,1},mx_{u,2}$ 得到的就行了。

T4。直接建边边数过多，不好处理。我们可以考虑建一些虚点，让 $u_i$ 和 $n+i$ 连边，$v_i$ 和 $n+i$ 连边。设这些新连的点为白点，与白点有连边的点在原图中一定相连，并且一定是一棵树。删除操作相当于把 $u$ 的子白点连到他的父白点上，使用并查集维护即可。

这时再考虑如何算答案。把三元组 $(a,b,c)$ 变成 $(a,x,b,y,c)$ （$x,y$ 就是白色点），再记 $f_u$ 表示白点 $u$ 的黑儿子个数，分情况讨论一下：

当 $x=y$ 时，相当于在 $x$ 的邻点中任选三个，$x$ 的邻点有 $f_x+1$ 个（因为要算上他的父亲）。故对答案的贡献为 $\displaystyle\sum_{x \in white} (f_x+1)f_x(f_x-1)$。
当 $x \ne y$ 时，若 $x,y$ 为 $b$ 的儿子，那么相当于在 $x,y$ 中选 $a,c$，贡献为 $\displaystyle\sum_{x,y \in son_b,x \ne y} f_x f_y$。变一下形，即 $(\sum f_x)^2 - \sum (f_x)^2$。
当 $x$ 为 $b$ 父亲，$y$ 为 $b$ 儿子时，相当于我们要在 $x$ 子树中找 $a$，$y$ 子树中找 $c$，其答案为 $2 \times f_x \displaystyle\sum_{b \in son_x}\displaystyle\sum_{y \in son_b}f_y$。乘二是因为三元组是有序的，$(a,c),(c,a)$ 应该被算两遍。

这时再记 $g_{u,u\in black}=\displaystyle\sum_{x\in son_u}f_x$，$h_{u,u\in white}=\displaystyle\sum_{x \in son_u}g_x$。

那么分析一下 $f$ 相当于一级儿子，$g$ 为二级儿子，$h$ 为三级儿子。每次删除一个点会影响他的一级儿子与他的上三级父亲，对于儿子，每个点只会被更新一遍，总复杂度 $O(n)$，对父亲每次只有 $3$ 个，复杂度 $O(1)$。故全局复杂度 $O(n)$。更新把 $h,g,f$ 更新即可。

2023.11.24

CWOI

T1 最大的子段和一定是 $[1,n]$，第二大一定是 $[2,n]$ 或者 $[1,n-1]$。以此类推，我们就可以用一个大根堆，取出队首，把当前值计入答案（因为他一定是当前最大的），再把值去掉左、右端点，放进堆中。到 $k$ 个就输出。

T2 高级 dp。一个暴力 dp 是设 $f_{u,i}$ 表示 $u$ 这个点值为 $i$ 的方案数。转移从儿子转过来，$f_{u,i}=\displaystyle\prod_{v \in son_u} \displaystyle\sum_{\lvert j-i \rvert \ge k}f_{v,j}$。这样有 $20$ 分。观察发现，转移的 $f_v$ 是连续的一段，前缀和优化有 $40$ 分。

接下来就是人类智慧时间。打表可以发现 dp 值中间有很长一段都是相同的（具体证明不太会，可以去看题解），于是我们可以只关心前面一段和后面一段的 dp 值，中间算一个就行了。易得树的最大深度是 $n-1=99$，又因为 $k\leq 100$,所以 dp 值一端最多只有 $99\times 100$ 个不同的，接下来就是一段相同的数。于是 $O(n^2k)$ 转移就行了。

T3 一个直接想法是对于每个询问二分答案，但是时间复杂度 $O(Tn^2 \log n)$ 的，不能接受。我们的瓶颈在于如何快速判断一个 $\text {mid}$ 是否可行。可以先预处理一个 $f_{i,j}$ 表示以 $(i,j)$ 作为右下角的最大边长是多少，dp 转移即可。这样在 check 时只需要判定在 $(x_1+mid-1,y_1+mid-1)$ 到 $(x_2,y_2)$ 中的最大值能否 $\ge mid$。因为要想边长为 $mid$，那么到左上角的距离至少要 $\ge mid$。又因为如果在这段区域中有值 $\ge mid$，那么一定能把他的边长缩小为 $mid$，从而使 $mid$ 合法。于是，用二维 st 表维护这个东西即可。

T4 因为不够细心而读错题了。下次做题不能太着急，要认真读完题再开始做。

题目说的是保证存在某两个城市之间的最短路，使这 $k$ 个特殊城市在这条最短路上。我却看成了要求一条最短路使得 $k$ 个特殊城市都在这条路上。根据题目的保证，我们可知这 $k$ 个城市串起来一定是条链。那我们随便提一个点起来，离他最远的一个特殊点一定是这条链的端点。我们再找到离这个端点最远的特殊点就得到另一个端点了。于是算出这两端点之间的距离就是答案了。两遍 dijkstra 即可。代码超级短。

2023.11.27

CWOI

T1 做了 $3h$，没救了。以后签到必须想清楚再写，今天就是写了一个换根，结果一点用没有，浪费了一个多小时。

T1 看我写的题解吧。

T2 既然他是 E2，那就先思考 E1 怎么做，也就是不带修改。一个 trick 是：让任意两个数的乘积不为完全平方数，我们可以先把每个数质因数分解，然后把每个因子只留一个再乘起来得到新的 $a_i$。因为要为完全平方数，那么一定要所有质因子的次幂为偶数，于是已经为偶数的可以不管了，只保留奇数。这样就可以通过看一段区间中是否有两数相同就可以知道其乘积是否为完全平方数了。

有了这个性质就可以设 $f_i$ 表示以第 $i$ 个数结尾，前面的最小划分组数。$f_i=\min \{f_j+1 \}$，满足 $[j+1,i]$ 没有相同的数。直接转移是 $O(n^2)$ 的。但是我们注意到 $f$ 一定单调递增，那么只需要找到最小的 $j$ 满足 $[j+1,i]$ 没有重复的数就行了。于是预处理出这个东西，$O(n)$。

再来思考带修怎么做。这时新增状态：$f_{i,j}$ 表示以第 $i$ 个数结尾，修改了 $j$ 次的最小组数。那么一个区间的修改次数就是其重复的数的数量。类比不带修的情况，要预处理出一个 $pre_{i,x}$ 表示第 $i$ 个位置，修改了 $x$ 次的最小位置。那么用桶预处理出这个东西，就能 $O(k^2)$ 转移了。时间：$O(nk^2)$。

T3 看我写的题解吧。

T4 nb 计数题。改了，但是写不动题解了。

2023.11.29

CWOI

最低档暴力分，还没打满。前三题一道不会，就一直来回横跳，一道没写出来，垫底了。

T1 直接求二维前缀和空间是开不下的。注意到每行的字符串最多只有 $100$ 个字符，也就是循环节最多只有 $100$ 个。那么我们可以对于每种长度的循环节单独求前缀和，因为长度相同的串其多余的部分都是相同的，所以长度相同的一起求即可。这样把所有长度的前缀和加起来即为答案。

T2 把 $x$ 每一位拆开，那么 $x+mirrored(x)$ 其实就相当于$x_1+x_{len},x_2+x_{len-1},\dots$（不进位），又因为要等于 $z$，那么将 $x$ 的每一位进位后就是 $z_1,z_2,\dots$。又因为 $x_i+x_{len-i+1}=x_{len-i+1}+x_i$，所以我们可以让 $z$ 转化成不进位的形式，这样就必须满足 $z_i=z_{len_z-i+1}$。所以，用两个指针一个从左，一个从右，实现把 $z$ 转化成不进位的形式，如果不能满足 $z_i=z_{len_z-i+1}$ 那就 return 0，否则每个位置的值就知道了，且互不影响，可以用乘法原理求出所有方案。对于每一位，如果他的值 $z_i < 10$，那就有 $z_i+1$ 种放法（$0 \sim z_i$），$\ge 10$ 就有 $19-z_i$ 种放法。注意要判一些情况，如首位为 $1$，可以是长度与 $z$ 相同的 $x$ 得到，也可以是长度比 $z$ 少 $1$ 的 $x$ 通过进位得到等。

T3 观察题目的放到最后这一过程，其实就是将第一个前面最大的数前面所有的数移到最后，并产生这段数长度的贡献。于是可以把数列看成一个环，移后相当于换起点，对于每个数直接向后找第一个比他大的数，加贡献即可。并且要将这些数删掉，可以用树状数组维护，删数相当于把这个数 $-1$，求和直接求和即可。注意环上求和需要判下标大小，数要离散化，有可能有相同的数都要存下来。

2023.12.1

CWOI

T3 打了 $60$ 分，但是 T2 只打了最低档暴力，导致分还不算很高，如果两题打满就跟 rk1 一个分了（。

T1 是个构造题，但是我不会啊，怎么办？暴搜打个表，发现固定 $n$ 对于不同的 $k$ 第一问答案都一样，就是一个公差为 $2$ 的等差数列。再观察最优解的形式，发现是前面放 $k-1$ 个 $1$，最后一个 $1$ 放在后面所有 $0$ 的正中间就可以了。注意特判 $k=0$。

题解证明：将数组做前缀和，令前缀和数组中 $1$ 的个数为 $X$，$0$ 的个数为 $Y$ ，则答案为 $X \times Y$ ，由于 $X+Y=n+1$，
所以我们只需要让 $X, Y$ 尽量接近，一种简单的做法是先在最前方放 $k-1$ 个 $1$，再在后面的位置中选择最优
的位置放一个 $0$，可以发现，这样构造一定能够做到 $X \times Y$ 取到最大。

T2 以后要仔细阅读题面的信息和限制。这道题的关键就藏在这里：保证任何两个区间都是不相交或包含的关系。有了这个性质，就可以把所有区间看成一种树形关系，小区间就是包含他的大区间的儿子。而一个区间要满足所有颜色互不相同，那他的子区间也就一定会满足这个条件。于是在做时就从小区间开始往上跳父亲，满足条件就更新答案，并且合并区间，为下一步跳做铺垫。实现可以用线段树 + umap + 并查集。

T3 一棵树的价值是 同色点距离的最大值，看到树上距离最大值很难不往树的直径上面想。于是我们以树的直径进行讨论。设直径的两个端点分别为 $x,y$。那么在 $x,y$ 同色时答案一定是直径长度。如果 $x,y$ 异色，那么我们可以枚举这个答案 $d$，并钦定是由直径端点和另外一个点造成贡献。因为 $d$ 现在是最大长度，所以和 $x$ 距离 $>d$ 的点要与 $x$ 异色，$y$ 同理。这样剩下的都是到 $x,y \leq d$ 的点了。必须要有 $d$ 这个答案，直接选好像不太好做，可以反着来：用总方案减去不合法方案。假设到 $x,y \leq d$ 的点有 $a$ 个，到 $x,y < d$ 的点有 $b$ 个，那么在 $a$ 个中随便上色的方案是 $2^a \times 2$，乘 $2$ 是因为直径异色，同理在 $b$ 中就是 $2^b \times 2$。又因为我们这个方案是强制让 $> d$ 的点不能产生贡献，于是用 $>d$ 不能产生贡献的方案 $-$ $\ge d$ 不能产生贡献的方案就是 $=d$ 能产生贡献的方案。于是答案加上 $(2^{a+1}-2^{b+1}) \times d$ 即可。当 $d < \min(dis(x,i),dis(y,i)$ 时就不合法了，直接退出即可。

2023.12.5

CWOI

$8:30$ 切了T1，接下来就在罚坐了。

T1 一个显然的方程是 $f_i=f_{i-1}+f_{i-2}+f_{i-k}+1$，但是直接转移是 $O(n)$ 的，不可行。观察发现这玩意儿可以直接矩阵转移，不过最后的答案是$\displaystyle\sum_{i=1}^{n}f_i$，所以在答案矩阵中还要加上一个 $sum$ 来记录所有 $f$ 的和。

T2 限制 border 的长度 $\leq$ 字符串长度除以 $2$ 上取整，也就是限制了前缀和后缀在字符串中至多能够有 $1$ 个字符是重叠的。可以设 $f_{i,x,y}$ 表示长度为 $i$ 的完全相同的子序列的对数，其中第 $1$ 个子序列结束于 $x$,第 $2$ 个结束与 $y$。可以注意到 $i$ 没用，那么去掉 $i$。同时枚举一个 $p$ 作为中间点，满足 $i\leq p$，$j\ge p$。但是答案是求每个 border 的长度之和，那么我们就要再记录一个长度和 $g_{i,j}$ 表示这样的子序列的长度和。对于一个 $s_i=s_j$ 的位置，$f_{i,j}=\displaystyle\sum_{x<i}\displaystyle\sum_{y<j}f_{x,y}$。而 $g$ 怎么转移呢？注意到其实就是让之前的所有 border 的长度 $+1$，原来的 border 就有 $f_{i,j}$ 个。因此 $g_{i,j}=\displaystyle\sum_{x<i}\displaystyle\sum_{y<j}g_{x,y}+f_{x,y}$。直接做是 $O(n^4)$ 的，二维前缀和优化可做到 $O(n^3)$。

T3 观察到最后的形式一定是每个点至多有 $1$ 条出边，一共有 $n$ 条边，那么就是一个内向基环森林，相当于一颗树 $+$ 一个环。于是暴力的想法是把所有边建出来，用 Kruskal 的思想求最大基环森林。具体的先按边权从大到小排序，再用一个并查集维护。不过因为有环所以要多加一个 $tag_u$ 表示 $u$ 这个连通块是否包含环。合并时如果 $tag_{f_u}$ 和 $tag_{f_v}$ 都为 $1$ 那就直接跳过，因为不能有两个环。当 $f_u \ne f_v$ 是直接加答案，并把 $tag$ 更新。如果 $f_u=f_v$，那么在 $tag_{f_u} \ne 0$ 时可以把 $u,v$ 连起来，并把 $tag$ 更新。正解其实观察可以发现：很多边都是没用的，只用存一些边就行了。因为连完最大的点后就已经是个树了，再加入次大点就能形成环。因此，只需要最大点，次大点分别与其他点连边就行了。

2023.12.7

CWOI

大众分。不过今天记住了检查和写拍，T2静态查出一个错，$65 \to 100$。

T1 一开始写了个找循环节，但是这玩意最坏是 $10^9$ 的。过了很久才换了种写法，把列竖式的形式写出来，发现小数的第 $i$ 位就是 $\displaystyle\dfrac{n\times 10^i}{m} $ 的最后一位，根据竖式也可以得出他就是用上一次的答案 $\times 10$ 再减去他模 $m$ 再除以 $m$（不好表示，建议在纸上写写），直接从 $l$ 到 $r$ 算就行了。

T2 答案肯定有单调性。于是问题转化成了是否有一个长度为 $k$ 的区间满足其逆序对个数 $\ge x$。滑动窗口+树状数组即可。

T3 $u$ 是优秀的相当于 $u$ 是重心。于是问题变成最少多少次操作能让 $u$ 成为重心。我们可以先把原树的重心找出来，那么现在只有包含重心的连通块大小 $>\frac{n}{2}$，我们每次就相当于要把重心的大小减小一些。而每次操作完都是把断开的连通块连到 $u$ 上，只考虑怎么删就行了。

对于那些不和 $u$ 在同一子树的连通块删去后会让重心减小 $siz_v$，而和 $u$ 在同一连通块的 $v$ 只会减少 $siz_v-siz_u$。有了这些，相当于选最少的数让重心的大小不超过 $\frac{n}{2}$，肯定从大到小选。然而 $siz_v-siz_u$ 和 $u$ 有关，每次都会改变，因此用一棵权值线段树维护即可。单点修改，区间查询。

2023.12.9

CWOI

不会推式子，数学学得有点菜。

T1 观察到一开始一整行都是 $0$ 或者一整列都是 $1$ 对答案没有影响，他们只需要最后一次覆盖就行，于是可以把他们替换成 $\text ?$，$\text ?$ 可以是 $0,1$（这是因为这一行/列都是最后一次被覆盖的，他的上一次是 $0,1$ 都无所谓。这个想法在ABC329E 出现过）。然后再继续找是否又有了全 $0$ 的行，全 $1$ 的列，有就把它们覆盖掉。直接模拟时间会炸，观察发现他就是把每行的 $0$ 的个数从大到小排序后删，删完后对所有列产生 $1$ 的贡献，列同理。于是直接排序后再 $O(n^2)$ 做就行了。

T2 因为有一对数要相同，因此我们可以先选 $n-1$ 个数，方案就是 $C_{m}^{n-1}$。然后考虑选那个重复的数，有 $n-2$ 种选法（不能与最大值相同）。因此这部分的答案就是 $C_{m}^{n-1}\times (n-2)$。再来看其他数的排布。把它们从大到小排序后，每个数都可以放在最大值的左边或者右边，不考虑相同的两个数，就有 $2^{n-3}$ 种方案。因此答案为三式相乘，使用卢卡斯定理计算组合数。

T3 容斥 dp。设 $f_{i,j}$ 表示前 $i$ 种数，有 $j$ 个位置被强制固定（直接放原来的 $a_p$，不能再变）的方案数。那么有：$f_{i,j}=\displaystyle \sum_{j=0}^{sum}\displaystyle\sum_{k=0}^{\min(j,sum)}f_{i-1,j-k}\times C_{cnt_i}^{k}\times C_{sum-j}^{cnt_i-k}$。其中 $cnt_i$ 表示第 $i$ 种数的个数，$sum$ 表示前 $i$ 种数的个数之和。方程的意思就是现在多了 $k$ 个位置被强制固定，而这 $k$ 个位置就是由第 $i$ 种数选 $k$ 个得到，因此是 $C_{cnt_i}^{k}$。同时现在还剩下 $sum-j$ 个位置没被固定，$cnt_i-k$ 个第 $i$ 种数没被选，因此再这空着的位置中放 $cnt_i-k$ 个数的方案就是 $C_{sum-j}^{cnt_i-k}$。最后求答案需要容斥，因为 $i$ 个位置被限制肯定会包含 $i+1$ 个位置被限制的情况。故答案为 $\displaystyle\sum_{i=0}^{n}f_{m,i}\times (-1)^i$ ，$m$ 是数的种类个数。

T4 签到题。记 $num_i$ 表示前 $i$ 个位置的和，把 $\texttt{(}$ 看作 $1$，$\texttt{)}$ 看作 $-1$。那么一个序列是合法的当且仅当 $num_n=0$ 并且 $\displaystyle\min_{i=1}^{n} \{num_i\}=0$ 。于是用线段树维护这个 $\min$，区间修改单点查询就行了。

2023.12.13

CWOI

以后得多练 data structure 了，感觉对莫队、分块、主席树一窍不通。不像图老师和龙哥两个 ds 巨佬，膜拜他们%%%。

T1 这出题人纯属**。对于 $k_0$ 的定义非常不清晰，导致我浪费了 $30$ 分钟去搞懂样例。题解就是每次把少的加 $2$，相当于答案是 $\lfloor \frac{r-l}{2} \rfloor +1$。然而 lht 在晚自习说每次加 $3$ 也对，验证过后确实是这样的，出题人真的没救了。

T2 区间询问，又能离线，容易想到莫队。首先思考如何去计算答案：我们可以把每个数变成他的质因子的乘积（每个质因子次幂都为 $1$），然后需要复制的就是所有质数和 $1$。对于质数，可以把两个不同的乘起来，这样只消耗 $1$ 的代价消除了两个质数，因此按照这个策略消是最优的。这里有个结论：当出现次数最多的质数的个数 $\ge$ 质数总数 $/2 +1$ 时，代价就是最多的个数加上 $1$ 的个数。否则就是质数总数 $/2 +1$ 再加 $1$ 的个数。加上 $1$ 的个数是因为 $1$ 只能单独与一个合数乘起来后再消除。结论的前半部分比较显然，后半部分相当于两两配对，再加上可能多出来的一个。

有了这个结论，那我们就只需要求区间出现次数最多的质数的出现次数了。这不就是区间众数吗？于是，某个煞笔开开心心地粘了一个蒲公英分块上去，再加上细节的修改，一共 $5.3$ KB 的代码，还 TLE 了?直接气晕了啊。既然分块常数大，那我们可以换一个方法：回滚莫队。好写，常数又比分块小很多，确实挺不错的。注意判一下 $-1$ 就行了。

T3 答案是有单调性的，可以考虑二分答案。对于原图，如果在一个边双中的点，那么一定可以定向使他们互达，因此就不用管了。那么缩完点后图就变成了一棵树，这时树上差分判断是否合法即可。

2023.12.14

CWOI

全场最大消愁。全程不会 T1，赛后才发现是憨憨递推题。感觉最近自己有被降智，很多思维题反应不过来，这方面还有待提升。

T1 把 $f$ 的递推式拆开手摸一遍，就会发现 $f_{l,r}$ 一定是通过他的所有子区间异或得来。就比如 $f_{1,2,3} = f_{1 \oplus 2,2 \oplus 3}=f_{1 \oplus 3}$，再比如要得到 $1 \sim 4$，就肯定要先知道 $1 \sim 2$，$2 \sim 3$，$3 \sim 4$，再得到 $1 \sim 3$，$2 \sim 4$，最后 $1 \sim 4$。而这个过程的最后一步都是两个区间合并为一个区间，因此 $f_{l,r}=f_{l,r-1} \oplus f_{l+1,r}$。这个可以先预处理，再求一个 $mx_{l,r}$ 表示 $l \sim r$ 的答案，简单转移即可。

T2 考虑换根 dp。设 $f_{u,i}$ 表示在 $u$ 的子树内，对 $u$ 造成了 $i$ 贡献的点的个数。那么 $f_{u,i}=\sum f_{v,i+1}$，因为距离的递增会造成贡献的递减。这时再考虑换根，那么 $f_{v,i}=f_{u,i+1}-f_{v,i+2}$。相当于从 $v$ 子树外的所有点转移，但是可能会计算到 $v$ 子树内的点而造成重复，因此要减掉多余的部分。$u$ 的答案就是 $\displaystyle\sum_{i=1}^{V}i\times f_{u,i}$。

T3 神奇 dp。首先将附魔的过程看成一棵树，父亲与儿子的一条连边表示父亲作为主物品，儿子作消耗品的一次附魔。于是对于一个有 $d$ 个儿子的点，他的累计惩罚就是 $\sum_{i=1}^{d-1}2^i = 2^d-1$。在第 $i$ 层的点经验消耗就为 $i \times a_u$ （因为每往上合并一层都会把他多算一遍）。因此，一个直接的贪心策略是把 $a_i$ 大的优先往上放，这样他被累加的次数就会尽量少。故我们只需要把 $a$ 从大到小排序后考虑怎么构造树形态就行了。

直接做没什么入手点，可以挖掘一些性质。

父节点的儿子数量一定 $\ge$ 其儿子的儿子数量。因为如果儿子的儿子 $>$ 了父亲的儿子数，那么把儿子的一些儿子移到父亲上，减少的惩罚是不少于增加的惩罚的，并且层数还减小了，所以答案一定更优。
同层的两个节点，度数差不会大于 $1$。否则可以进行移动让惩罚减小得不小于变多的。

有了这个性质，就可以 dp 了。设 $f_{i,j,k}$ 表示现在在第 $i$ 层，放了 $j$ 个点，这一层有 $k$ 个点的最小代价。转移枚举第 $i+1$ 层选了几个点，第 $i$ 层最小的度数就是 $\lfloor \frac{num}{k}\rfloor$，算出贡献即可。注意在转移时判断一下当前 $f \ge 10^5$ 时就 break，~~据BINYU所说~~算出来答案不会超过 $10^5$，不然会 TLE。同时全 $0$ 序列最好直接输出 $n-1$，不然直接 T 起飞！

2023.12.18

CWOI

输一手 T3，点分树学得太不扎实了，知道怎么做但是写不来。

T1 经典的差分。差分完后相当于每次可以选一个位置 $+1$ 或者 $-1$，最后让所有位置的绝对值 $\leq k$。那么相当于让所有 $>k$ 的变到 $k$ 的代价和 $<-k$ 的变到 $-k$ 的代价取 $\max$。第二问就是铺设道路。

T2 题解：剩下的 $10$ 分是留给出题人的（笑），如果做出来了建议去备考 NOI。所以只写了 $90$ 分，剩下的 $10$ 分面向数据点过了。注意到一盏灯的开关状态只和他的质因数个数有关，奇数就是开，偶数就是关。于是在线性筛时进行预处理就行了。$O(n)$。

T3 转换一下问题可以变成所有的 $d$ 之和减去询问点到所有首都的距离之和。可以树剖，但是淀粉树更加的无脑，直接写就完了。

2023.12.21

CWOI

T1 求出每一颗树的直径，把他们拼起来就是答案。

T2 一开始想了二分答案，但是答案没有单调性，因为 $h$ 变小的同时 $g$ 在变大。这时发现答案是个区间问题，直接求是不好做的，可以考虑固定一个右端点 $r$ 去计算答案。如果任意 $L \le i \le R$ 满足 $[i,r]$ 的 gcd 相等，那么我们一定会取 $L$ 作为左端点，因为 $g$ 相等他的 $\sum h$ 又更大。于是，我们就可以每次去找这个 $L$，可以二分实现。但是这样一直找复杂度对吗？因为每次找新的 $L$ 时 gcd 都会至少除以 $2$，因此最多找 $\log V$ 次就结束了。再算上 st 表求 gcd 的一个 log，总复杂度 $O(n \log^2n \log V)$。你会说 $10^6$ 怎么过，放心，卡不满，加上一些玄学优化跑得飞快。

T3 众数会不了一点。用的是题解的分治做法，不过膜拜MrcFrst。首先众数这东西没有什么可加、可减性，去扩展区间是不好做的。既然扩展不行就考虑合并。对于一个区间 $[l,r]$ 可以把它拆成 $[l,mid] \sim [mid+1,r]$。如果一个数 $x$ 是 $[l,r]$ 的绝对众数，那么他一定是 $[l,mid]$ 或者 $[mid+1,r]$ 的绝对众数。若不是，则两区间合并后 $cnt_x$ 一定 $\le len$。并且这段区间能成为绝对众数的数至多只有 $\log n$ 个，因为一个新的数要想当众数，他的数量必须要比旧众数翻倍，故至多 $\log n$ 个。因此，我们可以对于每个区间预处理出可能作为区间绝对众数的数有多少个，再去对于每个数计数即可。

计数部分：把众数看成 $1$，其他数看作 $-1$。再记 $s_i$ 表示序列的前缀和。那么一个区间 $[l,r]$ 合法，当且仅当 $s_r-s_{l-1}>0$。这就相当于满足了个数 $>len$。于是，对 $[l,mid]$ 用桶算出每个 $s_{i-1}$ 出现的次数，再来一次前缀和。最后对于每个 $[mid+1,r]$ 查询有多少个数小于 $s_i$ 即可。$O(n \log^2 n)$。

T4 把性质分打完了，都用了容斥了，还没把正解想出来，好菜。正难则反，对于只有一条路径的情况其不合法方案数就是 $k \times k^{n-c-1}=k^{n-c}$（$c$ 是这条路径上的边数）。对于路径条数 $\ge 2$ 时，直接算会有重复，但是 $m \le 15$，直接上容斥即可。把每条路径的边用并查集合并到一起（有交也合并到一起），算答案即可。

2023.12.23

CWOI

心态炸裂。挂了一堆分，输麻了。写了拍子T1还能挂，哎。

T1 可以考虑状压枚举 $a$ 剩下的状态，我们就知道 $b$ 要删哪些数。但是 $b$ 中可能会有重复的数，再去枚举怎么删时间就爆炸了。于是可以用折半搜索的思想，先将 $a$ 的状态存下来，再对 $b$ 进行枚举，二分一下值就行了。但是我没有判前导零，并且脑抽以为 $\frac{a}{b}$ 一定是整数，于是怒挂 $60$ 分。下次要更认真的读题了。

T2 设 $f_{S,i}$ 表示已经走完了集合 $S$ 中为 $1$ 的点，停在了 $i$ 点，到 $n$ 的最小期望。于是我们倒着转移，一个点 $i$ 有 $1-p_i$ 的概率可以骑车到达 $n$，就是 $\frac{dis_{a_i,n}}{y}$，另外 $p_i$ 就需要另外枚举一个点 $q$ 以此来中转到达 $n$，即 $\min \{f_{S\cup q,q}+\frac{dis_{a_i,a_q}}{x}\}$。最后找一个最小的 $f_{2^{i-1},i}+\frac{dis_{1,a_i}}{x}$ 就是答案。还要和 $\frac{dis_{1,n}}{x}$ 取 $\min$。

T3 首先考虑如何构造才能使答案唯一。因为是子序列构成子串，所以很容易算重。而题目又要求回文，所以从两边往中间构造是很优的，这样既保证了答案的唯一性，又好解决回文的问题。于是设 $f_{l,r,k}$ 表示左边选到了第 $l$ 个串，右边选到了第 $r$ 个串，左边还有 $k$ 个没匹配的方案数。$k$ 可以为负数，就代表右边还有 $-k$ 个没匹配，实现的时候再加一维 $0/1$ 表示左还是右就行了。那么区间 dp，从 $[l,r]$ 转移到 $[l+1,r]$，选了 $l+1$ 就需要看 $l+1$ 这个串是否与右边剩下的 $k$ 个字符构成回文（哈希判断），可以就累加。同时也可以直接从 $f_{l,r,k}$ 转移到 $f_{l+1,r,k}$，代表不选 $l+1$ 的方案。对于 $[l,r-1]$ 同理。统计答案就去看 $f_{l,r,k}$，$[1,l-1]$ 和 $[r+1,n]$ 已经构成回文了，只需要看剩下的 $k$ 个是否是回文就行了。但是这样会算重，因为 $f$ 的转移还包含了不选一个 $i$ 的方案，这样会使 $f_{l,r,k}$ 被重复选很多遍。因此再开一个 $g_{l,r,k}$ 存方案，只从选了 $i$ 的 $f$ 转移就行了。

2023.12.26

CWOI

T2 会被卡成 $O(p^2)$ 的做法过了！非常的开心，赛后也是在 hack 大师 BINYU 的~~疯狂hack~~帮助下优化成了正确的复杂度。

upd：BINYU 的数据被加上去了，变成了 $60$。

T1 求第 $k$ 小/大问题很自然地想到了二分，关键在于怎么 check。注意到固定 $i$ 后就是一个形如 $y=b_i \times c_j + a_i$ 的一次函数，他是单调的！因此我们可以对于每个 $i$ 二分出有多少个 $c_j$ 会使 $y$ 的函数值比 $mid$ 小，最后返回 $\ge k$ 即可。$O(n \log n \log V)$。

T2 很神奇的一道题。可以先思考如何计数。输入时就把 $n$ 处理成 $N \times N +1$，那么式子就是 $(n\mod a+b)\mod c =N_3$。$n,N_3$ 我们是知道的，于是可以把式子拆开分别算，先算 $n\mod a+b$ 的个数。枚举每个 $a$ 求出所有 $n\mod a$ 的个数。再考虑枚举整个式子的值：如果 $\le p$，那么就能写成 $0+p=1+p-1=2+p-2=\dots$ 这样的形式，相当于 $n\mod a$ 的个数。若 $>p$，便有了数量上限，前缀和减一下即可。这时再去枚举前一个式子的值，设其为 $num$，那么把同余式写成等式就是 $num-N3=k\times c$。因此 $c$ 必须是左式的因数才能满足条件，$O(p\sqrt p)$ 统计答案即可，同时对每个 $num$ 存一下可行的 $c$ 有哪些，为输出方案做铺垫。

为了方案字典序从小到大，必须先枚举 $a$ 再枚 $b$ 再枚 $c$。但这样时间爆炸，考虑优化。我们可以先枚举一个 $a$，去看有哪些 $b$ 和它放一起能组成有对应 $c$ 的 $num$。这样就保证了每次进入内层循环都会有答案产生，否则就是 break。最多 $10^5$ 次，复杂度就对了。

T3 首先考虑如何让得分最大。一定是对于每个 $a_i$ 去找第一个大于它的数与它配对，这样更大的数留给更大的 $a_i$ 会更可能产生多的贡献。但这样不一定字典序最小，有可能两个位置互换后答案不变，但是后边的值更大。因此从后往前放就能初步保证答案正确了。

这样肯定还是不够的，可以再继续交换。交换的条件就是对于一个 $i$，在他后面的 $j$ 满足 $c_j>c_i$ 并且换完后贡献不变。那么贡献如何不变呢？

当 $c_i>a_i$ 时，必须要 $c_i>a_j$，这样答案才不会变。
当 $c_i\le a_i$ 时，只需 $c_j>c_i$ 即可。因为 $c_j$ 一定大于 $c_i$，换过来答案肯定不变，毕竟 $c_j>a_i$。

这时可以发现，就是在 $i$ 的后面找比 $c_i$ 小的 $a_j$ 和比自己大的 $c_j$ 交换就行了。第二个直接 set，第一个维护 $a$ 的权值线段树即可。

T4 二份答案。赛时想假了，以为先把所有加到 $h_i+a_i\times m$ 再砍就行，但这样会砍成负数。关键在于问题的转化，既然正着砍会有负数不好处理，那就倒着加回去。于是问题就是一开始所有树都 $\le mid$，每次可以选 $k$ 课树长 $p$，每棵树每天会缩 $a_i$，中间不能变为负数，看 $m$ 天后是否能让所有树都 $\ge h_i$。于是我们用一个堆维护每棵树减到负数的时间，优先把小的拿出来，因为他们很快就要变成负数了，把他们加上 $p$。最后看堆是否为空即可。

2023.12.29

CWOI

年前最后一场模拟赛，垫底了。是为新年攒 rp 吗（

感觉自己会把简单问题复杂化，本来 $O(n^2k2^k)$ 是随便过的，我却以为过不了，便写了一个超级玄学做法，浪费了我 $3$ 小时，还挂了 $5$ 分，有点抽象了啊。二三题暴力全 T，心态不好导致的。希望接下来的一年能好好锻炼一下我的心理素质。

T1 先用 dijkstra 跑一遍全源最短路，然后状压：设 $f_{s,i}$ 表示坐了 $S$ 状态的车后，到了第 $i$ 个点的最小时间。转移枚举坐的哪个车，再枚举起点和终点就行了。

T2 先不考虑删点，如果所有点都可行，那么一个点的贡献是多少。因为这个点能转移的点只有 $>$ 它的点，因此直接累加比他大的点的贡献就行（这个点旁边的 $4$ 个），$\le$ 它的点他也能走到，但是不能接着动了，因此只累加 $1$。再考虑删掉一个点的贡献。比它 $<$ 的点都累加了它的贡献，因此删除的次数就要加上旁边比他小的点的删除次数。但是其他点还是能走到这里，因此再算答案时还要加上一个 $del_{x,y}$ 才行。