结论

第一次考金，没有期望能过。不过这次的题可能是史上最水的一次金，做的我认为不是很理想。

T1: A了

T2: 1/3

T3: 0

最近学业和各种其他的课外项目来了，练OI的动力和机会少了很多。慢慢来吧，看看这一届USACO能不能过金。

T1 Flight Routes G

肯定是抽象为图。在纸上画了画sample，找到了几个性质：

• 边都为双向边
• 考虑加边时只会从小点到大
• 给点i连新边只会影响点i和小于点i的相邻点

到这里就差不多了，连新边时再连新边或者拆旧边维护相邻点的连通性即可。

使用原始的邻接矩阵存图，很方便。

剩：3.5小时

T2 Minimum Longest Trip G

明显图论，图论算是我最喜欢的题型，感觉良好。

因为这么快拿满了第一题，心有点急。第一眼认为就是反建边拓扑求DAG最长路，优先队列维护字典序（我以为只需要保证最长路的点字典序最小即可，其实是所有路标）。

模版熟记于心，代码很快就写出。测sample发现了问题😁。

折腾了一会，准备理一下思路。时间不允许我们记录路上的路标再在结尾比较。我决定维护一种单调性，保证第一个走到的最长路就是字典序最小的。

简单点来说没成功，dp递归啥都试了试。拿了1/3，打个暴力可以再拿两个点，心有点乱了。思考了一下发现第三题拿满还有机会可以过，去看下一题。

后面就再也没回来了。

剩余：1小时多

复盘发现这题解比我想象的复杂，第一步走错后面就不好处理了，按我的水平赛内最优应该也只是捞部分分。

T3 Haybale Distribution G

一眼认为结果是先减后增，准备二分QlogN拿下。 O(1)求结果交给前缀和。

二分答案不对，打纯暴力先捞点分顺便验证我剩下的写的有没有问题。

好！暴力除了sample全WA+T。

暴力都不对…发呆，摆烂，遗憾退场。

寄。

复盘发现暴力全错是因为忽略了重叠坐标（蠢），结果确实是先减后增，可以二分。如果注意到重叠坐标可能第一发就拿满了，反手再去T2混点分有可能可以过。

后言

节奏从第二题读题读错并且乱改版开始就乱了，第三题开做的时候只顾着拿分没有好好思考。

下个月见。