题解：P11890 [XRCOI Round 1] A. 相聚相逢本无意

Pyrf_uqcat · 2025-03-15 22:22:24 · 题解

赛时搞了好久，做法是将每个子任务逐个击破。

子任务一

子任务说明 x\ne 0 且 y\ne 0。

无需考虑太多，当有 y 个 x 时，只需要在序列中放 y 个 x-1 就可以了，在前面把 0 到 x-2 都需要至少放 1 个以保证 \operatorname{MEX} 为 x。

可以拿下子任务一得到三十分。

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+5;

int n,ans[N]={-1},k;

struct Node
{
    int x,y;
}a[N];

bool flag[N];

map<int,int> mp;

bool cmp(Node x,Node y)
{
    return x.x<y.x;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=ans[k]+1;j<a[i].x-1;j++)
        {
            ans[++k]=j;
        }
        while(a[i].y--) ans[++k]=a[i].x-1;
        if(k>2e5) cout<<-1<<endl,exit(0);
    }
    cout<<k<<endl;
    for(int i=1;i<=k;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}

子任务二

现在 y 可能会等于 0 了。

当 x 一个都没有时，说明不会出现 x-1。既然不会出现 x-1，则当有 x 大于出现 0 次的数时，这个序列无法构造出来。只需用一个变量进行标志是否出现过 0，即可实现优化。

通过子任务二拿到六十分。

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+5;

int n,ans[N]={-1},k,flagg;

struct Node
{
    int x,y;
}a[N];

bool flag[N];

map<int,int> mp;

bool cmp(Node x,Node y)
{
    return x.x<y.x;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(flagg&&a[i].y) cout<<-1<<endl,exit(0);
        if(a[i].y==0)
        {
            flagg=1;
            continue;
        }
        for(int j=ans[k]+1;j<a[i].x-1;j++)
        {
            ans[++k]=j;
        }
        while(a[i].y--) ans[++k]=a[i].x-1;
        if(k>2e5) cout<<-1<<endl,exit(0);
    }
    cout<<k<<endl;
    for(int i=1;i<=k;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}

子任务三

当要出现 x=0 时，则说明第一个数不能是零。而这是一个不递减队列，说明后面永远不会出现 0，那么后面的所有 \operatorname{MEX} 都等于 0。只有当后面所有的数都出现零次才行，所以再来一个变量进行标记是否出现过 x=0。

拿下子任务三得到九十分。

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+5;

int n,ans[N]={-1},k,flagg,flaggg;

struct Node
{
    int x,y;
}a[N];

bool flag[N];

map<int,int> mp;

bool cmp(Node x,Node y)
{
    return x.x<y.x;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(flagg&&a[i].y) cout<<-1<<endl,exit(0);
        if(flaggg&&a[i].y) cout<<-1<<endl,exit(0);
        if(a[i].y==0)
        {
            flagg=1;
            continue;
        }
        if(a[i].x==0)
        {
            flaggg=1;
            continue;
        }
        for(int j=ans[k]+1;j<a[i].x-1;j++)
        {
            ans[++k]=j;
        }
        while(a[i].y--) ans[++k]=a[i].x-1;
        if(k>2e5) cout<<-1<<endl,exit(0);
    }
    if(flaggg)
    {
        cout<<a[1].y<<endl;
        for(int i=1;i<=a[i].y;i++)
        {
            cout<<1<<' ';
        }
        cout<<endl;
        return 0;
    }
    cout<<k<<endl;
    for(int i=1;i<=k;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}

子任务四

经过前三个子任务但还是有几个点没过，这是因为漏了一个特殊的样例。当 x=0 且 y=0 时，这就和子任务一样了，可以理解为没有这一次输入，判断一下即可。

赛时通过代码

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+5;

int n,ans[N]={-1},k,flagg,flaggg;

struct Node
{
    int x,y;
}a[N];

bool flag[N];

map<int,int> mp;

bool cmp(Node x,Node y)
{
    return x.x<y.x;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].x==0&&a[i].y==0) continue;
        if(flagg&&a[i].y) cout<<-1<<endl,exit(0);
        if(flaggg&&a[i].y) cout<<-1<<endl,exit(0);
        if(a[i].y==0)
        {
            flagg=1;
            continue;
        }
        if(a[i].x==0)
        {
            flaggg=1;
            continue;
        }
        for(int j=ans[k]+1;j<a[i].x-1;j++)
        {
            ans[++k]=j;
        }
        while(a[i].y--) ans[++k]=a[i].x-1;
        if(k>2e5) cout<<-1<<endl,exit(0);
    }
    if(flaggg)
    {
        cout<<a[1].y<<endl;
        for(int i=1;i<=a[i].y;i++)
        {
            cout<<1<<' ';
        }
        cout<<endl;
        return 0;
    }
    cout<<k<<endl;
    for(int i=1;i<=k;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}

题外：

这辈子写过最长的题解，四千多字符，同时也是写过的最复杂的方法。其实应该是可以直接推得结果的，但是赛时搞了好久每个子任务都错了一两个，只能使用这么不聪明的方法了。