[洛谷题解] CF1209C Paint the Digits • KMnO4y

题目：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';
        }
    }
}

cpp