题解 | #小红的kmp#

最后5分钟极限ak

G题解: 很trick的构造

可以发现n=4的时候无解(x

n/4 为偶数情况：

考虑把小于n/4的奇数和对应的2倍偶数连在一起 例如： n = 16时，有 1-2 , 3-6 , 5-10 , 7-14 , 然后把4个平均分配两个颜色 红色：1、3、10、14 蓝色：2、6、5、7 就做完了

n/4为奇数的情况，可以考虑把n<=12的处理掉，有 1-4,3-6,5-10 分配： 红色：4，3，5 蓝色：1，6，10

然后就规约到偶数情况了

代码：

#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;

#define ll long long
#define endl "\n"

void solve(){
    int n;cin>>n;
    vector<int> a(n);
    for(int &x:a)cin>>x;
    if(n == 4){
        cout<<-1;
        return;
    }
    map<int,int> mp1 , mp2;
    if(n/4 % 2 == 0){
        for(int i = 1;i< n/2;i+=2){
            if(i%4 == 1){
                mp1[i]++;
                mp2[2 * i]++;
            }else{
                mp1[2 * i]++;
                mp2[i]++;
            }
        }
    }else{
        mp1[4] = mp1[3] = mp1[5] = 1;
        mp2[1] = mp2[6] = mp2[10] = 1;
        for(int i = 7 ;i < n/2;i+=2){
            if(i%4 == 1){
                mp1[i]++;
                mp2[2 * i]++;
            }else{
                mp1[2 * i]++;
                mp2[i]++;
            }
        }
    }
    for(int x : a){
        if(mp1[x]) cout<<1;
        else if(mp2[x]) cout<<2;
        else cout<<0;
    }
}

int main() {
    solve();
}