【游记】ZROI 21noip赛前20天 day9

比赛链接（正睿）

	T1	T2	T3	T4
得分	30	15	30	20
估分	?	20	30	20

比赛开始，首先着手做T1。T1的题目大意是：给出一棵黑白染色的树，每次选择一个点，使得其所在的颜色相同的连通块颜色反转，最少操作的次数。

发现曾经做过相似的题目，于是开始往树的直径方向思考，但由于题目给出的是一棵树，没有想到缩点的方法，于是放弃了思路。之后，我又对照样例，猜想了一个结论，遍历所有点，如果颜色与目标颜色不同，则以这个结点为根找最大的连通块进行更改。当时没有构造出$\text{hack}$数据，我敲完后提交了。

我的第一个思路离正解很近。正解是将所有同色的联通块缩成一个点，答案便是树的直径除$2$。

之后又开了T2，题目大意是：给出一个数列，长度$\le {10}^5$，$n$个操作。操作分为三种，$a_i=b,a_i+=b,a_i\ast =b$。看到题面，暂时没有思路，先写出了$O(2^n)$暴力。

其实这是一道贪心题。首先，第一个操作显然可以转化为操作$2$。对于每个操作给一个权值，进行操作会让答案大多少倍。对于操作$2$我们先加$b$大的，这样得出权值，最后排序一下即可。

接着又看T3，大意为：给定$s$，对于$[1,n]$的升序序列$a$，找到一个$n$的排列$b$使得$\sum _{i=1}^n{a}_i\mathrm{mod}{b}_i=s$ 。发现用全排列$O(n!)$的复杂度可以过$15\mathrm{\%}$的数据，接着，通过特判$s\le 2$的情况可以过掉另外$15\mathrm{\%}$的数据点，我敲完后提交。

T4给定一棵树，要求满足$a$到$b$的距离为$q$，$c$到$b$的距离为$p$，且$a$到$b$的路径和$c$到$d$的路径没有交的四元组$(a,b,c,d)$的数量。两点在树上的距离，想到倍增$\text{LCA}$。对于$20\mathrm{\%}$的数据，想到直接枚举$(a,b,c,d)$。虽然还要检查是否有重复的点，复杂度最坏是$O(n)$，但枚举完$a,b$后只会留下距离符合要求的，所以实际跑不满$O(n^5)$，成功通过这一$\text{subtask}$。