【游记】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*=b\)。看到题面，暂时没有思路，先写出了\(O(2^n)\)暴力。
其实这是一道贪心题。首先，第一个操作显然可以转化为操作\(2\)。对于每个操作给一个权值，进行操作会让答案大多少倍。对于操作\(2\)我们先加\(b\)大的，这样得出权值，最后排序一下即可。
接着又看T3，大意为：给定\(s\)，对于\([1,n]\)的升序序列\(a\)，找到一个\(n\)的排列\(b\)使得\(\sum_ {i=1}^{n} a_i \mod b_i=s\) 。发现用全排列\(O(n!)\)的复杂度可以过\(15\%\)的数据，接着，通过特判\(s\le 2\)的情况可以过掉另外\(15\%\)的数据点，我敲完后提交。
T4给定一棵树，要求满足\(a\)到\(b\)的距离为\(q\)，\(c\)到\(b\)的距离为\(p\)，且\(a\)到\(b\)的路径和\(c\)到\(d\)的路径没有交的四元组\((a,b,c,d)\)的数量。两点在树上的距离，想到倍增\(\text{LCA}\)。对于\(20\%\)的数据，想到直接枚举\((a,b,c,d)\)。虽然还要检查是否有重复的点，复杂度最坏是\(O(n)\)，但枚举完\(a,b\)后只会留下距离符合要求的，所以实际跑不满\(O(n^5)\)，成功通过这一\(\text{subtask}\)。