CF1894B Two Out of Three

· · 题解

思路

简简单单构造题，就是要认真读题，是能且只能满足两个条件。

我们可以考虑每种数字，如果数字只有一个，是不能满足任何一个条件的，那就随便给一个 b 即可。

如果这个数字有多个，那么就只能有两种 b，否则就会满足三个条件，所以一种数字最多满足一种条件。

所以，如果只有一个或者甚至没有两个及以上的数字，那么必定无解。

再来考虑如何构造，可以直接钦定一种数字满足一个条件，其他所有数字满足另一种条件。

因为只是构造题，只要合理就可以随便造，所以可以先选一个出现多次的数字为特殊数字，然后把所有数字的非最后一个都给 1，然后对于每种数字的最后一种，如果是特殊数字，就给 2，否则就给 3。

这样，必定有一种数字（特殊数字）满足条件 1，其他出现多次的数字满足条件 2，其他数字不满足任何条件，这样就恰好满足两个条件。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,a[105],num[105],res,f;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n),f=res=0;
        for(int i=1;i<=100;++i) num[i]=0;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]),++num[a[i]],res+=(num[a[i]]==2);
        if(res<2){printf("-1\n");continue;}
        for(int i=1;i<=n;++i)
        {
            if(num[a[i]]==1)
            {
                if(f==a[i]) printf("2 ");
                else printf("3 ");
            }
            else f=(!f&&num[a[i]]>1)?a[i]:f,printf("1 "),--num[a[i]];
        }
        puts("");
    }
    return 0;
}