「Codeforces Round 434 div2」本人的第一次cf酱油记 | Bill Yang's Blog
0%

「Codeforces Round 434 div2」本人的第一次cf酱油记

先写一份题解,然后再写一写我自己的情况。

比赛题目

A. k-rounding

题目大意: 给出两个整数$n$、$k$,求出最小的整数$x$使得$x$末尾有$k$个0,同时满足$n\mid x$。
题目分析: 暴力出奇迹啊,直接求个$n$与$10^k$的最小公倍数即可。


B. Which floor?

题目大意: 一栋楼有若干层,每层楼有若干房间,每层楼的房间数是相同的。房间与楼层都从1开始编号,房间对应的楼层随着房间编号的增加是单调不降的。现在给出一些房间所在的楼层,求出$n$所在的楼层,保证不矛盾且有解,若不唯一输出-1
题目分析: 枚举每层楼所含有的房间数,判定一下条件是否满足,注意一下边界(见代码)。


C. Did you mean…

题目大意: 给出一个字符串,要求将字符串拆成若干个字符串,满足要求:每一个字符串中不含有连续的3个辅音字母,若有连续的相同字母,不算做连续3个辅音字母。也就是说lll满足要求,$xl\quad llllll\quad x$满足要求,$xbb$不满足要求。有spj。
题目分析: 模拟,枚举起始位置$i$,枚举这一段的长度$j$,判断这一段是否满足要求,若满足要求,$j$++,否则分为一段。


D. Polycarp’s phone book

题目大意: 给出$n$个字符串,每个字符串长度为9,求出每个字符串中最短的自己独有的子串。(即其他串不含有该子串)。有spj。
题目分析: 什么啊,长度才9,随便乱搞啊。遍历每个串的所有子串,开个map保存该子串的RK-Hash出现次数。用Map1保存该串中这个子串的出现次数,用Map2保存所有串中这个子串的出现次数。最后枚举每个串的子串(长度从小枚举到大),若全局出现次数=本串出现次数,则说明该串是独有的,输出即可。


E. Tests Renumeration

题目大意: 读不懂。
题目分析: 不知道。


F. Wizard’s Tour

题目大意: 你可以通过飞机传送到一个图中的任意一个点,你可以每次必须走两条边,然后又通过飞机传送到任意一个点,要求走过的边不重复。输出最多可走的次数以及方案。
题目分析: 没仔细想,以后补档。(update 2017-09-20 Wizard’s Tour)


然后就到了振奋人心的吐槽时间了

比赛开始,首先打开A题,本人英语渣通过了2分钟的读题,确认了这是一道水题。然后我就分解算出了剩余的2和5的个数,补上去得到答案。最后发现其实求个lcm就可以了,没办法谁叫我垃圾,拿到723分。

A题代码(已通过final test)

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;
typedef long long LL;
inline const LL Get_Int() {
LL 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;
}
LL x,n,k,cnt2=0,cnt5=0;
int main() {
x=n=Get_Int();
k=Get_Int();
while(x%2==0) {
cnt2++;
x/=2;
}
x=n;
while(x%5==0) {
cnt5++;
x/=5;
}
LL remain2=max(k-cnt2,0ll),remain5=max(k-cnt5,0ll),sum=1;
for(int i=1; i<=remain5; i++)sum*=5;
printf("%I64d\n",(1<<remain2)*sum*n);
return 0;
}

然后就开始看第二题。题目没读得太懂,最后在神犇学弟huangziyue的帮助下读懂了题意。
“哎呀这不是水题吗?枚举个每层的房间数不就完了?”
仿佛遭到了稀神探女的毒奶,这题调了几乎1个小时始终Wrong answer on pretest 3
调到绝望,然后死亡,选择继续看第三道题。
看着看着题,题读懂了,正准备写,突然achen说:“快来做D题,这是水题。”
好的,D题确实分要多些,我选择D题。读完题,这个字符串长度才9,随便Hash,map乱搞一下不就可以过?写了大概10分钟提交1A。

D题代码(已通过final test)

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL 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;
map<LL,int>M1[70005],M2;
char s[70005][15];
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
scanf("%s",s[i]+1);
for(int j=1; j<=9; j++)
for(int k=1; k+j-1<=9; k++) {
LL sum=0;
for(int x=k; x<=k+j-1; x++)sum=sum*15+s[i][x]-'0'+1;
M1[i][sum]++;
M2[sum]++;
}
}
for(int i=1; i<=n; i++) {
bool bj=0;
for(int len=1; len<=9&&!bj; len++)
for(int k=1; k+len-1<=9&&!bj; k++) {
LL sum=0;
for(int x=k; x<=k+len-1; x++)sum=sum*15+s[i][x]-'0'+1;
if(M2[sum]-M1[i][sum]==0) {
bj=1;
for(int x=k; x<=k+len-1; x++)printf("%c",s[i][x]);
putchar('\n');
}
}
}
return 0;
}

AC pretest时有1536分,这波不错很稳。
比赛通知:“由于评测队列太长,比赛延时10分钟,评测队列将会很快完成。”
然后回去尝试攻克C题。读了下题,模拟啊?速度开始码代码,achen手速比较快就提前交了,然后WA,原来是题意理解错了。(感谢achen)
然后重新读了一下题意重新写了一份代码,交上去A了pretest,大概花了30分钟,AC时只剩下984分了。

C题代码(已通过final test)

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
#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;
}
bool Check(char x) {
if(x=='a'||x=='e'||x=='i'||x=='o'||x=='u')return false;
return true;
}
string s;
char tmp[3005];
int main() {
scanf("%s",tmp);
int len=strlen(tmp);
string s=tmp;
s=' '+s;
for(int i=1; i<=len;) {
bool bj=0;
for(int j=i+2; j<=len; j++)
if(Check(s[j])&&Check(s[j-1])&&Check(s[j-2])&&((s[j]!=s[j-1])||(s[j-1]!=s[j-2]))) {
for(int x=i; x<j; x++)putchar(s[x]);
putchar(' ');
i=j;
bj=1;
break;
}
if(bj==0) {
for(int j=i; j<=len; j++)putchar(s[j]);
break;
}
}
return 0;
}

最后我读了一下E题,并不能读懂,好的然后跟着achen、KEKE_046一起想F题。似乎不是特别难想,但是始终搞不明白题目想要求什么?大概思考了半个小时放弃了。
比赛通知:“因为技术原因,本次比赛不计rate,我们对此深感抱歉。”
什么玩意儿?打了这么久你就给我看这个?垃圾cf,毁我青春。

KEKE_046和Summer_Wang陆续离开了战场,再不回去宿管老师就要通报批评了,然而我、achen、huangziyue是走读完全不虚。
接着我们一直在想B题哪里错了,还和远在天边的hyc进行了交流,进展并不乐观。
距离比赛结束还有10分钟,突然achen瞬间想出了为什么一直WA,为什么呢?因为输出说明中写的是if it is possible to determine it in a unique way注意这里是it而不是them。意思是如果有多种方案但是$n$在同一个楼层,只记为一种方案。这就是语言习惯的问题了,我们不背锅。
发现这个问题后我立即改代码,然后在比赛结束前7分钟提交了。

B题代码(已通过final test)

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<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,m,a[105],b[105],Ans[105],cnt=0;
int main() {
n=Get_Int();
m=Get_Int();
if(m==0) {
if(n==1)puts("1");
else puts("-1");
return 0;
}
for(int i=1; i<=m; i++) {
a[i]=Get_Int();
b[i]=Get_Int();
if(a[i]==n) {
printf("%d\n",b[i]);
return 0;
}
}
for(int num=1; num<=100; num++) {
bool bj=1;
for(int j=1; j<=m; j++)
if((a[j]-1)/num+1!=b[j]) {
bj=0;
break;
}
if(bj&&(n-1)/num+1!=Ans[cnt])Ans[++cnt]=(n-1)/num+1;
}
if(cnt==1)printf("%d\n",Ans[1]);
else puts("-1");
return 0;
}

提交后我一看评测队列,哇整整30页!
过了1分钟变成了27页,再过一分钟变成了22页。
又过了1分钟怎么变成了24页?
这队列还是双端队列会后移?

等到比赛结束1分钟后我的B题成功通过了pretest。
而achen成功输出错了变量gg。(心疼achen)
曾经有个大神说过不打unrate的比赛,但是我们这样中途unrate是不是有点不好呢?
这场比赛告诉了我们,心态不好必定炸,英语不好必定炸,RP不好必定炸。

吐槽到此结束,滚回去等final test。
update:final test完成了,以下是我的成绩:

路漫漫其修远兮,还需继续努力啊!

姥爷们赏瓶冰阔落吧~