「简单题」 [Codeforces 1209C] Paint the Digits

· · 题解

一开始猜了一个把 LIS 找出来就完了。然后发现假的离谱。然后就考虑观察性质，发现如果存在合法答案，那么对于一个 i 如果位置不变，会有 1\sim i-1 都 \leqslant i 。不难发现这是个十分强的必要条件。于是可以这么把答案取出来，然后去 check 一下充分性就好了。复杂度线性。

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

const int N = 301000 ;

using namespace std ;

int n, T ;
int maxc ;
int maxv ;
int res[N] ;
int ans[N] ;
int base[N] ;
bool vis[N] ;
vector <int> ans1, ans2 ;

int main(){
    scanf("%d", &T) ;
    while (T --){
        scanf("%d", &n) ;
        maxv = maxc = 0 ;
        ans2.clear() ; ans1.clear() ;
        memset(vis, 0, sizeof(vis)) ;
        for (int i = 1 ; i <= n ; ++ i)
            scanf("%1d", &base[i]) ;
        for (int i = 1 ; i <= n ; ++ i)
            if (maxv > base[i])
                 vis[i] = 1, maxc = max(base[i], maxc) ;
            else maxv = std :: max(maxv, base[i]) ;
        for (int i = 1 ; i <= n ; ++ i){
            if (vis[i] || base[i] < maxc)
                 ans1.push_back(i) ;
            else ans2.push_back(i) ;
        }
        int cnt = 0 ;
        for (auto k : ans1) ans[k] = 1, res[++ cnt] = base[k] ;
        for (auto k : ans2) ans[k] = 2, res[++ cnt] = base[k] ;
       // for (int i = 1 ; i <= n ; ++ i) printf("%d ", res[i]) ; puts("") ;
        for (int i = 1 ; i <= n ; ++ i)
            if (res[i] < res[i - 1]) goto cc ;
        for (int i = 1 ; i <= n ; ++ i)
            printf("%d", ans[i]) ; puts("") ; continue ;
        cc : puts("-") ;
    }
}