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

比赛链接(正睿)

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

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

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

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

之后又开了T2,题目大意是:给出一个数列,长度个操作。操作分为三种,。看到题面,暂时没有思路,先写出了暴力。

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

接着又看T3,大意为:给定,对于的升序序列,找到一个的排列使得 。发现用全排列的复杂度可以过的数据,接着,通过特判的情况可以过掉另外的数据点,我敲完后提交。

T4给定一棵树,要求满足的距离为的距离为,且的路径和的路径没有交的四元组的数量。两点在树上的距离,想到倍增。对于的数据,想到直接枚举。虽然还要检查是否有重复的点,复杂度最坏是,但枚举完后只会留下距离符合要求的,所以实际跑不满,成功通过这一