题解：P8079 [WC2022] 猜词

LionBlaze · 2025-12-18 22:19:41 · 题解

水黑啊，最多蓝吧。

首先要注意的就是猜的单词不一定是可能是答案的单词，有时候猜不可能是答案的单词可以帮助你确定答案。

然后就是用朴素的信息熵的方法很难 AC，因为有可能在接近答案的时候一直在通过猜测能够帮助确定答案但不可能是答案的单词。一个折中的方法是，如果它可能是答案就在信息熵的基础上增加一个特定权值。

跑得非常慢。但是呢会发现每局开始时的不同信息只有首字母，而只有 26 种可能情况，所以可以先在本地打表预处理出每个首字母的最优猜测（做信息熵题的时候的一个常用策略）。然后就没啦！但是喜提最劣解。

:::info[代码&提交记录] record。

#ifdef ONLINE_JUDGE
#define vvv
#else
#define vvv extern "C"
#endif

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <random>

using namespace std;

vector<string> vss[30];
vector<string> vsvs;

vvv void init(int num_scramble, const char *scramble)
{
    string vsc = scramble;
    for(int i=0;i<num_scramble;i++)
    {
        vss[scramble[i * 5] - 'a'].push_back(vsc.substr(i * 5, 5));
        vsvs.push_back(vsc.substr(i * 5, 5));
    }
}
pair<vector<int>, vector<int>> convgs(bool *gold, bool *silver)
{
    if(gold == nullptr) return {{-1}, {-1}}; // 114514
    vector<int> ra, rb;
    for(int i=0;i<5;i++)
    {
        if(gold[i]) ra.push_back(i);
        if(silver[i]) rb.push_back(i);
    }
    return {ra, rb};
}
vector<string> maybe;
void inti(char ch)
{
    maybe = vss[ch - 'a'];
}
pair<vector<int>, vector<int>> afkcheck(const string &ca, const string &ya) // /?/
{
    bool gold[10], silver[10];
    for(int i=0;i<5;i++)
    {
        gold[i] = false; silver[i] = false;
        if(ca[i] == ya[i]) gold[i] = true;
    }
    for(int i=0;i<5;i++)
    {
        if(ca[i] == ya[i]) continue;
        for(int j=0;j<5;j++)
        {
            if(!gold[j] && ca[j] == ya[i]) silver[i] = true;
        }
    }
    return convgs(gold, silver);
}
void rpc(const string &gus, const pair<vector<int>, vector<int>> &vt)
{
    vector<string> g;
    for(const string &x : maybe)
    {
        if(afkcheck(x, gus) == vt) g.push_back(x);
    }
    maybe = g;
}
string lstgus;
unsigned hashser(const pair<vector<int>, vector<int>> &hsh)
{
    unsigned res = 0;
    for(int i : hsh.first)
    {
        res |= (1 << i);
    }
    for(int i : hsh.second)
    {
        res |= (1 << i) << 5;
    }
    return res;
}
unsigned cnt[1030];
long double gete(const string &gss)
{
    for(int i=0;i<1024;i++)
    {
        cnt[i] = 0;
    }
    long double sum = 0;
    for(const auto &x : maybe)
    {
        if(gss == x) sum += 0.2L;
        cnt[hashser(afkcheck(x, gss))]++;
    }
    for(int i=0;i<1024;i++)
    {
        if(cnt[i]) sum -= (cnt[i] * 1.0L / maybe.size()) * log(cnt[i] * 1.0L / maybe.size());
    }
    return sum;
}
string bestans()
{
    long double maxn = -1;
    string ans;
    for(const auto &x : vsvs)
    {
        auto res = gete(x);
        // printf("x = %s, res = %Lf\n", x.c_str(), res);
        if(res > maxn)
        {
            maxn = res;
            ans = x;
        }
    }
    // printf("result: %s\n", ans.c_str());
    return ans;
}
string rr;
string bstgus[30] = {"slier", "lares", "lares", "tores", "tarns", "arles", "lares", "lares", "snare", "ousel", "ranis", "nares", "tares", "aides", "tries", "lares", "raise", "aides", "plate", "nares", "snare", "riles", "nares", "cones", "kanes", "aeons"};
vvv const char *guess(int num_testcase, int remaining_guesses, char initial_letter, bool *gold, bool *silver)
{
    auto res = convgs(gold, silver);
    if(remaining_guesses != 5)
    {
        rpc(rr, res);
        rr = bestans();
        return rr.c_str();
    }
    else
    {
        inti(initial_letter);
        rr = bstgus[initial_letter - 'a'];
        return rr.c_str();
    }
}

:::