CTSC2017 密钥

题目

题解

考虑环上问题的一般套路:把圆环拆开再复制一份,每次取一个大小为圆环长度的区间。

例如 (1,2,3,4)的圆环就可以拆开成[1,2,3,4,1,2,3,4]

然后拆开以后,每次枚举一个区间,以左端点为X,计算这个区间的答案。

这样就是一个很优秀的O(n2)O(n^2)算法辣!

初步思考一下......

记录cnticnt_i1..i1..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(n2)O(n^2)解法辣!

我们可以再记录一下一段区间内每个A点的cnt[x]出现的次数。

然后可以直接查找cnt大于/小于cnt[l]的A点个数。

然后我们就又得到了一个O(n2)O(n^2)解法辣

这个查找我会树状数组优化!O(nlogn)O(n\log n)但是还是过不了10710^7的数据。

观察每次查找的cnt[l]相对上一次的差的和是O(n)O(n)的。

我们考虑如果我们知道 小于/大于X 的点数,需要加入/删除某一点或者将X+1/-1,这几个操作都能O(1)O(1)

总复杂度O(n)O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#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;
}
文章目录
  1. 1. 题解
|

博客使用Disqus作为评论系统