26.9.8 比赛记录

更新于 2026年9月26日约 2 分钟阅读

挂完了,模拟赛两道绿题,写的都是正解,结果 28+3528+35 分,赛后发现给代码加上 1414 个字节,再把 putchar 换成 cout,我就 200200 分了!赛时我怎么死活没调出来!

看来我的 debug 能力还需加强。

T1 P8269

把牛的访问关系建成一个图,容易发现每个点都有且仅有一个出边,所以这是内向基环树森林(类似 P9013)。然后可以发现基环树的树部分,所有牛都可以产生哞叫,剩下的环部分,让牛按照顺序产生哞叫,发现最后剩下一个牛只能待在原地。我们取环上权值最小的牛,把他的 viv_i 减去。

至于怎么遍历基环树,怎么判断环,用几次 dfs 就可以了。注意细节,赛时就是因为细节问题没调出来。

T2 P10277

赛时做法比较乱,并且没有过,自认为做的没问题。在 dfs 里加了一个条件判断,就过了。

就是维护一个优先队列,按照面试结束的时间把牛存进优先队列里。每次取结束时间最早的,接在他后面,并把他弹出队列。如果有多个相同结束时间的,那么接哪个都有可能。牛们排在谁后面的关系构成一张图,从 Bessie 开始遍历,检查各个农夫的可达性。

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC