CF1896G Pepe Racing 题解

· · 题解

CF1896G Pepe Racing 题解

题目传送门。

被 Idleness limit exceeded 卡了一小时发现是少了一个 for 循环。。。

这个题细节很多，注意仔细看代码，好好推敲。

题意

交互题，有 n^2 个数，有个比较器每次可以告诉你 n 个数里面的最大值的位置，要求你给前 n^2-n+1 大个数从大到小排序，比较器最多使用 2n^2-2n+1 次。

解法

注意到 n 很小，所以不考虑时间复杂度，只考虑查询次数。

考虑一个一个找，每次找到一个最大值就把它从集合里删掉，再进行重复操作。

考虑给 n^2 个数分块，分成 n 块，每块 n 个数。

找一次全局最大值，只需要在每组询问一个块内最大值，再把这些块内最大值放在一起询问全局最大值。

显然多次这样做不合理。考虑优化寻找的方法。

注意到每次找到一个最大值，就要删去它。而删去它只会改变一个块的最大值。

那我们只需要查询被改变的块的块内最大值，再查询一次全局最大值。

但是现在删去了一个数，块内不到 n 个数。我们只需要找一个其他块的不是块内最大值的随便一个值（即这个值要在其他块内出现过且不是其块内最大值）补充即可。正确性显然。

分析查询次数。预处理每块最大值和第一次的全局最大值要 n+1 次；修改一次最大值要 2 次查询，由于只需排名 n^2-n+1 个人，而第一个人已经考虑了，总次数是 n+1+2(n^2-n)=2n^2-n+1。

还多了 n 次，考虑优化。

考虑只剩下 2n-1 个数未排名。

由于还是分成了 n 块，所以每块的块内最大值就是这最后 n 大的数，因为我们已经确定了 n-1 个最小的。

为什么我们已经确定了 n-1 个最小的呢？因为它们这些数在之前的补充的过程中没有被补到块内最大值，也就是它们这些数永远小于当前的所有块内的最大值。

然后对于 n 个块内最大值询问 n-1 次（最后一个可以排除出来）就行了。

分析查询次数：n+2(n^2-2n+1)+n-1=2n^2-2n+1，刚好通过。

详见代码，注释清楚。

AC 代码

注意下面代码：所有数组存的都是下标。

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
const int N=410;
int ask(set<int> &s) // 询问区间最大值
{
    cout<<"? ";
    for(auto a:s)cout<<a<<" ";
    cout<<"\n",fflush(stdout); // 清空缓冲区！！！
    int x;
    cin>>x;
    return x;
}
bool vis[N]; // 记录出现过的块内最大值
int n;
void get(set<int> &s) // 补充块
{
    int num=1;
    while(s.size()<n) // 补到 n
    {
        while(vis[num]||s.find(num)!=s.end())num++; // 不能是其他块的块内最大值
        s.insert(num);
    }
}
int maxx[N]; // 块内最大值
set<int>a[N]; // 元素
vector<int>ans; // 答案数组
void solve()
{
    cin>>n;
    for(int i=0;i<=n*n+1;i++)vis[i]=false,maxx[i]=0,a[i].clear(); // 多测不清空，爆零两行泪
    ans.clear();
    for(int i=1;i<=n;i++)
    {
        for(int j=(i-1)*n+1;j<=i*n;j++)a[i].insert(j); // 初始化元素
        maxx[i]=ask(a[i]),vis[maxx[i]]=true; // 查询块内最大值
    }
    for(int _=n*n;_>=2*n;_--) // 2n-1 之前的操作
    {
        set<int>now;
        for(int i=1;i<=n;i++)now.insert(maxx[i]); // 把块内最大值放进一个 set
        get(now); // 补充少的元素
        int x=ask(now),id=0; // 查询全局最大值
        for(int i=1;i<=n;i++)
            if(maxx[i]==x)id=i; // 记录全局最大值出现的块编号
        ans.push_back(x); // 计入答案
        a[id].erase(x),get(a[id]); // 删去全局最大值并补充
        maxx[id]=ask(a[id]),vis[maxx[id]]=true; // 因为修改（有删除）了，所以重新查询块内最大值
        for(int i=1;i<=n;i++)
            if(i!=id)a[i].erase(maxx[id]); // 由于之前补入的是其他块内的元素，所以有可能存在相同，要删去，我就是这里少了，卡了 1 小时
    }
    set<int>now;
    for(int i=1;i<=n;i++)now.insert(maxx[i]); // 直接把块内最大值放进 set
    get(now);
    for(int _=n-1;_;_--) // 注意是 n-1
    {
        int x=ask(now); // 查询最大值
        now.erase(x),get(now),ans.push_back(x); // 删除、补入、计入答案的常规操作
    }
    for(int x:now)
        if(vis[x])ans.push_back(x); // 把最后一个补进来，由于块内最大值是之前被 vis 记录过的，所以可以用 vis 来补
    cout<<"! ";
    for(int a:ans)cout<<a<<" ";
    cout<<"\n",fflush(stdout); // 输出答案，注意要清空缓冲区！！！
}
int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

后记

注意事项：

多测不清空，爆零两行泪！

如果有讲错的地方，欢迎提出修正；如果有讲得不清楚的地方，欢迎提问。

给个赞吧，给个关注吧 QWQ~