codeforces 215 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A:要满足题目的条件,其实就是重复着放就可以了,所以x,y,z的个数不能相差太远,两个种类的字母的个数不能大于等于2,如果单词长度小于等于2,直接yes,所以问题转化为怎么计算一个区间内xyz的个数,用线段树或者树状数组

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 100010

struct SegTree{
int l,r,mid;
int cntx,cnty,cntz;
SegTree(){}
SegTree(int __l,int __r){
l = __l; r = __r; mid = (l+r)>>1;
cntx = cnty = cntz = 0;
}
}t[N<<2];

char text[N];
int n,m;

void PushUp(int rt){
t[rt].cntx = t[lson(rt)].cntx + t[rson(rt)].cntx;
t[rt].cnty = t[lson(rt)].cnty + t[rson(rt)].cnty;
t[rt].cntz = t[lson(rt)].cntz + t[rson(rt)].cntz;
}

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b){
if(text[a] == 'x') t[rt].cntx = 1;
else if(text[a] == 'y') t[rt].cnty = 1;
else t[rt].cntz = 1;
return ;
}
int mid = t[rt].mid;
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
PushUp(rt);
}

SegTree query(int rt,int a,int b){
if(t[rt].l == a && t[rt].r == b)
return t[rt];
int mid = t[rt].mid;
if(b <= mid) return query(lson(rt),a,b);
else if(a > mid) return query(rson(rt),a,b);
else{
SegTree res1 = query(lson(rt),a,mid);
SegTree res2 = query(rson(rt),mid+1,b);
SegTree res3 = SegTree(a,b);
res3.cntx = res1.cntx + res2.cntx;
res3.cnty = res1.cnty + res2.cnty;
res3.cntz = res1.cntz + res2.cntz;
return res3;
}
}

bool check(int cntx,int cnty,int cntz){
if(abs(cntx - cnty) >= 2) return false;
if(abs(cntx - cntz) >= 2) return false;
if(abs(cnty - cntz) >= 2) return false;

return true;
}

int main(){
while(scanf("%s",text)!=EOF){
n = strlen(text);
build(1,0,n-1);
scanf("%d",&m);
while(m--){
int l,r;
scanf("%d%d",&l,&r);
if(r-l+1 < 3){
puts("YES"); continue;
}
l--; r--;
SegTree res = query(1,l,r);
if(check(res.cntx,res.cnty,res.cntz))
puts("YES");
else
puts("NO");
}
}
return 0;
}
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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 100010
#define lowbit(i) ((i)&(-i))

char text[N];
int n,m;
int sum[3][N];

void add(int id,int pos){
while(pos <= n){
sum[id][pos]++;
pos += lowbit(pos);
}
}

int query(int id,int pos){
if(pos == 0) return 0;
int res = 0;
while(pos){
res += sum[id][pos];
pos -= lowbit(pos);
}
return res;
}

bool check(int *cnt){
for(int i = 0; i < 3; i++)
for(int j=i+1; j < 3; j++)
if(abs(cnt[i]-cnt[j]) >= 2)
return false;
return true;
}

int main(){
while(scanf("%s",text)!=EOF){
n = strlen(text);
cl(sum,0);
for(int i = 0 ; i < n; i++){
if(text[i] == 'x') add(0,i+1);
else if(text[i] == 'y') add(1,i+1);
else add(2,i+1);
}
scanf("%d",&m);
while(m--){
int l,r,cnt[3];
scanf("%d%d",&l,&r);
if(r-l+1 < 3){
puts("YES"); continue;
}
for(int i = 0 ; i < 3; i++)
cnt[i] = query(i,r) - query(i,l-1);

if(check(cnt)) puts("YES");
else puts("NO");
}
}
return 0;
}
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
def check(cnt):
for i in range(3):
for j in range(i+1,3):
if abs(cnt[i] - cnt[j]) >= 2:
return False
return True

string = raw_input()
length = len(string)
color = [[0]*100010 for _ in range(3)]
count = [[0]*100010 for _ in range(3)]
pos = int(0)
for x in string:
pos += 1
if x == 'x':
color[0][pos] = 1
elif x == 'y':
color[1][pos] = 1
else:
color[2][pos] = 1
for i in range(3):
for k in range(1,length+1):
count[i][k] = count[i][k-1] + color[i][k]
Q = int(raw_input())
for q in range(Q):
l,r = map(int,raw_input().split())
if r-l+1 < 3:
print "YES"
continue
cnt = [0,0,0]
for i in range(3):
cnt[i] = count[i][r] - count[i][l-1]
if check(cnt) == True:
print "YES"
else:
print "NO"

B:其实就是统计B中每个数字有多少个,然后在A中去找。找的时候我是把A分成了P个系列,意思就是

第1个系列:a[1],a[1+p],a[1+2p]…..

第2个序列:a[2],a[2+p],a[2+2p]….

第p个系列:a[p],a[2p],a[3p]

这样分是因为对于一个系列,我们可以较快地统计出来,因为在一个系列里我们先拿了m项,然后统计,然后删除一个头添加一个尾,这样就可以一直推下去,这样整个A序列中每个元素也只能被操作一次。

至于统计,A中的数字如果在B中就+1,消掉了就减1,没有的话就忽略,但是还有些细节就不说了。最后的答案记得排序再输出。一开始纯手写,比较长,跑得还可以,后来用map写,代码短了,速度稍慢些,只贴出map的代码

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 200010

map<int,int>mapA,mapB;
int n,m,p,A[N],B[N];
vector<int>ANS;

int main(){
while(scanf("%d%d%d",&n,&m,&p)!=EOF){
mapB.clear();
for(int i = 1; i <= n; i++)
scanf("%d",&A[i]);
for(int i = 1; i <= m; i++)
scanf("%d",&B[i]);
for(int i = 1; i <= m; i++)
mapB[B[i]]++;

ANS.clear();
for(int x = 1; x <= p; x++){
LL temp = (LL)x + (LL)(m-1)*(LL)p;
if(temp > (LL)n) break;
int val = 0,front = x,rear = x+(m-1)*p;
mapA.clear();
for(int i = front; i <= rear; i+=p){
if(mapB.find(A[i]) == mapB.end()) continue;
if(mapA[A[i]] < mapB[A[i]]) val++;
mapA[A[i]]++;
}
if(val == m) ANS.pb(front);
while(true){
int key;
key = A[front]; front += p;
if(mapB.find(key) != mapB.end()){
if(mapA[key] <= mapB[key]) val--;
mapA[key]--;
}
rear += p;
if(rear > n) break;
key = A[rear];
if(mapB.find(key) != mapB.end()){
if(mapA[key] < mapB[key]) val++;
mapA[key]++;
}
if(val == m) ANS.pb(front);
}
}
sort(ANS.begin() , ANS.end());
printf("%d\n",ANS.size());
//if(ANS.size() == 0) continue;
for(int i = 0; i < ANS.size(); i++)
printf("%d ",ANS[i]);
puts("");
}
return 0;
}