前三题过水，第四题分类讨论两个端点之间的距离和所在位置是清醒或睡眠 即可。
题意：一张图上有一些结点有保安，每个保安有不同的警戒度 \(h_i\)，定义 一个结点是安全的 为这个结点可以到达一个保安 \(x\)，且距离 \(\leq x\)。
问有多少个安全的结点。
痛失第五题
很简单的思路：从每个保安开始广搜，每多走一个点可以视作警戒度减一。同时在每个点记录到这个点时最大的警戒度。
先把保安按警戒度大小排个序。
然后依次广搜即可。
交互题。
初始在一号节点，要通过至多 \(2n\) 次移动到达 \(n\) 号结点，每到一个节点，就会告诉你该节点的相邻节点。
考虑图的深度优先遍历。完整遍历一张图时，一定进入了每个节点恰好一次。同时，除了每次遍历的第一个节点外，一定会从每个节点返回上一个节点一次。所以模拟深度优先遍历，在 \(2n\) 次移动之内必然可以遍历整张图，到达节点 \(n\)。
每次优先向未访问过的节点移动，如果某个节点的相邻节点都被访问过则返回上一个节点，记录每个节点的上一节点模拟即可。
题意：给出 \(m\) 个由 a 和 b 组成的长度 \(\leq 6\) 的字符串，求出字符串 \(T\) 的个数，满足：
-
\(T\) 的长度为 \(n\)；
-
\(T\) 的所有子串都不包含给出的 \(m\) 个字符串。
答案取模。
注意到 \(N\leq 10^{18}\)。
矩阵快速幂。
定义 \(dp[i]\) 为长度 \(i\) 的不包含给定字符串的个数。
考虑 \((dp[i-5],\cdots,dp[i])\) 转移到 \((dp[i-4],\cdots,dp[i+1])\)。
（六个是因为长度 \(6\)）
如果不存在任何限制，转移矩阵应该长这样：
\[\begin{pmatrix} 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&1\\ 64&0&0&0&0&0\\ \end{pmatrix} \]左下角的 \(64\) 是因为从 \(i-4\sim i+1\) 共 \(6\) 个位置，一共有 \(2^6=64\) 种字符串，除去最后 \(6\) 长度的，还有前面 \(i-5\) 个。
考虑每一个给出的字符串。对于每一个给出的字符串，
标签：结点,ABC,305,遍历,字符串,保安,节点,dp From： https://www.cnblogs.com/FLY-lai/p/18012017