隐藏
「Codeforces Round 436 div2」本人的第三次cf酱油记 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「Codeforces Round 436 div2」本人的第三次cf酱油记

比赛题目

A. Fair Game

题目大意: A和B在玩一个游戏,每个人选一个数字,然后取走所有写有这个数字的卡牌,游戏是公平的定义为有一种方案使得A和B可以取走所有卡牌且使得A和B取走的数目相同。
题目分析: Hash判一下如果有两个不同的且个数相同即可判为YES。

B. Polycarp and Letters

题目大意: 一个字符串只有大小写字母,在一段不含有大写字母的区间内选出若干个互不相同的小写字母,问最多能选多少个。
题目分析: 从左往右扫一遍,每遇到小写字母加入Hash,遇到大写字母清空Hash并统计答案,最后再统计一遍答案即可。

C. Bus

题目大意: 有一个公交车在数轴上移动,不断地在$x=0$与$x=a$之间往返,从左移动到右或从右移动到左算做一次旅游,公交车满油时可以行驶$b$单位长度,在$x=0$、$x=a$间$x=f$处有一个加油站可以加满油,问完成$k$次旅游最少加多少次油。
题目分析: 模拟,判断下一次直接走到终点能不能再到达加油站,如果能直接走到终点,不能就走到加油站,特殊处理一下第$k-1$次旅游即可。

D. Make a Permutation!

题目大意: 给出一个序列,你可以修改一个位置的数变成任意数,问修改为一个排列最少需要几次修改。在满足该条件的情况下,构造字典序最小的方案。
题目分析: 判断重复了多少个即可得出最少修改多少次。字典序最小的方案需要首先满足排列最小,因此每一个数$x$至少有一个位置不会改变,否则修改次数就多了。维护指针$i$从左往右扫描位置,维护指针$j$从小往大扫描值,显然如果$i$位置的Hash>2,那么就要替换掉一个,$j$找到最小的Hash为0的点,考虑是否要将$i$位置替换为$j$。若$a_ij$或有标记,直接替换。

E. Fire

题目大意: 房子起火,你需要拯救$n$个物品,每个物品有三个属性:$t_i$拯救它所需要的时间,$d_i$拯救它的最晚时间,当总时间$\ge d_i$无论是否在拯救都记为拯救失败,$p_i$拯救它获得的价值,构造一个方案使价值最大。
题目分析: 对$t_i$排序后做一个背包即可。

F. Cities Excursions

题目大意: 没有看
题目分析: 不知道


比赛过程

首先拿到A题,读完题后速度搞定,瞬间get 488分。

A题代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,Hash[105],cnt=-1,tot=0,ans[105];
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)Hash[Get_Int()]++;
for(int i=1; i<=100; i++)
if(Hash[i]) {
if(cnt!=-1&&Hash[i]!=cnt) {
puts("NO");
return 0;
}
cnt=Hash[i];
tot++;
ans[tot]=i;
}
if(tot!=2) {
puts("NO");
return 0;
}
puts("YES");
for(int i=1; i<=tot; i++)printf("%d ",ans[i]);
return 0;
}

然后开始写B题,速度码过提交WA,改了一下还是WA。
why?原来是题意读错了,改了一下提交成功AC。

B题代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,sum=0,ans=0,Hash[505];
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
char x;
cin>>x;
if(x<='Z'&&x>='A') {
ans=max(ans,sum);
sum=0;
memset(Hash,0,sizeof(Hash));
continue;
}
Hash[x]++;
if(Hash[x]==1)sum++;
}
ans=max(ans,sum);
printf("%d\n",ans);
return 0;
}

接着看C题,感谢KEKE_046贡献题意,然后开始打模拟。
模拟讨论情况有点多,稍微有点复杂,需要调试一会儿。
achen似乎不怎么会写模拟,KEKE_046率先AC,接着是我,然后在KEKE_046的帮助下achen也AC了。

C题代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
long long a,Oil,Station,k,ans=0;
int main() {
a=Get_Int();
Oil=Get_Int();
Station=Get_Int();
k=Get_Int();
long long x=0,pos=0,bj=1,nowo=Oil;
while(x<k) {
if(x==k-1) {
if(bj==1) {
if(a-pos<=nowo) {
nowo-=a-pos;
pos=a;
bj=-1;
x++;
} else if(Station-pos<=nowo&&pos!=Station) {
pos=Station;
nowo=Oil;
ans++;
} else {
puts("-1");
return 0;
}
} else {
if(pos<=nowo) {
nowo-=pos;
pos=0;
bj=1;
x++;
} else if(pos-Station<=nowo&&pos!=Station) {
pos=Station;
nowo=Oil;
ans++;
} else {
puts("-1");
return 0;
}
}
} else {
if(bj==1) {
if(a-pos+a-Station<=nowo) {
nowo-=a-pos;
pos=a;
bj=-1;
x++;
} else if(Station-pos<=nowo&&pos!=Station) {
pos=Station;
nowo=Oil;
ans++;
} else {
puts("-1");
return 0;
}
} else {
if(pos+Station<=nowo) {
nowo-=pos;
pos=0;
bj=1;
x++;
} else if(pos-Station<=nowo&&pos!=Station) {
pos=Station;
nowo=Oil;
ans++;
} else {
puts("-1");
return 0;
}
}
}
}
printf("%I64d\n",ans);
return 0;
}

接着继续看D题,构成排列随便搞搞即可以了啊?
想着这题真水,然后就开始打代码了。
待到输出方案时发现要构造字典序最小,怎么搞?
随便yy了一个贪心交上去竟然A了。

D题代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,a[200005],Hash[200005],Ans[200005],bj[200005],ans=0;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
Hash[a[i]]++;
}
for(int i=1; i<=n; i++)
if(Hash[i])ans+=Hash[i]-1;
printf("%d\n",ans);
int j=1;
for(int i=1; i<=n; i++) {
if(Hash[a[i]]>1) {
while(Hash[j]!=0)j++;
if(j>a[i]&&!bj[a[i]]) {
bj[a[i]]=1;
Ans[i]=a[i];
continue;
}
Hash[j]++;
Hash[a[i]]--;
Ans[i]=j;
} else Ans[i]=a[i];
}
for(int i=1; i<=n; i++)printf("%d ",Ans[i]);
return 0;
}

KEKE_046在这道题调了很久,似乎错了几次。
在我的帮助下,achen、KEKE_046成功完成了D题,开始进攻E题。

E题第一眼不是一个背包吗,今天怎么这么水。
然后码好代码后提交,Wrong answer on pretest 3
wtf?噢,好像背包有后效性啊,和选择的顺序是有关系的。
怎么办呢?网络流?不行。贪心?好像可以吧,我用背包维护可以撤销决策的贪心,写起来很复杂而且还有反例,时间复杂度也高。

怎么搞啊?!!又随便yy了一个排序+背包,按照可以拯救它的最晚时间排序,然后做一个背包,提交后Wrong answer on pretest 3
wtf?这题怎么做啊。

比赛后一看别人的AC代码,不就是排序+背包吗?我怎么过不了?
仔细一看原来是我背包写错了,我写的二维背包不选$i$物品时居然没从$i-1$转移过来。。。

我就想说这两句话:

改成一维就过了。

E题代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
struct Thing {
int time,need,value,id;
bool operator < (const Thing& b) const {
return time<b.time||(time==b.time&&need<b.need)||(time==b.time&&need==b.need&&value>b.value);
}
} a[105];
int n,ans=0,f[2005],g[105][2005],tot=0,Ans[105],endx,endy;
void Output(int x,int y) {
if(x==0||y==0)return;
if(g[x][y]) {
Ans[x]=1;
tot++;
Output(x-1,y-a[x].need);
} else Output(x-1,y);
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i].need=Get_Int();
a[i].time=Get_Int();
a[i].value=Get_Int();
a[i].id=i;
}
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)
for(int j=a[i].time-1; j>=a[i].need; j--) {
if(f[j]<f[j-a[i].need]+a[i].value) {
f[j]=f[j-a[i].need]+a[i].value;
g[i][j]=1;
if(f[j]>ans) {
ans=f[j];
endx=i;
endy=j;
}
}
}
printf("%d\n",ans);
Output(endx,endy);
printf("%d\n",tot);
for(int i=1; i<=n; i++)
if(Ans[i])printf("%d ",a[i].id);
return 0;
}

这次比赛暴露了很多问题,比如背包都写不来了,水题想半天。
cf的题真的不难啊,究竟发生了什么让我们卡在了E题。。。

这是最后的情况:

成功变成蓝名!还是比较开心的。

姥爷们赏瓶冰阔落吧~