杜斯特伍德生存指南

题解

各位村民：
你们好，我是这场死亡游戏的策划者和主持者。我不知道你们是否参悟了游戏获胜的奥秘，但我保证，这本指南，能让你在这场风暴中存活下来。

1.守卫的指南

在第一个考验中，我们文件的密名就已经告诉了你一切，那就是著名的Joseph问题的变种约瑟夫环。
在这类问题中，我们并不要求找到每一次淘汰的人，我们只要求找到最终淘汰的人。
对于这次考验，你有这样的选择：

40%

你可以用我们解决Joseph问题的一般解法，即直接模拟，判断是否满足。
模拟核心代码可以像这样

int pos=1;int t=n;
    while (t){
        int cnt=0;
        for (int i=pos;cnt!=k;i++){
            if (i>n) i%=n;
            if (dead[i]) continue;
            cnt++;
            if (cnt==k){
                dead[i]=1;
                t--;
                pos=i+1;
                if (t==0) printf("%d ",i);
                break;
            }
        }
    }

100%

我们先不管我们的问题，先来看这样一个场景
野孩子当前排出去了一个房子在，那么现在房子的主人安全了，他要从下一个房子找。
那么岂不是相当于重新编一次号？
每次相当于重新编号以后这一次和上一次不就相差k吗，那我们可以直接通过递推式来递推出来答案。
递推式如下:

int ans=0;
for (int i=2;i<=n;i++) s=(s+k)%i;
printf("%d",s+1);

上面就是正解的核心代码；
注意一点，我们通过%的方式写出来的答案均为从0开始，题中明确给出从一开始，因此要注意+1.

纵火犯指南

在纵火犯的考验中，我们事实上是寻找一个图从哪几个点遍历能遍历到整个图，因为数据小，拿分的方法很多，此处只给出正解的方法。
题中虽然是矩阵，却是有向图。题中求的实际上可转化为强连通分量缩点后入度为0的强连通分量的个数。
Tarjan即可，此处不在给出代码

修路工的考验

你可以去看我的另一篇题解架设电话线，原题。