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

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

0%

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

发表于 更新于 分类于 Valine：

比赛题目

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题。。。

这是最后的情况：

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

相关文章
姥爷们赏瓶冰阔落吧~