时间限制 1000 ms 内存限制 65536 KB
题目描述
果园大咖圣哲有12个棵树，其中有且仅有一个是有病的，有病的树比真的或轻或重，给出3次天平测量重量的结果，每次告知左侧和右侧的树各有哪几个，以及天平的平衡状态，问第几棵树是生病的，并且请准确说出这棵树是轻是重。
数据保证每次天平的左右两边树数量相等。
输入格式
输入有多组数据，第一行有一个整数T(T≤15)。
每组的数据有三行：
每一行分别为三个字符串S1,S2,S3
S1表示天平左侧放置的树，S2表示天平右侧放置的树，S3表示天平平衡后右侧的状态up,down,even。
S1,S2由ABCDEFGHIJKL组成，分别以此表示12棵树。
输出格式
每组数据输出独占一行，输出是三种可能中的一种：
X is light.
X is heavy.
cannot judge.
输入样例
2
A B up
B A down
A C even
AB CD even
EF GH even
I J even
输出样例
B is light.
cannot judge.分析
法一：数据小，可以直接暴力枚举病树，以及是轻是重，当只有一种情况符合三次天平结果则有答案。
法二：even时，两边的都是健康的，up时，可能右边的有轻的，或者左边的有重的，down，相反。
v[i]记录第i棵树可能重或者可能轻的次数，up时，就给天平右边的v[i]--，左边的v[i]++。最后找除了健康的树以外，v[i]绝对值最大的，如果只有一个，那就是答案。健康的数的v[i]赋一个能区分开的值，比如v[i]设为9，如果第一次是even，后面最多减两次，为7，而可能不健康的数v最大为3，这样就可以区分开。
代码
#include<iostream>
#include<cmath>
#include<cstring>
#define l v[s1[j]-'A']
#define r v[s2[j]-'A'] using namespace std; int t,v[];
char ch;
string s1,s2,s3,ans; void solve(int f)
{
for(int j=; j<s1.size(); j++)
{
l+=f;
r-=f;
}
} void judge()
{
ch=;
int max=,maxi=-,t;
for(int i=; i<; i++)
if(v[i]<)
{
t=abs(v[i]);
if(t==max) maxi=-;
else if(t>max)
{
max=t;
maxi=i;
}
}
if(maxi>=)
{
ch=maxi+'A';
if(v[maxi]<) ans=" is light.\n";
else ans=" is heavy.\n";
}
}
int main()
{
cin>>t;
while(t--)
{
memset(v,,sizeof v);
for(int i=; i<; i++)
{
cin>>s1>>s2>>s3;
if(s3=="up") solve();
else if(s3=="down") solve(-);
else for(int j=; j<s1.size(); j++)l=r=;
}
judge();
if(ch) cout<<ch<<ans;
else cout<<"cannot judge.\n";
}
return ;
}