CTSC2017 密钥
题解
考虑环上问题的一般套路：把圆环拆开再复制一份，每次取一个大小为圆环长度的区间。
例如 (1,2,3,4)的圆环就可以拆开成[1,2,3,4,1,2,3,4]
然后拆开以后，每次枚举一个区间，以左端点为X，计算这个区间的答案。
这样就是一个很优秀的\(O(n^2)\)算法辣！
初步思考一下......
记录\(cnt_i\)为\(1..i\)中1的个数-0的个数。
那么左端点（为X的点）为l时，cnt[x]-cnt[l]就是从l到x（l不算） 1的个数-0的个数。
对于前两问，在这个区间里面cnt[x]-cnt[l]>0并且那个位置是1（1是A 0是B），那么那个A是强的。
对于第三问，在这个区间里面cnt[x]-cnt[l]<0并且那个位置是0（0是A 1是B），那么那个A是强的。
那么我们又得到了一个 很优秀的\(O(n^2)\)解法辣！
我们可以再记录一下一段区间内每个A点的cnt[x]出现的次数。
然后可以直接查找cnt大于/小于cnt[l]的A点个数。
然后我们就又得到了一个\(O(n^2)\)解法辣
这个查找我会树状数组优化！\(O(n\log n)\)但是还是过不了\(10^7\)的数据。
观察每次查找的cnt[l]相对上一次的差的和是\(O(n)\)的。
我们考虑如果我们知道 小于/大于X 的点数，需要加入/删除某一点或者将X+1/-1，这几个操作都能\(O(1)\)。
总复杂度\(O(n)\)
#include<cstdio>
#include<cstring>
#define debug(...) fprintf(stderr,__VA_ARGS__)
int p[40000009];
int seed, n, k, S;
int getrand()
{
seed = ((seed * 12321) ^ 9999) % 32768;
return seed;
}
void generateData()
{
scanf("%d%d%d",&k,&seed,&S);
int t = 0;
n = k * 2 + 1;
memset(p, 0, sizeof(p));
for (int i = 1; i <= n; i++)
{
p[i] = (getrand() / 128) % 2;
t += p[i];
}
int i = 1;
while (t > k)
{
while (p[i] == 0)
i++;
p[i] = 0;
t--;
}
while (t < k)
{
while (p[i] == 1)
i++;
p[i] = 1;
t++;
}
for(int i=1;i<=n;++i)p[i+n]=p[i];
}
int cnt[40000009],f[20000005],line,ans;
int fi[20000005],ians;
void add(int a,int b){
f[a]+=b;
if(a>line)ans+=b;
}
void iadd(int a,int b){
fi[a]+=b;
if(a<line)ians+=b;
}
int count(int a){
while(line<a){
ians+=fi[line];
ans-=f[++line];
}
while(a<line){
ans+=f[line];
ians-=fi[--line];
}
return ans;
}
int icount(int a){
while(line<a){
ians+=fi[line];
ans-=f[++line];
}
while(a<line){
ans+=f[line];
ians-=fi[--line];
}
return ians;
}
int main()
{
#ifdef cnyali_lk
freopen("cipher.in","r",stdin);
freopen("cipher.out","w",stdout);
#endif
generateData();
cnt[0]=10000000;
for(int i=1;i<=n+n;++i){
cnt[i]=cnt[i-1];
if(p[i])++cnt[i];
else --cnt[i];
}
line=10000000;
int ans1=0,ans2=0,ans3=0;
for(int i=1;i<n+n;++i){
if(p[i])
add(cnt[i],1);
else iadd(cnt[i],1);
if(i>=n){
if(p[i-n+1])add(cnt[i-n+1],-1);
else{
iadd(cnt[i-n+1],-1);
if(count(cnt[i-n+1])==0)ans1=(i-n+1);
if(count(cnt[i-n+1])==S)ans2=(i-n+1);
if(icount(cnt[i-n+1])==S)ans3=(i-n+1);
}
}
}
printf("%d\n%d\n%d\n",ans1,ans2,ans3);
return 0;
}