2068160 2006-09-15 17:18:10 Accepted 1184 C++ 00:00.00 844K St.Crux 这是一个古老的题目，12枚硬币称3次，求出其中那枚轻或重的硬币。 当然，这道题比求解法简单多了，只需求证明。而我们知道，证明一样物体的存在，只需要把与其对立面的物体从物理层面乃至精神层面完全地、不留遗迹地消灭，这点在人类文明史中得到了最有力的支持......因此，最简单的办法是枚举24种情况，然后一一搜索，不满足者剔除即可。但显然这比较笨拙。 有没有简单一点的办法——假如不是12枚，而是12亿枚？好吧，同样是剔除，我们可以从判断语句入手。 比如 ABCD EFGH even 我们知道了这八枚都是even的。 又比如 ABCI EFJK up 我们知道了ABCI里必然有一枚是heavy的，而EFJK必然有一枚light。因此ABCI就是heavy的嫌疑对象，反之亦然。这是可能性。 从上面的语句中，我们还能得到隐含的条件：DGHL必然是even的。这是必然性。 所以，只要把不满足必然性的可能性剔除就OK了。 至于这个问题的解法，大致是用到二分，具体怎么写还有待研究。 #include <iostream>#include <cstring>#include <string>#include <vector>using namespace std; int n, b[12], l0, l1, c[12];string s0, s1, s2; void proc();void print(); int main(){ //freopen("in.txt", "r", stdin); cin >> n; int i, k; for(i = 0; i < n; i ++) { memset(b, 0, sizeof(b)); for(k = 0; k < 3; k ++) { cin >> s0 >> s1 >> s2; l0 = s0.size(), l1 = s1.size(); proc(); } print(); } return 0;} void proc(){ int j, t; //cout << s0 << " " << s1 << " " << s2 << endl; memset(c, 0, sizeof(c)); if(s2 == "even") //两边相等 { for(j = 0; j < l0; j ++) { t = s0[j] - 'A'; if(b[t] == 2) continue; b[t] = 2; //2代表相等 } for(j = 0; j < l1; j ++) { t = s1[j] - 'A'; if(b[t] == 2) continue; b[t] = 2; } } else if(s2 == "up") //左边重 { for(j = 0; j < l0; j ++) { t = s0[j] - 'A'; c[t] = 1; if(b[t] == 2) continue; if(b[t] == 1) b[t] = 2; //有1存在说明这是标准重量 if(!b[t]) b[t] = 3; //3代表重的可能性 } for(j = 0; j < l1; j ++) { t = s1[j] - 'A'; c[t] = 1; if(b[t] == 2) continue; if(b[t] == 3) b[t] = 2; //有3存在说明这是标准重量 if(!b[t]) b[t] = 1; //1代表轻的可能性 } for(j = 0; j < 12; j ++) { if(!c[j]) { t = j; if(b[t] == 2) continue; b[t] = 2; } } } else if(s2 == "down") //右边重 { for(j = 0; j < l0; j ++) { t = s0[j] - 'A'; c[t] = 1; if(b[t] == 2) continue; if(b[t] == 3) b[t] = 2; if(!b[t]) b[t] = 1; } for(j = 0; j < l1; j ++) { t = s1[j] - 'A'; c[t] = 1; if(b[t] == 2) continue; if(b[t] == 1) b[t] = 2; if(!b[t]) b[t] = 3; } for(j = 0; j < 12; j ++) { if(!c[j]) { t = j; if(b[t] == 2) continue; b[t] = 2; } } } //print();} void print(){ int i; for(i = 0; i < 12; i ++) { if(b[i] == 2) continue; if(b[i] == 1) { printf("%c is the counterfeit coin and it is light.\n", i + 'A'); } if(b[i] == 3) { printf("%c is the counterfeit coin and it is heavy.\n", i + 'A'); } }}
评论