Codeforces Round 277 Div.2 解题报告

A. Calculating Function

Problem Description

计算f(n):
f(n)=-1+2-3+..+(-1)^n*n

Solution

水题一个

源代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#include<string.h>
int main()
{

long long n;
while(scanf("%I64d",&n)!=EOF)
{
if(n%2==0)
{
printf("%I64d\n",n/2);
}
else printf("-%I64d\n",(n+1)/2);
}
}

B. OR in Matrix

Problem Description

给你一个01矩阵B,让你求是否有一个01矩阵A,若其中元素Aij==1,则其所在行列均置为1之后能得到矩阵B。若能,输出YES与矩阵A,否则输出NO。

Solution

先统计B的横行竖列的1的个数,若某元素这一列1的个数为m并且这一行1的个数为n,则在矩阵A中将这个元素所在的位置变为1。比赛中交的代码就是这个版本,结果二判判死了……
实际上少了一种情况,如下例所示:
3 3
1 0 1
0 0 1
1 1 1
这样应该是NO,但是程序跑出来的却是:
YES
0 0 0
0 0 0
0 0 1
解决方案是:利用生成的A在利用转变的规则生成一个C出来,将C与B进行比较,若全等,则输出YES和矩阵,否则NO。

源代码:

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
97
98
99
100
101
#include<stdio.h>
#include<string.h>
int main()
{

int maz[150][150],a[150],b[150],ma[150][150],mc[150][150];
int n,m;
int i,j,k;
int flag;
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(maz,0,sizeof(maz));
memset(ma,0,sizeof(ma));
memset(mc,0,sizeof(mc));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
flag=1;
for(i=1;i<=m;i++)
{
a[i]=0;
for(j=1;j<=n;j++)
{
scanf("%d",&maz[i][j]);
if(maz[i][j]==1)
{
a[i]++;
b[j]++;
flag=0;
}
}
}
/*for(i=1;i<=n;i++)
{
printf("%d ",b[i]);
}
printf("\n");
for(i=1;i<=m;i++)
{
printf("%d ",a[i]);
}
printf("\n");*/

for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(a[i]==n&&b[j]==m)
{
ma[i][j]=1;
flag=1;
}
}
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(ma[i][j]==1)
{
for(int ii=1;ii<=m;ii++)
{
mc[ii][j]=1;
}
for(int ii=1;ii<=n;ii++)
{
mc[i][ii]=1;
}
}
}
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(maz[i][j]!=mc[i][j])
{
flag=0;
}
}
}
if(flag==0)
{
printf("NO\n");
}
else
{
printf("YES\n");
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(j!=1)
{
printf(" ");
}
printf("%d",ma[i][j]);
}
printf("\n");
}
}
}
return 0;
}

C. Palindrome Transformation

Problem Description

利用规则生成回文串,求最少步数。

Solution

首先算出所需要按上下键的步数,之后在左半个串里面计算p与最左边maxl和最右边maxr需要改变的距离大小,选择小的加上maxr-maxl即为最终答案。貌似程序里有处p—,ans++写的没什么用处……

源代码:

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
#include<string.h>
#include<stdio.h>
#include<math.h>
int main()
{

int i,j,k;
int maxl,maxr;
char s1[50010],s2[50010],temp;
int len,p,num[50010],now,ans;
while(scanf("%d%d",&len,&p)!=EOF)
{
ans=0;
memset(num,0,sizeof(num));
scanf("%c",&temp);
for(i=1; i<=len/2; i++)
{
scanf("%c",&s1[i]);
}
for(i=len-len/2; i>0; i--)
{
scanf("%c",&s2[i]);
}
maxl=len/2+1;
maxr=0;
for(i=1; i<=len/2; i++)
{
if(s1[i]!=s2[i])
{
if(maxl>i)
{
maxl=i;
}
if(maxr<i)
{
maxr=i;
}
now=fabs(s1[i]-s2[i]);
if(now>13)
{
now=26-now;
}
num[i]=now;
ans+=now;
}
}
if(ans==0)
{
printf("0\n");
continue;
}
//printf("%d\n",ans);
if(len%2==1&&p==(len/2+1))
{
p--;
ans++;
}
else if(p>len/2)
{
p=len-p+1;
}
// printf("%d %d\n",maxl,maxr);
if(maxl-p>0)
{
ans+=maxr-p;
}
else if(maxl<=p&&maxr>=p)
{
if(p-maxl<maxr-p)
{
ans+=(maxr-maxl)+p-maxl;
// printf("-%d\n",ans);
}
else
{
ans+=(maxr-maxl)+maxr-p;
//printf("--%d\n",ans);
}
}
else if(p>maxr)
{
ans+=p-maxl;
}
printf("%d\n",ans);
}
return 0;
}

比赛过程中看到某人的A题写的非常屎于是重构了一下,发现可以hack,于是果断hack了一发,结果是我的代码重构错了……又减了50分……鉴于我之前已经掉到了浅绿,这次果断涨了240多分,不过还是差了4分才能蓝……