Letter by Letter 字典树+dp

题目链接:

Letter by Letter

题目大意:

给你n个单词, 每个单词的长度都是k, 这个题目是交互式的, 你每次猜出n个单词里面的一个, 每次猜一个字母, 交互程序会给出0(错误), 1(正确)两个回复, 从第一个字母开始猜, 每猜对一个就接着猜下一个单词, 直到程序给出k个1(全部猜出来了)
但是这个交互器会尽可能让你多猜, 也就是说, 它会一直给出0, 直到不能在给0 (例如说共有两个单词abcd, bcad, 你第一次猜a, 它会给出0, 然后你只能再猜b, 它不能再给出0, 因为再给出0就没办法继续下去了; 但如果你第一次猜b, 它还是会给出0, 然后你只能再猜a, 它不得不给出1)
题目要求你猜测最小次数猜出这个单词

解题思路

很容易想到用字典树把所有单词存下来, 然后沿着树往下猜
因为无论你猜什么, 交互器都会给出0, 直到只剩下最后一个选项可以猜, 所以我们要把最坏的选项最先猜(交互器会否定这个答案), 最好的选项最后一个猜(交互器会给出1)
dp[i] := 以节点i为根节点, 猜到结束所需要猜测的的次数(最坏情况)
很明显, 在叶子处, dp = 0;
对于其他节点, 子节点树为n, dp[i] = max{node[i]->son[j]->dp + i}, 1<=j<=k
要使dp[i]最小, 我们应该让子节点以其dp值从小到大排序, 这样得出的dp[i]最小
然后每次按子节点的dp值, 从大到小猜

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

const int MAXN = 1E5 + 100;
struct node
{
    bool flag;
    int dp;
    node * nxt[26];
    node()
    {
        dp = 0;
        flag = 0;
        fill(nxt, nxt+26, nullptr);
    }
};
node * root;
void insert(const char * s)
{
    node * p = root;
    for(int i=0; s[i]!='\0'; ++i)
    {
        if(p->nxt[s[i]-'a'] == nullptr) p->nxt[s[i]-'a'] = new node;
        p = p->nxt[s[i]-'a'];
    }
    p->flag = 1;
}
int n, k;
char s[MAXN];

void dfs(node * root)
{
    vector<int> dps;
    for(int i=0; i<26; ++i)
    {
        if(root->nxt[i] != nullptr) 
        {
            dfs(root->nxt[i]);
            dps.push_back(root->nxt[i]->dp);
        }
    }
    sort(dps.begin(), dps.end(), greater<int>());
    for(int i=0; i<(int)dps.size(); ++i)
    {
        if(dps[i]+i+1 > root->dp) root->dp = dps[i]+i+1;
    }
}

void solve(node * root)
{
    vector<pair<int, int>> dps;
    for(int i=0; i<26; ++i)
        if(root->nxt[i] != nullptr) dps.push_back({root->nxt[i]->dp, i});
    sort(dps.begin(), dps.end(), greater<pair<int, int>>());
    for(int i=0; i<(int)dps.size(); ++i)
    {
        cout << char(dps[i].second+'a') <<endl;
        int ans;
        cin >> ans;
        if(ans)
        {
            solve(root->nxt[dps[i].second]);
            break;
        }
    }
}

int main()
{
    root = new node;
    cin >> n >> k;
    for(int i=0; i<n; ++i)
    {
        cin >> s;
        insert(s);
    }
    dfs(root);
    solve(root);
    return 0;
}