Description
为了准备期末考试了,laprovence正被讨厌的数字逻辑搞的头昏脑胀,尤其后面的一堆乱七八糟的概念,简直不知所云@#~!*&~
这不有道简单的题就把他给难住了,题目大意是这样的:给出n个发光二极管,每个二极管都有两种状态,亮(on)与灭(off),然后给出一组每两个二极管之间的约束关系,
约束关系有以下3 种
1)a and b 表示第a个与第b个二极管必须同时亮
2)a or b表示第a个与第b个二极管至少有一个亮
3)a xor b 表示第a个与第b个二极管必须是一个亮,一个灭
Input
第一行两个整数n(二极管的个数,n<=10),m(m组约束关系,m<=50)
然后m行约束关系以a and b,a or b,a xor b的形式给出
多组测试数据,当n=0,m=0时结束
Output
输出每个二极管的状态(一行,每两个状态之间用空格隔开,最后一个不要空格,保证只有一组解),如果没有解输出No solution
Sample Input
2 1
1 and 2
3 3
1 and 2
2 xor 3
1 and 3
0 0
Sample Output
on on
No solution
思路:
优先考虑and的语句,将其中的灯全打开,然后在bfs遍历这些灯,考虑另外两种语句,如果可以判断某个灯的状态则且灯当前状态和应该所处的状态不矛盾则继续,否则则No solution
代码:
#include<iostream> #include<queue> using namespace std; char arr[2][5]={"or","xor"}; int Graph[15][15];//1,2,3分别代表i,j之间的关系为and,or,xor int flag[15];//-1,0,1分别表示每个灯的状态,-1->off,0->no status,1->on int main() { int n,m; scanf("%d %d",&n,&m); while(!(n==0&&m==0)) { queue<int>q; memset(Graph,0,sizeof(Graph)); memset(flag,0,sizeof(flag)); for(int i=0;i<m;i++) { int a,b; char rel[5]; scanf("%d %s %d",&a,rel,&b); for(int j=0;j<2;j++) { if(strcmp(rel,arr[j])==0) { Graph[a][b]= Graph[b][a] = j+2; break; } } if(Graph[a][b]==0) { if(flag[a]==0) { flag[a] = 1; q.push(a); } if(flag[b]==0) { flag[b]=1; q.push(b); } } } bool res = true; while(res == true&&q.size()) { int cur = q.front(); q.pop(); for(int i=1;i<=n;i++) { if(i==cur); else { if(Graph[cur][i]==2) { if(flag[cur]==-1) { if(flag[i]!=-1) { if(flag[i]==0) q.push(i); flag[i]=1; } else res = false; } } else if(Graph[cur][i]==3) { if(flag[cur]==1) { if(flag[i]!=1) { if(flag[i]==0) q.push(i); flag[i]=-1; } else res = false; } else if(flag[cur]==-1) { if(flag[i]!=-1) { if(flag[i]==0) q.push(i); flag[i]=1; } else res = false; } } } } } if(res) { for(int i=1;i<=n;i++) { if(flag[i]==-1) printf("off"); else if(flag[i]==1) printf("on"); if(i==n) printf("\n"); else printf(" "); } } else printf("No solution\n"); scanf("%d %d",&n,&m); } }
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
boj 上08 09 年复试模拟题的答案
JAVA_BOJ
boj:算法
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
BOJ
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
解决问题 Boj.kr
BOJ:日本央行
boj:算法求解