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;
}