poj1029

题意：给定一些硬币，已知其中有一个假硬币重量与其余不同，其余硬币重量相同。给出若干次天平测量结果，问能否判断出这个硬币是哪个，若能则输出是哪个。

分析：两端重量相等则两端的硬币都是真的，每个不等情况中必然包含那个假的，且每次出现在同一边（总在小的一边或总在大的一边）。也就是说，只要某些硬币在不等 的一边中不是每次都出现，则它一定是真的。用以上方法进行判断哪些是真的，暂时忽略没出现过的，看有多少个不是真的，如果只有一个则必然是结果，若有多个则无法判断。如果出现过的都是真的，看没出现过的有几个，如果只有一个则为结果，否则无法判断。

还有人说可以暴力枚举哪个球是有问题的，是轻是重，每次观察与测量结果是否矛盾。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define maxn 1005

bool l[maxn];
bool exist[maxn];
bool r[maxn];
bool real[maxn];
bool x[maxn], y[maxn];
int n, k;
bool first =true;

void makereal()
{
    for (int i =0; i < n; i++)
        if (!real[i])
            real[i] = x[i] || y[i];
}

void myless(bool*x, bool*y)
{
    if (first)
    {
        first =false;
        for (int i =0; i < n; i++)
        {
            l[i] = x[i];
            r[i] = y[i];
        }
    }
    for (int i =0; i < n; i++)
        if (l[i] ^ x[i])
        {
            real[i] =true;
            l[i] =false;
        }
    for (int i =0; i < n; i++)
        if (r[i] ^ y[i])
        {
            real[i] =true;
            r[i] =false;
        }
}

int main()
{
    //freopen("t.txt", "r", stdin);
    scanf("%d%d", &n, &k);
    memset(l, 1, sizeof(l));
    memset(r, 1, sizeof(r));
    for (int i =0; i < k; i++)
    {
        int a;
        scanf("%d", &a);
        memset(x, 0, sizeof(x));
        for (int i =0; i < a; i++)
        {
            int b;
            scanf("%d", &b);
            b--;
            x[b] = exist[b] =true;
        }
        memset(y, 0, sizeof(y));
        for (int i =0; i < a; i++)
        {
            int b;
            scanf("%d", &b);
            b--;
            y[b] = exist[b] =true;
        }
        char st[5];
        scanf("%s", st);
        if (st[0] =='=')
            makereal();
        else if (st[0] =='<')
            myless(x, y);
        else
            myless(y, x);
    }
    int ans =-1;
    int cnt =0;
    for (int i =0; i < n; i++)
        if (!real[i] && exist[i])
        {
            ans = i;
            cnt++;
        }
    if (ans !=-1&& cnt ==1)
    {
        printf("%d\n", ans +1);
        return 0;
    }else if (cnt > 1)
    {
        printf("0\n");
        return 0;
    }
    cnt =0;
    ans =-1;
    for (int i =0; i < n; i++)
        if (!exist[i])
        {
            cnt++;
            ans = i;
        }
    if (ans !=-1&& cnt ==1)
        printf("%d\n", ans +1);
    else
        printf("0\n");

    return 0;
}