「找性质」 [Codeforces 1209G1] Into Blocks (easy version)
皎月半洒花
2020-06-16 21:28:46
感觉这个 G1 还是比较 naive 的?找个性质这题就没了。
大概做题时有这么几个 Observation,当时拿笔写了下来,感觉应该是比较正常思路:
1、答案上界一定是 $n-\max \{col{\rm num}\}$ .
2、如果一个颜色存在不相邻,那么要么会被全部涂成别的颜色,要么会被保留。
3、根据 $2$ 不难发现,一段交错排布的元素最后必然只会保留一种颜色。
4、根据 $3$ 可以得到一个贪心:将所有颜色按照出现次数从大到小排序。一开始预处理出所有颜色第一次出现的位置 $s_i$ 和最后一次出现的位置 $t_i$,那么不难看出要把 $[s_i,t_i]$ 之间的元素都涂成当前颜色。不难知道这样是最优的。
然后实现上遇上了一点小阻碍。大概就是说随着不停地染色,可能会有一些别的颜色被染成当前颜色,这样就要动态更新当前颜色的 $s_i$ 和 $t_i$ 。然后就因为觉得这个不好维护就摸了一会儿…结果发现其实是很好维护的。具体来说,从大到小做一定可以让每个点至多被染一次色,复杂度可以保证;同时发现 $[s_i,t_i]$ 分别满足单调性,就可以暴力 `while` 做了。
最后复杂度显然排序外线性。
```cpp
int ans ;
int cnt ;
int n, q ;
int buc[N] ;
int fst[N] ;
int lst[N] ;
int vis[N] ;
int base[N] ;
pint ord[N] ;
vint pos[N] ;
#define m_k make_pair
bool comp(pint a, pint b){
return a.fr == b.fr ? a.sc < b.sc : a.fr > b.fr ;
}
int main(){
cin >> n >> q ; int x, y ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr(), buc[base[i]] ++ ;
for (int i = 1 ; i <= n ; ++ i)
pos[base[i]].push_back(i) ;
for (int i = 1 ; i <= n ; ++ i)
if (!fst[base[i]]) fst[base[i]] = i ;
for (int i = n ; i >= 1 ; -- i)
if (!lst[base[i]]) lst[base[i]] = i ;
for (int i = 1 ; i <= 200000 ; ++ i)
if (buc[i]) ord[++ cnt] = m_k(buc[i], i) ;
sort(ord + 1, ord + cnt + 1, comp) ;
for (int i = 1 ; i <= cnt ; ++ i){
x = ord[i].fr ; y = ord[i].sc ;
if (vis[y]) continue ; vis[y] = 1 ;
if (x == lst[y] - fst[y] + 1) continue ;
int l = fst[y], r = lst[y] ;
for (int p = fst[y] ; p <= lst[y] ; ++ p){
// printf("%d ", p) ;
if (base[p] != y && !vis[base[p]]){
vis[base[p]] = 1 ;
// printf("%d ", base[p]) ;
for (auto k : pos[base[p]]){
chkmin(l, k) ;
chkmax(r, k) ;
base[k] = y, ++ ans ;
}
}
// puts("") ;
}
// printf("%d %d\n", l, r) ;
while (1){
int tl, tr ;
// printf("%d %d\n", l, r) ;
tl = fst[y], tr = lst[y] ;
if (l == fst[y] && r == lst[y]) break ;
fst[y] = l, lst[y] = r ;
for (int p = tl - 1 ; p >= l ; -- p){
// printf("(%d %d %d)", p, base[p], vis[base[p]]) ;
if (base[p] != y && !vis[base[p]]){
vis[base[p]] = 1 ;
// printf("%d ", base[p]) ;
for (auto k : pos[base[p]]){
chkmin(l, k) ;
chkmax(r, k) ;
base[k] = y, ++ ans ;
}
}
// puts("") ;
}
for (int p = tr + 1 ; p <= r ; ++ p){
if (base[p] != y && !vis[base[p]]){
vis[base[p]] = 1 ;
for (auto k : pos[base[p]]){
chkmin(l, k) ;
chkmax(r, k) ;
base[k] = y, ++ ans ;
}
}
}
}
// debug(base, 1, n) ;
// printf("%d %d %d %d %d\n", x, y, fst[y], lst[y], ans) ;
}
printf("%d\n", ans) ;
return 0 ;
}
```
把最后一个 for 里 if 的 `y` 写成了 `x` 导致 `Wa On 7` 呜呜呜。
#