「简单题」 [Codeforces 1209C] Paint the Digits
皎月半洒花
2020-06-16 21:28:39
一开始猜了一个把 LIS 找出来就完了。然后发现假的离谱。然后就考虑观察性质，发现如果存在合法答案，那么对于一个 $i$ 如果位置不变，会有 $1\sim i-1$ 都 $\leqslant i$ 。不难发现这是个十分强的必要条件。于是可以这么把答案取出来，然后去 check 一下充分性就好了。复杂度线性。
```cpp
#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("-") ;
}
}
```
#