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

· · 题解

思路解析

这题有点过于抽象了，要考虑一堆特殊情况，将近四个小时才调出来，建议至少评黄。

有些特殊情况有点过于极端了，真的就是很难想到，下面我就逐个分析一下。

首先先看特殊性质，因为 x\not=0,y\not=0，所以可以直接构造，按顺序枚举从 0 到最大的 x 的每个数一遍，如果有 y 的话就输出 y 遍，否则就是 1 遍，这样第一个子任务就可以过掉了。

然后我们再看第二个子任务，这里的特殊性质是 x\not=0 ，模拟一遍样例我们可以发现，如果一个 x 的 y 值为 0 的话，就无法构造出符合要求的序列。但是为什么会 WA 几个点呢，因为如果这个 x 的值大于其他 y 值不等于 0 的 x 的最大值的话，那么这个 x 就不需要考虑构造，直接忽略这个约束就行了。

然后我们再看第三个子任务，这里的特殊性质的 y\not=0 ，也就是说， x 可以为 0。因为要求构造的序列都为非负数，那么如果 x 为 0 的话，序列开头只能是 1，而构造的序列想要满足其他约束，那么 1 后就只能用 0，这就与题目要求的单调不降冲突了，所以如果有 x 的值为 0，那么一定无解。

测试一下发现，依然有几个点 WA 了，为什么呢？因为如果一个特殊情况只有 x 为 0 没有其他约束的话，也可以构造出一个符合要求的序列，所以要单独考虑这种情况而写一个特殊的构造。

把一二三号子任务结合起来看第四个子任务，仍然会有 WA 的点。这里没有了特殊性质的限制。仔细思考后我们发现，把二三号子任务结合在一起看，如果有一个 x 的值为 0 且 y 值不为 0，和一个 x 值不为 0 但 y 值为 0 的情况依然是有解的，因为后一个可以忽略不看，只满足前一个条件就行了。

再考虑一个新的特殊情况，如果有一个 x 的值为 0 且 y 值不为 0，和一个 x 值不为 0 但 y 值不为 0 的情况，那么肯定是无解的，原因和子任务二的特殊情况相同。

找明白所有的特殊情况后，我们最终才能得出正确的思路。然后我们就可以开始写代码了。在这里，我使用一个桶数组记录每个数字应该输出多少次，而这些值初始都为一，经过输入限制后再进行修改，最后计算总输出次数然后分别输出即可，如果特判遇到上述所示的所有特殊情况则按要求进行构造或输出无解。这样，我们就完成了整道题目。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[100009],ma=0,ans=0;
int main()
{
    cin>>n;
    for(int i=0;i<=1009;i++)
    {
        a[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        long long b,c;
        cin>>b>>c;
        a[b-1]=c;
        if(c!=0)ma=max(ma,b);
    }
    if(ma!=0&&a[-1]!=0)//这里的-1是为了记录x值为0的情况，如果出问题了可以把所有a数组下标右移一位再试
    {
        cout<<-1;
        return 0;
    }
    if(ma==0&&a[-1]!=0)
    {
        cout<<a[-1]<<endl;
        for(int i=1;i<=a[-1];i++)
        {
            cout<<1<<" ";
        }
        return 0;
    }
    for(int i=0;i<ma;i++)
    {
        if(a[i]==0)
        {
            cout<<-1;
            return 0;
        }
        ans+=a[i];
    }
    cout<<ans<<endl;
    for(int i=0;i<ma;i++)
    {
        for(int j=1;j<=a[i];j++)
        {
            cout<<i<<" ";
        }
    }
}

完结撒花！