我没有其他组别的号了。所以只能写 Bronze 的游记了。
如果行的话,下一次我会写 Silver 的。
一开始看了看三道题,T1T2 感觉都很不可做,直奔 T3。
一看 T3(Bessie 很 nb,会各种各样的东西,会科学,会魔法,今天我们发现她会分身术),不就是个二分吗?秒杀。
好的,现在搞 T1T2,直接《男 左 女 右 我 选 左》,开了 T1。
T1 一看数据范围就知道这题不一般,得推,结果发现答案只与最后一位有关系,秒杀。
所以只有 T2 了。剩下的三个小时四十五分钟(是的,T1T3只用了 15 分钟)可以全部用来死磕 T2。
一开始毫无头绪,干脆写模拟,但是用模拟我发现过程是有一定规律的!
找到规律,\(O(M)\) 瞬间变成 \(O(N \log N)\),T2 搞定。
于是...就这样 AK 了...
附录:三道题 TJ
按照难易度从小到大排序。
T3
2~4
直接暴力。
\(O(NQ)\)。
5~9
想不出来。
AC
直接预处理出 Bessie 为了到达每一个农场她最晚要什么时候起来,然后排序 lower_bound
即可。
\(O(Q \log N)\)。
思维:普及-中位
代码:普及-下位
算法:普及-中位
无数据结构
综合:普及-中位
T1
直接想出了正解。
AC
本题有一个绝妙的性质,叫做:
对于一个数 \(x\),如果 \(10 \mid x\),则输出 E
,否则输出 B
。
这玩意可以拆成两部分。
第一部分,如果 \(10 \mid x\),则输出 E
:
考虑数学归纳法。
首先 10 肯定成立。
\[\because x \ \text{is not palid} \]\[\therefore \forall x \ \text{that is palid}, \ 10 \nmid x \]\[\therefore 10a \to y \to 10b \quad (b \lt a) \]所以成立。
第二部分也就很简单了:直接选取个位,坑死对方。
\(O(N)\)。
思维:普及-上位
代码:普及-下位
无算法
无数据结构
综合:普及-中位
T2
这个题我要精讲!
4~8
直接大模拟。
\(O(NM)\)。
AC
经典多解题。
首先建有向图。
解法一
Spetial Thank to appear_hope for this solution.
可以观察到除了环以外,每一个弱连通块每分钟会损失 1 单位牛奶。
直接计算。
\(O(\min(M, N))\)。
解法二
用模拟程序推出来的。
我们维护一个最终会流光的桶的集合,然后按照流光的时间从小到大选取。
对于一个流光的桶,被这个桶影响到的桶如果也会流光,那么也要将这个新桶加入集合。
\(O(\min(M, N \log N))\)。
标签:10,普及,log,中位,T2,USACO24Bronze,流光,TJ,Once From: https://www.cnblogs.com/hhc0001deljbk/p/18021094