CodeForces 786C Till I Collapse

左手的ㄟ右手 2021-11-02 00:20 179阅读 0赞

time limit per test2 seconds  
memory limit per test256 megabytes  
inputstandard input  
outputstandard output

## 解题思路 ##

### 无法AC的暴力 ###

从1到n枚举k，对于每一个k，从左到右贪心扫一遍序列，统计已有的颜色种类，如果种类数超过了就再分一组，将种类数置为1。扫完一遍就得到答案了。显然复杂度\\(O(n^2)\\)过不了。于是有了两个方向的优化——枚举k太多了，减少枚举k的次数，“加剪枝”；对于固定的k，扫一遍太多了，对于每一个k，不老老实实扫序列，而是在序列上“跳着扫”。

### 加剪枝 ###

剪枝是这样的——如果显然随着k的增加，答案是单调不下降的，所以如果\\(k==l\\)时和\\(k==r\\)时最少分组数量相同，即\\(ans\[l\]==ans\[r\]\\)，那么k取值在\\(\[l,r\]\\)之间时，最少分组数量也是相同的。仿佛活在梦里哦……

举个例子，输入的序列是自然数1 2 3 4 5 6 7 8 9 10，当\\(k==5\\)时，显然答案是2，当\\(k==9\\)时，显然答案也是2，那么当\\(k==6、k==7、k==8\\)时，答案不用算就是2。过于暴力。

然后枚举k的方法类似线段树划分区间，看看k在最大时和最小时相不相等，不相等就二分，看k在最小时和中间值时相不相等，以此类推……

复杂度不会分析，应该和序列的形态有关，还和二分方式有关。

对于下面给的代码，本机（CPU为i7-8565U）实测，当输入长度为十万的自然数序列时，耗时1.3s，但是CF评测姬快，所以可以AC。

### 跳着扫 ###

我们一步一步扫描序列时，当发现目前序列中颜色种数超过k，就分出新的一组。区间内的种数，然后联想到这题\[[SDOI2009\]HH的项链][SDOI2009_HH]（这篇博客貌似已经成为我的博客里被引用最多的一篇，当然只是自引），然后显然要在线做，于是单纯的权值线段树不够用了，上主席树，想到这篇[HDU 5919 Sequence ll][]，每次从当前点开始向后跳k个1(把第一次出现的置为1)，这样子每次不用扫描总共n步了，只用跳ans\[k\]步就好，然后我们知道ans\[k\]不是很大(意会)，所以跑得快。

时间复杂度嘛，我们扫k次，总共要跳\\(\\sum\_\{i=1\}^\{n\} ans\[i\]\\)次（[这篇博客][Link 1]说ans\[k\]总和大概是\\(n\\log n\\)级别），每次在主席树上找下一个点的复杂度是一个log，于是总的复杂度就是\\(O(n\\log ^2n)\\)。

我觉得这两种优化可以综合一下诶……

## 源代码 ##

使用了第一种优化

#include<stdio.h> #include<string.h> int n; int a[100010]; int b[100010];//桶 int ans[100010]; int f(int k) { memset(b,0,sizeof(b)); int cnt=1,id=b[a[1]]=1;//分组内的颜色数量和当前组编号 for(int i=1;i<=n;i++) { if(b[a[i]]==id) continue;//同一组中再次出现的颜色 b[a[i]]=id;//或者说之前分走了一组，这是新的一组，该组中第一次出现这个颜色 cnt++;//该组中颜色数量加一 if(cnt>k)//该分新的一组了 { b[a[i]]=++id; cnt=1; } } return id; } void solve(int kl,int kr) { ans[kl]=f(kl); ans[kr]=f(kr); if(ans[kl]==ans[kr]) { for(int i=kl+1;i<kr;i++) ans[i]=ans[kl]; return; } int mid=kl+kr>>1; solve(kl,mid); solve(mid+1,kr); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i); solve(1,n); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }

转载于:https://www.cnblogs.com/wawcac-blog/p/11272967.html

[SDOI2009_HH]: https://www.cnblogs.com/wawcac-blog/p/6901275.html
[HDU 5919 Sequence ll]: https://www.cnblogs.com/wawcac-blog/p/11250811.html
[Link 1]: https://blog.csdn.net/qq_39759315/article/details/88974718