草关机没保存。。重写一遍。。

CF1434D

题解证明了答案的一端一定是直径的一端。

于是对每个点维护它到根的距离以及它到根的路径的颜色即可。相当于区间反转，全局 $0$ 位置最大值。线段树维护即可。

CF1423F

$k > n$ 与 $k < n$ 的情况显然。

考虑一个不变的量，在修改前后 $\sum i a_i \bmod n$ 是不会改变的。于是可以猜这么个结论，并且手动打表后发现没啥问题。

CF1406E

考虑先把所有小于 $\sqrt n$ 的质因子删除。然后枚举每个 $\le \sqrt n$ 的质因子以及幂次看看是否存在这个数的倍数即可找出所求数的不到 $\sqrt n$ 的因数个数以及幂次。

然后，我们假装实际上确实发现了这个数由 $< \sqrt n$ 的质因子。那么我们枚举所有大于 $\sqrt n$ 的质数（大概是 $90000$ 个），看看这个质数的倍数的个数是否为 $1$ 。如果不为 $1$ 我们就找到了大于 $\sqrt n$ 的质因子。

但是这么做有个问题。如果我们实际上求的就是大于 $\sqrt n$ 的质数呢？

一个显然的做法是直接扫过去，每个数删一下再求一下倍数个数。但是这么做需要 $2 \times 90000$ 左右，无法接受。

于是考虑分块。我们对于这些质数分块后，每次先把一个块删完，再通过 A 1 的方式确定质数是否在这之中即可。需要大概 $90000 + 2\sqrt n$ 次操作。可以接受。

CF1153F

首先这题是可以积分的。但是中间可能涉及到多项式。。现在写一下题解的高论做法。

考虑这 $2n$ 个区间端点随机选取，所以 $0$ 概率重合。然后有一个结论：直接让每个区间长度为期望下的 $\frac 1 {2n+1}$ 即可。

然后设 $dp[i][j]$ 表示前 $i$ 号端点后面的区间被覆盖 $j$ 次的方案数量。算期望就是 $dp[i][j] \times dp[2n - i]][j] \times j!$ ，也就是前后分别由 $j$ 个位置覆盖到这里，拼接起来，拼接的方案由 $j!$ 种。

注意最后除以 $dp[2n][0]$ 即总方案即可。

模拟赛C 秋天的第一杯奶茶

以下复杂度默认 $n,m,q$ 同阶。

考虑询问 $[x,y]$ ，差分一下就是区间 $[1,x-1]$ 的修改对 $[x,y]$ 的询问的影响（记作 $[1,x-1][x,y]$）。

然后可以直接莫队一下，这个往左往右加入拿 BIT 维护即可。复杂度 $O(n\sqrt n \log n)$ ，期望得分 $85\sim 95$ 、

这种东西的优化很类似于区间逆序对。考虑再次差分，变成 $[1,x - 1][1,y] - [1,x - 1][1,x - 1]$ ，也就是进行完 $[1,x-1]$ 的操作后询问 $[1,y] - [1,x-1]$ 。

首先 $[1,x][1,x]$ 是很可做的， 考虑向后添加一个东西，如果是询问那么在修改的 BIT 上查，否则在询问的 BIT 上查，并且改一下 BIT ，于是 $O(n\log n)$ 即可预处理。

然后考虑 $[1,x][1,y]$ 怎么处理，首先可以莫队，复杂度 $O(n\sqrt n \log n)$ 。

然后考虑二次离线，把修改挂在 $x$ 上。然后 $x$ 会移动 $O(n)$ 次，$y$ 会移动 $O(n\sqrt n)$ 次。但是 $x$ 的修改是区间加，可以用类似区间加 BIT 的操作把区间修改变成单点修改。

用一个根号平衡可以做到 $O(n\sqrt n)$ 。

代码被咕咕咕了。

Gym 101612E

一个比较简单的集训队作业题。

考虑一个数被连进去，要么是被链接到所有数的 $\text{lcm}$ ，要么被连接到这个数的倍数。

明显，如果这个数存在倍数，我们必然会把它变成它的倍数。因为如果最优方案下会把它的倍数都变成 $\text{lcm}$ ，那么我们开始就把这个数也变成 $\text{lcm}$ 即可。

于是，我们可以把数分成两种，是否由倍数。如果我们已经把某一个数字给变成 $\text{lcm}$ 了，那么所有无倍数的都可以这么操作。所以相当于是，最优决策分为两种：要么把出现次数最小的数变成 $\text{lcm}$ 后对其他数都变成 $\text{lcm}$ ，要么只操作有倍数的数。

Gym 102412G

这题倒也确实很 $\text{Atcoder Quality}$ 。。。

看到这题第一想法大概是能否 $dp[S]$ 表示把 $S$ 以及子集都染合法的最优代价。但是发现不太能转移。

有这么一个非常妙的结论：

$\exist i \in S , \forall S_1 \{i\} \sube S_1 \sube S$ $S_1$ 是同一种颜色，同时有 $S\setminus \{i\}$ 的染色方案合法，这个条件是 $S$ 合法的充要条件。

• 充分性：只要这个条件成立，我们把集合分成 $S_1,S_2$ 两类，分别表示是否包含 $i$。 如果选择的两个集合都在 $S_1$ 的子集，那么它们一定是同一种颜色。否则，如果都在 $S_2$ ，那么它们不可能对 $S$ 造成影响（因为并起来不可能成为 $S$），但是我们知道 $S_2$ 对于 $S\setminus \{i\}$ 合法，所以它们也一定满足条件。否则如果两边各有一个集合，我们知道其中一个的颜色必然和 $S$ 相同，另外一个无论是否相同都是合法的。
• 必要性：如果这个条件不成立，也就是 $\forall i\in S ,\{i\} \sube S_1 \sube S$ $S_1$ 不是同一种颜色或者 $S_2\sube S \setminus \{i\}$ 的染色方案不合法。我们假定真的构造出了一组合法的染色，并且因此我们必然没有第二种条件，也就是有$\forall i\in S ,\exist S_1,\{i\} \sube S_1 \sube S$ $S_1$ 与 $S$ 颜色不同。我们对于所有 $i$ 的这个与 $S$ 颜色不同 $S_1$ 拿出来并起来，必然可以并出 $S$ ，所以 $S$ 的颜色应该和 $S$ 不同，推出了矛盾。

于是就可以 $dp$ 了。

CF1361C

枚举最高位，然后相当于是后面一些位作为编号建图。然后如果这个图有欧拉回路，一定构造了一组方案让最后几位都是 $0$ 。

枚举最高位建图判断一下即可。

最后还是过了，并且获得了求欧拉回路的正确姿势：

void dfs( int u ) {
	while( !G[u].empty() ) {
		auto t = G[u].back(); G[u].pop_back();
		if( vis[t.se] ) continue;
		vis[t.se] = 1;
		dfs( t.fi );
		vec.eb( mp( t.se , u ) );
	}
}

CF949E

个人觉得很漂亮的一个题。

首先可以证明一个最优的方案一定有要么只出现 $2^k$ 要么只出现 $-2^{k}$ ，且不会多次出现。

证明很显然，我拿 $a,a$ 明显不如拿 $a,2a$。拿 $-a,a$ 也不如拿 $2a,-a$ 。

从低到高考虑每一位。我们维护当前数组里的所有值。如果有数为奇数，我们要么必须拿 $-1$ 要么必须拿 $1$ 。而且在拿了这两个都一种之后，所有数都会变成偶数。于是我们可以把所有数除以二并且进入一个子问题。

但是直接暴力找，大概是分治的节点个数乘以 $n$ ，难以接受。但是可以发现向下分治的时候值域折半了，所以我们给整个序列去重后，复杂度就是 $O(c\log c)$ 。

模拟赛B 真夏は誰のモノ

最后的序列在合并相同的字符后一定得到的是原序列的一个子序列。这个子序列满足相邻的字符不相同。

考虑只要是这样的一个子序列把每个字符扩展出去，一定可以回到原串。

所以我们可以分别做这两件事：算出长度为 $i$ 的相邻不同的子序列个数，算出长度为 $n$ 有多少种分成 $i$ 段的方法，这两种方案乘起来即可。

第二个问题是很简单的，$dp$ 一下中间用前缀和优化一下转移即可。

第一个问题，我们设 $dp[i][j]$ 为最后一个字符在 $j$ ，当前子序列长度为 $i$ 的，满足相邻字符不相同本质不同子序列个数，设 $F[i]$ 表示在当前位置之前的长度为 $i$ 的本质不同的，满足相邻字符不相同的子序列数量。考虑如何转移。对于一个位置，如果存在它的前驱，也就是之前也有这个字符，那么转移就是 $dp[i][j] = F[i-1] - dp[lst][i - 1]$ ，也就是可以是之前除开从上一个这个东西结尾的地方结尾的长度的为 $i-1$ 的串之外的长度为 $i-1$ 的串转移。还有 $F[i] += dp[i][j] - dp[i][lst]$ ，也就是加上增加的本质不同子序列个数。否则，如果之前不存在，显然可以直接 $dp[i][j] = F[i-1]$ ，直接把这个值统计进 $F[i]$ 即可。

这东西本质上类似于 $O(n)$ 推本质不同子序列数量。

第二个问题还有一个容斥做法。我们钦定有 $i$ 个段比 $k$ 长，然后把这些去掉组合数算个方案即可。