做了两题
Problem D: 逻辑运算
Description
还记得大学里学过的模电么，今天就让我们将与或非变成一道题吧。
给你一个与或非的表达式，求出这个表达式的值，表达式总共有八种字符。
三种逻辑运算符按照优先级排列如下。
‘！’：表示取反。
‘&’：逻辑与。
‘|’：逻辑或。
两个字符‘T’，‘F‘分别表示true和 false。
另外还有左右括号，空格三种字符。跟一般的表达式一样，括号可以改变优先级。
Input
每组数据输入一行字符串,字符串长度小于等于100.
Output
输出一个数0或1，表示逻辑表达式的答案。
Sample Input
T
Sample Output
1 思路:还是波兰式，关于！这个单目运算符想了半天，后来在它前面加了个废操作数,变成了双目运算符,结果就好了
1 #include2 #include 3 #include 4 #include 5 #include 6 #define maxn 100009 7 using namespace std; 8 stack q; 9 stack p;10 long long priorit[1000],ans[maxn],h;11 bool opp[maxn];12 char ch[maxn];13 int main()14 {15 priorit[(int)'!']=3;16 priorit[(int)'&']=2;17 priorit[(int)'|']=1;18 priorit[(int)'(']=0;19 while(gets(ch+1)!=NULL)20 {21 while(!q.empty())q.pop();22 while(!p.empty())p.pop();23 h=0;24 memset(ans,0,sizeof(ans));25 memset(opp,0,sizeof(opp));26 long long len=strlen(ch+1),idx=1,j=1;27 for(int i=1;i<=len;i++)28 {29 if(ch[i]!=' ')ch[j++]=ch[i];30 }31 len=j-1;32 while(idx<=len)33 {34 long long num=0,flag=0;35 if(ch[idx]=='!')36 {37 ans[++h]=2;38 }39 if(ch[idx]=='T')num=1,flag=1;40 if(ch[idx]=='F')num=0,flag=1;41 if(flag==0)42 {43 if(ch[idx]=='(')q.push('(');44 else if(ch[idx]==')')45 {46 while(!q.empty()&&q.top()!='(')47 {48 ans[++h]=-(long long)q.top();49 opp[h]=1;50 q.pop();51 }52 q.pop();53 }54 else55 {56 while(!q.empty()&&priorit[(long long)q.top()]>=priorit[(int)ch[idx]])57 {58 ans[++h]=-(int)q.top();59 opp[h]=1;60 q.pop();61 }62 q.push(ch[idx]);63 }64 }65 else66 {67 ans[++h]=num;68 }69 idx++;70 }71 while(!q.empty())72 {73 ans[++h]=-(long long)q.top();74 opp[h]=1;75 q.pop();76 }77 for(int i=1;i<=h;i++)78 {79 // printf("%I64d ",ans[i]);80 if(opp[i]==0)p.push(ans[i]);81 else82 {83 long long u=p.top();84 p.pop();85 long long v=p.top();86 p.pop();87 if(ans[i]==-(int)'!')88 {89 if(u==2)p.push(!v);90 else p.push(!u);91 }92 if(ans[i]==-(int)'&')p.push(u&v);93 if(ans[i]==-(int)'|')p.push(u|v);94 }95 }96 if(!p.empty())printf("%d\n",p.top());97 else printf("0\n");98 }99 }
Problem F: 无向图找环
Description
给你一副无向图，每条边有边权，保证图联通，现在让你判断这个图是否有异或值大于零的环存在。
Input
多组测试数据，每组先输入两个数n m，表示图的点跟边的数量。
然后是m行，每行三个数a b c。代表一条边的起点，终点，边权。
1 <= n<= 100000, 1 <= m <= 200000.
1 <= a <= n, 1 <= b <= n, a != b.
0 <= c <= 32767
Output
对于每组数据输出Yes或者 No。
Sample Input
3 31 2 02 3 13 1 1
Sample Output
No 思路:dfs找简单环,所有的环都是简单环组合而成,所以简单环只要有一个不是０就可以
1 #include2 #include 3 #include 4 #include 5 #define maxn 400009 6 #define LL long long 7 using namespace std; 8 LL head[maxn],next[maxn],point[maxn],value[maxn]; 9 LL now,cir[maxn],xo[maxn],h,n,m;10 bool visit[maxn];11 void add(int x,int y,LL v){12 next[++now]=head[x];head[x]=now;13 point[now]=y;value[now]=v;14 }15 void dfs(int k)16 {17 visit[k]=1;18 for(int i=head[k];i;i=next[i]){19 int u=point[i];20 if(visit[u]==1)cir[++h]=xo[u]^xo[k]^value[i];21 else xo[u]=xo[k]^value[i],dfs(u);22 }23 }24 int main()25 {26 LL x,y,v;27 while(cin>>n>>m)28 {29 memset(visit,0,sizeof(visit));30 now=0;h=0;31 memset(head,0,sizeof(head));32 for(int i=1;i<=m;i++){33 cin>>x>>y>>v;34 add(x,y,v);add(y,x,v);35 }36 dfs(1);37 int flag=0;38 for(int i=1;i<=h;i++)39 {40 if(cir[i]>0)41 {42 flag=1;break;43 }44 }45 if(flag==1)46 {47 printf("Yes\n");48 }49 else printf("No\n");50 }51 return 0;52 53 }