IOI2020 国家集训队作业小结 4

AGC029 C Lexicographic constraints

相当于要求我们建一个 TRIE。那么二分答案，然后用数组维护 TRIE 的右链即可。

数组开不下，改成 map 即可。

复杂度$O(n\log_2^2n)$。

AGC030 C Coloring Torus

对于一个$n \times n$的网格，称$(r, c)$为处于第$r + 1$行，第$c + 1$列的格子。一个对网格的好的$k$染色是满足下述条件的染色方案：

1. 每个格子被染成$1, 2, 3, \cdots , k$这$k$种颜色之一。
2. $k$种中的每种颜色都被至少一个格子使用。
3. 对于任意颜色$i, j(1\le i\le k, 1 \le j \le k)$，满足所有颜色为$i$的格子，其相邻的颜色$j$的格子个数相同。这里，与$(r, c)$相邻的格子为$((r − 1) \bmod n, c)$，$((r + 1) \bmod n, c)$，$(r, (c − 1) \bmod n)$，$(r, (c + 1) \bmod n)$（如果一个格子多次出现，那么会算多次）。

给出$k(1 \le k \le 1000)$，选择一个$1 \le n \le 500$，任意构造一个对$n \times n$的网格的好的$k$染色。

当$k\le 500$时，每行一个颜色。

对于$n$是偶数：

void make(int n){
    FOR(i,0,n-1)FOR(j,0,n-1)a[i][j]=(i+j)%n;
    FOR(i,0,n-1)if(i&1)FOR(j,0,n-1)a[i][j]+=n;
}

这样构造出来的矩阵是$k=2n$时的答案。

观察发现，把矩阵中所有$n+i$的颜色替换为$i$，矩阵的性质是不会被破坏的。那么我们可以用这个方法删掉一个颜色。

因此直接构造一个$n=500$时的矩阵，然后删掉$1000-k$个颜色即可。

时间复杂度$O(n^2)$。

AGC029 E Wandering TKHS

考虑结点 u 比父亲多走到了哪些点。设$p_u$表示 u 的父亲。$m(u)$表示路径$1\sim p_u$中结点编号的最大值。令$Q(u,x)$表示 u 只经过$\le x$的点能走到的后代结点数量（$u$自己不算）。那么对于所有$u>1$，我们有

$$ans(u)-ans(p_u)= \begin{cases} Q(u,m(u))+1 & (u>m(p_u))\\ Q(u,m(u))-Q(u,m(p_u)) & (u<m(p_u)) \end{cases}$$

原因是如果$u>m(p_u)$，那么以$p_u$为起点时就不会访问到$u$，我们就要新加入$u$以及它子树中的信息。否则一定会访问到$u$。但是从$p_u$出发只会经过$\le m(p_u)$的点，而从$u$出发为经过$\le m(u)$个点，所以要进行一定的修改。那么现在我们只要求出$Q(u,m(u)),Q(u,m(p_u))$即可。

$Q$的转移式如下：

$$Q(u,x)=\sum_{v\in Son(u),v\le x} Q(v,x)+1$$

直接递归记忆化，复杂度是对的。因为对于$Q(u,m(u))$，我们找到所有它后代中第一次$>m(u)$的点并剪掉它这棵子树，之后$u$的子树中点$v$的询问就只剩下$Q(v,m(u))$了。同理$Q(u,m(p_u))$递归到每个点也只有常数种询问。

时间复杂度$O(n\log_2n)$或$O(n)$。

AGC029 F Construction of a tree

这题 sb 了。读题度锅了导致自闭。

假设$1$是根，先网络流从每个集合里选一个数形成一个$2\sim n$的排列，把它们看作每个集合的关键点。接下来从${1}$开始贪心能找到父节点就接上去。相当于我们把每个集合的每个点与它的关键点连有向边，在图上 DFS。一个 DFS 生成树就是答案。

显然能构造出来一定是对的，考虑中途一步不能构造出来的时候，说明无论如何与已经确定的$k$个点相关的边数都达不到$k$条，显然这在树中是不可能的，因此是无解的。