[洛谷题解] CF1209C Paint the Digits

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

题目：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