自动搬运

查看原文

来自洛谷，原作者为

	TsH_GD 肥沃

搬运于2025-08-24 21:59:18，当前版本为作者最后更新于2021-10-13 14:29:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题的第一篇题解（也是我的第一篇题解）

题链

分析

没人攻击的骑士一定在 $\rm kernel$ 里，把没人攻击的加入队列，然后被他攻击的骑士一定在 $\rm kernel$ 外。

$\rm kernel$ 外的骑士的攻击无效，因为如果一个骑士如果只被外面的骑士攻击，他就是 $\rm kernel$ 里的。

于是 被 外面的骑士攻击 的骑士 的被攻击次数 -1，如果被攻击次数为 $0$ 了就加入队列。

某个导致我 WA 的地方：被攻击次数 -1 这个操作不能重复，所以要判断当前这个“外面的骑士”是不是已经处理过。

code:

#include<queue>
#include<cstring>
using namespace std;
const int maxn=2e5+100;
int n,a[maxn],d[maxn],k[maxn];
queue<int> q;

int main()
{
    while(~scanf("%d",&n))
    {
        while(!q.empty()) q.pop();
        memset(d,0,sizeof(d));
        memset(k,0,sizeof(k));
        for(int i=1; i<=2*n; i++)
        {
            scanf("%d",&a[i]);
            d[a[i]]++;
        }
        for(int i=1; i<=2*n; i++)
        {
            if(d[i]==0)q.push(i);
        }
        while(!q.empty())
        {
            int p=q.front();
            q.pop();
            k[p]=1;
            if( k[ a[p] ]==-1  )continue;//没有它而让我WA的地方
            k[a[p]]=-1;
            d[a[a[p]]]--;
            if(d[a[a[p]]]==0)q.push(a[a[p]]);
        }
        for(int i=1; i<=2*n; i++)
        {
            if(i<=n&&k[i]>=0)printf("%d ",i);
            else if(k[i]==1)printf("%d ",i);
        }
        printf("\n");
    }
    return 0;
}

qwq，一定要过啊