P9529题解报告

· · 题解

题目传送门

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

解法

本题解有所借鉴这位大佬的博客文章JOISC 2022

首先，我们可以想到顺次填满每一个串。然后，我们考虑对每个团子分组，将新来的团子加入到还没有出现这种颜色的串上，这样问题就转化为怎样快速判断从哪个串开始没有这种颜色的。

我们想到可以二分，因为这种颜色的团子一定是前面一段有，后面全部都没有的。简单证明一下：我们是从前往后顺次放置每一种颜色的，所以有这种颜色的串一定是从 1 开始的一段连续序列。

接下来就是二分的过程：具体的判断就是把所有团子中排除掉 1 至 mid 的区间的所有团子加上当前要考虑的团子。如果不排除当前要考虑的团子，那么能组成的串的数量应当是大于等于 m-mid，但是删掉这一个之后，如果 mid 以及之前是有这个颜色的，那么一定会减少一个串，使得串的数量小于 m-mid，这样就能直接二分了。

具体细节见代码：

#include<bits/stdc++.h>
void Solve(int N, int M);
int Query(const std::vector<int> &x);
void Answer(const std::vector<int> &a);

using namespace std;

namespace{
    int n,m;
    vector<int> V[505];
}

int work(int now,int pos)
{
    vector<int> G;
    for(int i=now+1;i<=n*m;i++) G.push_back(i);
    for(int i=pos;i<=m;i++)
    {
        for(int j=0;j<V[i].size();j++)
        {
            G.push_back(V[i][j]);
        }
    }
    return Query(G)<m-pos+1;
}

void Solve(int x,int y)
{
    n=x,m=y;
    for(int i=1;i<=n*m;i++)
    {
        int l=1,r=m,pos;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(work(i,mid)) pos=mid,l=mid+1;
            else r=mid-1;
        }
        V[pos].push_back(i);
    }
    for(int i=1;i<=m;i++) Answer(V[i]);
}