Codeforces Round #277(Div. 2) （A Calculating Function, B OR in Matrix, C Palindrome Transformation）

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 /*
  5  题意：计算f(n) = -1 + 2 -3 +4.....+（-1）^n *n的值    
  6  思路：偶数和 - 奇数和（或者用等差数列计算化简得到结果） 
  7 */
  8 #include<algorithm>
  9 #define N 10000
 10 using namespace std;
 11 
 12 int main(){
 13     long long n;
 14     cin>>n;
 15     if(n%2==0)  cout<<n/2<<endl;
 16     else cout<<(n-1)/2 - n<<endl;
 17     return 0;
 18 } 
 19 
 20 /*
 21 题意：给定B矩阵，判定能否通过A矩阵得到，如果能，打印出这样的A矩阵
 22     Bij = Ai1||Ai2....||Ain || A1j || A2j .....|| Amj
 23 思路：如果Bij == 0， 那么A矩阵的第i行和第j列的值都为0；
 24       然后检查Bij == 1的时候，那么A矩阵的第i行元素和第j列元素至少要一个1！ 
 25 */ 
 26 #include<iostream>
 27 #include<cstring>
 28 #include<cstdio>
 29 #include<algorithm>
 30 #define N 105
 31 using namespace std;
 32 
 33 int a[N][N];
 34 int b[N][N];
 35 int row[N], col[N];
 36 int main(){
 37     int n, m;
 38     cin>>n>>m;
 39     for(int i=1; i<=100; ++i)
 40         for(int j=1; j<=100; ++j)
 41             a[i][j] = 1;
 42     bool flag = true;
 43     for(int i=1; i<=n; ++i)
 44         for(int j=1; j<=m; ++j){
 45             cin>>b[i][j];
 46             if(b[i][j] == 0){
 47                 for(int k=1; k<=m; ++k)
 48                     a[i][k] = 0;
 49                 for(int k=1; k<=n; ++k)
 50                     a[k][j] = 0;
 51             }
 52         } 
 53     for(int i=1; flag && i<=n; ++i)
 54         for(int j=1; flag&& j<=m; ++j)
 55             if(b[i][j] == 1){
 56                 int k, h;
 57                 for(k=1; k<=m; ++k)
 58                     if(a[i][k]==1) break;
 59                 for(h=1; h<=n; ++h)
 60                       if(a[h][j] ==1 ) break;
 61                 if(k>m && h>n) flag = false;
 62             }
 63     if(flag){
 64         cout<<"YES"<<endl;
 65         for(int i=1; i<=n; ++i){
 66             cout<<a[i][1];
 67             for(int j=2; j<=m; ++j)
 68                 cout<<" "<<a[i][j];
 69               cout<<endl;
 70         } 
 71     }
 72     else cout<<"NO"<<endl;
 73     return 0;
 74 } 
 75 
 76 /*
 77 题意：从字符串的某一个位置开始，执行向左，向右的操作到达某一个字符的位置，
 78     通过向上，向下来完成字符的转换，知道字符串变成一个回文串为止！
 79     
 80 思路：贪心，在一半的区间完成这些操作一定是最少的（回文串是对称的，所以我们只考虑
 81       一半的区间是对的），并且最多转一次弯儿！ 
 82 */ 
 83 #include<iostream>
 84 #include<cstring>
 85 #include<cstdio>
 86 #include<algorithm>
 87 #define N 100005
 88 using namespace std;
 89 char str[N];
 90 int num;
 91 int main(){
 92     int n, p;
 93     cin>>n>>p;
 94     cin>>str+1;
 95     int len = n;
 96     if(p>len/2) p = len-p+1;
 97     int lx = N, rx = -1;
 98     for(int i=1; i<=len/2; ++i)//找到个需要更改字符区间 
 99         if(str[i] != str[len-i+1]){
100             num += min(abs(str[i]-str[len-i+1]), 'z'-max(str[i], str[len-i+1])+(min(str[i], str[len-i+1])-'a')+1);
101             if(lx > i) lx=i;
102             if(rx < i) rx=i;
103         }
104      
105     if(lx != N){
106         if(lx<=p && rx>=p){
107             int d1 = abs(rx-p);
108             int d2 = abs(lx-p);
109             if(d1>d2) num+=2*d2+d1;
110             else num+=2*d1+d2;
111         } 
112         else if(rx<=p)  num+=p-lx;
113         else if(lx>=p)  num+=rx-p; 
114         cout<<num<<endl;
115     } else cout<<0<<endl;
116     return 0;
117 }