蓝桥杯2017年第八届真题-填字母游戏 （C++代码）

解题思路:

        这题数据以前是很水的，现在貌似更新到官方数据了。

        还是跟以前的思路一样，搜索加个记忆化，注意这里不要用 map ，map 会大大增加复杂度（那么答案只有一个了），这里

用字符串 hash，我用特殊方法得知输入最长的字符串长度是 20，如果全是 * 的话一共有 3^20 种状态，想必怎么装都装不下

（丧心病狂，大概也不会空那么多位置的吧），这里用 3 进制来存放每一个状态即可（已经是压缩到极限了，即每个数对应一个

状态），数组开爆就过了，太小的话有些状态会引起冲突，导致错误，大概就是这样。

        哈希（AC代码）：

#include <bits/stdc++.h>
constexpr auto Inf = 0X3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != 'Q' && o != 'C'); return o;
	}
}
using namespace IO;

const int SIZE = 1E7 + 7;
string ovo; int M[SIZE], MAP[233];

int Hash() {
	unsigned long long v = 0;
	for (int pos = 0; ovo[pos]; pos++) v = v * 3 + MAP[ovo[pos]];
	return v % 9817117;
}

/* 993217 492253 9817117 */

int F() {
	int u = Hash();
	if (M[u] != Inf) return M[u];
	if (ovo.find("LOL") != string::npos) return M[u] = -1;
	if (ovo.find("*") == string::npos) return M[u] = 0;
	int res = -1;
	for (int pos = 0; ovo[pos] && res != 1; pos++)
		if (ovo[pos] == '*') {
			ovo[pos] = 'L', res = max(res, -F());
			if (res != 1)
				ovo[pos] = 'O', res = max(res, -F());
			ovo[pos] = '*';
		}
	return M[u] = res;
}

int main() {
	MAP['*'] = 0, MAP['L'] = 1, MAP['O'] = 2;
	int N, BIT = sizeof M; cin >> N;
	while (N--) {
		memset(M, Inf, BIT);
		cin >> ovo, cout << F() << endl;
	}
}

        map 的记忆化（ T 掉的 40 分）：

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

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != 'Q' && o != 'C'); return o;
	}
}
using namespace IO;

string ovo; map<string, int> M;

int F() {
	if (M.find(ovo) != M.end()) return M[ovo];
	if (ovo.find("LOL") != string::npos) return -1;
	if (ovo.find("*") == string::npos) return  0;

	int res = -1;
	for (int pos = 0; ovo[pos]; pos++)
		if (ovo[pos] == '*') {
			ovo[pos] = 'L'; res = max(res, -F());
			ovo[pos] = 'O'; res = max(res, -F());
			ovo[pos] = '*';
		}
	return M[ovo] = res;
}

int main() {
	int N; cin >> N;
	while (N--) {
		M.clear(), cin >> ovo, cout << F() << endl;
	}
}