Codeforces Round #277 (Div. 2) 解题报告

题目地址：http://codeforces.com/contest/486

A题.Calculating Function

奇偶性判断，简单推导公式。

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     long long  n;
 9    cin>>n;
10     if(n%2==0) {
11         cout<<(-1)*((n-2)/2+1)+n<<endl;
12     } else
13         cout<<((n-1)/2+1)*(-1)<<endl;
14     
15     return 0;
16 }

B题.OR in Matrix

把必须为0的先填上，然后判断1的是否符合条件。若符合，让剩下的全为1输出，不符合就输出no。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 
 6 using namespace std;
 7 
 8 int n,m,
 9      a[110][110],b[110][110];
10 
11 void change(int x,int y)
12 {
13     for(int i=1;i<=n;i++) {
14         a[x][i]=0;
15     }
16     for(int j=1;j<=m;j++) {
17         a[j][y]=0;
18     }
19        
20 }
21 
22 int check(int x,int y)
23 {
24     for(int i=1;i<=n;i++) {
25      if(a[x][i]) return 1;
26     }
27     
28     for(int i=1;i<=m;i++) {
29         if(a[i][y]) return 1;
30     }
31     
32     return 0;
33 }
34 
35 int main()
36 {
37         memset(a,-1,sizeof(a));
38         
39         scanf("%d%d",&m,&n);
40         for(int i=1;i<=m;i++)
41             for(int j=1;j<=n;j++) {
42                 scanf("%d",&b[i][j]);
43                 if(!b[i][j]) {
44                     change(i,j);
45                 }
46             }
47         
48         for(int i=1;i<=m;i++)
49             for(int j=1;j<=n;j++) {
50                 if(b[i][j]) {
51                     if(check(i,j)) continue;
52                     printf("NO
");
53                     exit(0);
54                 }
55             }
56         
57         printf("YES
");
58         for(int i=1;i<=m;i++){
59             for(int j=1;j<=n;j++){
60             if(a[i][j]<0) printf("%d ",a[i][j]+2);
61                 else printf("%d ",a[i][j]);
62             }
63             printf("
");
64         }
65         
66     return 0;
67 }

C题.Palindrome Transformation

转化为回文串需要改动的最小步骤数。

只在P所在的那半侧改变。然后求出较小的移动的步数。累加。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<algorithm>
 5 
 6 const int N=1e5+3511;
 7 using namespace std;
 8 
 9 int main()
10 {
11     int i,n,p,len,ret=0,l,r;
12     char a[N];
13     
14     scanf("%d%d",&n,&p);
15     scanf("%s",a);
16     
17     p--;
18     if(p>=n/2) p=n-1-p; 
19     
20     l=n;r=-1;
21     for(int i=0;i<n/2;i++) {
22         if(a[i]!=a[n-1-i]) {
23             ret+=min(abs(a[i]-a[n-1-i]),26-abs(a[i]-a[n-1-i])); 
24             l=min(l,i);
25             r=max(r,i);
26         }    
27     } 
28    
29     if(l==n) {
30         printf("0
");
31         return 0;
32     }
33     
34     ret+=(r-l)+min(abs(l-p),abs(r-p));
35        
36     printf("%d
",ret);
37         
38     return 0;
39 }