P3633 [APIO2011]猜单词 题解

· · 题解

分析

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

暴力解法

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

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

复杂度分析

大概是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;
}

总结

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

Q:

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

A:

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