USACO24Bronze 游记兼 TJ All in Once
我没有其他组别的号了。所以只能写 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 肯定成立。
所以成立。
第二部分也就很简单了：直接选取个位，坑死对方。
\(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))\)。