2021-team8-005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

= 流水账 =
签到依旧很顺利，然后遇到了J，思考后xqj给出一个做法，会被一种图卡掉，rtx表示反过来再做一遍就可以，开始码之后发现算法问题很大，但还是很莽地交了，然后就过了？？？yys对C有了思路，开始上机，A和E开题，觉得不可做，之后C出现一些困难，rtx去辅助，有一些进展，但随后出现了更多问题，于是rtx上机改变思路重构代码，居然过了，（感谢帮忙调代码的时候发现了很多坑）。

= 总结 =
我们队最擅长签到（雾），签到要快。应该把题都看完，找适合自己队的做，不一定非要做先有人做出来的题。

= 题解 =
A: （听说可以看成树形结构，然后dp，挺复杂的）

B: 发现结论：每一次一定赌上当前能赌的最大钱数，该结论可通过反向模拟、分段分类讨论证明。然后模拟即可。

C: 看成一个自动机，要求经过一个模式后，除给定点外其他点都转移到终点集合。所有状态一起推进，每一次判断当前哪些转移可行，贪心地随便选一个转移即可。怎么判断一个转移是否可行：首先，至少一个非给定状态转移到另一个状态，其次，所有状态不能转移到给定状态，最后，给定状态尽量不转移，如果必须转移也要转移到非终点集合。

D: 求出两点的LCA和他们与当前树根的LCA，分类讨论即可。

E: （没听清）

F: 签到

G: 拓扑序从后往前，维护一个堆，贪心

H: （好像没人碰？）

I: （听说是后缀自动机上跑费用流）

J: （数据特别弱，敢交就能过）看别人代码，似乎正解是 将所有入度为0的点random_shuffle一下，依次dfs，不走重复的点，得到dfs到最多点的起点，这样做很多次（1000），然后很大概率能得到答案

流水账

签到依旧很顺利，然后遇到了J，思考后xqj给出一个做法，会被一种图卡掉，rtx表示反过来再做一遍就可以，开始码之后发现算法问题很大，但还是很莽地交了，然后就过了？？？yys对C有了思路，开始上机，A和E开题，觉得不可做，之后C出现一些困难，rtx去辅助，有一些进展，但随后出现了更多问题，于是rtx上机改变思路重构代码，居然过了，（感谢帮忙调代码的时候发现了很多坑）。

总结

我们队最擅长签到（雾），签到要快。应该把题都看完，找适合自己队的做，不一定非要做先有人做出来的题。

题解

A: （听说可以看成树形结构，然后dp，挺复杂的）

B: 发现结论：每一次一定赌上当前能赌的最大钱数，该结论可通过反向模拟、分段分类讨论证明。然后模拟即可。

C: 看成一个自动机，要求经过一个模式后，除给定点外其他点都转移到终点集合。所有状态一起推进，每一次判断当前哪些转移可行，贪心地随便选一个转移即可。怎么判断一个转移是否可行：首先，至少一个非给定状态转移到另一个状态，其次，所有状态不能转移到给定状态，最后，给定状态尽量不转移，如果必须转移也要转移到非终点集合。

D: 求出两点的LCA和他们与当前树根的LCA，分类讨论即可。

E: （没听清）

F: 签到

G: 拓扑序从后往前，维护一个堆，贪心

H: （好像没人碰？）

I: （听说是后缀自动机上跑费用流）

J: （数据特别弱，敢交就能过）看别人代码，似乎正解是 将所有入度为0的点random_shuffle一下，依次dfs，不走重复的点，得到dfs到最多点的起点，这样做很多次（1000），然后很大概率能得到答案