总时间限制: 1000ms 内存限制: 65536kB
描述 赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。 输入 第一行有一个数字n，表示有n组测试用例。 对于每组测试用例： 输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用“up”，“down” 或 “even”表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。 输出 输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。 样例输入 1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even 样例输出 K is the counterfeit coin and it is light. 来源 East Central North America 1998
思路分析：枚举，某种意义上说，不枚举这题还真做不出来。
典型错误思路：设置标志矩阵，假设为bool类型，true表示为真币，false为假币，初始全部设为false，存储三次读入的结果，当result为even的时候，将两边coins的状态全部置为true，这个思路对于这组测试数据来说，是可以work的。考察测试数据： ABCD EFGH even IJ KA up JK AB up 不能得到正确的结果，因为此数据中只有up，且并不是所有的硬币都出现过。所以上述的思路是有问题的，不推荐使用。
可行的思路： 从A枚举到L，逐一考察当前coin为假币，并分别考虑light和heavy的情况，共24种。code的核心在于函数Is_Fake(char ch, bool light , bool heavy),其实一个bool变量就够用了，就是switch里面的判断逻辑个人驾驭得有些混淆，故两个利于分辨。 Is_Fake函数的工作过程： 接收一个字符ch，查看两个bool量的状态。对于每组测试数据内的每组称量结果，先判断result，根据result选择对待，判断依据如下： 1、平衡状态下，当前假币ch不应该出现在左右字符串中 2、右端up的状态下：要么假币较轻且在右串，要么假币较重且在左串 3、右端down的状态下：要么假币较重且在右串，要么假币较轻且在左串 依据strchr函数可以判断给定的ch是否在给定的字符串内，并以此进行相关判断。 （char *strchr( const char *str, int ch ); 函数strchr和strlen、strcat一样，都需要包含string.h 功能：函数返回一个指向str 中ch 首次出现的位置，当没有在str 中找ch到返回NULL。）
当且仅当，一组测试数据内的三组结果都合法，才会返回true，然后所有的判断结束，Print相关结果并break；若对任意一组数据，当前的状态与上面三点判断依据之一冲突，假设不成立，当即返回false表示当前的假设不成立，继续之后的枚举。
一步比较小的改进： 当然，与POJ 2977类似，可以优化一下枚举的空间。具体而言： 对于每一组的result，当result = even时，将左右字符串里面的字符mark一下，代表这些被mark的coins肯定不是假币，那么在枚举的过程中，枚举到这些假币的过程中，可以直接跳过Is_Fake函数（//平衡状态下，当前假币ch不应该出现在左右字符串中，而被mark的coins肯定会碰上这个雷。 case 'e': if (strchr(pLeft, ch) || strchr(pRight, ch)) return false;） 在这中优化之后，程序的效率可以得到一定的提升。总结一下： 1）枚举每一枚硬币的真假两种状态 2）在Is_Fake函数中验证假设是否成立，归纳出相关result状态下的可能的硬币状态 3） 优化一下搜索空间，减少不必要的函数调用和条件判断等。
#include <iostream> #include <string.h> //#define LOCAL char Left[3][10]; char Right[3][10]; char Result[3][10]; bool mask[30];//硬币状态存储 bool Is_Fake(char ch,bool light,bool heavy) { char *pLeft = nullptr, *pRight = nullptr; for (int i = 0; i < 3; ++i) { pLeft = Left[i]; pRight = Right[i]; switch (Result[i][0]) { //右端up的状态下：要么假币较轻且在右串，要么假币较重且在左串 case 'u': if (light && strchr(pRight, ch) == nullptr ||heavy && strchr(pLeft,ch) == nullptr) return false; break; //平衡状态下，当前假币ch不应该出现在左右字符串中 case 'e': if (strchr(pLeft, ch) || strchr(pRight, ch)) return false; break; //右端down的状态下：要么假币较重且在右串，要么假币较轻且在左串 case 'd': if (light && strchr(pLeft, ch) == nullptr || heavy && strchr(pRight, ch) == nullptr) return false; break; } } return true; } int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); #endif int k; scanf("%d", &k); while (k--) { memset(Left, '\0', sizeof(Left)); memset(Right, '\0', sizeof(Right)); memset(Result, '\0', sizeof(Result)); memset(mask, true, sizeof(mask)); for (int i = 0; i < 3; ++i) { scanf("%s%s%s", Left[i], Right[i], Result[i]); //缩小枚举的范围，当状态为even的时候，左右字符串里面的所有字符都不是待求的硬币 if (!strcmp(Result[i], "even")) for (int k = 0; k < strlen(Left[i]); ++k) mask[Right[i][k] - 'A'] = mask[Left[i][k] - 'A'] = false; } for (int i = 0; i < 12; ++i) //current stand for j + 'A' { if (!mask[i]) continue; char ch = i + 'A'; //改进之后用双状态一起上，以免混淆 if (Is_Fake(ch, true,false))//猜测ch是一枚比真币轻的假币 { printf("%c is the counterfeit coin and it is light.\n",ch); break; } else if (Is_Fake(ch, false,true))//否则猜测ch是一枚比真币重的假币 { printf("%c is the counterfeit coin and it is heavy.\n",ch); break; } } } return 0; }