TIPS:up/down 是以天平右臂为准
-
思路1：
由于是通过结果反推硬币真假，想到，将每个硬币都先假设为假币（假币分轻重，故一共有
12*2
种情况，如:A轻假/重假，B轻假…），带入3次测试结果，看是否成立，若成立该硬币为假币，反之为真；
- 3种假设不成立的情况：
情况1.如果天平是even假币存在
情况2.如果天平是up:轻币在左，重币在右 或 假币不在
情况3.如果天平是down:轻币在右，重币在左 或 假币不在（OJ里省略了，对结果没影响，但实际上不能省略，见 注1）
- code1：
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
char Right[3][7];
char Left[3][7];
char result[3][5];
bool IsFake(char c, bool Weight){
char *l, *r;
for(int i = 0; i < 3; ++i){
l = Left[i];
r = Right[i];
if(Weight){
//如果是轻币
if(result[i][0] == 'e')
if(strchr(l, c) || strchr(r, c))
//1.天平even,假币存在
return false;
if(result[i][0] == 'u')
if(strchr(l, c))
//2.天平up，轻币在左,或者轻币不在 `|| (strchr(r, c) == NULL && strchr(l, c) == NULL) ` Q:为啥可以省略轻币不在的情况？
return false;
if(result[i][0] == 'd')
if(strchr(r, c))
//3.天平down,轻币在右，或者轻币不在
return false;
}
else{
//如果是重币
if(result[i][0] == 'e')
if(strchr(l, c)|| strchr(r, c))
//1.天平even,假币存在
return false;
if(result[i][0] == 'u')
if(strchr(r, c) || (strchr(r, c) == NULL && strchr(l, c) == NULL))
//2.天平up，重币在右 ，或者重币不在
return false;
if(result[i][0] == 'd')
if(strchr(l, c) || (strchr(r, c) == NULL && strchr(l, c) == NULL))
//3.天平down,重币在左 ，或者重币不在
return false;
}
}
return true;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; ++i){
for(int j = 0; j < 3; ++j){
cin >> Left[j] >> Right[j] >> result[j];
}
for(char c = 'A'; c <= 'L'; ++c){
if(IsFake(c, true)){
//如果是轻币
cout << c << " is the counterfeit coin and it is light.\n";
break;
}
if(IsFake(c, false)){
//如果是重币
cout << c << " is the counterfeit coin and it is heavy.\n";
break;
}
}
}
return 0;
}
- code 2(PKU郭炜):
#include <iostream>
#include <cstring>
using namespace std;
char Right[3][7];
char Left[3][7];
char result[3][5];
bool IsFake(char c, bool Weight){
char *l, *r;
for(int i = 0; i < 3; ++i){
if(Weight){
l = Left[i];
r = Right[i];
}
else{ //优化代码：如果是重币，左右天平互换（相当于把重当作轻来看）
r = Left[i];
l = Right[i];
}
switch(result[i][0]){
case 'u':
if(strchr(r, c) == NULL)
return false;
break;
case 'e':
if(strchr(l, c) || strchr(r, c))
return false;
break;
case 'd':
if(strchr(l, c) == NULL)
return false;
break;
}
}
return true;
}
int main(){
int n;
cin >> n;
while(n--){
for(int j = 0; j < 3; ++j) cin >> Left[j] >> Right[j] >> result[j];
for(char c = 'A'; c <= 'L'; ++c){
if(IsFake(c, true)){
cout << c << " is the counterfeit coin and it is light.\n";
break;
}
else if(IsFake(c, false)){
cout << c << " is the counterfeit coin and it is heavy.\n";
break;
}
}
}
return 0;
}
- code3(PKU刘家瑛)：
-
思路2：
枚举出A~L每个硬币是假币的情况：用1代表重假币，0代表真币，-1代轻假币，计算左右天平各自的重量；
- 3种假设不成立的情况(比思路1清晰)：
情况1.右侧较沉（左<右），结果却不是down
情况2.右侧较轻（左>右），结果却不是up
情况3.一边沉（左=右），结果却不是even
#include <cstdio>
int status[20];
char left[3][7], right[3][7], result[3][5];
bool test(){
int i, j;
int SumLeft, SumRight;
for(i = 0; i <3; ++i){
SumLeft = 0;
SumRight = 0;
for(j = 0; j < 6 && left[i][j] != 0; ++j){
SumLeft += status[left[i][j] - 'A'];
SumRight += status[right[i][j] - 'A'];
}
if(SumLeft < SumRight && result[i][0] != 'd')
return false;
if(SumLeft > SumRight && result[i][0] != 'u')
return false;
if(SumLeft == SumRight && result[i][0] != 'e')
return false;
}
return true;
}
int main(){
int i, n;
scanf("%d", &n);
while(n-- > 0){
for(i = 0; i < 3; ++i)
scanf("%s %s %s", left[i], right[i], result[i]);
for(i = 0; i < 12; ++i)
status[i] = 0; //0初始化数组，也可以用memset来初始化!
for(i = 0; i < 12; ++i){
status[i] = 1; //假设第i个硬币是重币
if(test()) //如果证明确实是重币，跳出循环
break;
status[i] = -1;
if(test())
break;
status[i] = 0;
}
printf("%c is the counterfeit coin and it is %s.\n", i + 'A',
status[i] == 1 ? "heavy" : "light");
}
return 0;
}
- 补充知识:
在写C++程序中，总会遇到要从一个字符串中查找一小段子字符串的情况
- 头文件：
C++:#inlcude<string>
C: #include<string.h>
对于在C中，我们经常用到strstr()或者strchr()这两种方法(见 code1)。而对于C++的string，我们往往会用到find()。
find()
：
在一个字符串中查找一个指定的单个字符或字符数组。如果找到，就返回首次匹配的开始位置；如果没有查找到匹配的内容，就返回
string::npos
。
find_first_of()
：
在一个目标串中进行查找，返回值是第一个与指定字符组中任何字符匹配的字符位置。如果没有查找到匹配的内容，则返回
npos
。
find_last_of()
：
在一个目标串中进行查找，返回最后一个与指定字符组中任何字符匹配的字符位置。如果没有查找到匹配的内容，则返回
npos
。
find_first_not_of()
：
在一个目标串中进行查找，返回第一个与指定字符组中任何字符都不匹配的元素位置。如果找不到那样的元素则返回
npos
。
find_last_not_of()
：
在一个目标串中进行查找，返回下标值最大的与指定字符组中任何字符都不匹配的元素的位置。若找不到那样的元素则返回
npos
。
rfind()
：
对一个串从尾至头查找一个指定的单个字符或字符组。如果找到，就返回首次匹配的开始位置；如果没有查找到匹配的内容，则返回
npos
。
find(string, int)
：
第一个参数用来指示要查找的字符，第二个参数用来表示从字符串的何处开始查找子串(默认的查找位置是0)。
(转载自：https://www.cnblogs.com/sword-/p/8030004.html ）
- 注1：
测试输入：
1
ABCD EFGH even
ABJD EFIH up
CDJA HBKL up
理论输出：
实际输出：
-
注2：
！！！！！注意
\n
- 该题同 1013:Counterfeit Dollar
POJ 2692：假币问题 / POJ 1013:Counterfeit Dollar