Codeforces Round #277 (Div. 2)

官方题解：http://codeforces.com/blog/entry/14678

A. Calculating Function

第3分钟AC，这手速也是拼了，虽然页面刷了1分多钟才刷出来。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,n,m,x,y,T,ans,big,cas;
19 bool flag;
20 int main()
21 {
22     LL n,ans;
23     scanf("%I64d",&n);
24     ans=n/2;
25     if (n%2) ans-=n;
26     printf("%I64d
",ans);
27     return 0;
28 }

View Code

B. OR in Matrix

对于m行n列的01矩阵A，构造相同规格的01矩阵B，对于第i行第j列，如果A矩阵中第i行或者第j列中存在有数字1，那么B中该位置也为1，现在给出B求A。

依然是手速题，显然B中如果有0的话，A中该行该列不可能有1，因此，一开始将A全设置为1，然后如果B中第i行第j列是0，就将A中第i行和第j列的元素全设为1。到最后对求得的A再检查一次，如果合法则输出YES，不合法输出NO。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,n,m,x,y,T,ans,big,cas,b[105][105],a[105][105];
19 bool flag;
20 int main()
21 {
22     scanf("%d%d",&n,&m);
23     memset(b,-1,sizeof(b));//为了memset方便，全设为-1，之后将-1看成1即可
24     for (i=1;i<=n;i++)
25     {
26         for (j=1;j<=m;j++)
27         {
28             scanf("%d",&a[i][j]);
29             if (a[i][j]==0)
30             {
31                 for (k=1;k<=n;k++)
32                 {
33                     b[k][j]=0;
34                 }
35                 for (k=1;k<=m;k++)
36                 {
37                     b[i][k]=0;
38                 }
39             }
40         }
41     }
42     for (i=1;i<=n;i++)
43     {
44         for (j=1;j<=m;j++)
45         {
46             if (a[i][j])
47             {
48                 flag=false;
49                 for (k=1;k<=n;k++)
50                 {
51                     if (b[k][j]!=0)
52                     {
53                         flag=true;
54                         break;
55                     }
56                 }
57                 if (!flag)
58                 {
59                     for (k=1;k<=m;k++)
60                     {
61                         if (b[i][k]!=0)
62                         {
63                             flag=true;
64                             break;
65                         }
66                     }
67                 }
68                 if (!flag)
69                 {
70                     printf("NO
");
71                     return 0;
72                 }
73             }
74         }
75     }
76                      
77     printf("YES
");
78     for (i=1;i<=n;i++)
79     {
80         for (j=1;j<m;j++)
81         {
82             printf("%d ",-b[i][j]);
83         }
84         printf("%d
",-b[i][m]);
85     }
86     return 0;
87 }

View Code

C. Palindrome Transformation

给出一串小写字母，再给一个指针，一开始指向第p个元素(输入中给p)，然后规定左右操作，分别为指针向左移一位和向右移一位，规定第一个元素向左是最后一个元素，最后一个元素向右是第一个元素。再规定上下操作，分别是将该位置的字母换为字母表中的上一位或者下一位，规定字母表也是循环的，即A的上一位是Z，Z的下一位是A。问至少需要多少步能将这串小写字母变成回文串。

贪心+分类讨论

其实不用模拟出指针的操作步骤。不妨假设p小于n/2(p在字符串的左半部分)，设st~ed为需要修改的范围(也就是，1~st-1和ed~n/2已经和右半部分对应位置相等了)。

如果指针p不在st~ed范围内，那么首先可能要移动p到st~ed范围内，再一个一个修改，（我们所说的修改就是将p位置的字符修改成字符串右半部分对应位置的字符，这比再将指针移到右半部分修改字符更优）。那么代价=修改字符的代价(题目中所说的上下操作次数)+ed-st+将p移动到st或者ed上的最小代价。

如果指针p在st~ed范围内，当我们修改完st~p的部分的时候肯定要回过头修改p+1~ed的部分，显然可以先将p移动到st或者ed上。代价的计算方法显然与上边相同，代价=修改字符的代价(题目中所说的上下操作次数)+ed-st+将p移动到st或者ed上的最小代价。

 1 /*MADE BY zhyfzy~~~~~~*/
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<set>
 8 #include<map>
 9 #include<stack>
10 #include<vector>
11 #include<queue>
12 #include<string>
13 #include<sstream>
14 #define eps 0.000001
15 #define ALL(x) x.begin(),x.end()
16 #define INS(x) inserter(x,x.begin())
17 using namespace std;
18 typedef long long LL;
19 int i,j,k,n,m,x,y,T,ans,big,cas,p,st,ed,st2,ed2;
20 bool flag;
21 char s[100005];
22 int main()
23 {
24     scanf("%d%d",&n,&p);
25     scanf("%s",s+1);
26     if (n==1)
27     {
28         printf("0
");
29         return 0;
30     }
31     m=(n+1)/2; 
32     ans=0;
33     st=1; ed=m;
34     for (i=1;i<=m;i++)
35         if (s[i]==s[n-i+1]) st++;
36         else break;
37     for (i=m;i>=1;i--)
38         if (s[i]==s[n-i+1]) ed--;
39         else break;
40     
41     if (st>m)
42     {
43         printf("0
");
44         return 0;
45     }
46     
47     for (i=1;i<=m;i++)
48     {
49         j=n-i+1;
50         ans+=min(abs((int)s[i]-(int)s[j]),26-abs((int)s[i]-(int)s[j]));
51     }
52     //cout<<ans<<endl;
53     st2=n-ed+1;
54     ed2=n-st+1;
55     if (n%2) 
56     {
57         ans+=ed-st;
58         if (p>m)
59         {
60             if (p>=st2&&p<=ed2) ans+=min(p-st2,ed2-p);
61             if (p<st2) ans+=st2-p;
62             if (p>ed2) ans+=p-ed2;
63         }
64         else
65         if (p<m) 
66         {
67             if (p>=st&&p<=ed) ans+=min(p-st,ed-p);
68             if (p<st) ans+=st-p;
69             if (p>ed) ans+=p-ed;
70         }else
71         if (p==m)
72         {
73             ans+=m-ed2;
74         }
75         printf("%d
",ans);
76     }else
77     {
78         ans+=ed-st;
79         if (p>m)
80         { 
81             if (p>=st2&&p<=ed2) ans+=min(p-st2,ed2-p);
82             if (p<st2) ans+=st2-p;
83             if (p>ed2) ans+=p-ed2;
84         }else
85         {
86             if (p>=st&&p<=ed) ans+=min(p-st,ed-p);
87             if (p<st) ans+=st-p;
88             if (p>ed) ans+=p-ed;
89         }
90         printf("%d
",ans);
91     }
92     
93     return 0;
94 }

View Code

D. Valid Sets

还没有更新

E. LIS of Sequence

还没有更新