EGOI2024 简单题解
Day1
T1 Infinite Race
由于只有重复超过一个人才肯定是跑过一圈的，所以只用用一个数组做标记就可以了，每超过一次就打上标记，否则去掉标记。
T2 Bouquet
定义 \(dp[i]\) 为，以第 \(i\) 种郁金香结尾的选法中最大可选的郁金香数量， 易得状态转移方程为：
\(dp[i]=max{dep[j]}+1(j<l_i\le i\le n,r_j<i)\)
取其中最大值即是答案。
在用线段树优化即可。
T3 Team Coding
最傻逼的一个题。
考虑根号分治。
对于个数大于 \(\sqrt n\) 的颜色，直接暴力。
对于个数小于 \(\sqrt n\) 的颜色，dfs 乱搞一下即可。
T4 Garden Decorations
vp 的时候没做出来qwq。
其实就是个构造题，感觉挺神秘的。
Day2
T1 Circle Passing
弱智题，二分一下就好了。
T2 Bikeparking
考虑贪心，先最大化 \(j<i\) 的匹配数量，然后尽可能多地保留 \(j=i\) 的匹配即可。
T3 Light Bulbs
考虑随机化。
我们维护确定的横着的灯泡以及竖着的灯泡集合，还有剩下的行与列集合。每确定一个横着的灯泡就删掉这一行，竖着的灯泡同理。
然后就很简单了。
T4 Make them Meet
一条链的情况
奇数轮连边 \(2*i\) 和 \(2*i+1\)，偶数轮连边 \(2*i+2\) 和 \(2*i+3\)。这样每个人会在链上不断循环走，经过 \(2n\) 轮后，两个人一定会相遇。
一棵树的情况
奇数轮连所有深度为奇数的点 \(u\) 到 \(fa_u\) 的边，偶数轮同理。同时在每一轮中，都连上 \(root\) 和 \(son\) 的边。
这样在 \(2n\) 轮后，两人一定会在 \(root\) 和 \(son\) 的边上相遇。
一般图的情况
对于树的构造，我们发现只要满足以下的条件就能套用到图上：
- 对于任意一个点 \(u\) 的所有儿子之间没有连边。（在给 \(u\) 和儿子染同种颜色时不会走错）
- 对于根节点 \(root\)，需要选出一个儿子 \(son\)，使得 \(root\) 和 \(son\) 的所有儿子没有连边。（在给 \(root,son\) 和这些点染同种颜色时不会走错）
所以，dfs 后分类讨论一下就好了。