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