CF1773I Interactive Factorial Guessing

Semsue · 2022-12-16 16:59:32 · 题解

看到 n 不大应该可以想到一个非常暴力的思路，先把所有阶乘用高精度算出来，精细实现的话只需要几毫秒。

然后枚举一个位置问他，那么就会把集合分成 10 个部分，我们取最大的部分最小的那个位置问，就类似点分治，递归下去建树即可。

我们实操发现这样深度最大刚好是 10。考场我粗略实现一下，刚好卡时限过去了。

考完仔细研究一下发现这个位置在后 2000 位里面选取即可，这下时限就很充裕了。

#include <bits/stdc++.h>
#define vi vector<int>
using namespace std;
vi operator * (vi a, int b)
{
    vi c;
    c.resize(a.size() + 5);
    for (int i = 0; i < (int)c.size(); i++) c[i] = 0;
    for (int i = 0; i < (int)a.size(); i++) c[i] = a[i] * b;
    for (int i = 0; i < (int)c.size() - 1; i++)
    {
        c[i + 1] += c[i] / 100000;
        c[i] %= 100000;
    }
    while ((int)c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
int N = 5982, rt;
vi fac[6000], temp[6000];
int vec[20005][10], tot, id[20005];
bool mark[20005];
int solve(vi &now)
{
    int tmp = ++tot;
    if (now.size() == 1)
    {
        mark[tot] = 1;
        id[tot] = now[0];
        return tot;
    }
    int cnt[10], pos = -1, mn = 0x3f3f3f3f;
    for (int i = 0; i < min((int)fac[now.back()].size(), 2000); i++)
    {
        for (int j = 0; j < 10; j++) cnt[j] = 0;
        for (int j = 0; j < now.size(); j++) cnt[((int)fac[now[j]].size() > i) ? fac[now[j]][i] : 0]++;
        int mx = 0;
        for (int j = 0; j < 10; j++) mx = max(mx, cnt[j]);
        if (mx < mn) pos = i, mn = mx;
    }
    vi nxt[10];
    for (int i = 0; i < 10; i++) nxt[i].clear();
    for (int i = 0; i < now.size(); i++) nxt[((int)fac[now[i]].size() > pos) ? fac[now[i]][pos] : 0].push_back(now[i]);
    for (int i = 0; i < 10; i++) if (nxt[i].size()) vec[tmp][i] = solve(nxt[i]);
    id[tmp] = pos;
    return tmp;
}
void init()
{
    temp[1].resize(1); temp[1][0] = 1;
    for (int i = 2; i <= N; i++) temp[i] = temp[i - 1] * i;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j < temp[i].size(); j++)
        {
            int x = temp[i][j], zz = 0;
            while (x || (j != temp[i].size() - 1 && zz < 5))
            {
                fac[i].push_back(x % 10);
                x /= 10;
                zz++;
            }
        }
    }
    vi now;
    now.resize(N);
    for (int i = 1; i <= N; i++) now[i - 1] = i;
    rt = solve(now);
}
char s[10];
void MAIN()
{
    int p = rt;
    for (int i = 1, x; i <= 10; i++)
    {
        printf("? %d\n", id[p]);
        fflush(stdout);
        scanf("%d", &x);
        p = vec[p][x];
        if (mark[p]) break;
    }
    printf("! %d\n", id[p]);
    fflush(stdout);
    scanf("%s", s + 1);
}
int main()
{
    init();
    int T; scanf("%d", &T);
    while (T--) MAIN();
    return 0;
}