考试LIST [2020.10]

2020.10.02

$\texttt{Location:NOIP2020}$

得分：$\texttt{300/300,Rank1}$。

[10.02]-错误

$\texttt{T2}$ 快速幂又双叒叕写错了，这次是船新错法：if(b & 1) 成了 if(b ^ 1)。

$\texttt{T3}$ 显然是 $\texttt{Trie}$ ，然而在各种奇怪的方向搞搞搞，浪费了很多时间。

[10.02]-部分正解

$\texttt{T1}$

和 [HEOI2016/TJOI2016]排序 很像。

考虑一个位置 $i$ 最终是多少，首先可以二分一个字符 $c$ ，把字符串里字典序 $\ge c$ 的变成 $1$ ，剩下的变成 $0$。这样每次进行排序实际就是一个线段树区间赋值操作了。最后判断这个位置 $i$ 是否是 $1$，然后对二分区间进行更改。

发现每个位置都需要二分，所以套整体二分即可。

貌似是非正解呢

或者......由于字符集并不大，因此可以考虑维护 $26$ 棵线段树，分别维护每个字符。然后把每个排序操作暴力拆成 $26$ 棵线段树的赋值操作，就可以了。

$\texttt{T2}$

首先发现每一列最多放一个 $1$，因此可以考虑对列进行 $\texttt{dp}$。

觉得左边右边两个限制很烦人，于是先考虑右边的限制要怎么做。令 $dp[i][j]$ 为前 $i$ 列，已经满足了 $j$ 个右边的限制的方案数。因此有方程：

$$dp[i][j]=dp[i-1][j]+dp[i-1][j-1] \times (s - (j-1))$$

$s$ 指的是这一列总共包含多少个右边的限制。大概意思就是考虑这一列是否满足一个右边限制。

然后考虑左边限制要如何满足，可以每次在枚举的列离开某一个左边限制时去进行考虑，可以得到：

$$dp[i][j]=dp[i][j]\times (i-j-p)^{\underline{d}}$$

$p$ 是在 $i$ 左边就已经结束的左边限制个数，$d$ 是 $i$ 处结束的左边限制个数。大概意思就是用还没有填 $1$ 的某一列来满足这些已经到结束位置的左边限制，注意可以用的列数是 $i-j-p$，其中 $j$ 列用来满足了右边限制，$p$ 列用来满足了其他的左边限制，同时方案数应乘上一个下降幂，实际就是一个排列。

而快速求每一个位置上的左边限制/右边限制个数，可以用前缀和优化。

复杂度 $\mathcal{O}(n\times m)$ 吧。

$\texttt{T3}$

看到异或，就要想 $\texttt{Trie}$ —— 鲁迅

妙题。

首先那个奇怪的柿子表示成二进制就是一个循环移位，如果令 $f(x)$ 为 $x$ 做一次这样的变化后得到的数，那么显然可以得到一个柿子： $f(x\oplus y)=f(x)\oplus f(y)$，其中 $\oplus$ 是异或。

令数组 $a$ 的前缀/后缀异或分别为 $pre_i,suf_i$，那么对于一个数字 $x$，在 $i$ 这里进行变换，所得到的答案应该是：

$$f(pre_i \oplus x) \oplus suf_{i+1}$$

然后根据上面的结论，可以变成：

$$f(pre_i) \oplus suf_{i+1} \oplus f(x)$$

发现 $f(x)$ 和 $x$ 没有本质区别，因为他们值域相同。

那么把所有的 $f(pre_i)\oplus suf_{i+1}$ 从高位到低位扔进 $\texttt{01Trie}$，然后进行讨论。

贪心地想，对于字典树上一个节点 $x$，如果他有 $0,1$ 两个儿子，那么显然对手不可能让你得到这一个位置的值，两边同时递归。否则如果只有一个儿子，那么我就选择和他相反的那个值，然后加上这个位置相应的权值，然后递归处理。

这样的话你就能得到所有极大的答案，进行排序之后取最大的即可。

2020.10.03

$\texttt{Location:NOIP2020}$

得分：$\texttt{230/300,Rank1}$。

[10.03]-错误

$\texttt{T1}$ 又双叒叕没算空间 $\texttt{RE}$ 了。

$\texttt{T2}$ 肝了很久，结果暴力分都没拿满。

[10.03]-部分正解

$\texttt{T1}$

二分一个半径 $d$，每个点都变成一个半径为 $d$ 的圆。如果这些圆的并连接了整个矩形的上端点和下端点，那么一定走不过去。

因此可以暴力每次 $\mathcal{O}(k^2)$ 枚举两个点，用并查集维护两个圆之间的连通性，这样是 $\mathcal{O}(k^2\log^2 k)$ 的 貌似有一个 log 跟的不是 k 。

发现这 $k^2$ 条边中有很多无用边，因此可以考虑进行优化。对整个图两两连边，然后跑出一棵最小生成树，每次只要考虑连接最小生成树之中的那些边就可以了，因为如果两点在最小生成树上都没有被连起来，那么没有别的边可以把他们联通。

使用 $\texttt{Kruskal}$ 可以做到 $\mathcal{O}(k^2\log k^2 + k\log^2 k)$，可以得到 12s 的好成绩，使用著名的 $\texttt{Prim}$ 可以优化到 $\mathcal{O}(k^2 + k\log^2 k)$，即可通过。

$\texttt{T2}$

神仙题，这题真的是 $\texttt{God knows}$......。

首先，跳出二分图的设定，单独看一个排列。发现在二分图上删除一条边，相当于删掉在排列上由这个点贡献的所有逆序对。

然后可以发现，想要删除所有的点，在排列上必须删除某一个极长的上升子序列，找这些极长上升子序列中 $c$ 值和最小的即可。然后就很自然地想到 $\mathcal{O}(n^2)$ 的 $\texttt{dp}$，设 $dp[i]$ 为选 $i$ 为最后一个删除点，那么有：

$$dp[i] = \min_{j} \Big\{ dp[j] + c_i \Big\}$$

其中 $j$ 满足 $j < i,p_j <p_i$ 且不存在一个 $j < k < i$ 使得 $p_j < p_k < p_i$。

考虑使用线段树进行优化（由于本题难以理解，特写出每个函数的定义与写法）。

可以发现，如果某一个位置 $j$ 可以为后面的 $i$ 作贡献，那么一定不存在中间的一个 $k$ 使得 $p_j<p_k<p_i$ 貌似已经说过一遍了。首先考虑每次把 $i$ 插入线段树的 $p_i$ 位置，也就是以 $p$ 为值域，那么可以用 $maxpos$ 数组维护值域区间内最大的 $i$。发现在线段树上值域为 $[l,r]$ 的位置对 $x$ 的贡献满足这样的条件: $maxpos(l,r) > maxpos(r + 1,p_x)$，意思是：$p\in [l,r]$ 的这些点一定需要存在一个位置出现在 $[r+1,p_x]$ 的后面，否则任意一个 $[l,r]$ 内的数字，在原数组的位置和 $x$ 中间必有一个满足条件的 $k$（上面的 $p_j<p_k<p_i$）。

不妨再设 $mindp[x]$ 表示：线段树 $x$ 节点的左儿子中，满足出现位置大于其右儿子的 $maxpos$ 的点的 $\texttt{dp}$ 值的最小值。

现给出函数的定义：

$$\texttt{int Getmaxpos(l,r):}$$

求区间 $[l,r]$ 中在原数组中出现位置的最大值，就是上文的 $maxpos$。

$$\texttt{int Getmindp(x,l,r,minpos):}$$

线段树节点 $x$ 代表区间 $[l,r]$，求该区间内所有满足在原数组出现位置大于 $minpos$ 的 $\texttt{dp}$ 值的 $\min$。具体写法是：若 $l==r$，则值一定是 $dp[maxpos[x]]$。否则，若 $maxpos[rs(x)] < minpos$ 说明右边绝对不存在满足条件的值，返回 $\texttt{Getmindp(ls(x),l,mid,minpos)}$；若 $maxpos[rs(x)] >= minpos$ 则首先向 $\texttt{Getmindp(rs(x),mid+1,r,minpos)}$ 递归，然后考虑左子树：$mindp[x]$ 的定义告诉我们，中间存有的 $\texttt{dp}$ 值来自左子树，且满足 $maxpos[rs(x)]$ 的条件，而 $maxpos[rs(x)]$ 的条件比 $minpos$ 更紧，因此一定全部满足 $minpos$ 的限制，那么直接在 $mindp[x]$ 与右子树递归结果取 $\min$ 即可。

$$\texttt{void pushup(x,l,r):}$$

更新线段树节点的 $maxpos$ 和 $mindp$。$maxpos$ 很容易更新，左右子树取 $\max$ 即可。而 $mindp$ 按照定义调用 $\texttt{Getmindp(ls(x),l,mid,max(0,maxpos[rs(x)]))}$ 即可。

$$\texttt{void update(x,l,r,pos,val):}$$

插入一个新点，直接更新其 $maxpos$，然后 $\texttt{pushup(x,l,r)}$ 即可。

$$\texttt{int query(x,l,r,rlim):}$$

求 $[0,rlim]$ 内满足条件的 $\texttt{dp}$ 值的 $\min$，照样递归，考虑在 $r \le rlim$ 的时候如何返回：如果 $r + 1\le rlim$ 说明区间 $[l,r]$ 的右侧与 $rlim$ 之间存在别的点，那么一定存在一个限制，返回 $\texttt{Getmindp(x,l,r,max(-1,Getmaxpos(r+1,rlim)))}$，否则有 $r==rlim$，顶住了右端点则没有其他限制，返回 $\texttt{Getmaxpos(x,l,r,0)}$。

这样的话，我们每次只需要令 $dp[i] = query(1,0,n,p[i])+c[i]$，然后把点 $i$ 加到线段树的 $p_i$ 位置上即可。

最后的答案是 $\texttt{query(1,0,n,n)}$。

时间复杂度 $\mathcal{O}(n\log^2 n)$。

$\texttt{T3}$

神题。

首先由于 $v$ 是 $u$ 的祖先，因此可以把 $dis(v,u)$ 写作 $dep_u-dep_v$，那么柿子可以写成：

$$-\dfrac{c_u-c_v}{dep_u-dep_v}$$

仔细观察，这实际上就是过 $(dep_u,c_u),(dep_v,c_v)$ 两个点的直线的斜率的相反数，要求其 $\min$，就是斜率的 $\max$，考虑维护一个这样的下凸壳。

可以发现每往凸壳里加一个点，那么一定加在所有的点的右边，因为 $dep$ 递增。然后考虑对每一个点 $x$ 维护倍增数组 $p[x][i]$，表示从 $x$ 开始，在这个凸壳上向左边跳 $2^i$ 步到凸壳上哪个点。每加入一个新点 $u$，就可以找到加入他之后凸壳上距离他最近的点 $v$，将 $p[u][0]$ 设置为 $v$，更新倍增数组即可。

2020.10.04

$\texttt{Location:NOIP2020}$

得分：$\texttt{166/400,Rank2}$。

[10.04]-错误

$\texttt{T1}$ 乱搞即可 $\texttt{90pts}$，写了 $\texttt{NTT}$ 还只有 $\texttt{60pts}$......

$\texttt{T2}$ 实际上是可以做的，却完全没有开。

$\texttt{T3}$ 写了正解，卡常成了 $\texttt{76pts}$......

[10.04]-部分正解

$\texttt{T1}$

考虑最简单的树形 $\texttt{dp}$，就直接树形背包就可以了，貌似卡一卡上下界就有 $\texttt{90pts}$ ？

然后发现这个背包是一个卷积形式，又模数是信仰 $998244353$，因此可以用 $\texttt{NTT}$ 优化。

考虑正解，设 $dp[i][j]$ 为遍历到 $i$，已经走了权值和为 $j$ 的方案数。每次将父亲的 $\texttt{dp}$ 值传给儿子，然后在回溯的时候更新父亲的 $\texttt{dp}$ 值，也就是加入这个儿子的贡献。有：

$$dp[v][j+a_v]=dp[u][j]$$

也就是选择走到 $v$ 这个点上，就会得到 $a_v$ 的贡献。然后在回溯时：

$$dp[u][j] = dp[u][j] \times 2^{siz_v-1} + dp[v][j]$$

首先如果不进入 $v$，那么 $v$ 中 $siz_v-1$ 条边状态任选。考虑进入的情况，如果已经进入，那么回溯时经过了 $u$，但 $u$ 这个点已经在联通块中了，所以 $a_u$ 不会产生贡献，只要加上 $dp[v][j]$ 即可。

复杂度 $\mathcal{O}(nk)$。

$\texttt{T2}$

首先令原数组为 $a_i$，给定数组为 $b_i$。

将两个数组分别排序，一定有结论：

$$b_1=a_1+a_2,b_2=a_1+a_3$$

假设现在我们知道了 $a_1$，那么就可以求出 $a_2,a_3$。将 $a_1+a_2,a_1+a_3,a_2+a_3$ 从 $b$ 中去除后，最小的数字一定是 $a_1+a_4$，然后即可求出 $a_4$。以此类推即可求出所有的值。

那么现在只要枚举 $a_1$，即可得到 $\texttt{50pts}$。

我们发现，现在我们知道 $a_1+a_2,a_1+a_3$，假设我们知道 $a_2+a_3$，则可以求出 $a_1,a_2,a_3$，那和以上等价了。因此我们直接枚举 $a_2+a_3$ 是 $b$ 中哪一个，然后暴力去检查。

时间复杂度 $\mathcal{O}(n^3)$。

$\texttt{T3}$

只有期望才能打败期望

考虑构造一个势能函数 $E(S)$，令其某一后继状态为 $S'$，有 $E(S')-E(S)$ 的期望值为 $1$，最后答案就是初始状态和最终状态的势能函数之差。

令 $E(x)$ 为一个大小为 $x$ 的部落的势能函数，整个状态的势能函数为每个部落的势能函数之和。定义一个运算 $\oplus$ 表示两个部落的战争，那么有：

$$E(x)\oplus E(y)+1=p(E(x+1)+(y-1)E(1))+p(E(y+1)+(x-1)E(1))+(1-2p)(x+y)E(1)$$

也就是右式是 $E(x)\oplus E(y)$ 的一个后继状态，其势能 $+1$。

发现 $E(1)$ 很多很麻烦，那么就设其为 $0$。然后就有：

$$E(x)\oplus E(y)+1=p(E(x+1)+E(y+1))$$

构造一下，可以令：

$$E(x+1)=\dfrac{2E(x)+1}{2p}$$

找一下规律，可以展开得到这样的柿子：

$$E(x)=\sum_{i=1}^{x-1} \dfrac{1}{2p^i}$$

后面是个等比数列，化一下变成：

$$E(x)=\dfrac{\dfrac{1}{2p^x}-\dfrac{1}{2p}}{1-\dfrac{1}{p}}$$

然后直接上光速幂即可，即预处理 $\dfrac{1}{2p}$ 的 $\lfloor \sqrt{n} \rfloor$ 之内的幂，和 $\Big(\dfrac{1}{2p}\Big)^{\lfloor \sqrt{n} \rfloor}$ 的 $1$ 到 $\lfloor \sqrt{n} \rfloor$ 次方，就可以 $\mathcal{O}(1)$ 求了。

时间复杂度 $\mathcal{O}(n)$。

$\texttt{T4}$

问题其实就是多次询问某个路径中有多少个给定的子路径。

$\text{dfn}$ 序把一个路径可以搞成若干二维平面上的矩形，那询问两点就是问他被多少矩形给覆盖。由于还有时间的限制，所以就是一个三维偏序问题。直接上 $\text{CDQ}$ 分治即可。

2020.10.07

$\texttt{Location:NOIP2020}$

得分：$\texttt{295/400,Rank N/A}$。

其实不算考试，只是做了高二的题

[10.07]-错误

$\texttt{T4}$ 在某一个地方可以被卡，差评，并且写出来锅非常多，还是要想清楚再写。

[10.07]-部分正解

$\texttt{T1}$

首先瞪眼大法，考虑对于一个点 $(x,t)$，所有过他的二次函数的顶点应该呈一个什么形状。

不难发现实际上这些恰好过这个点 $(x,t)$ 的二次函数的顶点，恰好就在一个二次函数上。

也可以直接数学移项：

$$(x-m)^2+k \le t \Rightarrow -(x-m)^2+t\ge k$$

也就是删掉函数 $f(x)=-(x-m)^2+t$ 下方的点。

现在问题就转化为：

给定一些点，支持动态加点，和删除恰好在一个给定的，开口向下的二次函数上，或其下方的点。

发现所有点坐标都是正整数，因此考虑暴力枚举。

每次枚举一个 $i$ ，删除 $(i,y)$ 的点，其中满足 $y \le t-(i-m)^2$。不难发现这个东西在枚举 $\sqrt{t}$ 次之后就会小于等于 $0$。因此每次更新都是 $\sqrt{t}$。

然后对于每一个横坐标 $x$ ，都用一个优先队列维护横坐标为 $x$ 的所有点的 $y$，从大到小。然后每次暴力删除即可。

时间复杂度 $\mathcal{O}(n\log n+q \sqrt{10^6})$。

$\texttt{T2}$

建立 $\texttt{st}$ 表，维护区间内的 $\texttt{gcd}$。

暴力枚举最小的数字，二分往左右扩展，更新答案即可。

值得注意的是，不同的位置可能扩展到相同的左端点，因此最后需要去重......

时间复杂度 $\mathcal{O}(n\log^2 n)$。

$\texttt{T3}$

不会

$\texttt{T4}$

令 $1$ 为根，考虑所有从根向下的路径。

令 $dp[i]$ 为从 $1$ 到 $i$ 的路径上，能拿到的所有权值之和。应该很好算，标记哪些已经拿到了钥匙即可。

再考虑换根 $\texttt{dp}$。

首先，对于一个钥匙在 $x_i$，权值放在 $y_i$，权值为 $w_i$ 的条件，称其获取点为 $x_i$，贡献点为 $y_i$，贡献为 $w_i$。

考虑从 $x$ 转移到其儿子 $y$ 的过程。

对于所有以 $x$ 为获取点的条件，如果其贡献点在 $y$ 及其子树内，那么换根之后无法拿到钥匙，把 $y$ 的子树内所有 $\texttt{dp}$ 值减去该条件的 $w$。那些以 $x$ 为获取点，同时以 $x$ 为贡献点的条件，也需要在 $y$ 的子树内删去其贡献。

对于所有以 $y$ 为获取点的条件，如果其贡献点在 $y$ 子树内，则没有影响。如果其贡献点 $p$ 是 $y$ 的祖先，令在 $y$ 到 $p$ 的路径上 $p$ 的儿子为 $s$，给除了 $s$ 的子树内以外的点加上该条件的贡献，也就是他们也可以获取该条件的钥匙了。如果 $y$ 与其贡献点不是祖先后代关系，则直接给其贡献点的子树内加上该条件的贡献。特殊处理以 $y$ 为获取点，同时以 $y$ 为贡献点的那些条件，在 $y$ 变成根后除了 $y$ 的子树内的 $\texttt{dp}$ 值之外，其他的都要加上其贡献，因为其子树内已经能得到这个条件的贡献了。

不难发现，每次进行换根的操作，所做的都是对某一个点的子树内全体加上/减去一个值。直接通过 $\texttt{dfn}$ 序把 $\texttt{dp}$ 值压到线段树上即可。

注意那些获取点与贡献点为同一个点的条件，把他们用一个数组记下来，每次直接一次性更新。然后对挂在每个获取点上的条件，将其按照获取点的 $\texttt{dfn}$ 排序，然后每次在换根的时候只需要二分到数组的对应区间进行更新。不然会被卡

2020.10.11

$\texttt{Location:NOIP2020}$

得分：$\texttt{190/300,Rank3}$。

体验极差！！！

[10.11]-错误

$\texttt{T1}$ 花费时间太长了。

$\texttt{T2}$ $\texttt{bitset}$ 开小了，挂了 $\texttt{30pts}$。

$\texttt{T3}$ 乱搞可以有 $\texttt{50pts}$，然鹅只写了 $\texttt{20pts}$ 的人口普查。

[10.11]-部分正解

$\texttt{T1}$

发现 $k$ 很小，同时我们只关心到某一个点的路径的奇偶性，所以可以考虑使用二进制压一下。

可以把每一行连边压成 $k$ 个数字的形式，第 $d$ 行第 $i$ 个数字从右往左第 $j$ 位表示第 $d$ 层第 $i$ 个点与第 $d+1$ 层第 $j$ 个点之间是否有边。然后同时可以用同样的方法求出如果这一行翻转之后的状态。

再考虑 $dp$，设 $dp[i][S]$ 表示在第 $i$ 层，到每个点的路径数量 $\mod 2$ 的值，存在 $S$ 中。

考虑 $S$ 中某一位，如果其为 $1$，说明到这个点路径数量是奇数条，只有他们有用。因为到这个点的路径数量如果是偶数，那么他对别的点的贡献都是偶数，可以不管。然后考虑这个 $S$ 在这一行不进行翻转之后得到的状态 $S'$，把 $S$ 中为 $1$ 的位置的转移数字异或起来即可。

然后就有 $dp[i+1][S']+=dp[i][S]$。

翻转之后也是一样的，注意第 $1$ 行与第 $m-1$ 行不能翻转了。

最后答案就是 $dp[m][0]$，也就是到汇点的路径数量是偶数。

时间复杂度 $\mathcal{O}(mk 2^k)$，可能有点卡，不过有 $\texttt{O2}$。

$\texttt{T2}$

输入方式毒瘤，差评

正解随机化，差评

题意描述出锅，差评

考虑 $\texttt{50pts}$ ，可以先把某一个集合压成一个长度为 $2n$ 的 $\texttt{bitset}$，然后暴力枚举两个集合,求他们的交，$\texttt{bitset}$ 与起来 $\texttt{count}$ 即可。时间复杂度 $\mathcal{O}(\dfrac{n^3}{\omega})$。

然后考虑两个集合的交的大小的期望。设 $c_i$ 表示第 $i$ 位为 $1$ 的数字个数，然后有：

$$\sum_{i=1}^{2n} c_i = n(n+1)$$

也就是 $n+1$ 个数字，每个都有 $n$ 个二进制下的 $1$。

两个随机集合的交可以表示成：

$$\min\Big\{\sum_{i=1}^{2n} \dfrac{\binom{c_i}{2}}{\binom{n+1}{2}}\Big\}=\dfrac{n-1}{2}$$

也就是某一位的并是 $1$ 的概率之和。

说明随机两个集合的交是非常大的。注意到 $n$ 是偶数，而期望 $\dfrac{n-1}{2} > \dfrac{n-2}{2}$，说明一定存在交为 $n$ 及以上的。同时这大了一个常数，所以至少有 $n$ 对。 证明待补

然后就只要随机 $\mathcal{O}(n)$ 对即可。

时间复杂度 $\mathcal{O}(\dfrac{n^2}{\omega})$。

$\texttt{T3}$

设 $F[x][k],G[x][k]$ 分别为 $x$ 以下距离为 $k$ 的可匹配灭火器单位 和 所需被匹配的点个数。

由于 $\texttt{dp}$ 状态复杂，所以选择贪心的方法，自底向上贪心地更新。

考虑一个点 $x$ 的 $F[x][k]$，他们迫切需要被满足，并且在这个点只能被 $G[x][0]$ 给满足。然后，为了尽量不浪费那些 $G$，我们优先满足一些长度恰好为 $k$ 的匹配，让他们尽量在 $x$ 处被满足。为什么要在这里尽量满足？因为再向上的话，他们如果被其他方案匹配，一定可以进行一次交叉互换，使得其变成这样的匹配。考虑完所有的 $k$ 之后，再考虑 $k-1$ 长度的匹配，让他们也尽量满足，证明方法与上面类似。

每次 $\texttt{DFS}$ 完一个子树之后，向上传递那些剩下的信息，然后再进行相同的操作。

为什么每次只考虑 $k$ 和 $k-1$？首先需要注意的是 $F[x][k]$ 与 $G[x][k]$ 只关心他们和 $x$ 的距离恰好为 $k$，而并不在意他们是否在一棵子树中。因此，对于一些不是很迫切需要匹配的对，我们可以把他们先放着，然后到其祖先处再进行操作。关键在于长度为 $k-2$ 的匹配对，他们为什么可以在更浅的深度被考虑？因为当一个点 $x$ 到其父亲 $fa$ 处时，这样一个匹配对两个点的相对深度均 $\texttt{+1}$。然后不难发现，这个长度为 $k-2$ 的匹配对恰好在 $fa$ 被认为是一个长度为 $k$ 的匹配对！然后他就可以被考虑到了。

需要注意的是，对于根，还有一些长度在 $k-2$ 及其以下的匹配对没有被考虑，所以结束 $\texttt{DFS}$ 之后还需要做一个贪心。在这里，每次优先考虑那些距离 $1$ 更远的灭火器，让他们尽量发挥作用。最后，在距离 $1$ 不大于 $k$ 的某些位置可能还存在一些未匹配的点，再对答案加上这个值即可。

时间复杂度 $\mathcal{O}(nk)$。

2020.10.17

$\texttt{Location:NOIP2020}$

得分：$\texttt{100/400,Rank3}$。

[10.17]-错误

挂分无数......

[10.17]-部分正解

$\texttt{T1}$

每个瓶子都是独立的 $\text{ICG}$ 游戏，所以考虑求出每个游戏的 $\text{SG}$ 函数。以下一个游戏表示为 $(a,b,k)$，表示现在有 $a$ 颗糖果，容量为 $b$，分裂系数为 $k$，$\text{SG}(a,b,k)$ 是该游戏的 $\text{SG}$ 函数。

对于 $(a,b,2)$ ，也就是 $k=2$ 的情况：

如果 $b$ 是奇数，那么容易得到奇数点必败，偶数点必胜。因为对于一个奇数 $a$， $a+1,2a$ 均是偶数。

那么 $a,b$ 均为奇数时 $\text{SG}(a,b,2)=0$。继续分类考虑，如果 $a$ 为偶数，那么设其为 $2i$，则对于局面 $(2i,b,2)$ 可转化到 $(2i+1,b,2),(4i,b,2)$，第一个局面显然必败，第二个局面 $\text{SG}$ 是 $1$ 或者 $2$ 且容易发现他们交替出现。通过归纳可以得出 $\text{SG}(2i,b,2)=3-\text{SG}(4i,b,2)$。

如果 $b$ 是偶数，那么设 $b=4q+r\ (r\in \{0,2\})$。

若 $a>q$，那显然最多进行两次 $\times k$ 操作，可以通过分为进行一次或进行两次两类，然后可以求出其 $\text{SG}$ 值，否则若 $a\le q$，则有结论：

$(a,b,2)$ 与 $(a,q,2)$ 同胜负。

至于证明，只需要证 $(q,b,2)$ 是先手必败态且任意 $a$ 能一步跳到 $q$ 以上的点都是先手必胜。

对于 $(q,b,2)$ 先手必败，可以证 $(2q,b,2),(q+1,b,2)$ 先手必胜。

首先 $\text{SG}(4q,b,2)=0$，因为无法进行 $\times k$ 操作，又 $4q$ 与 $b$ 同奇偶。那么 $(2q,b,2)$ 先手必胜，因为他可以一步到 $(4q,b,2)$。

而对于 $(q+1,b,2)$，如果他可以一步跳到 $(2q+2,b,2)$，那么就赢了，因为 $(2q+2,b,2)$ 无法进行 $\times k$ 的操作（$4q+4>b$），又 $2q+2$ 与 $b$ 同奇偶，所以 $(2q+2,b,2)$ 先手必败。如果不能变成 $(2q+2,b,2)$，也就是 $2q+2>b$，即 $2q+2>4q+r$，解出 $q<\dfrac{2-r}{2}$，显然在 $r\in \{0,2\}$ 的时候无非负整数解。因此也可以证明 $(q+1,b,2)$ 先手必胜。

所以这样就成功证明了 $(q,b,2)$ 先手必败。

然后考虑证明，能跳过 $(q,b,2)$ 的那些状态都先手必胜。不难发现只有通过操作 $\times k$ 才能跳过 $q$，上界是 $(2q-2,b,2)$。所以一步跳过的话，如果状态是 $(x,b,2)$，那么 $\dfrac{q}{2} < x < q$。跳过 $q$，到达 $(q+2,b,2)$ 直至 $(2q-2,b,2)$ 中任意状态，不难发现他们恰好都能且只能进行一次 $\times k$ 操作，并且 $\times k$ 之后还是一个偶数点，因此那个点先手必败。这样就证明了一步跳过 $q$ 的话，到达的点一定先手必胜。

所以，$(q,b,2)$ 先手必败，且任意可以跳过 $q$ 到达的点都先手必胜，所以 $(a,b,2)$ 与 $(a,q,2)$ 同胜负。

这样可以拓展到所有 $k$ 为偶数的情形，设 $b=k^2q+r$，然后做以上的东西即可。

考虑 $k$ 为奇数的情况。

可以发现 $a+1$ 与 $ka$ 奇偶性不相同，可以证明 $\text{SG}(\left\lfloor \dfrac{b}{k}\right\rfloor, b, k)=2$：

首先对于任意 $x>\left\lfloor \dfrac{b}{k}\right\rfloor$，都不能执行 $\times k$ 操作，又 $\text{SG}(b,b,k)=0$，所以 $\text{SG}(x,b,k)$ 为 $0,1$ 交替出现。又 $(\left\lfloor \dfrac{b}{k}\right\rfloor, b, k)$ 是第一个可以做 $\times k$ 操作的位置，且他能到达的位置奇偶性不同，所以其 $\text{SG}=2$。

然后有结论：

构造数列 $\{s_n\}$ 满足 $s_1=\left\lfloor \dfrac{b}{k}\right\rfloor$，$s_n=\left\lfloor\dfrac{s_{n-1}-1}{k}\right\rfloor(n\in \mathbb{N}^+)$。

这个证明非常有意思。对于一个点 $x<\left\lfloor \dfrac{b}{k}\right\rfloor$，由于 $x+1$ 与 $kx$ 奇偶性不相同，所以其 $\text{SG}$ 值为 $\text{mex}(\text{SG}(x+1,b,k),\text{SG}(kx,b,k))$。

考虑一下 $(\left\lfloor \dfrac{b}{k}\right\rfloor-1,b,k)$ 这个位置，他可以转移到 $(\left\lfloor \dfrac{b}{k}\right\rfloor,b,k)$，或者 $(k\times (\left\lfloor \dfrac{b}{k}\right\rfloor-1),b,k)$，由于 $\text{SG}(\left\lfloor \dfrac{b}{k}\right\rfloor,b,k)=2$，所以实际上这个后继状态是没什么用的。因此只需要知道 $\text{SG}(k\times (\left\lfloor \dfrac{b}{k}\right\rfloor-1),b,k)$ 是多少，然后取反即可。

不难发现这个东西不止在上面那一个点如此，还可以继续往更小的数进行。

直到什么时候呢？直到点 $\left\lfloor \dfrac{\lfloor \frac{b}{k}\rfloor-1}{k}\right\rfloor$ 这个位置。发现他 $\times k$ 不再跨过 $\left\lfloor \dfrac{b}{k}\right\rfloor$ 了，所以他 $\text{SG}=2$。可以发现这就成为了一个循环，并且 $\left\lfloor \dfrac{\lfloor \frac{b}{k}\rfloor-1}{k}\right\rfloor$ 就是数列中 $\left\lfloor \dfrac{b}{k}\right\rfloor$ 的后一项！

所以，只需要判断一个点处于数列中哪两个数中间即可。

时间复杂度 $\mathcal{O}(\sum \log b_i)$。

$\texttt{T2}$

设 $dp[i][x]$ 为现在要进行第 $i$ 次操作，手上暴击率为 $x\%$ 的概率。最后答案就是所有 $\texttt{dp}$ 值的和。

发现精度只要求到 $10^{-2}$ ，所以暴力求，直到精度小于要求即可。

$\texttt{T3}$

咕咕咕

$\texttt{T4}$

首先，如果一开始就没有 $k\times k$ 的空矩形，先手必败。

如果所有 $k\times k$ 的矩形两两相交，那么他们一定有至少一个公共点。先手先找出一个，再放 $1$ 在这个公共点上，后手必找不到 $k\times k$ 的矩形。因此这样先手必胜。

那么现在至少有 $2$ 个互不相交的 $k\times k$ 的矩形。假设现在整个矩形中只有他们两个矩形中是 $0$，其他全是 $1$ 了，那一定是先手必败。因为你必须放一个 $1$，而对手在另外一个 $k\times k$ 的矩形上放 $1$，你便无法找出 $k\times k$ 的矩形。

所以双方都不会先下在这两个矩形中，而是先把别的地方填满。不难发现这只跟除了这两个矩形之外的 $0$ 格子的奇偶性有关。又这两个矩形一定存在偶数个 $0$ 的点，所以这种情况下，只需要判断初始状态中，整个矩形里有多少 $0$，奇数则先手必胜，偶数则先手必败。

时间复杂度 $\mathcal{O}(n^2)$。

2020.10.18

$\texttt{Location:NOIP2020}$

得分：$\texttt{0/300,N/A}$。

去 ACM 了...

[10.18]-错误

抱灵选手......

[10.18]-部分正解

$\texttt{T1}$

考虑最简单的 $\texttt{Josephus}$ 问题。设 $f(x,m)$ 为大小为 $x$ ，一次跳 $m$ 步的答案（从 $0$ 编号），然后就有：

$$f(x,m) = (f(x-1,m)+m)\bmod x$$

答案是 $f(n,m)$，可以 $\mathcal{O}(n)$ 求解。

发现 $n$ 比 $m$ 大不少，因此取模操作可能失败很多次。那就考虑一次跳多个 $m$ 步，直到能够取模成功。

注意这里编号从 $0$ 开始，所以最后还要 $\texttt{+1}$。

时间复杂度可以证明是 $\mathcal{O}(m\log n)$ 的。但是我不会证

$\texttt{T2}$

发现有：

$$\sum_{1\le i < j \le n}(a_i\times b_j-a_j\times b_i)^2 $$

$$=\Big(\sum_{i=1}^n a_i^2\Big)\times \Big(\sum_{i=1}^n b_i^2\Big)-\Big(\sum_{i=1}^n a_i\times b_i \Big)^2$$

然后直接上数据结构维护即可。

$\texttt{T3}$

考虑 $\texttt{dp}$。设 $dp[i][j]$ 为 $a$ 中考虑到 $i$，$b$ 中考虑到 $j$ 且必须选入 $b_j$ 的最长长度。

当 $a_i=b_j$，有：

$$dp[i][j]=\max_{k<j,b_k<b_j=a_i}\{dp[i-1][k]\}+1$$

首先从小到大枚举 $i$，接着如果一个 $j$ 满足 $a_i=b_j$，那就可以通过以上柿子转移。

如何快速求 $\max$ 里的东西？由于 $a_i$ 在这里其实是固定的，所以可以考虑在从小到大枚举 $j$ 的时候，拿一个变量记录：$\max_{k<j,b_k<a_i}\{dp[i-1][k]\}$。这是 $\mathcal{O}(1)$ 的。

最后再记录一下从哪里转移即可输出路径。

时间复杂度 $\mathcal{O}(n\times m)$。

2020.10.20

$\texttt{Location:NOIP2020}$

得分：$\texttt{110/300,Rank5}$。

[10.20]-错误

$\texttt{phalanx}$ 一题空间爆炸......

$\texttt{position}$ 最后没调出来......

$\texttt{photo}$ 挂了 $\texttt{20pts}$。

是真的菜。

[10.20]-部分正解

$\texttt{position}$

显然放在中位数上最优。

如果中位数可以选，就选中位数。否则找左边、右边最近的可选点，因为他类似一个单峰函数。

注意左边可选点需要再二分一次，因为要找最左边的点。

$\texttt{photo}$

发现如果带有限制的点连边，要么成环，要么是一棵树。

如果成环，一定无解。

一棵树的情况，考虑 $\texttt{dp}$。设 $dp[x]$ 为 $x$ 及其子树都放好位置的方案数。组合数转移一下即可。懒得写了。

$\texttt{phalanx}$

矩形和用二维前缀和维护。

首先可以考虑二维 $\texttt{st}$ 表，但是空间开不下。

设 $dp[0/1][i][j][k]$ 为以 $(i,j)$ 为左上角，边长 $2^k$ 的矩形的 $\max / \min$ 值。

对于任意矩形，由于长不超过宽的 $2$ 倍。因此手玩一下可以发现，他们都可以通过不超过 $8$ 个 $2^k$ 的矩形求出。

2020.10.22

$\texttt{Location:NOIP2020}$

得分：$\texttt{150/300,Rank2}$。

[10.22]-错误

$\texttt{bus}$ 以为写了正解，刚开始没有对拍，拍了才知道假了......

[10.22]-部分正解

$\texttt{bus}$

设 $dp[x]$ 为到 $x$ 的最小代价，有 $\texttt{naive}$ 的转移：

$$dp[x]=\min_{i}\{dp[i]+\dfrac{x-i}{c_i}\times v_i\}\ (c_i|(x-i))$$

不难化成斜率优化的形式：

$$\dfrac{i\times v_i}{c_i}-dp[i]=x\times \dfrac{v_i}{c_i}+dp[x]$$

然后要使截距 $dp[x]$ 最小，那就维护一个上凸壳。由于上面 $c_i|(x-i)$ 的条件，也就是 $x\equiv i\ (\bmod\ c_i)$，所以可以考虑开 $maxc\times maxc$ 个栈维护上凸壳，$s[x][y]$ 表示 $\bmod\ x$ 的时候余数为 $y$ 的上凸壳。

不难发现一个 $x$ 只会在 $s[p][x\bmod\ p]$ 的 $maxc$ 个栈中找，还只会加入 $s[x][x\bmod\ c_x]$ 这一个上凸壳，所以复杂度是对的。

时间复杂度 $\mathcal{O}(n\times maxc)$。

$\texttt{card}$

显然位运算要分位考虑。

设 $cnt[i][0/1]$ 为 $2^i$ 这一位上 $0/1$ 的个数。

对于 $2^x$ 这一位，贡献是：

$$2^x\times \sum_{i=0} \binom{cnt[x][1]}{2\times i + 1}\times \binom{cnt[x][0]}{k - (2\times i + 1)}$$

也就是选奇数个 $1$。

$\texttt{password}$

发现数据范围实际非常小，而 $n$ 又非常大。所以考虑使用矩阵快速幂。

对于字符串内出现的匹配串，可以很快通过矩阵快速幂解决。关键是那些在两个串合并的时候出现的匹配串。

首先求出数组 $\text{cnt[a][b]}$ 表示第 $a$ 个串与 $b$ 个串接起来之后，交界处会产生多少个匹配串，这个可以直接 $\mathcal{O}(m^2|G|^2)$。然后考虑要如何求这个东西，首先很快可以发现，由于 $|S|<|G|$，所以我们只关心一个串的开头与结尾。这个东西是有循环节的，非常显然的是这个循环节长度最大也是 $m^2$ 级别，所以考虑先暴力求出这个循环节。

接着，我们设 $s_i$ 是第 $i$ 个串上述交界处匹配串的个数。令生成第 $i$ 个串的时候，交界处增加的串的个数是 $k$，那么：

$$s_i=k+\sum_{j=i-m}^{i-1} s_j$$

后半部分可以直接矩阵快速幂，考虑如何求 $k$。发现一个在循环节不同位置上的 $i$，对应的 $k$ 实际是不相同的。如果把整个转移写作一个矩阵，那对于循环节上每向后转移一位，其矩阵不完全相同。

因此考虑按循环节分一块，也就是把整个循环节的矩阵全乘起来得到一个大矩形。前面非循环节的部分可以暴力乘，然后乘上大矩阵的 $\left \lfloor\dfrac{n-l}{len}\right\rfloor$ 倍，其中 $l$ 是非循环节长度，$\text{len}$ 是单个循环节的长度。最后还会有一些不满一个循环节的项，也暴力乘即可。

需要注意的是，循环节第一次出现的时候不能将其认为是循环节，而应该归在暴力中。因为第一个循环节的矩阵与之后的不一定相同。

2020.10.24

$\texttt{Location:NOIP2020}$

得分：$\texttt{30/400,Rank...}$。

[10.24]-错误

$\texttt{T1}$ 空间爆炸......

[10.24]-部分正解

$\texttt{T1}$

设 $f(x)$ 是 $x$ 每一位的乘积，如果 $f(x)\ne 0$，那么一定每个数字都是 $1-9$。不难发现对于一个 $f(x)$，其质因数只可能是 $2,3,5,7$。所以可以数位 $\texttt{dp}$，设置 $dp[p][i_2][i_3][i_5][i_7]$ 表示有 $p$ 位，数位积为 $2^{i_2}\times 3^{i_3}\times 5^{i_5}\times 7^{i_7}$ 的数字个数。这里可以 $\mathcal{O}(\log_{10}^5 n)$ 求解。

然后现在需要找出一对数字，满足其 $\gcd \le k$，可以四维前缀和优化。

$\texttt{T2}$

首先发现如果一个数字回到原位，整个序列就会还原。

那么如果只看 $1$ 位置的变化的话，设长度为 $n$，可以发现每一次移动，相当于在 $\bmod\ n+1$ 的意义下 $\times 2$。那么现在就是需要找到一些数字，满足：

$$2^k\equiv 1\ (\bmod\ n+1)$$

其中需要满足 $k_{\min}=n$。

这实际上就是在问：$2$ 是否是 $n+1$ 的原根。那么又有欧拉定理：

$$2^{\varphi(n+1)}\equiv 1\ (\bmod\ n+1)$$

也就是说当 $n + 1$ 不是质数时，$\varphi(n+1) < n$，所以一定不合法。

那么现在就只需要对每一个满足 $n+1$ 是质数的 $n$ 进行判断了。但是如何判断 $k$ 的最小值是否是 $n$？

考虑将 $n$ 质因数分解，如果 $k_{\min}\ne n$，那么一定存在一个质因数 $p$，使得：

$$2^{\frac{n}{p}}\equiv 1\ (\bmod\ n+1)$$

所以只需要对 $n$ 的每一个质因数判断即可。实际上，$10^7$ 以内一个数字不同质因数个数是 $\mathcal{O}(8)$ 级别，如果算满，复杂度大概在 $\mathcal{O}(\dfrac{n}{\log n}\times \log n\times 8)=\mathcal{O}(8n)$，可以通过。

$\texttt{T3}$

显然当 $x=y$ 时方案数为 $1$。

否则可以证明 我不会 $x,y$ 的取值是无关的，不妨把他们看成 $0$ 和 $1$。

发现操作可以看做一棵 $k$ 叉树，叶子表示一个原本的细胞，而其他的节点表示他的儿子合并起来，权值就是儿子权值的平均值。

然后不难发现这个东西就只和叶子的深度相关了，设 $1$ 叶子的深度分别为 $a_1,a_2...a_m$，$0$ 叶子深度是 $b_1,b_2...b_n$。然后可以发现，根的权值是：

$$\sum_{i=1}^m (\dfrac{1}{k})^{a_i}$$

现在假设 $0$ 叶子权值也是 $1$，那显然根权值为 $1$。把这些 $0$ 叶子的贡献删掉，剩下的就是 $1$ 叶子的贡献。因此可以把问题转化为：

问有多少 $z$ 可以表示成 $\sum_{i=1}^m (\dfrac{1}{k})^{a_i}$，且 $1-z$ 可以表示成 $\sum_{i=1}^n (\dfrac{1}{k})^{b_i}$。

把这个和看做一个 $k$ 进制的小数 $0.c_1c_2c_3...$。如果他们加起来不发生进位，那一定有 $\sum c=m$，也就是一共有 $m$ 个 $1$ 叶子。发生进位，则 $\sum c$ 减小 $k-1$。因此可以得到：

$$\sum c \equiv m\ (\bmod\ k-1)$$

同时，$1-z$ 每一位的和可以表示为 $1+\sum k-1-c$，$+1$ 是因为最后一位应该是 $k-c$。设有 $L$ 位小数的话，上式可以表示为 $L\times (k-1) + 1 + \sum c$，他要和 $n$ 在模 $k-1$ 的意义下同余。

然后就可以 $\texttt{dp}$ 了，设 $dp[i][j]$ 为现在考虑到小数点后第 $i$ 位，现在前面的 $c$ 的和为 $j$ 的合法方案数。可以前缀和优化一下转移，就是 $\mathcal{O}(nm)$ 的了。需要注意的是，在取答案的时候，当前状态最后一个小数位不能为 $0$，那就再加一维，设 $dp[i][j][1/0]$ 为现在考虑到小数点后第 $i$ 位，现在前面的 $c$ 的和为 $j$ ，最后一位是/不是 $0$ 的合法方案数。

$\texttt{T4}$

结论：

后手必胜当且仅当 $n$ 为偶数且字符串不同排列个数为奇数。

首先证明：

若字符串有偶数种不同的排列，则先手必胜。

如果先手存在一种删除字符的方案使得自己必胜，那就选择删除。

否则就是不存在自己必胜的方案，那么就会选择重排，对方同样会选择重排。这样最后到对手时无法重排了，就不得不删除字符。

若当前字符串有奇数种排列，那一定存在一种删除字符的方法使删除后的字符串仍然有奇数中排列。

设 $a_i$ 是每种字符的出现次数，那么一个字符串的排列个数为：

$$\dfrac{n!}{\prod a_i!}$$

删除一个字符，相当于选择一个 $a_i$，将上式乘以 $\dfrac{a_i}{n}$。以上是奇数当且仅当上下的 $2$ 的次幂相等，那显然 $n$ 中 $2$ 的次幂大于等于任意 $a_i$。所以可以选择 $2$ 次幂最小的 $a_i$，这样就使得删除后的字符串仍然有奇数中排列。

因为偶数种排列的字符串必胜，所以双方一定选择按以上方法删除，这就只和字符串长度有关了。因此可以得出结论：

如果当前字符串有奇数种排列，$n$ 为奇数则先手必胜，$n$ 为偶数则后手必胜。

然后就可以总结出以上结论了。

现在我们需要做的，就是拿总数减去这些后手必胜的状态。

对于 $n!$，其中 $2$ 的个数应该是 $\sum_{i} \lfloor \dfrac{n}{2^i}\rfloor$，因此可以得到：

对于任意 $x$，有：

$$\sum_{i} \lfloor \dfrac{a_i}{2^x}\rfloor=\lfloor \dfrac{n}{2^x}\rfloor$$

没想清楚

这就可以说明如果 $n$ 中某一个二进制位是 $1$，那么必定有且仅有一个 $a_i$ 在这一位为 $1$，如果 $n$ 这一位是 $0$，那必定 $a_i$ 中每一个这一位都是 $0$。

这就说明 $a_i$ 是 $n$ 的一些不交的子集，并且他们的和为 $n$。

然后就可以 $\texttt{dp}$ 了，设 $dp[i][j]$ 为前 $i$ 种字符中 $a_i$ 或起来为 $j$ 的

$$\prod \dfrac{1}{a_i!}$$

的和。可以枚举子集暴力做，最后乘一个 $n!$ 即可。

但是这样太慢，过不去。考虑每次转移的时候，强制规定他取走 $n$ 中最低位的 $1$，其实就是 $\texttt{lowbit}$，就设 $dp[i][j]$ 是选择了 $i$ 个字符，或起来是 $j$ 的 $\prod \dfrac{1}{a_i!}$ 的和。实际上就是不关心这里放的字符是具体哪一个，而是记录有多少种不同的字符。

由于每次一定去掉一个 $n$ 中的 $1$，所以 $i$ 的范围从 $26$ 变成大概 $17$ 的样子，同时状态也减少了很多，然后就可以通过了。

同样你可以直接做快速子集卷积，由于相当于对原本做加法卷积的部分做快速幂，因此改成 $\ln$ 然后 $\exp$ 回来就可以了 或许可以叫做暴力搞过去？

2020.10.28

$\texttt{Location:NOIP2020}$

得分：$\texttt{300/300,Rank1}$。

[10.28]-错误

$\texttt{T2}$ 没想清楚直接写了，浪费了很多时间。

[10.28]-部分正解

$\texttt{T1}$

首先特判一下：

$n=1$ 输出 $0/m$ (在于题目理解)。

$n\ne 1,m=1$ 输出 $0$。

$m=2$，$n$ 为奇数输出 $0$，$n$ 为偶数输出 $2$。

设 $f(n,m)$ 是长度为 $n$，数字种类为 $m$ 的方案数。

把环断开，不考虑 $1$ 和 $n$ 相邻的情况，那方案数应该是：

$$m\times (m-1)^{n-1}$$

但是这样会存在问题，可能 $1$ 与 $n$ 相等。需要容斥一下。不难发现当 $1$ 和 $n$ 相等的时候相当于将 $1$ 和 $n$ 缩成一个点，然后就变成了长度为 $n-1$ 的问题了。

那么就有：

$$f(n,m)=m\times (m-1)^{n-1}-f(n-1,m)$$

边界条件是 $f(2,m)=m\times (m-1)$。

这里就可以矩阵快速幂了，而把柿子拆一下有通项的解法。

把柿子拆掉，可以写成这种形式：

$$f(n,m)=m\times \sum_{i=1}^{n-1} (-1)^{i-1}(m-1)^{n-i}$$

根据 $n-1$ 的奇偶性分类成奇数项和偶数项，设奇数项之和为 $a$，偶数项之和为 $b$，不难发现是他们分别是等比数列的形式。然后就可以直接快速幂搞出来了。

发现指数实际上只和 $n$ 有关，因此可以把 $n$ 模一下 $\varphi(mod)$，可以稍微加快一点点。

时间复杂度 $\mathcal{O}(\log mod)$。

$\texttt{T2}$

发现数据范围非常小，考虑状压 $\texttt{dp}$。

设 $dp[S]$ 为当前已经可以区分的状态为 $S$ 时的最小代价。其中 $S$ 有 $k\times (k-1)$ 位，每一位代表其中某两个矩阵是否可以被区分开了。

然后设 $trans[i][j]$ 表示 $(i,j)$ 这一个位置可以区分开的矩阵对。求 $trans$ 就直接 $\mathcal{O}(nmk^2)$ 即可。

然后就有：

$$dp[S|trans[i][j]]=\min(dp[S|trans[i][j]],dp[S]+1)$$

十分显然。

但是 $k\times (k-1)$ 有 $30$，开不下，所以需要压缩一下。不难发现矩阵对是无序的，所以相当于我们对于同一个矩阵对，在状态中存了两个位置。这很不划算，所以通过一些变换，把每一个矩阵对对应到恰好一个位置，就只有 $\dfrac{30}{2}=15$ 位了，可以接受。

时间复杂度 $\mathcal{O}(T\times(nmk^2+nm\times 2^{d}))$，其中 $d=\dfrac{k\times(k-1)}{2}$。

$\texttt{T3}$

首先十分显然的是：关键点，关键路径就是最短路图的子图。

那就建出最短路图，现在到达关键点 $i$ 的代价为 $dis[i]$ 的话，题目中要求的实际上就是这两种东西的数量：

关键点 $p$ 的个数使得 $dis[p]=dis[i]$。
一条关键路径 $x\texttt{->}y$ 使得 $dis[x]<dis[i]<dis[y]$。

很显然，第一种就是正好在节点上，第二种就是在这条关键路径上。

由于数据并不大，所以第一个是很好搞的。现在考虑第二个要怎么做。

对于一条关键路径 $x\texttt{->}y$，不难发现他对 $(dis[x],dis[y])$ 这一段区间内的 $dis[i]$ 有 $1$ 的贡献。那现在实际上我们需要做的就是多次给某一个区间 $\texttt{+1}$。

数据结构固然可做，但是太麻烦了。可以考虑将所有关键点的 $dis$ 离散化下来，然后考虑一个数组 $s$，每次一条关键路径就在 $s$ 上对应区间更新，然后答案就取 $s[dis[i]]$（此处 $dis[i]$ 已离散化）。

很常见的套路了，先考虑 $s$ 的差分形式，最后前缀和回来。

这样就只需要 $s[dis[x]+1]+1$，$s[dis[y]]-1$ 即可（$dis$ 已经离散化）。

2020.10.31

$\texttt{Location:NOIP2020}$

得分：$\texttt{110/400,Rank3}$。

[10.31]-错误

很多暴力分没有认真写......

[10.31]-部分正解

$\texttt{T1}$

震惊！信息竞赛竟出几何！

首先有结论：

九点圆的圆心是 $\Delta ABC$ 垂心 $H$ 和外心 $O$ 连线的中点。

发现三点都在单位圆上，所以外心正好是原点。

再来考虑垂心。首先显而易见的做法是枚举一条边，然后对于其他 $n-2$ 个点可以取平均数当做同一个点，然后搞来搞去得到垂心。时间复杂度 $\mathcal{O}(n^2)$。

然后考虑到 $\vec{OH}=\vec{OA}+\vec{OB}+\vec{OC}$，又 $O$ 是原点，所以直接有九点圆圆心为 $\dfrac{A+B+C}{2}$。然后就只要计算一下每个点对答案的贡献就可以了。

时间复杂度 $\mathcal{O}(n)$。

$\texttt{T2}$

咕咕咕

$\texttt{T3}$

咕咕咕

$\texttt{T4}$

首先发现，对于原题中的操作，实际上就是将一个点复制一遍。复制的作用实际上就是为了使这个点可以通过更多次。

先考虑一下更简单的问题，如果是存在哈密顿回路的时候结束游戏，设其需要 $g'$ 步操作。设置每个点在某种方案中的通过次数分别为 $s_i$，那一定有：

$$g'=\sum_{i=1}^n (s_i - 1)$$

题解求和不打括号差评

意思是除了第一次到达一个点之外，每一次到达这个点都需要进行一次操作，然后通过复制的新点来完成这个点的功能。

如果设每个点的度数分别为 $d_i$，那么显而易见的是 $\sum s_i \ge \sum d_i$，因为原图是一棵树，所以每个点实际上都需要从每一条边走出，再回来。因此就有：

$$g'=\sum_{i=1}^n (s_i-1)\ge \sum_{i=1}^n (d_i-1)=2n-2-n=n-2$$

也就是操作次数下界是 $n-2$。容易发现的是如果按照欧拉序走这棵树，就可以卡到下界（这里的欧拉序指每次到这个点就将这个点加入序列）。因此如果原图是哈密顿回路的话，答案 $g'=n-2$。

再考虑哈密顿路的情况，实际上就是不需要走回出发的点了。我们考虑返回出发点的过程，从求欧拉序的角度来看就是一直在回溯。每回溯到上一个点，就会进行一次操作。

因此可以发现，哈密顿路的情况和哈密顿回路的情况相比，实际上就是减少了回去时进行的操作。由于我们希望 $g_{\min}$，因此就希望减少的量 $\max$。显然，取直径是最优的。

为什么取直径一定可行呢？假设现在已经得到一个哈密顿回路，那我从任意点出发，一定可以回到原点。也就是说哈密顿回路起点实际上可以任选，那就选直径的一端作为起点即可。

时间复杂度 $\mathcal{O}(n)$。