codeforces 207 div.1

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

A:n个骑士（1-n标号）比赛，有m个比赛记录，每个比赛记录的形式为L R winner 表示L到R标号内还没输的人比赛，胜者只有一个就是winner
例如 3 5 4 表示3,4,5比赛，4胜利，3和5都输了，退出
3 7 4 表示4,6,7比赛，4胜利，6和7都输了，退出
题目保证了数据是正确的不会出现矛盾，输出是，n个数字，ans[i]表示第i个骑士是被谁打败的，ans[1] = 5,1骑士是被5骑士打败的，最后胜利的人只有一个，ans[i] = 0
1.一开始ans初始化为0
2.把这些比赛从最后一个开始更新,对于L，R区间的ans值，全部更新为winner，但winner的ans值保持不变
3.依次更新到第1个比赛后，输出所有ans值即可
这样做的正确性就不解释了，还是很容易理解的，因为我的思路是用线段树，其实每个人的ans值是决定于最初的那些比赛的，但是倒过来更新，才方便使用线段树，线段树写了90行，不咋地

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#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 N 300010
#define M 300010

struct SegTree{
	int l,r,mid,len,color,lazy;
	SegTree(){}
	SegTree(int __l,int __r,int __color){
		l = __l; r = __r; color = __color;
		mid = (l+r)>>1; len = r-l+1; lazy = 0;
	}
}t[N<<2];
int n,m;
int L[M],R[M],winner[M];

void PushDown(int rt){
	if(t[rt].lazy == 0) return ;
	t[lson(rt)].color = t[rson(rt)].color = t[rt].color;
	t[lson(rt)].lazy = t[rson(rt)].lazy = 1;
	t[rt].lazy = 0;
}

void build(int rt,int a,int b){
	t[rt] = SegTree(a,b,0);
	if(a == b) return ;
	int mid = t[rt].mid;
	build(lson(rt),a,mid);
	build(rson(rt),mid+1,b);
}

void updata(int rt,int a,int b,int color){
	if(t[rt].l == a && t[rt].r == b){
		t[rt].color = color;
		t[rt].lazy = 1;
		return ;
	}
	PushDown(rt);
	int mid = t[rt].mid;
	if(b <= mid) updata(lson(rt),a,b,color);
	else if(a > mid) updata(rson(rt),a,b,color);
	else{
		updata(lson(rt),a,mid,color);
		updata(rson(rt),mid+1,b,color);
	}
}

void travel(int rt){
	if(t[rt].l == t[rt].r){
		printf("%d ",t[rt].color);
		return ;
	}
	PushDown(rt);
	int mid = t[rt].mid;
	travel(lson(rt));
	travel(rson(rt));
}

int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		build(1,1,n);
		for(int i = 0 ; i < m; i++)
			scanf("%d%d%d",&L[i],&R[i],&winner[i]);
		for(int i = m-1; i >= 0; i--){
			int a,b;
			a = L[i]; b = winner[i]-1;
			if(a <= b) updata(1,a,b,winner[i]);
			a = winner[i]+1; b = R[i];
			if(a <= b) updata(1,a,b,winner[i]);
		}
		travel(1);
		puts("");
	}
	return 0;
}

B.最后保证了两个短串a，b在翻倍后是更长的，把后来的长串称为S,T。求出lena和lenb的LCM，那么我们只需要知道LCM长度里面的匹配情况即可，后面的都是一样的周期。对于LCM的串，我们以GCD = (lena,lenb)的单位来分割两个串，这样做的结果是，不会出现一部分的分割是尾接着头的
例如 abcd ， 不会分割出 cda 这样的尾接着头的串，也就是原来的a和b串都能被完整地分割掉
例如
a = abcd
b = aabbcc
GCD = 2 , LCM = 12
ab cd ab cd ab cd
aa bb cc aa bb cc
分割的结果就是这样
那么对于a串，a[i]可以马上知道它位于一个GCD的单元的哪个位置，那就是 i % GCD
那么a和b串，只要a[i]和b[j]是位于GCD单元的同一个位置的话，他们就会对上，就能比较是否相同
所以，对于a串里面的a[i],位于GCD单元的pos位置，那么b串中位于pos位置的字符都会且仅会和a[i]对上一次
因为只有26个字母，所以我们可以记录GCD单元中pos位置上，26个字母分别有多少个，那么计算起来就很方便了

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

char a[N],b[N];
LL lena,lenb;
LL x,y,GCD,LCM;
LL mapb[N][26];

LL gcd(LL a,LL b){
	return b == 0LL ? a : gcd(b,a%b);
}
LL lcm(LL a,LL b){
	return a / gcd(a,b) * b;
}

int main(){
	while(scanf("%I64d%I64d",&x,&y)!=EOF){
		scanf("%s%s",a,b);
		lena = strlen(a);
		lenb = strlen(b);
		GCD = gcd(lena,lenb);
		LCM = lcm(lena,lenb);
		cl(mapb,0);
		for(int i = 0; i < lenb; i++){
			int pos = i % GCD;
			mapb[pos][b[i]-'a']++;
		}
		LL sum = 0LL;
		for(int i = 0; i < lena; i++){
			int pos = i % GCD;
			sum += (lenb/GCD - mapb[pos][a[i]-'a']);
		}
		sum *= (lena * x / LCM);
		printf("%I64d\n",sum);
	}
	return 0;
}