2025总结

USACO25FEB

B

开了个小号，打了一下，T1 简单切掉， T2、T3 没看，但是听他们一片哀嚎感觉好像有点问题，算了，找个时间去看一看吧。

S

正经打的，其实吧，这个银组本质上是不难的，只不过有点需要思维（我没有的东西），但是还是写出来了。

T1

题意：给出一个序列，可以将一个数放到它之前的一个位置（只能做一次），求换之后的最大字典序子序列。

十分显然，观察得到，假设没有提前操作，一个单调栈即可解决，当有提前操作时，它只有可能影响最大和次大值，直接做就行了，关键性质时只能提到前面，需要一定注意力。

注意 USACO 是全文比较，不忽略行末空格。

T2

题意：给出一个字典，其中每个字符串互不为其他字符串的前缀，按一定顺序给出字典序列，每次求在第几个时可以得出答案（序列不重，也就是说前面询问的也是信息）

简单题，建立字典树，倒序操作，转删为加，每个节点只会访问一次，时间复杂度可过。最关键的是要逆向思维，转删为加。

T3

题意：给定 $a,b$ 每次可选择 $a\operatorname{+=}b \space \texttt{or} \space b\operatorname{+=}a$，求能否达到 $c,d$。

2025022920250301

喜报：今天考试开始时陈老下发了所有题目的数据，成功被迫换题。

T1

太棒了，又是使用一个大半年没用的算法又一遍打对的一天。矩阵快速幂考场上从零开始推，大样例又一遍过，简直是太棒啦！

还有就是和出题人进行心理博弈的经验++，我就赌出题人在极限数据全放的极限数据，没有小数据，我就写了一个对于所有询问全都非常大的代码，并成功成为考场上唯二的 A 掉这道题的人。

T2

没发现题目的变形，转而向原题面进行了一通复杂的推演，最后因为推论太过复杂而放弃，其实形式化并变形以后事情变得异常简单，DP 完全可以在 30min 以内推出。

所以就是阅读能力和形式化能力太差了，如果在考场上能早点发现变形，那我也就绝对不至于考成这个鬼样子。

T3

一点都不会，于是我放弃了这道题，这道题我们机房一共 7 人，共有 3 人为此题编写了代码，共获得了 0pt 的好成绩。

但是赛后看题解就是简单 Hash+二分，最难的是想到前面的 DP 最优性（还是观察能力的问题）。

T4

那张图的转化是我没想到的，数形结合是一个非常基本的算法思想吧，但是我考试时全想着怎么心理博弈了，最后成功失败，本来以为是骗分学竞赛，现在发现是想象学竞赛观察力竞赛了（恼）。