Codeforces Round #819
source link: https://www.shuizilong.com/house/archives/codeforces-round-819/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
C. Jatayu’s Balanced Bracket Sequence
调整法。
基础情况是 ((()))。。连通分量为 n。我们观察什么情况下连通分量会减少。
(()())。。比如这样。。条件是之前出现过层级一样的括号序列使得以当前位置结尾的合法序列不止一组。
于是只要开个 bool 数组记录一下哪些层级出现过就好了，当然弹栈的时候要恢复。
D. Edge Split
首先考虑树的情况，发现无论如何染色都不影响结果。
得知我们每条边染色的目的，是减少对应颜色的一个连通分量。
因此我们考虑将其中一种染色固定成一颗生成树，这样只要保证多出的边不构成一个环即可。
而这在只有 3 条额外边的情况下总是可以保证的。
E. Almost Perfect
统计长度为 n 的置换中，满足 |pi–pi−1|≤1 的置换的数目。
对满足条件的置换进行循环分解，只有三种情况，(i) (i,j) (i,j,i+1,j+1)。
不考虑 4 的情况，可以枚举 2 的数目，两两配对，方案是：
Σi!j!∗(i−2∗j)!∗2j
也可以用类似斯特林数的方法得到地推公式。
预处理这个在枚举 4 的数目即可。
F. Late For Work
题意：一条直线，表示一条路。直线上有 n 个点，表示 n 个红绿灯。所有红绿灯的周期都是 t，第 i 个红绿灯的周期起点是，它在每个周期的前 gi 秒为绿灯，后 t – gi 秒为红灯。即在每个周期中 [0, gi) 时间时为绿灯，(gi, t] 为红灯。从第i个红绿灯到i+1个红绿灯所需的时间为 di。你可以从任意时间开始，问从第一个红绿灯开始，需要多少时间可以穿越这 n 个红绿灯。
印象中 14 年多校镇海中学 Round，和 SRM rng_58 时代都各出过类似的问题。。。
https://vjudge.net/problem/HDU-4881
Posted by
xiaodao
Category: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK