SRM 572 D1L2：EllysBulls，Brute Force，meet in the middle

题目：http://community.topcoder.com/stat?c=problem_statement&pm=12420&rd=15492

参考：http://apps.topcoder.com/wiki/display/tc/SRM+572

直接用回溯法brute force会超时，必须进行优化，可以使用将字符串分为两半，然后分别进行匹配的思想，使用此方法必须要用到关联容器map。

代码：

#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <bitset>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;

#define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC)
typedef pair<int, int> pii;
typedef long long llong;
typedef pair<llong, llong> pll;
#define mkp make_pair

/*************** Program Begin **********************/

class EllysBulls {
public:
	int K, cnt;
	string res;
	vector <string> guesses;
	vector <int> bulls;
	void next(string & s)
	{
		int len = s.size();
		int k = 0;
		while (k < len && ‘9‘ == s[k]) {
			s[k] = ‘0‘;
			++k;
		}
		if (k >= len) {
			s = "";
		} else {
			++s[k];
		}
	}
	int countMatches(const string & s, const string & g)
	{
		int res = 0;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == g[i]) {
				++res;
			}
		}
		return res;
	}
	string getNumber(vector <string> guesses, vector <int> bulls) {
		string res = "Liar";
		K = guesses[0].size();
		this->guesses = guesses;
		this->bulls = bulls;
		int n = guesses.size();
		// left half
		map <vector<int>, string> left_half;
		for (string s(K / 2, ‘0‘); s != ""; next(s)) {
			bool good = true;
			vector <int> matches(n);
			for (int i = 0; i < n; i++) {
				int m = countMatches(s, guesses[i]);
				if (m > bulls[i]) {
					good = false;
					break;
				} else {
					matches[i] = m;
				}
			}
			if (good) {
				if (left_half[matches] != "") {
					left_half[matches] = "Ambiguity";
				} else {
					left_half[matches] = s;
				}
			}
		}
		// right half
		for (string s(K - K / 2, ‘0‘); s != ""; next(s)) {
			bool good = true;
			vector <int> required(n);
			for (int i = 0; i < n; i++) {
				int m = bulls[i] - countMatches(s, guesses[i].substr(K / 2));
				if (m < 0) {
					good =false;
					break;
				} else {
					required[i] = m;
				}
			}
			if (good) {
				if (left_half.find(required) != left_half.end()) {
					if (left_half[required] == "Ambiguity") {
						return "Ambiguity";
					} else {
						if (res != "Liar") {
							if (res != left_half[required] + s) {
								return "Ambiguity";
							}
						} else {
							res = left_half[required] + s;
						}
					}
				}
			}
		}
		return res;
	}

};

/************** Program End ************************/

SRM 572 D1L2：EllysBulls，Brute Force，meet in the middle,布布扣,bubuko.com

SRM 572 D1L2：EllysBulls，Brute Force，meet in the middle

原文：http://blog.csdn.net/xzz_hust/article/details/20534655