凡科做网站需要备案吗,上海cms建站模板,学做网,衡水网站建设衡水wa到死#xff01;wa到死#xff01;这是一个看着简单#xff0c;坑及其多的题#xff01; 坑一#xff1a;POJ上是单组输入#xff0c;九度上是多组输入#xff0c;妈蛋要是研究生复试遇到这种大坑肯定死掉啊#xff01;而且对于codeforces比较习惯的 同学肯定会觉得巨…wa到死wa到死这是一个看着简单坑及其多的题 坑一POJ上是单组输入九度上是多组输入妈蛋要是研究生复试遇到这种大坑肯定死掉啊而且对于codeforces比较习惯的 同学肯定会觉得巨坑无比。 坑二九度OJ上绝对有多余的空字符什么getchar都不要用用cin输入跳过空格吧POJ上是没问题的 坑三有很多特殊情况如果算法不好的话wa的概率是很大的比如真的false coin没有出现在不等式中 先说一些共识 1如果出现的是“”式子那么两边肯定都是合格的coin而且false coin肯定不在这个等式里面 2如果出现了不等式即“或者”式子那么可以肯定在这些式子中肯定都存在一个false coin 3如果一个硬币是false coin在每个它出现的式子里都是不等式而且要么它总在轻的一方 要么它总在重的一方但是这个题其坑无比的是不能从这个角度想因为给的数据可能根本没有逻 辑就是说可能会有自相矛盾的数据在这种情况下他的逆命题有可能是真的首先我们把出 现在等式里的数字排除掉即如果每个不等式里某个数字都出现了即出现次数等于不等式的个数并 且它总是在重的一方或者总是在轻的一方那我们说这个数字极有可能是false coin但是还 要统计一下这样的数字是不是只有一个如果有两个或者没有都没办法判断 我的思路对于能通过等式判断出相等的元素用h【i】1标记上意味着false coin绝对不可能是这里面的数字 对于不等式A[i] B[i]设置一个light[i]数组和一个heavy[i]数组如果一个数出现在了轻的一边就让light[i]; 如果出现在了重的一边就让heavy[i]对于一个false coin要么他的heavy值等于不等式的个数cas要么他的light值 等于cas然后注意不要让ans重复就可以了。 #include bits/stdc.h
using namespace std;
#define INF 0x3f3f3f3f
const int maxn 10005;
int n,k,p;
int L[maxn],R[maxn];
int light[maxn],heavy[maxn];
int h[maxn];
char opt;
int cas;int main()
{while(cin n k){memset(light,0,sizeof(light));memset(heavy,0,sizeof(heavy));memset(h,0,sizeof(h));cas 0;for(int t 1;t k; t){cin p;for(int i 1; i p; i)cin L[i];for(int i 1; i p; i)cin R[i];cin opt;if(opt ){for(int i 1; i p; i)h[L[i]] h[R[i]] 1;}else if(opt ){cas;for(int i 1; i p; i){light[L[i]];heavy[R[i]];}}else{cas;for(int i 1; i p; i){heavy[L[i]];light[R[i]];}}}int cnt 0,ans;for(int i 1; i n; i){if(h[i]0(light[i]cas||heavy[i]cas)){ans i;cnt;}}if(cnt!1) printf(0\n);else printf(%d\n, ans);}
} 一些帮助大家debug的数据 input:
3 2
1 1 21 2 3
3 2
1 1 21 1 3
5 1
2 1 2 3 4
4 3
2 1 2 3 42 1 3 2 41 2 4
5 3
2 1 3 2 42 3 5 2 41 1 4
5 3
2 1 3 2 42 3 5 2 41 1 4
output:0
1
5
1
4
0转载于:https://www.cnblogs.com/Norlan/p/5422423.html
