九度OJ1486 /POJ 1029/2012北京大學研究生復試上機

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 = 1000+5;
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 2
<
1 2 3
<3 2
1 1 2
>
1 1 3
>5 1
2 1 2 3 4
=4 3
2 1 2 3 4
<
2 1 3 2 4
<
1 2 4
=5 3
2 1 3 2 4
>
2 3 5 2 4
>
1 1 4
>5 3
2 1 3 2 4
>
2 3 5 2 4
>
1 1 4
=output:0
1
5
1
4
0