【游记】ZROI 21noip赛前20天 day9
T1 | T2 | T3 | T4 | |
---|---|---|---|---|
得分 | 30 | 15 | 30 | 20 |
估分 | ? | 20 | 30 | 20 |
比赛开始,首先着手做T1。T1的题目大意是:给出一棵黑白染色的树,每次选择一个点,使得其所在的颜色相同的连通块颜色反转,最少操作的次数。
发现曾经做过相似的题目,于是开始往树的直径方向思考,但由于题目给出的是一棵树,没有想到缩点的方法,于是放弃了思路。之后,我又对照样例,猜想了一个结论,遍历所有点,如果颜色与目标颜色不同,则以这个结点为根找最大的连通块进行更改。当时没有构造出数据,我敲完后提交了。
我的第一个思路离正解很近。正解是将所有同色的联通块缩成一个点,答案便是树的直径除。
之后又开了T2,题目大意是:给出一个数列,长度,个操作。操作分为三种,。看到题面,暂时没有思路,先写出了暴力。
其实这是一道贪心题。首先,第一个操作显然可以转化为操作。对于每个操作给一个权值,进行操作会让答案大多少倍。对于操作我们先加大的,这样得出权值,最后排序一下即可。
接着又看T3,大意为:给定,对于的升序序列,找到一个的排列使得 。发现用全排列的复杂度可以过的数据,接着,通过特判的情况可以过掉另外的数据点,我敲完后提交。
T4给定一棵树,要求满足到的距离为,到的距离为,且到的路径和到的路径没有交的四元组的数量。两点在树上的距离,想到倍增。对于的数据,想到直接枚举。虽然还要检查是否有重复的点,复杂度最坏是,但枚举完后只会留下距离符合要求的,所以实际跑不满,成功通过这一。