acm.rar_ACM

POJ 1029 False coin Slyar:又是假币判断问题，跟POJ1013类似，不过这个题用1013那个算法WA了...后来换了种枚举的算法才过...思路就是假币应该在每个不等式中都出现，最后只要看哪个硬币出现的次数和不等式出现的次数相同，如果这个硬币唯一，那它就是确认的假币。 #include <iostream> #include <string> using namespace std; const int MAX = 1001; int main() { int n, k, p, total = 0; char sign; /* 记录原始数据 */ int t[MAX] = {0}; /* 标记硬币真假 */ int r[MAX] = {0}; /* 记录硬币重量 */ int w[MAX] = {0}; cin >> n >> k; while (k--) { /* 读入原始数据 */ cin >> p; for (int i = 0; i < 2 * p; i++) { cin >> t[i]; } cin >> sign; /* 标记肯定为真的硬币 */ if (sign == '=') { for (int i = 0; i < 2 * p; i++) { r[t[i]] = 1; } } /* 左轻右重 */ else if (sign == '<') { total++; for (int i = 0; i < p; i++) { w[t[i]]--; } for (int i = p; i < 2 * p; i++) { w[t[i]]++; } } /* 左重右轻 */ else if (sign == '>') { total++; for (int i = 0; i < p; i++) { w[t[i]]++; } for (int i = p; i < 2 * p; i++) { w[t[i]]--; } } } /* 假币在不等式中每次都应该出现 */ int count = 0, pos = 0; for (int i = 1; i <= n; i++) { if (r[i]) { continue; } /* 找出每次都出现的"假币" */ if (w[i] == total || w[i] == - total) { count++; pos = i; } } poj 1013 Counterfeit Dollar 关于称硬币的问题： 此题中赛利已经设计了正确的称量方案，保证从三组称量数据中能得到唯一的答案。答 案可以用两个变量表示：x假币的标号、w假币是比真币轻还是比真币重。x 共有12 种 猜测；w 有2 种猜测。根据赛利设计的称量方案，(x，w )的24 种猜测中，只有唯一的猜测 与三组称量数据都不矛盾。因此，如果猜测(x，w )满足下列条件，这个猜测就是要找的答 案：  在称量结果为"even'' 的天平两边，没有出现x ；  如果w 表示假币比真币轻，则在称量结果为"up'' 的天平右边一定出现x、在称量结果 为"down'' 的天平左边一定出现x  如果w 表示假币比真币重，则在称量结果为"up'' 的天平左边一定出现x、在称量结果 为"down'' 的天平右边一定出现x 具体实现时，要注意两点： 1) 选择合适的算法 对于每一枚硬币x 逐个试探：  x 比真币轻的猜测是否成立？猜测成立则进行输出。  x 比真币重的猜测是否成立？猜测成立则进行输出。 2) 选择合适的数据结构 以字符串数组存储称量的结果。每次称量时，天平左右最多有6 枚硬币。因此，字 符串的长度需要为7，最后一位存储字符串的结束符’\0’，便于程序代码中使用字符串 操作函数。 char left[3][7], right[3][7], result[3][7]; #include <stdio.h> #include <string.h> char left[3][7], right[3][7], result[3][5]; int islight( char x ) { int i; for ( i = 1; i <= 3; i++ ) switch( result[i][0] ) { case 'u': if( strchr(right[i], x) == NULL ) return 0; break; case 'e': if(strchr(right[i], x) != NULL || strchr(left[i], x) != NULL) return 0; break; case 'd': if(strchr(left[i], x) == NULL) return 0; break; } return 1; } int isheavy( char x ){ int i; for ( i = 1; i <=3; i++ ) switch( result[i][0] ) { case 'u': if( strchr(left[i], x) == NULL) return 0; break; case 'e': if(strchr(right[i], x) != NULL || strchr(left[i], x) != NULL) return 0; break; case 'd': if(strchr(right[i], x) == NULL) return 0; break; } return 1; } int main(){ int i,j,n; char c; scanf("%d",&n); while(n--){ for(i=1; i<=3; i++) scanf("%s %s %s",left[i],right[i],result[i]); for(c='A'; c<='L'; c++){ if(islight(c)){ printf("%c is the counterfeit coin and it is light.\n",c); break; } if(isheavy(c)){ printf("%c is the counterfeit coin and it is heavy.\n",c); break; } } } return 0; } /* 假币唯一则输出 */ if (count != 1) { cout << 0 << endl; } else { cout �