「找性质」 [Codeforces 1209G1] Into Blocks (easy version)

皎月半洒花

2020-06-16 21:28:46

Solution

感觉这个 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` 呜呜呜。 #