Codeforces Good Bye 2016 题解

2016的最后一场CF,很遗憾昨天没能打这场比赛。只能在今天——2016年的最后一天补上这套题。话说这场比赛是我开始接触CF以来看到报名的人最多的一场比赛,意义特殊。。
从道题通过的人数来看八道题应该分成两个层次(这个跟平常的div1和div2差不多吧),前面四道题应该就是我这个水平做的,后面四道题做出来的人不超过200人,最后一道题做出来的人只有个位数。。。
下面就是前面四道题的题解啦

A

题意

大水题,数列求和,注意上限

代码

1
2
3
4
5
6
7
8
int main()
{
int n,k,i;
scanf("%d%d",&n,&k);
k=240-k;
for(i=1;k>=5*i&&i<=n;++i)k-=5*i;
printf("%d",i-1);![enter description here][1]
}

B

题意

将地球想象成一个均匀的球体,一个人从北极出发进行一次旅行,给出n个指令,每个指令包含行走的距离和行走的方向,判断旅行的旅行是否符合以下规则:1.在北极只能向南边走;2.在南极只能向北边走;3.最后要回到北极

题解

以北极为坐标原点模拟旅行过程,设置标记变量标记是否在南北极,在南北极的时候就不能向东西方向走,同时判断行走的坐标点是否会超过20000或者小于0

代码

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
void solve()
{
int o;
cin>>o;
int k,l,t=0;
string s;
l=1; //标记在不在南北两级
while(o--)
{
cin>>k>>s;
if(l)
{
if(s=="East"||s=="West")
{
cout<<"NO"<<endl;
return;
}
}
if(s=="North")
{
t-=k;
if(t<0)
{
cout<<"NO"<<endl;
return;
}
}
if(s=="South")
{
t+=k;
if(t>20000)
{
cout<<"NO"<<endl;
return;
}
}
if(t==0||t==20000)
l=1;
else
l=0;
}
if(t==0)
{
cout<<"YES"<<endl;
return;
}
else
cout<<"NO"<<endl;
}

同思路但十分简化的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 #include<cstdio>
int main()
{
int n,p=0,x;char s[10];
scanf("%d",&n);
while(n--)
{
scanf("%d%s",&x,s);
if(!p&&s[0]!='S')return 0*puts("NO");
if(p==20000&&s[0]!='N')return 0*puts("NO");
if(s[0]=='S')p+=x;
if(s[0]=='N')p-=x;
if(p<0||p>20000)return 0*puts("NO");
}
puts(p?"NO":"YES");
}

感想

  • 对于英文题目,一开始理解的时候可能存在一些问题,在看懂样例之后一定要回去看原文,根据原文中的信息去写代码

C

题目以Codeforce的rating制度为背景,根据积分将用户的段位分成两个div1和div2,给出一个人2016年以来每次打比赛之前的所处的段位和比赛后的分数变化,根据这些来判断这个人最后可能最高的分数,可能的答案有:无穷大,不可能的情况,具体的数字

题解

  • 模拟题,设置一个最大值和最小值的范围,根据每一句比赛所给的条件来更新这个范围,在div1则最小值一定在1900以上,在div2则最大值一定在1899以下,更新范围以后再模拟变化再一次更新范围
  • 如果整个过程中出现一次div2,则永远都不会是无穷大
  • 不可能情况的确定,最大值和最小值不符合实际

代码1(范围判断为最后结果的范围)

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

void solve()
{
int t,maxi=1<<30,mini=-1<<30,flag=1; //是否可能是最大值
cin>>t;
while(t--)
{
int x,y;
cin>>x>>y;
if(y==1&&mini<1900)mini=1900;
if(y==2&&maxi>1899)maxi=1899,flag=0;
mini+=x,maxi+=x;
}
if(flag)
{
cout<<"Infinity"<<endl;
return;
}
if(mini>maxi)
{
cout<<"Impossible"<<endl;
return;
}
cout<<maxi<<endl;
}

代码2(范围判断为一开始的范围)

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
#include <bits/stdc++.h>

using namespace std;

const int inf = (int) 1e9;

int main() {
int n;
scanf("%d", &n);
int from = -inf, to = inf;
int delta = 0; //变化的值
for (int i = 0; i < n; i++) {
int d, cur;
scanf("%d %d", &cur, &d);
if (d == 1) {
from = max(from, 1900 - delta);
} else {
to = min(to, 1899 - delta);
}
delta += cur;
}
if (from > to) {
puts("Impossible");
return 0;
}
if (to == inf) {
puts("Infinity");
return 0;
}
printf("%d\n", to + delta);
return 0;
}

D

题意

以烟花爆炸为背景,相当与在由单位正方形组成的一个平面里面生成一颗树,在分岔点一定会一分为二,从跟到分支给出的是”树“的每一段的长度,求占用的点数(一个单位正方形代表一个点,可以重复占用一个点)

题解

  • 模拟这个平面,使用dfs进行递归,计算占用的正方形的数量
  • dfs递归函数传入四个参数:位置坐标,当前递归层数,树枝伸展方向
  • 去除重复操作:使用数组标记递归函数的执行情况,四个参数对应四维数组
  • 貌似还可以用dp等方法做出来

代码

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
int dy[8]={1,1,0,-1,-1,-1,0,1},dx[8]={0,-1,-1,-1,0,1,1,1};

bool used[400][400][31][8]; //去除重复操作的标记数组
bool a[400][400];

int t,f[31],h; //记录总数

void dfs(int x,int y,int d,int l)
{
if(used[x][y][d][l])return;
used[x][y][d][l]=1;
if(d==h)
return;
int ix=x,iy=y;
for(int i=1;i<=f[d];i++)
{
ix+=dx[l];
iy+=dy[l];
if(!a[ix][iy])
t++;
a[ix][iy]=true;
}
dfs(ix,iy,d+1,(l+1)%8);
dfs(ix,iy,d+1,(l+7)%8);
}

void solve()
{
memset(a,0,sizeof(a));
cin>>h;
for(int i=0;i<h;i++)
cin>>f[i];
t=0;
dfs(200,200,0,0);
cout<<t<<endl;
}