不带这样坑人的。。。。先是自己犯二。。。。输入忘记加上!=EOF然后华丽丽地output limit exceed。。。。。
后来加上就哇了。。。
思路:等号两边的一定一定是真的【真的是真的】
然后假硬币只会出现在重的一侧或者是轻的一侧,如果一个硬币既在重的一侧出现,又在轻的一侧出现,则一定是真硬币。
本来的思路是开了三个数组,一个是记录重的一个记录轻的,一个记录判断绝对是真的硬币,如果碰到=,所有的硬币都是真的,如果有一个硬币既出现在了重的一边又出现在了轻的一边,这个硬币绝对是真的,最后判断是否能确定假硬币的数量。结果这样写了之后华丽丽地wa掉了。
后来丛九九给了几组数据测试,第三组就挂了,然后才发现有的情况根本考虑不到。
错误的代码。。。大家不要这么做。。【捂脸】
#include <cstdio> #include <cstring> using namespace std; const int maxn=1010; int w[maxn],s[maxn]; bool tr[maxn]; int main() { int n,k,m; int tem[maxn]; while(scanf("%d%d",&n,&k)!=EOF) { memset(s,0,sizeof(s)); memset(w,0,sizeof(w)); memset(tr,false,sizeof(tr)); int result,ans; for(int i=0;i<k;i++) { scanf("%d",&m); for(int j=0;j<m*2;j++) { scanf("%d",&tem[j]); } getchar(); char ch; scanf("%c",&ch); if(ch=='=') { for(int j=0;j<m*2;j++) { tr[tem[j]]=true; w[tem[j]]=0; s[tem[j]]=0; // printf("%d %d %d\n",tem[j],s[tem[j]],w[tem[j]]); } } else if(ch=='<') { for(int j=0;j<m;j++) { if(tr[tem[j]]!=true) { s[tem[j]]++; //printf("%d %d %d\n",tem[j],s[tem[j]],w[tem[j]]); } if(tr[tem[m*2-1-j]]!=true) { w[tem[m*2-1-j]]++; //; printf("%d %d %d\n",tem[m*2-1-j],s[tem[m*2-1-j]],w[tem[m*2-1-j]]); } if(s[tem[j]]!=0&&w[tem[j]]!=0) tr[tem[j]]=true,s[tem[j]]=0,w[tem[j]]=0; if(s[tem[m*2-1-j]]!=0&&w[tem[m*2-1-j]]!=0) tr[tem[m*2-1-j]]=true,s[tem[m*2-1-j]]=0,w[tem[m*2-1-j]]=0; } } else if(ch=='>') { for(int j=0;j<m;j++) { if(tr[tem[j]]!=true) { w[tem[j]]++; //printf("%d %d %d\n",tem[j], s[tem[j]],w[tem[j]]); } if(tr[tem[m*2-1-j]]!=true) { s[tem[m*2-1-j]]++; //printf("%d %d %d\n",tem[m*2-1-j],s[tem[m*2-1-j]],w[tem[m*2-1-j]]); } if(s[tem[j]]!=0&&w[tem[j]]!=0) tr[tem[j]]=true,s[tem[j]]=0,w[tem[j]]=0; if(s[tem[m*2-1-j]]!=0&&w[tem[m*2-1-j]]!=0) tr[tem[m*2-1-j]]=true,s[tem[m*2-1-j]]=0,w[tem[m*2-1-j]]=0; } } } ans=0; for(int i=1;i<=n;i++) { //printf("%d %d %d\n",i,w[i],s[i]); if(w[i]!=0||s[i]!=0) { ans++; result=i; } } if(ans!=1) printf("%d\n",0); else printf("%d\n",result); } }
【多亏可爱的丛九九小朋友的讲解】换做法:
记录大于或者小于时候的操作数,如果一个硬币的操作数的绝对值(因为在重的一侧时候是+1,轻的一侧的时候是-1)等于操作数,那么这个硬币可能是假的喽。看有多少硬币符合假的条件,如果是1个则输出,否则就不确定。
可以考虑这么做。。。还因为i和j的问题wa了大半天。。。【捂脸】
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn=1010; int w[maxn],s[maxn],label[maxn]; int main() { int n,k; int step; while(scanf("%d%d",&n,&k)!=EOF) { step=0; memset(label,0,sizeof(label)); memset(w,0,sizeof(label)); for(int i=0;i<k;i++) { int m; char c; scanf("%d",&m); for(int j=0;j<2*m;j++) scanf("%d",&s[j]); getchar(); scanf("%c",&c); if(c=='=') { for(int j=0;j<2*m;j++) label[s[j]]=1; } else if(c=='<') { step++; for(int j=0;j<m;j++) if(label[s[j]]==0) w[s[j]]--; for(int j=m;j<2*m;j++) if(label[s[j]]==0) w[s[j]]++; } else if(c=='>') { step++; for(int j=0;j<m;j++) { if(label[s[j]]==0) w[s[j]]++; } for(int j=m;j<2*m;j++) { if(label[s[j]]==0) w[s[j]]--; } } } int ans=0,result=0; for(int i=1;i<=n;i++) if(label[i]==0&&abs(w[i])==step) { ans++; result=i; } if(ans!=1) printf("0\n"); else printf("%d\n",result); } }