Codeforces 390 题解

这次Codeforces的A和B都是比较简单的,A就是贪心算法(我一开始在理解题意的时候出了一点问题),B就是蛮力枚举。
看懂题目的话我觉得每道题在20分钟之内将把代码写出来是没有问题的,可是英语还是硬伤,努力学英语中。。。

A

题意

给你一个数组要求将他们进行划分成连续的几个部分,要求每个部分部分不为0

题解

  • 无法划分的情况:数组中的各个都为0
  • 对于剩下的情况,我一开始就只是统一处理:分成两组,第一组从1到最后一个不为0的前面一位,剩下的部分组成第二组。但是后来发现这样做是对于数组总和为0的时候可以,对于数组总和不为0时就是不对的,因为可能有第一组都是0的情况,所以还是要分两种情况讨论
  • 数组总和不为0时,就分成一组
  • 数组总和为0是,分成两组:第一组从1到最后一个不为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
void solve()
{
int n;
while(cin >> n)
{
int sum=0,tag=1,u;
int a[101];
for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];
if(a[i]) //记录最后一个不为0的数字
{
u=i+1;
tag=0;
}
}
if(tag)
{
cout<<"NO"<<endl;
return ;
}
if(sum)
{
cout<<"YES"<<endl<<"1"<<endl<<"1"<<" "<<n<<endl;
return ;
}
else
{
cout<<"YES"<<endl<<"2"<<endl<<"1"<<" "<<u-1<<endl<<u<<" "<<n<<endl;
}
}
}

B

题意

题目以小时候玩的井字旗为背景,给出残局,让你求出其中一方是否可以走一步就获得胜利(棋盘大小4*4)

题解

  • 依次考虑每个空格,胜利有两种情况
  • 中间和两边中的一个棋子是自己的,另一个是空格
  • 两个自己的棋子夹一个空格

代码

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
char a[6][6];
char tl[2]={'x','o'};
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

bool judge(int x,int y,int nu)
{
for(int i=0;i<8;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(a[xx][yy]==tl[nu])
{
xx=x-dx[i];
yy=y-dy[i];
if(a[xx][yy]=='.')
return true;
}
if(a[xx][yy]=='.')
{
xx=xx+dx[i];
yy=yy+dy[i];
if(a[xx][yy]==tl[nu])
return true;
}
}
return false;
}

void solve()
{
int num1=0,num2=0;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
{
cin>>a[i][j];
if(a[i][j]=='x')
num1++;
if(a[i][j]=='o')
num2++;
}
for(int i=0;i<6;i++)
a[i][0]=a[0][i]=a[6][i]=a[i][6]='*';
int be=0;
if(num2<num1)
be=1;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
{
if(a[i][j]==tl[be]&&judge(i,j,be))
{
cout<<"YES"<<endl;
return;
}
}
cout<<"NO"<<endl;
return;
}

简洁的代码

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
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,-1,1,0,-1};
char s[10][10];
void check(int i,int j)
{
for(int k=0;k<8;k++)
{
if(s[i+dx[k]][j+dy[k]]=='x'&&s[i+dx[k]*2][j+dy[k]*2]=='x')
{
puts("YES");
exit(0);
}
if(s[i+dx[k]][j+dy[k]]=='x'&&s[i-dx[k]][j-dy[k]]=='x')
{
puts("YES");
exit(0);
}
}
}
int main()
{
for(int i=2;i<=5;i++)scanf("%s",s[i]+2);
for(int i=2;i<=5;i++)for(int j=2;j<=5;j++)if(s[i][j]=='.')check(i,j);
puts("NO");
return 0;
}

总结

  • 还是要多练,切水题的时间比较长,不能死在水题上面
  • 看题目不能靠翻译,要锻炼自己的英语水平