听说这题可以暴力破解掉。。。感觉略麻烦的样纸。。。
然后用标记的方法……
几个注意点:
1、 出现的等号两边的绝壁的真的!
2、如果一个钢镚,即出现在重的一边,又出现在轻的一边,那这货绝壁是真的!
然后开始做!
遇到等号,将他们全都标记称真的。
重的,标记重的,轻的,标记轻的。
如果最后某个硬币的轻的重的标记等于总的操作数,就重点怀疑~~~
如果就一根这样的,就是那货假的。
如果多个,那就无法判断。
AC Memory : 736 KB Time : 110 ms
代码:
#include<iostream> #include<cstring> #include<fstream> #include<algorithm> #include<string> #include<map> using namespace std; const int Max=1000+10,inf=10000000; int w[Max],s[Max],label[Max]; int main() { int n,k; int tot; while(cin>>n>>k) { tot=0; memset(label,0,sizeof(label)); memset(w,0,sizeof(w)); for(int i=0;i<k;i++) { int m; char c; cin>>m; for(int i=0;i<2*m;i++) cin>>s[i]; cin>>c; if(c=='=') for(int i=0;i<2*m;i++) label[s[i]]=1; else if(c=='<') { tot++; for(int i=0;i<m;i++) if(label[s[i]]==0) w[s[i]]--; for(int i=m;i<2*m;i++) if(label[s[i]]==0) w[s[i]]++; } else if(c=='>') { tot++; for(int i=0;i<m;i++) if(label[s[i]]==0) w[s[i]]++; for(int i=m;i<2*m;i++) if(label[s[i]]==0) w[s[i]]--; } } int ans=0,found=0; for(int i=1;i<=n;i++) if(label[i]==0 && abs(w[i])==tot) { found++; ans=i; } if(found!=1)cout<<0<<endl; else cout<<ans<<endl; } return 0; }