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