P9529 [JOISC 2022 Day4] 一流团子师傅 题解

· · 题解

一道交互好题恶心题

感谢 Aaronwrq 大佬的帮助，题解有所借鉴 Jason0211 的题解。

思路

我们可以把每个串看成一个集合，所以总共有 m 个集合，对于每个团子，我们尝试将其插入某个集合中。插入时需要维护以下性质：

一：每个集合内的每个团子的颜色互不相同。

二：同一种颜色的团子是按串串的编号从左到右放到每个串串中的。

所以现在问题变为了如何检验这个颜色的团子放在哪里。

而我们似乎只能用 Query(x[]) 函数来检验，但是我们总共只能调用 50000 次 Query(x[]) 函数。而团子的总数最多有 m \times n 即 10000 个。所以我们需要在最多调用 5 次 Query(x[]) 函数的情况下来求出这个团子放在哪。

我们根据这些想到可以二分，因为根据性质二，这种颜色的团子一定是前面一段串串有，后面的串串全部都没有的，所以可以通过二分的方式来查找。而二分要调用大约 \log_2 25 次 Query(x[]) 函数，而 4 \le \log_2 25 \le 5，刚好小于等于 5，所以我们接下来就要考虑怎么二分了。

我们先假设前几个串串上已经有了一些团子，就像这样：

那么对于下一个这种颜色的团子，如果我们放在这两个已经有这种颜色的串上，就像这样：

由于这种颜色的团子的个数等于总的串串数，所以如果我们放在这两个已经有这种颜色的串上的话，所有剩下的团子就没有办法组成剩下串串的个数个一流团子串。（建议自己在纸上画一下）欸，这不就可以用到 Query(x[]) 函数了吗！

我们设当前的团子放在第 mid 个串上，那么如果所有没有处理的团子和第 mid+1 到第 m 个串上的所有团子加起来能做出至少 m-mid 个一流团子串的话，这个团子就可以放在第 mid 个串上。就像这样（能放的情况）：

我们就用这个进行二分，如果能做出至少 m-mid 个一流团子串，我们就把 r 赋值为 mid-1，同时用 ans 记录下 mid，否则就把 l 赋值为 mid+1，二分的边界条件为 l \le r。（至于为什么这么二分，读者可以自己研究一下）二分完后就把这个团子放入第 ans 个串串中。把每个团子都这样处理后这道题就做完了。

核心代码如下：

//注意是交互题
namespace {

    int n,m;
    vector<int> v[1000];
}  
bool work(int h,int j)
{
    vector<int> G;
    for(int qqq=h+1;qqq<=n*m;qqq++)
    {
        G.push_back(qqq);
    }
    for(int qqq=j+1;qqq<=m;qqq++)
    {
        for(int qq=0;qq<v[qqq].size();qq++)
        {
            G.push_back(v[qqq][qq]);
        }
    }
    return Query(G)>=m-j;
}
void Solve(int N, int M) 
{
    n=N;
    m=M;
    for(int qqq=1;qqq<=n*m;qqq++)
    {
        int ll=1,rr=m,mid,ans=-1;
        while(ll<=rr)
        {
            mid=(ll+rr)>>1;   
            int www=work(qqq,mid);      
            if(www)
            {   
                 rr=mid-1;
                ans=mid;//记录mid
            }
            else
            {
                ll=mid+1;
            }
        }
        v[ans].push_back(qqq);
    }
    for(int qqq=1;qqq<=m;qqq++)
    {
        Answer(v[qqq]);
    }
}

AC记录