HDU 1251 統(tǒng)計(jì)難題
要看論文準(zhǔn)備畢業(yè)設(shè)計(jì)了，好幾周都沒(méi)有搞ACM了，今天實(shí)在手癢了，就去hdu上溜達(dá)了一圈，挑幾個(gè)題做，于是乎就看到了這個(gè)題，典型的字典樹(shù)。
題目要求輸出以某個(gè)字符串為前綴的word的數(shù)目，建立字典樹(shù)之后就是個(gè)簡(jiǎn)單的查詢了，為了性能采用了靜態(tài)字典樹(shù)，由于不知道會(huì)有多少個(gè)單詞就猜了下感覺(jué)10w應(yīng)該夠了吧，提交上去access violation，明顯的越界訪問(wèn)，修改為20W一樣出錯(cuò)，后來(lái)火了，直接開(kāi)到50w過(guò)了，測(cè)試數(shù)據(jù)相當(dāng)狠呀。
不多說(shuō)了，參考代碼如下。
#include <stdlib.h>
struct node
{
int cnt;
int childs[26];
};
int avail = 1;
int cur = 0;
struct node tree[500000];
char buf[15];
int main(void)
{
int i;
int root;
int index;
int flag;
/*freopen("in.txt", "r", stdin);*/
while (fgets(buf, 15, stdin) != NULL && buf[0] != '\n')
{
i = 0;
root = 0;
while (buf[i] != '\n')
{
index = buf[i]-'a';
if (tree[root].childs[index] == 0)
{
tree[root].childs[index] = avail++;
}
++tree[tree[root].childs[index]].cnt;
root = tree[root].childs[index];
++i;
}
}
while (fgets(buf, 15, stdin) != NULL && buf[0] != '\n')
{
i = 0;
root = 0;
flag = 1;
while (buf[i] != '\n')
{
index = buf[i] - 'a';
if (tree[root].childs[index] == 0)
{
flag = 0;
break;
}
root = tree[root].childs[index];
++i;
}
printf("%d\n", flag == 1 ? tree[root].cnt : 0);
}
return 0;
}
ZOJ 1808 Immediate Decodability
這道題給出n個(gè)有1和0組成的字符串集合，然后要求判斷是否有某一個(gè)字符串是另一個(gè)字符串的前綴。是字典樹(shù)的典型應(yīng)用。
字典樹(shù)有靜態(tài)和動(dòng)態(tài)之分，動(dòng)態(tài)字典樹(shù)就是在插入時(shí)根據(jù)需要?jiǎng)討B(tài)malloc節(jié)點(diǎn)，而靜態(tài)字典樹(shù)則是事先開(kāi)辟一個(gè)較大的數(shù)組，然后設(shè)置一個(gè)變量index指向當(dāng)前數(shù)組中未被占用的節(jié)點(diǎn)下標(biāo)的最小值，即下一個(gè)可用節(jié)點(diǎn)的下標(biāo)。跟C語(yǔ)言中實(shí)現(xiàn)靜態(tài)鏈表類似。這兩種方法各有優(yōu)劣，動(dòng)態(tài)字典樹(shù)理論上可以插入任意多個(gè)節(jié)點(diǎn)，但是每次的malloc及最后的free會(huì)消耗很多時(shí)間。而靜態(tài)字典樹(shù)省去了內(nèi)存的動(dòng)態(tài)申請(qǐng)和釋放，節(jié)省了時(shí)間，但是可以插入節(jié)點(diǎn)數(shù)目受到事先開(kāi)辟的數(shù)組大小限制，可擴(kuò)展性較差。具體采用哪種實(shí)現(xiàn)方式根據(jù)需求而定。就本題而言時(shí)間要求1s，可以初步需要插入的判斷節(jié)點(diǎn)數(shù)目不會(huì)太多，因此為了提高運(yùn)行速度采用了靜態(tài)字典樹(shù)。
參考代碼如下：
#include <stdlib.h>
#include <string.h>
struct dick
{
/*左右孩子指針，指向左右孩子在數(shù)組中的下標(biāo)，做孩子為0，右孩子為1*/
int child[2];
/*是否是字符串的最后一個(gè)字符*/
int leaf;
};
/*從該數(shù)組中分配節(jié)點(diǎn)*/
struct dick d[1000];
/*指向下個(gè)可用節(jié)點(diǎn)的下標(biāo)*/
int index;
int main(void)
{
char buf[100];
int no = 0;
int flag = 1;
int i;
index = 0;
int start;
int tmp;
int test;
memset(d, 0, sizeof(d));
freopen("in.txt", "r", stdin);
while (gets(buf) != NULL)
{
if (buf[0] == '9' && buf[1] == '\0')
{
++no;
if (flag == 1)
{
printf("Set %d is immediately decodable\n", no);
}
else
{
printf("Set %d is not immediately decodable\n", no);
}
/*清理和初始化數(shù)據(jù)*/
flag = 1;
memset(d, 0, sizeof(d));
index = 0;
}
else if (flag == 1)
{
i = 0;
start = 0;
test = 1;
/*逐字符插入數(shù)據(jù)到字典樹(shù)中*/
while (buf[i] != '\0')
{
if (d[start].child[buf[i]-'0'] == 0)
{
if (d[start].leaf == 1)
{
break;/*發(fā)現(xiàn)已插入字符串是本字符串的前綴*/
}
/*分配新的節(jié)點(diǎn)*/
d[start].child[buf[i]-'0'] = ++index;
test = 0;
}
tmp = d[start].child[buf[i]-'0'];
if (buf[i+1] == '\0')
{
d[tmp].leaf = 1;
}
start = tmp;
++i;
}
if (test == 1)
{
flag = 0;
}
}
}
return 0;
}
ZOJ1058 Currency Exchange
水題一道，唯一需要注意的是題目中說(shuō)只能取到貨幣的百分之一，因此在每次進(jìn)行貨幣匯率轉(zhuǎn)換之后都要進(jìn)行處理，WA了一次就是因?yàn)榈阶詈筝敵龅臅r(shí)候才四舍五入，這個(gè)操作應(yīng)該在每次轉(zhuǎn)換匯率后都進(jìn)行。
參考代碼如下：
#include <stdlib.h>
double rates[5][5];
int indx[10];
int main(void)
{
int n;
int t;
double money;
int i, j;
int prev;
/*freopen("in.txt", "r", stdin);*/
scanf("%d", &t);
while (t--)
{
for (i = 0; i < 5; ++i)
{
for (j = 0; j < 5; ++j)
{
scanf("%lf", &rates[i][j]);
}
}
while (scanf("%d", &n) == 1 && n != 0)
{
prev = 0;
for (i = 0; i < n; ++i)
{
scanf("%d", &indx[i]);
}
scanf("%lf", &money);
money *= 100;
for (i = 0; i < n; ++i)
{
money *= rates[prev][indx[i]-1];
prev = indx[i]-1;
if (money - (int)money >= 0.5)
money = (int)money+1;
else
money = (int)money;
}
money *= rates[prev][0];
if (money - (int)money >= 0.5)
money = (int)money+1;
else
money = (int)money;
printf("%.2f\n", money/100);
}
if (t != 0)
{
printf("\n");
}
}
return 0;
}
ZOJ 1334 Basically Speaking
這是一道簡(jiǎn)單的進(jìn)制轉(zhuǎn)換題，也是一道讓我無(wú)語(yǔ)的題。
題目大意較為簡(jiǎn)單，但是提交了n次，一直PE，檢查了好多地方，實(shí)在感覺(jué)沒(méi)頭緒了，就活馬當(dāng)死馬醫(yī)，把printf(“%*c”, len, ‘ ’)換成了循環(huán)，因?yàn)橐覍?duì)齊，所以輸出些空格，竟然AC了，竟然是對(duì)printf的這種輸出格式理解有誤，無(wú)語(yǔ)呀。
參考代碼如下：
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
char a[50];
char ch[] = "0123456789ABCDEF";
int main(void)
{
int to, from;
unsigned sum;
int len;
int i;
unsigned t;
freopen("in.txt", "r", stdin);
while (scanf("%s %d %d", a, &from, &to) != EOF)
{
sum = 0;
t = 1;
len = strlen(a);
for (i = len-1; i >= 0; --i)
{
if (isdigit(a[i]))
{
sum += (a[i] - '0')*t;
}
else
{
sum += (a[i] - 'A' + 10)*t;
}
t *= from;
}
if (to == 10)
{
len = (int)log10(sum)+1;
if (len > 7)
{
printf(" ERROR\n");
}
else
{
printf("%7d\n", sum);
}
}
else
{
i = 0;
while (sum > 0)
{
a[i++] = ch[sum%to];
sum /= to;
}
if (i > 7)
{
printf(" ERROR\n");
}
else
{
len = 7-i;
printf("%*c", len, ' ');
--i;
while (i >= 0)
{
putchar(a[i--]);
}
printf("\n");
}
}
}
return 0;
}
ZOJ 1051 A New Growth Industry
這道題嚴(yán)格來(lái)說(shuō)屬于一道簡(jiǎn)單的模擬題，但是題目描述的太繁瑣了，影響了理解。而一旦看懂題意后就好辦了。
這道題的大意就是說(shuō)在一個(gè)20X20的方格中養(yǎng)一種細(xì)菌，這種細(xì)菌的DNA被改造了，周圍密度大時(shí)，繁殖減慢，密度減少，反之密度增加，且數(shù)量變動(dòng)大小由DNA序列決定，然后根據(jù)輸入進(jìn)行模擬，輸入n天后的情況。
題就這么簡(jiǎn)單，但是需要注意的是不能計(jì)算完一個(gè)方格的變化量之后立刻改變?cè)摲礁竦闹担驗(yàn)橹車姆礁?/span>k值還需要引用當(dāng)前的密度值。唯一可以使用的技巧就是把數(shù)組開(kāi)大點(diǎn)，題目是20X20，可以開(kāi)到22X22，只使用下標(biāo)1-20來(lái)表示題目中的方格，這樣在計(jì)算時(shí)就不用判斷是否越界了，可以節(jié)省一些時(shí)間。
參考代碼如下：
#include <stdlib.h>
int a[22][22];
int d[16];
int b[20][20];
int main(void)
{
int t;
int n;
int i, j;
int k;
//freopen("in.txt", "r", stdin);
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (i = 0; i < 16; ++i)
{
scanf("%d", &d[i]);
}
for (i = 1; i < 21; ++i)
{
for (j = 1; j < 21; ++j)
{
scanf("%d", &a[i][j]);
}
}
while (n--)
{
for (i = 1; i < 21; ++i)
{
for (j = 1; j < 21; ++j)
{
k = a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1] +a[i][j];
b[i-1][j-1] = d[k];
}
}
for (i = 1; i < 21; ++i)
{
for (j = 1; j < 21; ++j)
{
a[i][j] += b[i-1][j-1];
if (a[i][j] < 0)
a[i][j] = 0;
else if (a[i][j] > 3)
a[i][j] = 3;
}
}
}
for (i = 1; i < 21; ++i)
{
for (j = 1; j < 21; ++j)
{
switch(a[i][j])
{
case 0:putchar('.');break;
case 1:putchar('!');break;
case 2:putchar('X');break;
case 3:putchar('#');break;
}
}
printf("\n");
}
if (t != 0)
printf("\n");
}
return 0;
}
DNA Sorting(ZOJ 1188)
本題應(yīng)該來(lái)說(shuō)是一道比較容易的題，但是我覺(jué)得確實(shí)一道比較好的題：為了解決這道題可以寫(xiě)很短的代碼，也可以寫(xiě)很長(zhǎng)的代碼；可以寫(xiě)出比較高效的代碼，也可以寫(xiě)出比較低效的代碼。
原題大家可以到ZOJ上查看，本處就不累述了。題目大意就是根據(jù)一個(gè)由ATCG字符組成的字符串的逆序數(shù)進(jìn)行排序，然后輸出結(jié)果，如果有兩個(gè)字符串的逆序數(shù)相同則按照其輸入順序輸出，即要求排序函數(shù)是穩(wěn)定的。至此，本題的思路已經(jīng)很清晰了：接收數(shù)據(jù)à計(jì)算逆序à排序à輸出結(jié)果。
這里關(guān)鍵步驟是排序，要求穩(wěn)定排序，因此C語(yǔ)言中的qsort和STL中的sort不再適用，而要自己編寫(xiě)排序函數(shù)或者適用STL中的stable_sort。字符串逆序數(shù)的計(jì)算可以在輸入以后計(jì)算，也可以在輸入的同時(shí)就計(jì)算，根據(jù)接收字符串的方式而定，如果是整行接收的，只能以后再算了；如果是逐字符接收的，則可以邊接收邊計(jì)算。此處為了方便處理采用了整行接收的方法。具體代碼如下：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int degree;
char str[50];
bool operator < (const node& n) const
{
return degree <= n.degree;
}
};
node mat[100];
int main(void)
{
int t;
int m, n;
int i, j, k;
int deg;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &m, &n);
for (i = 0; i < n; ++i)
{
scanf("%s", mat[i].str);
deg = 0;
for (j = 0; j < m-1; ++j)
{
for (k = j; k < m; ++k)
{
if (mat[i].str[j] > mat[i].str[k])
++deg;
}
}
mat[i].degree = deg;
}
stable_sort(mat, mat+n);
for (i = 0; i < n; ++i)
{
printf("%s\n", mat[i].str);
}
if (t != 0)
printf("\n");
}
return 0;
}
該題在ZOJ上的題號(hào)是1225。
題目描述如下：
Background
In this problem you will be given a series of lists containing both words and
numbers. The goal is to sort these lists in such a way that all words are in alphabetical
order and all numbers are in numerical order. Furthermore, if the nth element
in the list is a number it must remain a number, and if it is a word it must
remain a word.
Input
The input will contain multiple lists, one per line. Each element of the list
will be separated by a comma followed a space, and the list will be terminated
by a period. The input will be terminated by a line containing only a single
period.
Output
For each list in the input, output the scramble sorted list, separating each element of the list with a comma followed by a space, and ending the list with a period.
Sample Input
0.
banana, strawberry, OrAnGe.
Banana, StRaWbErRy, orange.
10, 8, 6, 4, 2, 0.
x, 30, -20, z, 1000, 1, Y.
50, 7, kitten, puppy, 2, orangutan, 52, -100, bird, worm, 7, beetle.
.
Sample Output
0.
banana, OrAnGe, strawberry.
Banana, orange, StRaWbErRy.
0, 2, 4, 6, 8, 10.
x, -20, 1, Y, 30, 1000, z.
-100, 2, beetle, bird, 7, kitten, 7, 50, orangutan, puppy, 52, wor
本題不是難題，根據(jù)題意，只需把輸入中的數(shù)字和字符串分開(kāi)，然后分別按照相應(yīng)的規(guī)則進(jìn)行排序，并記錄下第i個(gè)是數(shù)字或者是字符，最后按照記錄情況一次輸出相應(yīng)的元素即可。因?yàn)樾枰獙?duì)字符串?dāng)?shù)組進(jìn)行排序，因此第一印象是使用C++的string和STL中的sort函數(shù)，但是結(jié)果卻因?yàn)閼械脤?xiě)一個(gè)排序函數(shù)多寫(xiě)了很多代碼。
具體代碼如下：
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
string s[80];
int a[80];
bool flag[80];
char buf[80];
bool cmp(string a, string b)
{
string tmpa = a;
string tmpb = b;
transform(a.begin(),a.end(), tmpa.begin(), ::tolower);
transform(b.begin(),b.end(), tmpb.begin(), ::tolower);
return tmpa < tmpb;
}
int main(void)
{
int alpha, num;
string t;
char *p;
int i, j;
int sign;
int tmp;
int k;
int m, n;
freopen("in.txt", "r", stdin);
while (fgets(buf, 80, stdin) != NULL && buf[0] != '.')
{
p = buf;
i = j = 0;
alpha = num = 0;
k = 0;
while (*p != '\n' && *p != '.')
{
while (*p == ' ')
++p;
sign = 1;
if (*p == '-' || isdigit(*p) || *p == '+')
{
if (*p == '-')
{
sign = -1;
++p;
}
else if (*p == '+')
++p;
tmp = 0;
while (*p != ',' && *p != '.')
{
tmp = tmp*10 + (*p-'0');
++p;
}
a[num++] = tmp*sign;
flag[k++] = false;
}
else
{
i = 0;
t = "";
while (*p != ',' && *p != '.')
{
t += *p;
++p;
++i;
}
s[alpha++] = t;
flag[k++] = true;
}
++p;
}
sort(a, a+num);
sort(s, s+alpha, cmp);
m = n = 0;
if (!flag[0])
{
printf("%d", a[0]);
++m;
}
else
{
printf("%s", s[0].c_str());
++n;
}
for (i = 1; i < k; ++i)
{
if (!flag[i])
{
printf(", %d", a[m]);
++m;
}
else
{
printf(", %s", s[n].c_str());
++n;
}
}
printf(".\n");
}
return 0;
}
Fibonacci Again
【題目描述】
There are another kind of Fibonacci
numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2)
Input
Input consists of a sequence of lines, each containing an integer n. (n <
1,000,000)
Output
Print the word "yes" if 3 divide evenly into F(n).
Print the word "no" if not.
Sample Input
0
1
2
3
4
5
Sample Output
no
no
yes
no
no
no
這道題應(yīng)該說(shuō)是很簡(jiǎn)單的題，如果說(shuō)考察了什么知識(shí)點(diǎn)的話時(shí)能說(shuō)是（a+b）%n = (a%n + b%n)%n，但是這個(gè)題卻有多種思路，可以從很多方面優(yōu)化，比較有意思。
【解題思路1】：
最簡(jiǎn)單的思路,開(kāi)一個(gè)大小為n的數(shù)組，初始化為0，遍歷一遍，如果某一項(xiàng)滿足條件則設(shè)置為1，就不多說(shuō)了，代碼如下：
#include <stdlib.h>
int r[1000000];
int main(void)
{
int a, b, tmp;
int i;
int n;
a = 7;
b = 11;
r[0] = r[1] = 0;
for (i = 2; i < 1000000; ++i)
{
tmp = ((a%3) + (b%3)) % 3;
if (tmp == 0)
r[i] = 1;
a = b;
b = tmp;
}
while (scanf("%d", &n) == 1)
{
if (r[n] == 0)
printf("no\n");
else
printf("yes\n");
}
return 0;
}
這個(gè)提交上去，由于執(zhí)行時(shí)只查表，時(shí)間不算多10ms，但是內(nèi)存消耗不小。下面看幾種優(yōu)化的方法。
【思路2】
這種題一般情況下會(huì)有規(guī)律。把前幾個(gè)能被3整除的數(shù)的下標(biāo)列出來(lái)一看，規(guī)律就出現(xiàn)了：2 6 10 14…，這就是一個(gè)等差數(shù)列嘛，這就好辦了，an = a1 + (n-1)*4,那么an-a1肯定能被4整除。代碼如下：
#include <stdlib.h>
int main(void)
{
int n;
while (scanf("%d", &n) == 1)
{
if ((n-2)%4 == 0)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
該解法如果說(shuō)還可以優(yōu)化的話，那只能把取余運(yùn)算變?yōu)槲贿\(yùn)算了。
if ((n-2)&3)
printf("no\n");
else
printf("yes\n");
【思路3】
如果把數(shù)列前幾項(xiàng)的值列出來(lái)，會(huì)發(fā)現(xiàn)數(shù)組中每8項(xiàng)構(gòu)成一個(gè)循環(huán)。這也很好辦。
代碼如下：
#include <stdlib.h>
int a[8];
int main(void)
{
int n;
a[2] = a[6] = 1;
while (scanf("%d", &n) == 1)
printf("%s\n", a[n%8] == 0 ? "no" : "yes" );
return 0;
}
其實(shí)這個(gè)還可以優(yōu)化，我們仔細(xì)觀察可以看到這些滿足條件的下標(biāo)有一個(gè)特點(diǎn)：
N%8 == 2或者n%8==6
代碼如下：
#include <stdlib.h>
int main(void)
{
int n;
while (scanf("%d", &n) == 1)
{
if (n%8 == 2 || n%8 == 6)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
Counterfeit
Dollar
該題ZOJ題號(hào)為1184， POJ題號(hào)為1013.
題目描述如下：
Sally Jones has a dozen Voyageur silver dollars. However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars. The counterfeit coin has a different weight from the other coins but Sally does not know if it is heavier or lighter than the real coins.
Happily, Sally has a friend who loans her a very accurate balance scale. The friend will permit Sally three weighings to find the counterfeit coin. For instance, if Sally weighs two coins against each other and the scales balance then she knows these two coins are true. Now if Sally weighs one of the true coins against a third coin and the scales do not balance then Sally knows the third coin is counterfeit and she can tell whether it is light or heavy depending on whether the balance on which it is placed goes up or down, respectively.
By choosing her weighings carefully, Sally is able to ensure that she will find the counterfeit coin with exactly three weighings.
Input
The first line of input is an integer n (n > 0) specifying the number of
cases to follow. Each case consists of three lines of input, one for each
weighing. Sally has identified each of the coins with the letters A-L.
Information on a weighing will be given by two strings of letters and then one
of the words ``up'', ``down'', or ``even''. The first string of letters will
represent the coins on the left balance; the second string, the coins on the
right balance. (Sally will always place the same number of coins on the right
balance as on the left balance.) The word in the third position will tell
whether the right side of the balance goes up, down, or remains even.
Output
For each case, the output will identify the counterfeit coin by its letter and
tell whether it is heavy or light. The solution will always be uniquely
determined.
Sample Input
1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
Sample Output
K is the counterfeit coin and it is light.
【分析】該題屬于枚舉范疇。沒(méi)有比較巧妙的可以一步到位求出結(jié)果的方法，可以一次枚舉這12枚錢幣，假設(shè)其為假，然后代入到3次稱量判斷中，如果使三次判斷都成立且判斷結(jié)果相同，那么毫無(wú)疑問(wèn)這枚錢幣是假的。首先可以進(jìn)行預(yù)處理，比較結(jié)果為EVEN的可以判定兩邊的錢幣都是真的，不必參與到枚舉中來(lái)。對(duì)于上面的輸入用例，假設(shè)K是假的，代入判斷1，k不出現(xiàn)，那么兩邊重量應(yīng)相等，成立。繼續(xù)稱量2，k出現(xiàn)在右邊，結(jié)果是UP，亦成立，且據(jù)此知道k是較輕的，因此k在右邊，而天平右邊翹起。下面進(jìn)行判斷3
，k沒(méi)有出現(xiàn)在天平兩邊，而且結(jié)果為even成立。通過(guò)三次稱量判斷，且結(jié)果一致，可以肯定k就是假幣，且較輕。為了說(shuō)明為題，對(duì)于上例假設(shè)L是假幣。代入稱量1，L不出現(xiàn)，結(jié)果even成立，稱量2，L不出現(xiàn)，結(jié)果為up不成立，因?yàn)橹挥幸幻都賻牛F(xiàn)假設(shè)L為假幣，而在L不出現(xiàn)的情況下天平不平衡，故L不是假幣。按照上述算法進(jìn)行枚舉，遇到可以肯定是假幣的貨幣時(shí)算法終止。
需要注意的是當(dāng)假設(shè)一枚硬幣為假且通過(guò)三次稱量時(shí)，需要判斷三次稱量k的輕重情況是否一致，如果一次推得該硬幣較輕，而另一次卻判斷該硬幣較重，那么該硬幣肯定不是假幣。在判斷是需要注意當(dāng)左右兩邊都不出現(xiàn)假設(shè)為假的硬幣時(shí)，需要特殊處理，不能簡(jiǎn)單的比較3次硬幣輕重是否相同，在左右兩邊都不出現(xiàn)該硬幣的情況下，不應(yīng)該把這次測(cè)量納入比較的范疇。除此之外需要的就是細(xì)心了，本人因?yàn)榇蛴〉臅r(shí)候多打印了個(gè)the，WA了6次，檢查了半個(gè)多小時(shí)，有種欲哭無(wú)淚的感覺(jué)。
具體代碼如下：
2 #include <stdlib.h>
3 #include <string.h>
4
5 char left[3][7], right[3][7];
6 char result[3][6];
7 int a[15];
8 int w;
9
10 int judge(char ch)
11 {
12 int r1, r2;
13 int i;
14 int a[3];
/*對(duì)當(dāng)前假設(shè)的硬幣進(jìn)行判斷*/
15 for (i = 0; i < 3; ++i)
16 {
17 r1 = strcmp(result[i], "even");
18 r2 = strcmp(result[i], "up");
19 if (strchr(left[i], ch) != NULL)
20 {
21 if (r1 == 0)
22 return 0;
23 else if (r2 == 0)
24 a[i] = 1;
25 else
26 a[i] = -1;
27 }
28 else if (strchr(right[i], ch) != NULL)
29 {
30 if (r1 == 0)
31 return 0;
32 else if (r2 == 0)
33 a[i] = -1;
34 else
35 a[i] = 1;
36 }
37 else
38 {
39 if (r1 != 0)
40 return 0;
41 a[i] = 3;
42 }
43 }
/*判斷結(jié)果是否一致*/
44 if (a[0] != 3)
45 w = a[0];
46 else if (a[1] != 3)
47 w = a[1];
48 else if (a[2] != 3)
49 w = a[2];
50 for (i = 0; i < 3; ++i)
51 {
52 if (a[i] != 3 && a[i] != w)
53 {
54 return 0;
55 }
56 }
57 return 1;
58 }
59 int main(void)
60 {
61 int n;
62 int i;
63 char *p;
64 char ch;
65 int r;
66 scanf("%d%*c", &n);
67 while (n--)
68 {
69 memset(a, 0, sizeof(a));
70 for (i = 0; i < 3; ++i)
71 {
72 scanf("%s%s%s", left[i], right[i], result[i]);
73 if (strcmp (result[i], "even") == 0)
74 {
75 p = left[i];
76 while (*p != '\0')
77 {
78 a[*p-'A'] = 1;
79 ++p;
80 }
81 p = right[i];
82 while (*p != '\0')
83 {
84 a[*p-'A'] = 1;
85 ++p;
86 }
87 }
88 }
89 for (ch = 'A'; ch <= 'L'; ++ch)
90 {
91 if (a[ch-'A'] == 1)
92 continue;
93 r = judge(ch);
94 if (r == 1)
95 {
96 if (w > 0)
97 {
98 printf("%c is the counterfeit coin and it is heavy.\n", ch);
99 }
100 else
101 {
102 printf("%c is the counterfeit coin and it is light.\n", ch);
103 }
104 break;
105 }
106 }
107 }
108 return 0;
109 }