189 8069 5689
OpenJudge NOI 2.1 6188:比饭量
每个人有两个断言，正确断言的个数可能是2，1，0。显然3人的饭量也是不同的，这里假设为1，2，3。
题目中说：“饭量和正确断言的个数是反序的关系”，也就是说：饭量越大，断言正确数越少。饭量越小，断言正确数越大。即二者间有如下关系：
| 饭量 | 正确断言数 |
|---|---|
| 3 | 0 |
| 2 | 1 |
| 1 | 2 |
即：每个人的饭量数值和正确断言数的加和都等于3。
每个断言可以写成一个关系表达式，该表达式的值为true（1）或false（0），把一个人的断言写成的关系表达式的值加起来，即为正确断言的数量。
例：
A说：B比我吃的多，C和我吃的一样多
设a，b，c为A，B，C的饭量，那么这两个断言可以写为：b >a,c == a。正确断言的数量即为：(b >a) + (c == a)
注：题目中说“按饭量大小输出3个人的顺序”，指的是按升序输出。
解法2：深搜设三人的饭量是1，2，3，且两两不同。那么3人饭量所有可能的情况数就是3个数的全排列，可以使用深搜来搜索到所有的排列，而后判断每人的断言数是否与饭量顺序相反，如果是，则输出。
【题解代码】 解法1：枚举#includeusing namespace std;
int main()
{int a, b, c;//表示3人的饭量
for(a = 1; a<= 3; ++a)
for(b = 1; b<= 3; ++b)
for(c = 1; c<= 3; ++c)
{if(a != b && a != c && b != c)//两两不同
{ if(a + (b >a) + (c == a) == 3 &&
b + (a >b) + (a >c) == 3 &&
c + (c >b) + (b >a) == 3)//每个人的饭量数值和正确断言数的加和都等于3
{ if(a< b && a< c && b< c)//升序输出字符序列
cout<< "ABC";
else if(a< b && a< c && c< b)
cout<< "ACB";
else if(b< a && b< c && a< c)
cout<< "BAC";
else if(b< a && b< c && c< a)
cout<< "BCA";
else if(c< a && c< b && a< b)
cout<< "CAB";
else if(c< a && c< b && b< a)
cout<< "CBA";
return 0;
}
}
}
return 0;
} #includeusing namespace std;
int w[3], p[4];//w[0]:A的饭量 w[1]:B的饭量 w[2]:C的饭量 p[i]:饭量为i的人
bool vis[4];
functionf[3];//f[i]:求第i人的断言数
void initFunc()
{f[0] = [](){return (w[1] >w[0]) + (w[2] == w[0]);};//B比我吃的多，C和我吃的一样多
f[1] = [](){return (w[0] >w[1]) + (w[0] >w[2]);};//A比我吃的多，A也比C吃的多
f[2] = [](){return (w[2] >w[1]) + (w[1] >w[0]);};//我比B吃得多，B比A吃的多。
}
void dfs(int k)//确定第k个数字
{if(k >2)//找到解
{if(f[p[3]]()< f[p[2]]() && f[p[2]]()< f[p[1]]())//如果饭量越大，断言数越少
{ for(int i = 1; i<= 3; ++i)//输出序列
cout<< char(p[i]+'A');
}
return;
}
for(int i = 1; i<= 3; ++i)
{if(vis[i] == false)
{ w[k] = i;//k的饭量为i
p[i] = k;//饭量为i的人是k
vis[i] = true;
dfs(k+1);
vis[i] = false;
}
}
}
int main()
{initFunc();
dfs(0);
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧