26.9.8 比赛记录
更新于 2026年9月26日约 2 分钟阅读
挂完了,模拟赛两道绿题,写的都是正解,结果 分,赛后发现给代码加上 个字节,再把 putchar 换成 cout,我就 分了!赛时我怎么死活没调出来!
看来我的 debug 能力还需加强。
T1 P8269
把牛的访问关系建成一个图,容易发现每个点都有且仅有一个出边,所以这是内向基环树森林(类似 P9013)。然后可以发现基环树的树部分,所有牛都可以产生哞叫,剩下的环部分,让牛按照顺序产生哞叫,发现最后剩下一个牛只能待在原地。我们取环上权值最小的牛,把他的 减去。
至于怎么遍历基环树,怎么判断环,用几次 dfs 就可以了。注意细节,赛时就是因为细节问题没调出来。
T2 P10277
赛时做法比较乱,并且没有过,自认为做的没问题。在 dfs 里加了一个条件判断,就过了。
就是维护一个优先队列,按照面试结束的时间把牛存进优先队列里。每次取结束时间最早的,接在他后面,并把他弹出队列。如果有多个相同结束时间的,那么接哪个都有可能。牛们排在谁后面的关系构成一张图,从 Bessie 开始遍历,检查各个农夫的可达性。