CF1854D Michael and Hotel 题解

Links

洛谷

Codeforces

Description

这是一个交互题。

有一个有 $n$ 个点的内向基环树森林，zlsim 位于 $1$ 号节点，请你通过以下操作求出哪些节点（包括 $1$）可以通过从这两点开始沿边行走若干步汇至一点。

给出两个参数 $u,k$ 和点集 $S$，询问是否能够通过从 $u$ 出发走 $k$ 步达到任意 $S$ 中的节点。

你最多可以询问 $2000$ 次。

Solution

一个很显然的题意转化是我们要找到的是节点 $1$ 所在的连通块。这个连通块一定是一颗内向基环树，因此我们可以很容易的找到一个环上的点。具体的方法如下：

将剩余点分等为两部分。
询问从 $1$ 出发，行进 $n$ 次之后是否能到达第一部分，若能到达，保留第一部分，若不能，保留第二部分。
重复上述步骤，只剩一个点时停止。

每次减半，因此我们只需要 $ \left \lceil \log_{2}500 \right \rceil = 9$ 次操作就能找到一个点。

接下来我们不断按照上面的方式询问从上一个找到的在环上的点开始行进一次能到达的点，就能找到所有环上的点。假设环上有 $k$ 个点，我们需要 $9\times k$ 次操作，这样不能满足题目条件。

考虑如何加快找点的速度，我们可以进行以下操作：

设已经找到的在连通块内的点集为 $S$，剩余点集为 $V$。
$\forall i \in V$，询问从 $i$ 开始行进 $|S|$ 步能否到达 $S$，若能，将其加入 $S$。
如果这次新找到的点数量小于 $|S|$，结束查找。

这样我们就能找到环上的点，但也会找到一些在该连通块内不属于环上的点，这对我们接下来的操作没有影响。

现在环内所有点已经确定，我们可以用 $n - |S|$ 次询问确定剩余的点，具体的，对于每个不在 $S$ 中的点 $u$，询问从 $u$ 开始行进 $n$ 步能否到达 $S$，若能到达一定在该连通块内，否则不在该连通块内。

假设我们通过二分找到 $p$ 个环上的点，需要的询问数如下：

二分：$9 \times p$。
倍增找点：令$p_{1} = p, \forall i > 1,p_{i} = 2 p_{i - 1}$，则第 $i$ 次需要 $n - p_{i}$ 个询问，当 $p_{i} \ge n$ 时结束（假设这时 $i = x$）。
最后需要 $n - p_{x}$ 次询问确定剩余点。

当 $p$ 取 $63$ 时满足题意。

Codes

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 511

int n;
int tot = 0;
int ls = 1;
bool check(int tim,int l,int r)
{
    cout<<"? "<<ls<<" "<<tim<<" "<<r - l + 1<<" ";
    for(int i = l;i <= r;i++)
    {
        cout<<i<<" ";
    }
    cout<<endl;
    int op;
    cin>>op;
    return op;
}
set<int> nodes;
bool vis[max_n];
signed main()
{
    ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    cin>>n;
    int l = 1,r = n;
    ls = 1;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(1000,l,mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    nodes.insert(l);
    vis[l] = 1;
    ls = l;
    for(int i = 1;i <= 62;i++)
    {
        l = 1,r = n;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(check(1,l,mid))
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        if(vis[l])
        {
            break;
        }
        vis[l] = 1;
        nodes.insert(l);
        ls = l;
    }    
    if(nodes.size() == 63)
    {
        int sz = nodes.size(); 
        while(true)
        {
            tot = 0;
            for(int i = 1;i <= n;i++)
            {
                if(!vis[i])
                {
                    cout<<"? "<<i<<" "<<sz<<" "<<nodes.size();
                    for(auto node:nodes)
                    {
                        cout<<" "<<node;
                    }
                    cout<<endl;
                    int op;
                    cin>>op;
                    if(op)
                    {
                        vis[i] = 1;
                        nodes.insert(i);
                    }
                }
            }
            sz *= 2;
            if(sz > nodes.size())
            {
                break;
            }
        }
    }
    
    for(int i = 1;i <= n;i++)
    {
        if(!vis[i])
        {
            cout<<"? "<<i<<" "<<1110<<" "<<nodes.size();
            for(auto node:nodes)
            {
                cout<<" "<<node;
            }
            cout<<endl;
            int op;
            cin>>op;
            if(op == 1)
            {
                nodes.insert(i);
            }
        }
    }
    cout<<"! "<<nodes.size()<<" ";
    for(auto node:nodes)
    {
        cout<<node<<" ";
    }
    cout<<endl;
    return 0;
}