[Testing Round #13][Codeforces 753C] Interactive Bulls and Cows (Hard)

    题意：Bull and Cows游戏。猜一个四位数码（保证数码各位互不相同），每次交互时选手给电脑一个四位数码，电脑会返回两个值a和b，a表示同一位置上数码相同的位置个数，b表示电脑与选手的四位数码共同包含但是位置不同的数码个数。要求7次内猜出数字。

    题解：这题要求出完美解状态数量过多，不过贪心解也能在7次之内完成。设当前可选数的集合为S，现在要找到一个数字t，使得通过该返回值排除掉的可选数在最坏情况下最多。易见第一次无论选什么都是等价的，所以可以考虑第一次选0123;第二次选取时，对每个a,b都事先考虑好选什么数去猜（否则容易超时），这个可以预先打表实现。然后就决策树继续做就好了。

#include <bits/stdc++.h>
using namespace std;

void Get_Num(int x,int &x0,int &x1,int &x2,int &x3)
{
	x0=x%10;
	x1=x%100/10;
	x2=x%1000/100;
	x3=x/1000;
}

void Compare(int x,int y,int &b,int &c)
{
	b=0,c=0;
	int num[2][4];
	Get_Num(x,num[0][0],num[0][1],num[0][2],num[0][3]);
	Get_Num(y,num[1][0],num[1][1],num[1][2],num[1][3]);
	for (int i=0;i<4;i++) if (num[0][i]==num[1][i]) b++;
	sort(num[0],num[0]+4);
	sort(num[1],num[1]+4);
	for (int i=0,j=0;i<4;i++)
	{
		while (j<4 && num[0][i]>num[1][j]) j++;
		if (j<4 && num[0][i]==num[1][j]) j++,c++;
	}
	c-=b;
}

int a[2][10000],num[2];

void Fliter(int o,int x,int b,int c)
{
	num[o^1]=0;
	for (int i=0;i<num[o];i++)
	{
		int b0,c0;
		Compare(x,a[o][i],b0,c0);
		if (b0==b && c0==c) a[o^1][num[o^1]++]=a[o][i];
	}
}

int Val(int o,int x)
{
	int cnt[25];
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<num[o];i++)
	{
		int b,c;
		Compare(x,a[o][i],b,c);
		cnt[b*4+c]++;
	}
	return *max_element(cnt,cnt+25);
}

int main()
{
	for (int i=123;i<10000;i++)
	{
		int x0,x1,x2,x3;
		Get_Num(i,x0,x1,x2,x3);
		if (x0==x1 || x0==x2 || x0==x3 || x1==x2 || x1==x3 || x2==x3) continue;
		a[0][num[0]++]=i;
	}
	int last=123;
	printf("0123\n");
	fflush(stdout);
	for (int t=0;t<7;t++)
	{
		int b,c;
		scanf("%d%d",&b,&c);
		if (b==4) return 0;
		Fliter(t&1,last,b,c);
		if (t==0)
		{
			if (b==0 && c==0) last=4567;
			if (b==1 && c==0) last=456;
			if (b==0 && c==1) last=456;
			if (b==2 && c==0) last=145;
			if (b==1 && c==1) last=145;
			if (b==0 && c==2) last=1045;
			if (b+c==3) last=124;
			if (b+c==4) last=1230;
		}
		else
		{
			int minv=10000,o=(t&1)^1,tmp;
			for (int i=0;i<num[o];i++)
				if ((tmp=Val(o,a[o][i]))<minv) minv=tmp,last=a[o][i];
		}
		printf("%04d\n",last);
		fflush(stdout);
	}
	return 0;
}