自动搬运

查看原文

来自洛谷，原作者为

	code_hunter 此人严重需要清醒点

搬运于2025-08-24 21:51:00，当前版本为作者最后更新于2021-05-10 21:22:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

这是一个一种 A 、 B 间的博弈，但不是公平组合游戏。面对这种题目，首先应当思考一种暴力算法，并脑算一组小规模数据，以此来检验读题是否准确，同时，这个暴力算法也很可能还是一个可得分的算法。

暴力解法

下面来梳理一下决策过程：

• A 选择单词的长度。

• B 选择猜的字母。

• 在保证仍有单词的情况下，A 选择是否让 B 对,若让 B 对，则还应给出单词的位置。

• 重复上两步，直至出现：

  1.B 猜出单词——B赢。

  2.B 猜错数严格大于单词长度——A赢。

由于是要求必胜策略，采用搜索枚举所有情况。具体地，当做决策时，当前一方必胜当且仅当所有决策中存在必胜的选项。

复杂度分析

大概是$O(k \cdot len^{len})$（实测可过的）

具体实现

#include <bits/stdc++.h>

#define For(i,a,b) for(int i = a ; i <= b ; i ++)
#define FoR(i,a,b) for(int i = a ; i >= b ; i --)
typedef long long ll;
const int MAXK = 1123;
const int MAXL = 11;
using namespace std;

int C , K;
char words[MAXK][MAXL];
bool can_use[MAXK];//单词是否可用
bool cannot_use[29];//字母是否可猜
int stk[MAXK] , tp;
int cnt , len;

int findch(char *s , char c) {
	for (int i = 0 ; s[i] ; i ++)
		if (s[i] == c)
			return i;
	return -1; 
}

bool win_A(int blank , int p = 0) {//A 是否必胜
	if (blank < 0) 
		return true;
	if (cnt <= 1)
		return false;
	For (ch , 0 , 25) {//B 决策
		bool flag = false;
		if (cannot_use[ch] == true)
			continue;
		register int nw = tp;
		For (i , 1 , K)//A决策
			if (can_use[i] && (~findch(words[i] , ch + 'A')))
				can_use[cnt -- , stk[++ tp] = i] = false;
		if (win_A(blank - 1 , p + 1))
			flag = true;
		//cout << "asdf" << flag << endl;
		while (tp > nw)
			can_use[cnt ++ , stk[tp --]] = true;
		if (flag)
			continue;
			
		For (k , 0 , len - 1) {
			For (i , 1 , K)
				if (can_use[i] && findch(words[i] , ch + 'A') != k)
					can_use[cnt -- , stk[++ tp] = i] = false; 
			cannot_use[ch] = true;
			if (win_A(blank , p + 1))
				flag = true;
			cannot_use[ch] = false;
			while (tp > nw)
				can_use[cnt ++ , stk[tp --]] = true;
			if (flag)
				break;
		}
		if (!flag)
			return false;
	}
	return true;
}

void work() {
	scanf ("%d" , &K);
	For (i , 1 , K) {
		scanf ("%s" , words[i]);
	}
	for (len = 1 ; len <= 7 ; len ++) {
		cnt = 0;
		For (i , 1 , K)
			cnt += (int)(can_use[i] = (len == strlen(words[i])));
		tp = 0; 
		memset(cannot_use , false , sizeof(cannot_use)); 
		if (cnt > 0 && win_A(len)) {
			printf ("Yes\n");
			return;
		}
	}
	printf ("No\n");
}

int main() {
	scanf ("%d" , &C);
	while (C --) 
		work();
	return 0;
}

总结

你看，这马蜂清新、优美、可读性强、短小精悍。如果你想在通过的前提下，进一步优化，可以

• 若剩余单词数大于 A 决策数的剩余空格次方，则 A 必胜。
• 若剩余单词数小于等于剩余空格数 + 1 , 则 B 必胜。

Q:

这题作为一个朴素的搜索有什么意义呢？

A:

提高对冗长问题的分析能力与代码能力。