1172--猜数字

原题链接

http://acm.hdu.edu.cn/showproblem.php?pid=1172
Sample Input
6
4815 2 1
5716 1 0
7842 1 0
4901 0 0
8585 3 3
8555 3 2
2
4815 0 0
2999 3 3
0

Sample Output
3585
Not sure

problem of processing

首先本题的思路一开始没有想对，想了半天之后，看了题解豁然开朗，对这种类型的题，可以sample中的n个样例看成success的n个条件，要想success，必须每个条件成立，但是只能说明这个num成立，并不能排除没有其他num成立的。因此，总体的success的条件为n个条件成立，并且仅此只有一个成立。

接下来就是如何检验俩个num数字相同并且位置相同，和只有数字相同的个数。这个没想到好办法，
只想到了n^2的时间复杂度。

总体思想，数量不大，暴力枚举

代码

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 105;
int a[maxn], b[maxn], c[maxn];
int vis[maxn];
int n;//index表示数字位置都正确
//int cnt;//表示光数字正确
int save[maxn];

int compareIsTrue(int x, int y, int z)
{
    memset(vis,0,sizeof(vis));
    //将x转化成数组
    int index = 0;
    int cnt = 0;
    int tem = x;
    int org[5];
    int i = 0;
    while(tem)
    {
        org[i++] = tem % 10;
        tem /= 10;
    }
    //进行位置比对
    for(i=0; i<4; ++i)
    {
        if(save[i] == org[i])
        {
            index++;
        }
    }
    if(index != z)
        return 0;

    for(int j=0; j<4; ++j)
    {
        for(int k=0; k<4; ++k)
        {
            if(vis[k])
                continue;
            if(save[j] == org[k])
            {
                cnt++;
                vis[k]=1;
                break;
            }
        }
    }
    if(cnt != y)
        return 0;
    return 1;
}
int main()
{
    while(cin >> n && n)
    {
        int success = 0;
        int successNum = 0;

        for(int i=0; i<n; ++i)
        {
            cin >> a[i] >> b[i] >> c[i];
// scanf("%d%d%d",&a[i],&b[i],&c[i]);
        }

        for(int i=1000; i<10000; ++i)
        {
            bool flag = true;
            int tem = i;
            int k = 0;
            while(tem)
            {
                save[k++] = tem % 10;
                tem /= 10;
            }
            for(int j=0; j<n; ++j)
            {
                if(!compareIsTrue(a[j],b[j],c[j]))
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
            {
               success++;
               successNum = i;
            }
            if(success == 2)
                break;

        }
        if(success == 1)
            cout << successNum <<endl;
        else
            cout << "Not sure" <<endl;

    }
    return 0;
}