【UVALive 7334】Kernel Knights
Kernel UVALive
2023-09-11 14:19:25 时间
题意
有两个队的骑士1到n和n+1到2n,每个骑士只能互相攻击对手队的一个骑士。kernel的意思是在这个kernel里的骑士不会互相攻击,在kernel外的骑士被kernel里的骑士攻击。
现在告诉你所有骑士攻击的骑士,求一个kernel。
分析
没人攻击的骑士一定在kernel里,把没人攻击的加入队列,然后被他攻击的骑士一定在kernel外。
kernel外的骑士的攻击无效,因为如果一个骑士如果只被外面的骑士攻击,他就是kernel里的。
于是 被 外面的骑士攻击 的骑士 的被攻击次数 -1,如果被攻击次数为0了就加入队列。
某个导致我WA的地方:被攻击次数 -1 这个操作不能重复,所以要判断当前这个“外面的骑士”是不是已经处理过。
反例:
4
5 5 8 7
3 3 4 4
正确答案:1 2 6 7 8
重复操作的错误答案:1 2 3 6 7 8
处理完后,剩下的就是一个边数为偶数的环,只要输出它的一边就好了。
这题也可以DFS。
代码
#include<cstdio> #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; }
相关文章
- 解决编译内核模块helloworld.c:1: 错误:代码模式‘kernel’在 32 位模式下不受支持问题,未编译对64位的支持
- linux(centos8):查看操作系统的当前版本(os/kernel/bash)
- Linux Boot,Kernel 和 Service 介绍
- nginx conf by linux kernel
- linux kernel下输入输出console怎样实现
- 【Linux 内核】调度器 ② ( sched_class 调度类结构体源码 | 源码路径 linux-5.6.18kernelschedsched.h )
- Kernel space是啥?
- 编写kernel第一个Hello World
- Kernel,内核模块签名机制、CONFIG_MODULE_SIG
- Kernel: text段为什么前面是两个点,LD_DEAD_CODE_DATA_ELIMINATION, ffunction-sections
- 嵌入式Linux开发,去掉内核kernel开机画面logo屏幕上的打印信息