【解题报告】Codeforces Round 597 (Div. 2)

【解题报告】Codeforces Round 597 (Div. 2)

真香警告.jpg……

A. Good ol’ Numbers Coloring

Source

看完样例就很显然了,切掉就好了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int read(){
int s = 0,ne = 1; char c = getchar();
for(;c<'0'||c>'9';c=getchar()) if(c == '-') ne = -1;
for(;c>='0'&&c<='9';c=getchar()) s = (s<<1)+(s<<3)+c-'0';
return s * ne;
}
int t,a,b;
int gcd(int a,int b){return !b ? a : gcd(b, a % b);}
int main()
{
t = read();
while(t--){
a = read(); b = read();
if(gcd(a,b) == 1) printf("Finite\n");
else printf("Infinite\n");
}
return 0;
}

B. Restricted RPS

Source

每步贪心,能干就干。

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int CN = 2e5+5;
int read(){
int s = 0,ne = 1; char c = getchar();
for(;c<'0'||c>'9';c=getchar()) if(c == '-') ne = -1;
for(;c>='0'&&c<='9';c=getchar()) s = (s<<1)+(s<<3)+c-'0';
return s * ne;
}
int t,n,s0,s1,s2,opt[CN],ans[CN]; bool bt[CN];
int main()
{
t = read();
while(t--){
n = read(); s1 = read(); s0 = read(); s2 = read();
for(int i=1;i<=n;i++){
char c; cin>>c;
if(c == 'P') opt[i] = 0;
if(c == 'R') opt[i] = 1;
if(c == 'S') opt[i] = 2;
}

memset(bt,0,sizeof(bt));
int cnt = 0;
for(int i=1;i<=n;i++){
if(!opt[i] && s2) bt[i] = true,s2--;
if(opt[i] == 1 && s0) bt[i] = true,s0--;
if(opt[i] == 2 && s1) bt[i] = true,s1--;
}
for(int i=1;i<=n;i++){
if(bt[i]) ans[i] = (opt[i] + 2) % 3,cnt++;
else{
if(s0) ans[i] = 0,s0--;
else if(s1) ans[i] = 1,s1--;
else if(s2) ans[i] = 2,s2--;
}
}

int vs = n / 2;
if(n % 2) vs += 1;
if(cnt >= vs){
printf("Yes\n");
for(int i=1;i<=n;i++){
if(!ans[i]) cout<<'P';
if(ans[i] == 1) cout<<'R';
if(ans[i] == 2) cout<<'S';
}
printf("\n");
}
else printf("No\n");
}
return 0;
}

C. Constanze’s Machine

Source

这题看上去还是比较有感觉的,只不过式子错了,这就很dl了(真香)。

首先显然可以把每个连续字段的方案数算出来然后再乘法原理,剩下的问题是求一个“连续字段”的方案数。

关于“连续字段”的方案,这个问题可以抽象成给你一段序列类似于“uuuuuu”这个样子,让你在其中划若干条长度为 2 的线,两两线不能相交,求方案数。那么显然这个东西可以设个状态写写方程,于是设 f[i] 表示考虑长度为 i 的序列的方案数。考虑新加入的这个元素,我们可以把它和元素 i-1 划成一段,方案数 f[i-2] ;也可以不划到任何一段,方案数 f[i-1] 。于是 f[i]=f[i-1]+f[i-2] ,又是 fibonacci 数列…然后做完了。

比赛的时候方程推成了 f[i]=f[i-1]+i-2 ,因为实际上我只考虑了划两段的情况…然后pretest9一直WA,自闭了,看来还是不够熟练…

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

#define LL long long

const int CN = 2e5+5;
const LL R = 1e9+7;

char ch[CN]; int n;
LL f[CN],ans = 1;

int main()
{
cin>>ch; n = strlen(ch);

f[1] = 1; f[2] = 2;
for(LL i=3;i<=n;i++) f[i] = (f[i-1] + f[i-2]) % R;

bool flag = true;
for(int i=0;i<n;i++) if(ch[i] == 'm' || ch[i] == 'w') flag = false;

if(!flag) printf("0");
else{
for(int i=0;i<n;i++){
if(ch[i] != 'n' && ch[i] != 'u') continue;
int p = i,l = 1;
while(p < n && ch[p] == ch[p+1]) p++,l++;
(ans *= f[l]) %= R;
i = p;
}
printf("%I64d",ans);
}

return 0;
}

D. Shichikuji and Power Grid

Source

第一眼没什么感觉,看了 tutorial 发现就是个 mst … 建一个虚点向每个点连边,表示建电站就好了,看来还是不够熟练…

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define LL long long

const int CN = 2010;

class fs{
public: int fr,to; LL di;
void init(int f,int t,LL d) {fr=f;to=t;di=d;}
bool operator < (const fs& a)const {return di < a.di;}
}E[CN * CN];
int ecnt = 0;
void add(int x,int y,LL z) {E[++ecnt].init(x,y,z);}
class ufs{
public: int fa[CN];
ufs() {for(int i=1;i<CN;i++) fa[i] = i;}
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
bool exm(int x,int y) {return find(x) != find(y);}
void merge(int x,int y) {fa[find(x)] = find(y);}
}ck;

int n,px[CN],py[CN],pc[CN],pk[CN];
int abs(int x) {return x<0 ? -x : x;}
int dist(int a,int b) {return abs(px[a] - px[b]) + abs(py[a] - py[b]);}

bool sel[CN * CN]; LL si = 0;
void MST(){
memset(sel,false,sizeof(sel));
sort(E+1,E+ecnt+1);
int cnt = 0;
for(int i=1;i<=ecnt;i++){
if(!ck.exm(E[i].fr, E[i].to)) continue;
ck.merge(E[i].fr, E[i].to);
cnt++; si += E[i].di; sel[i] = true;
if(cnt == n - 1) break;
}
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&px[i],&py[i]);
for(int i=1;i<=n;i++) scanf("%d",&pc[i]);
for(int i=1;i<=n;i++) scanf("%d",&pk[i]);

for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
add(i,j,1ll*(pk[i]+pk[j])*dist(i,j));
for(int i=1;i<=n;i++) add(i,n+1,pc[i]);
n += 1;

MST();

printf("%I64d\n",si);
int cnt = 0;
for(int i=1;i<=ecnt;i++) if(sel[i] && E[i].to == n) cnt++;
printf("%d\n",cnt);
for(int i=1;i<=ecnt;i++) if(sel[i] && E[i].to == n) printf("%d ",E[i].fr);
printf("\n");
cnt = n - 1 - cnt;
printf("%d\n",cnt);
for(int i=1;i<=ecnt;i++) if(sel[i] && E[i].to != n) printf("%d %d\n",E[i].fr,E[i].to);

return 0;
}

$$ - - - - \mathcal{End} - - - - $$


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×