[洛谷题解] CF1209C Paint the Digits

发布于 2019-09-20  184 次阅读


题目:CF1209C Paint the Digits


题意简述

给出一个序列(数值为0到9,即一个数字位),要求将其分成两个子序列,并首尾相接成一个不下降序列。输出任意一组可行解。

输出格式:输出一行长度为原序列长度的,1和2构成的数字串。如果第i个元素分到子序列1(放在前面的那个),第i位是1,否则是2


解题思路

我们注意到序列元素很小,可以枚举序列1和序列2的分界值t

那么显然序列1的所有元素不大于t,且是不下降序列。序列2的所有元素不小于t,且是不下降序列。

我们从后往前扫描(模拟一下会发现从后往前才能对)确定出子序列1。具体地,维护一个min值,初始化为10。从后向前扫描原序列,对于每一个不大于t的值:

  • 如果这个值不大于min,将这个值加入序列1,并更新min为这个值
  • 否则
    • 如果这个值小于t,显然它也不可能出现在序列2中,无解。
    • 如果这个值等于t,它可以出现在序列2中,暂时不将其放入序列1

操作完成后,就剩下的元素就构成了序列2,此时判断序列2是否不下降就可以了。

代码

// status: [Accepted]
// oj:     [Codeforces]

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
int arr[MAXN];
int n;
int col[MAXN];

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin>>T;

    while(T--) {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) {
            char c;
            cin>>c;
            arr[i] = c-'0';
        }

        bool solved = false;
        for(int t=0;t<10;t++) {
            int m1 = 10;
            int m2 = 10;
            bool ok = 1;
            for(int i=1;i<=n;i++) col[i]=-1;
            for(int i=n;i>=1;i--) {
                if(arr[i]<=t) {
                    if(arr[i]<=m1) col[i] = 1;
                    if(arr[i]>m1 && arr[i]!=t) {ok=0;break;}
                    if(arr[i]<=m1) m1=arr[i];
                    // if(t==4) cerr<<"Colored "<<i<<'>'<<arr[i]<<" 1"<<endl;
                }
            }
            for(int i=n;i>=1;i--) {
                if(arr[i]>=t && col[i]!=1) {
                    col[i] = 2;
                    if(arr[i]>m2) {ok=0;break;}
                    m2=arr[i];
                }
            }
            if(ok) {
                for(int j=1;j<=n;j++) {
                    cout<<col[j];
                }
                cout<<'\n';
                solved = 1;
                break;
            }
        }

        if(!solved) {
            cout<<'-'<<'\n';
        }
    }
}

undefined