CF2164G Pointless Machine

Furioso_Slient · 2025-11-21 08:51:21 · 题解

提示：本题解的做法偏娱乐向，且需要基于原有的正确做法，观看本题解前请先观看其他题解理解标准思路做法。

背景

我近期不想熬夜，就没打 CF，然后我教练打完这场后，把自己的昵称临时改成了 Why not 33 queries:(，这引起了我的注意，等我写完这道题后，我也改了。

但我和教练一直在想：原有的基于二进制的思路真的不行么，就一定需要 3\times\log_3 10^5 +1 这样的形式么？为什么不存在二进制的解？为什么就不能存在 2 \times (\log_2 10^5 -1)+1 这种形式的解？

而且，我们对原有的询问方式进行了分析，发现：如果用三进制的形式询问，会导致相关询问信息被浪费。

然后经过我们两人两天的爆肝，终于宣称在今日（25.11.21）凌晨 5 点解决了本问题。

前置条件 / 性质：

• 在 CF 中，如果你的代码 TLE，代码会进行重测。次数约在 3 到 4 次。
• 本题时限 4 秒，重测时 time(0) 不易取同一个值。
• 本题解默认你已经会了 33 次询问的二进制解法

做法：

因为我们的确切询问次数从 16 次压缩到了 15 次，所以我们需要从这方面切入：

我们通过随机数的方法，随机打乱节点顺序，然后询问 30 次，分类方式同其他题解的二进制写法，最后附加一次确定节点度数的询问。

我们对每次询问的结果进行差分后存起来，然后利用拨叶子发逐个离析深度为 1 的节点，但每次离析的时候会存在一个问题：如何确定这个节点的父亲？

通过每次询问，我们可以将一个节点的父亲锁定在两个节点之间，并通过如下比较确定父亲：

• 首先，我们通过每次询问确定的结果还原两个节点，这个数字通过异或和位移进行生成。因为我们询问了 15 次，所以这些结果可以表示 2^{15} 以内的数字，也就是 32768 以内的数字。
• 如果我们询问的 n 小于 2^{15}，显然易得这个数字唯一，直接确定即可。
• 否则，会出现一个假父亲，也就是那个第 16 位结果不确定，我们先还原出假节点，随后进行部分有效性检查，如果所有节点都被证明可以有效成为这个候选叶子的父亲，我们就猜一个。

对，你没有听错，就是猜一个，这个就是这个算法检索的核心：先钦定，后验证

我们随机猜一个节点后，先暂时不管他，如果因为这个节点导致后面出现了错误，就回溯到这个节点，修改它的值。

理论而言，到这里，应该可以找到答案了。但这也只是理论，我们容易计算，每一个节点的出错概率为 \frac{1}{3\times 10^5}，最劣情况下的出错期望为 \frac{10}{3}，不过因为 CF 的重测机制，冲过去还是没有问题的。

同时，因为存在回溯操作，出错后进行一定的回溯也可以完美解决出错问题。剩下的都是细节上的处理了。

此处提供我老师的代码，欢迎 Hack.

using namespace std;
int n;
int deg[1<<17];
int q[35][1<<17];
int num[35][1<<17];
int pos[35][1<<17];
int code[1<<17];
const int the_number = 1<<15;
void query(const vector<int> &v1, const vector<int> &v2,int qid)
{
    int cnt = 0;
    for (auto x : v1)
    {
        printf("%d ",code[x]);
        cnt ++;
        pos[qid][x] = cnt;
    }
    for (auto x : v2)
    {
        printf("%d ",code[x]);
        cnt ++;
        pos[qid][x] = cnt;
    }
    printf("\n");
}
int check(int now, bool last = false, int guess = 0)
{
    int i;
    int val = now;
    for (i=0;i<15;i++)
    {
        val ^= ((num[i*2][pos[i*2][now]] ^ num[i*2+1][pos[i*2+1][now]]) << i);
    }
    if (n < the_number)
    {
        return val;
    }
    int val1 = val;
    int val2 = val ^ the_number;
    if (val2 > n)
    {
        return val;
    }
    if (val1 == 0)
    {
        return val2;
    }
    if (deg[val1] == 0)
    {
        return val2;
    }
    if (deg[val2] == 0)
    {
        return val1;
    }
    if (!last)
    {
        if (deg[val1] == 1)
        {
            return val2;
        }
        if (deg[val2] == 1)
        {
            return val1;
        }
    }
    for (i=0;i<15;i++)
    {
        if (num[i*2][pos[i*2][now]] == num[i*2+1][pos[i*2+1][now]])
        {
            if (num[i*2][pos[i*2][now]] == 1)
            {
                if (pos[i*2][now] < pos[i*2][val1])
                {
                    return val2;
                }
                if (pos[i*2][now] < pos[i*2][val2])
                {
                    return val1;
                }
            }
            else
            {
                if (pos[i*2][now] > pos[i*2][val1])
                {
                    return val2;
                }
                if (pos[i*2][now] > pos[i*2][val2])
                {
                    return val1;
                }
            }
        }
    }
    for (i=0;i<31;i++)
    {
        if ((pos[i][val1] < pos[i][now]) && (num[i][pos[i][val1]] == deg[val1]))
        {
            return val2;
        }
    }
    for (i=0;i<31;i++)
    {
        if ((pos[i][val2] < pos[i][now]) && (num[i][pos[i][val2]] == deg[val2]))
        {
            return val1;
        }
    }
    if (guess == 1)
    {
        return val1;
    }
    if (guess == 2)
    {
        return val2;
    }
    return -1;
}
int que[50000005];
int rail = 0;
vector<pair<int,int> > ans;
int timeline[50005];
int cnt;
bool add_ans(int now, int x)
{
    if ((x > n) || (x <= 0))
    {
        return false;
    }
    cnt++;
    ans.push_back(make_pair(now, x));
    int i;
    for (i=0;i<31;i++)
    {
        if (pos[i][x] > pos[i][now])
        {
            num[i][pos[i][x]] --;
        }
    }
    deg[now] --;
    deg[x] --;
    if (deg[x] == 1)
    {
        que[rail++] = x;
    }
    if ((deg[now] < 0) || (deg[x] < 0))
    {
        return false;
    }
    return true;
}
void rollback(int return_rail, int return_cnt)
{
    rail = return_rail;
    for (;cnt>return_cnt;)
    {
        cnt--;
        int now = ans[cnt].first;
        int x = ans[cnt].second;
        ans.pop_back();
        int i;
        for (i=0;i<31;i++)
        {
            if (pos[i][x] > pos[i][now])
            {
                num[i][pos[i][x]] ++;
            }
        }
        deg[now] ++;
        deg[x] ++;
    }
}
bool dfs(int front = 0, int begin_cnt = 0)
{
    int now_rail = rail;
    for (;cnt<n-1;front++)
    {
        int now = que[front];
        int x = check(now, cnt == (n-2));
        if (x == -1)
        {
            if (timeline[now] == cnt)
            {
                int y = rand()%2+1;
                int x = check(now, cnt == (n-2), y);
                int temp_rail = rail;
                int cur_cnt = cnt;
                if (add_ans(now, x) && dfs(front+1, cnt))
                {
                    return true; 
                }
                rollback(temp_rail, cur_cnt);
                x = check(now, cnt == (n-2), 3-y);
                if (add_ans(now, x) && dfs(front+1, cnt))
                {
                    return true;
                }
                rollback(now_rail, begin_cnt);
                return false;
            }
            else
            {
                timeline[now] = cnt;
                que[rail++] = now;
                continue;
            }
        }
        if (!add_ans(now, x))
        {
            rollback(now_rail, begin_cnt);
            return false;
        }
    }
    int i;
    for (i=1;i<=n;i++)
    {
        if (deg[i] < 0)
        {
            rollback(now_rail, begin_cnt);
            return false;
        }
    }
    return true;
}
int a[1<<17]; 
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    struct timeval tv;
    gettimeofday(&tv, NULL);
    srand(tv.tv_sec + tv.tv_usec + getpid()); 
    int i;
    for (i=1;i<=the_number;i++)
    {
        a[i] = i;
    }
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
            code[i] = i;
        }
        random_shuffle(code+1,code+n+1);
        random_shuffle(code+1,code+n+1);
        random_shuffle(code+1,code+n+1);
        printf("%d\n",31);
        for (i=0;i<15;i++)
        {
            int j;
            vector<int> v1, v2;
            if (n > the_number)
            {
                random_shuffle(a+1,a+the_number +1);
                random_shuffle(a+1,a+the_number +1);
                random_shuffle(a+1,a+the_number +1);
                for (j=1;j<=the_number;j++)
                {
                    if (a[j] <= n - the_number)
                    {
                        if ((1<<i)&a[j])
                        {
                            v1.push_back(a[j]);
                        }
                        else
                        {
                            v2.push_back(a[j]);
                        }
                    }
                }
                for (j=1;j<=the_number;j++)
                {
                    if (a[j] > n - the_number)
                    {
                        if ((1<<i)&a[j])
                        {
                            v1.push_back(a[j]);
                        }
                        else
                        {
                            v2.push_back(a[j]);
                        }
                    }
                }
                for (j=1;j<=the_number;j++)
                {
                    if (a[j] + the_number <= n)
                    {
                        if ((1<<i)&a[j])
                        {
                            v1.push_back(a[j] + the_number);
                        }
                        else
                        {
                            v2.push_back(a[j] + the_number);
                        }
                    }
                }
            }
            else
            {
                for (j=1;j<=n;j++)
                {
                    if (j <= n)
                    {
                        if ((1<<i)&j)
                        {
                            v1.push_back(j);
                        }
                        else
                        {
                            v2.push_back(j);
                        }
                    }
                }
            }
            query(v1, v2, i*2);
            query(v2, v1, i*2+1);
            if (i == 14)
            {
                reverse(v1.begin(), v1.end());
                reverse(v2.begin(), v2.end());
                query(v2, v1, 30);
                fflush(stdout);
                int i,j;
                for (i=0;i<31;i++)
                {
                    for (j=1;j<=n;j++)
                    {
                        scanf("%d",&q[i][j]);
                        num[i][j] = q[i][j] - q[i][j-1];
                    }
                }
                for (i=1;i<=n;i++)
                {
                    int x;
                    if (i > (int)v2.size())
                    {
                        x = v1[i-v2.size()-1];
                    }
                    else
                    {
                        x = v2[i-1];
                    }
                    deg[x] = num[30][i] + num[28][n-i+1];
                }
            }
        }
        rail = 0;
        for (i=1;i<=n;i++)
        {
            if (deg[i] == 1)
            {
                que[rail++] = i;
            }
        }
        ans.clear();
        for (i=1;i<=n;i++)
        {
            timeline[i] = -1;
        }
        cnt = 0;
        dfs();
        for (auto x : ans)
        {
            printf("%d %d\n",code[x.first], code[x.second]);
        }
        fflush(stdout);
    }
    return 0;
} 

再度提示一下：本题解偏娱乐向，仅提供一种思路，驳辩有些人认为二进制不可做的问题。