POJ 1029 False coin
Slyar：又是判断问题，跟POJ1013类似，不过这个题用1013那个算法WA了...后来换了种枚举的算法才过...思路就是应该在每个不等式中都出现，最后只要看哪个硬币出现的次数和不等式出现的次数相同，如果这个硬币唯一，那它就是确认的。
#include <iostream>
#include <string>
using namespace std;
const int MAX = 1001;
int main()
{
int n, k, p, total = 0;
char sign;
/* 记录原始数据 */
int t[MAX] = {0};
/* 标记硬币真假 */
int r[MAX] = {0};
/* 记录硬币重量 */
int w[MAX] = {0};
cin >> n >> k;
while (k--)
{
/* 读入原始数据 */
cin >> p;
for (int i = 0; i < 2 * p; i++)
{
cin >> t[i];
}
cin >> sign;
/* 标记肯定为真的硬币 */
if (sign == '=')
{
for (int i = 0; i < 2 * p; i++)
{
r[t[i]] = 1;
}
}
/* 左轻右重 */
else if (sign == '<')
{
total++;
for (int i = 0; i < p; i++)
{
w[t[i]]--;
}
for (int i = p; i < 2 * p; i++)
{
w[t[i]]++;
}
}
/* 左重右轻 */
else if (sign == '>')
{
total++;
for (int i = 0; i < p; i++)
{
w[t[i]]++;
}
for (int i = p; i < 2 * p; i++)
{
w[t[i]]--;
}
}
}
/* 在不等式中每次都应该出现 */
int count = 0, pos = 0;
for (int i = 1; i <= n; i++)
{
if (r[i])
{
continue;
}
/* 出每次都出现的"" */
if (w[i] == total || w[i] ==  - total)        {
count++;
pos = i;
}
}
poj 1013 Counterfeit Dollar
关于称硬币的问题：
此题中赛利已经设计了正确的称量方案，保证从三组称量数据中能得到唯一的答案。答案可以用两个变量表示：x 的标号、w 是比真币轻还是比真币重。x 共有12 种猜测；w 有2 种猜测。根据赛利设计的称量方案，(x，w )的24 种猜测中，只有唯一的猜测与三组称量数据都不矛盾。因此，如果猜测(x，w )满足下列条件，这个猜测就是要的答案：
在称量结果为"even'' 的天平两边，没有出现x ；
如果w 表示比真币轻，则在称量结果为"up'' 的天平右边一定出现x、在称量结果为"down'' 的天平左边一定出现x
如果w 表示比真币重，则在称量结果为"up'' 的天平左边一定出现x、在称量结果为"down'' 的天平右边一定出现x
具体实现时，要注意两点：
1) 选择合适的算法
对于每一枚硬币x 逐个试探：
x 比真币轻的猜测是否成立？猜测成立则进行输出。
x 比真币重的猜测是否成立？猜测成立则进行输出。
2) 选择合适的数据结构
以字符串数组存储称量的结果。每次称量时，天平左右最多有6 枚硬币。因此，字
符串的长度需要为7，最后一位存储字符串的结束符’\0’，便于程序代码中使用字符串
操作函数。
char left[3][7], right[3][7], result[3][7];
#include <stdio.h>
#include <string.h>
char left[3][7], right[3][7], result[3][5];
int  islight( char x ) {
int i;wa字符串是什么
for ( i = 1; i <= 3; i++ )
switch( result[i][0] ) {
case 'u': if( strchr(right[i], x) == NULL ) return 0;
break;
case 'e': if(strchr(right[i], x) != NULL || strchr(left[i], x) != NULL) return 0;
break;
case 'd': if(strchr(left[i], x) == NULL)    return 0;
break;
}
return 1;
}
int  isheavy( char x ){
int i;
for ( i = 1; i <=3; i++ )
switch( result[i][0] ) {
case 'u': if( strchr(left[i], x) == NULL)  return 0;
break;
case 'e': if(strchr(right[i], x) != NULL || strchr(left[i], x) != NULL) return 0;
break;
case 'd': if(strchr(right[i], x) == NULL)  return 0;
break;
}
return 1;
}
int main(){
int i,j,n;
char c;
scanf("%d",&n);
while(n--){
for(i=1; i<=3; i++)
scanf("%s %s %s",left[i],right[i],result[i]);
for(c='A'; c<='L'; c++){
if(islight(c)){
printf("%c is the counterfeit coin and it is light.\n",c);
break;
}
if(isheavy(c)){
printf("%c is the counterfeit coin and it is heavy.\n",c);
break;
}
}
}
return 0;
}
/* 唯一则输出 */
if (count != 1)
{
cout << 0 << endl;
}
else
{
cout << pos << endl;
}
//system("pause");
return 0;
}
poj 1083  Moving Tables
就是把这400个房间分成200分，1-2，3-4，。。。每次移动时，都要把经过的“份”算上，这样最后份中最大的那个数即可
#include <iostream>
#include <climits>
#include <cstring>
#define SIZE 220
using namespace std;
void swapnum(int &a,int &b);
int getindex(int k);
int main ()
{
int t,n;
cin>>t;
while(t--){
cin>>n;
int x,y;
int cross[SIZE];
memset(cross,0,sizeof(cross));
for(int i=0;i<n;++i){
cin>>x>>y;
int start,end;
if(x>y){
swapnum(x,y);
}
start=getindex(x);
end=getindex(y);
for(int i=start;i<=end;++i){
cross[i]++;
}
}
int maxnum=INT_MIN;
for(int i=0;i<SIZE;++i){
maxnum=maxnum>cross[i]?maxnum:cross[i];
}
cout<<maxnum*10<<endl;
}
return 0;
}
void swapnum(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
int getindex(int k)
{
if(k%2==0){
return k/2;
}
else if(k%2==1){
return k/2+1;
}
}
poj 2028 When Can We Meet?
题意：
ICPC委员会要安排一个会议，但是成员们都太忙了，所以很难安排，所以要我们编程个最合适的日子让更多的人来参加这个会议。
一共有N个人，至少要Q个人参加，第i个人有mi天是有空的，分别是date1，date2…..datem，表示明天开始的第datei天，比如date1为1表示明天有空，date2为2表示后天有空，……要输出最好的那天，要求是参加的人尽可能多，如果用相同人数的要尽量靠前。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。