Codeforces ラウンド #277 (ディビジョン 2)_html/css_WEB-ITnose

A. 計算関数

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

正の整数 n の場合関数を定義しましょう f:

f(n)?=??-?1?+?2?-?3?+?..?+?(?-?1)nn

あなたのタスクは f を計算することです(n) 指定された整数 n の場合。

入力

単一行には正の整数 n (1?≤?n?≤?1015) が含まれます。

出力

Print f(n) in a単一行。

サンプル テスト

入力

出力

入力

出力

-3

注意

f(4)?=?? -?1?+?2?-?3?+?4?=?2

f(5)?=??-?1?+?2?-?3?+?4?-?5?= ??-?3

#include <iostream>#include <cstdio>#include <cstring>#include <stack>using namespace std;int main(){#ifdef xxz    freopen("in.txt","r",stdin);#endif // xxz long long n;    while(cin>>n)    {        long long sum = 0;        sum += n/2;        if(n%2) sum -= n;        cout<<sum<<endl;    }    return 0;}

マトリックスの B. OR

テストごとの時間制限

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

論理 OR を 2 つの論理値 (i. e.セット {0,?1} に属する値）。論理値の一方または両方が 1 に設定されている場合は 1 に等しく、そうでない場合は 0 です。同じ論理値で 3 つ以上の論理値の論理和を定義できます。マナー:

ここで、ai?=?1 の場合は 1 に等しく、そうでない場合は 0 に等しいです。

Nam には m 行と n 列で構成される行列 A があります。行には 1 から m までの番号が付けられ、列には 1 から n までの番号が付けられます。行 i (1?≤?i?≤?m)、列 j (1?≤?j?≤?n) の要素は Aij と表されます。 A のすべての要素は 0 または 1 です。Nam は行列 A から、次の式を使用して同じサイズの別の行列 B を作成します:

.

(Bij は行列 A の行 i と列 j のすべての要素の OR です)

Nam は行列 B を与え、行列 A を推測するように要求します。Nam は賢いですが、A のサイズが大きくなる可能性があるため、おそらく行列 B の計算中に間違いを犯す可能性があります。

入力

最初の行には 2 つの整数が含まれていますm と n (1?≤?m,?n?≤?100)、それぞれ行列の行数と列数です

次の m 行にはそれぞれ、行列 B の行を表すスペースで区切られた n 個の整数が含まれています (各要素B の値は 0 または 1)。

出力

最初の行で、Nam が B の計算を間違えた場合は「NO」を出力し、それ以外の場合は「YES」を出力します。最初の行が「YES」の場合、指定された行列 B を生成できる行列 A を表す n 個の整数で構成される mrows も出力します。複数の解がある場合は、いずれかを出力します。

サンプル テスト

入力

2 21 00 0

出力

NO

入力

2 31 1 11 1 1

出力

YES1 1 11 1 1

input

2 30 1 01 1 1

output

YES0 0 00 1 0

把A数组全部赋值为1，然后根据B数组再把A数组一些元素赋值为0，最后算A和B比较，注意如果开始把A全部初始化为0，很难算出来（稍微思考就知道了，如果全部赋值为0，那么1的时候你不知道把A的哪些赋值为1，就容易出错）

#include <functional>#include <algorithm>#include <iostream>#include <fstream>#include <sstream>#include <iomanip>#include <numeric>#include <cstring>#include <climits>#include <cassert>#include <complex>#include <cstdio>#include <string>#include <vector>#include <bitset>#include <queue>#include <stack>#include <cmath>#include <ctime>#include <list>#include <set>#include <map>using namespace std;int n , m;int g[1111][1111];int res[1111][1111];bool check_1(int row , int column){    int ok = 0;     for(int k = 0 ; k < n ; k ++)            ok |= res[row][k];    for(int k = 0 ; k < m ; k ++)            ok |= res[k][column] ;   if(ok) return true;    else return false;}int main(){    #ifdef xxz    freopen("in.txt","r",stdin);    #endif    while(~scanf("%d%d",&m,&n))    {        for(int i = 0 ; i < m ; i ++)        {            for(int j = 0 ; j < n ; j ++)            {                scanf("%d",&g[i][j]);            }        }        for(int i = 0 ; i < m ; i ++)        {            for(int j = 0 ; j < n ; j ++)            {                res[i][j] = 1;            }        }              for(int i = 0 ; i < m ; i ++)        {            for(int j = 0 ; j < n ; j ++)            {                if(g[i][j] == 0)                {                    for(int k = 0 ; k < n ; k ++)                        res[i][k] = 0;                    for(int k = 0 ; k < m ; k ++)                        res[k][j] = 0;                }            }        }        int flag1 = 0;        for(int i = 0 ; i < m ; i ++)        {            for(int j = 0 ; j < n ; j ++)            {                if(g[i][j] == 1)                {                    if(!check_1(i , j))                        flag1 = 1;                }                if(flag1)                    break;            }            if(flag1)                break;        }        if(flag1)            printf("NO\n");        else        {            printf("YES\n");            for(int i = 0  ; i < m  ; i ++)            {                for(int j = 0 ; j < n ; j ++)                {                    printf("%d%c",res[i][j], j == n - 1 ? '\n' : ' ');                }            }        }    }}

C. Palindrome Transformation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Nam is playing with a string on his computer. The string consists of n lowercase English letters. It is meaningless, so Nam decided to make the string more beautiful, that is to make it be a palindrome by using 4 arrow keys: left, right, up, down.

There is a cursor pointing at some symbol of the string. Suppose that cursor is at position i (1?≤?i?≤?n, the string uses 1-based indexing) now. Left and right arrow keys are used to move cursor around the string. The string is cyclic, that means that when Nam presses left arrow key, the cursor will move to position i?-?1 if i?>?1 or to the end of the string (i. e. position n) otherwise. The same holds when he presses the right arrow key (if i?=?n, the cursor appears at the beginning of the string).

When Nam presses up arrow key, the letter which the text cursor is pointing to will change to the next letter in English alphabet (assuming that alphabet is also cyclic, i. e. after 'z' follows 'a'). The same holds when he presses the down arrow key.

Initially, the text cursor is at position p.

Because Nam has a lot homework to do, he wants to complete this as fast as possible. Can you help him by calculating the minimum number of arrow keys presses to make the string to be a palindrome?

Input

The first line contains two space-separated integers n (1?≤?n?≤?105) and p (1?≤?p?≤?n), the length of Nam's string and the initial position of the text cursor.

The next line contains n lowercase characters of Nam's string.

Output

Print the minimum number of presses needed to change string into a palindrome.

Sample test(s)

input

8 3aeabcaez

output

Note

A string is a palindrome if it reads the same forward or reversed.

In the sample test, initial Nam's string is:  (cursor position is shown bold).

In optimal solution, Nam may do 6 following steps:

The result, , is now a palindrome.

只要考虑一半就行，然后判断一半的一半离pos是近还是远计算就行

#include <functional>#include <algorithm>#include <iostream>#include <fstream>#include <sstream>#include <iomanip>#include <numeric>#include <cstring>#include <climits>#include <cassert>#include <complex>#include <cstdio>#include <string>#include <vector>#include <bitset>#include <queue>#include <stack>#include <cmath>#include <ctime>#include <list>#include <set>#include <map>using namespace std;int n , pos;char s[100100];int main(){#ifdef xxz    freopen("in.txt","r",stdin);#endif    int T,Case = 0;;    while(cin>>n>>pos)    {      pos--;      cin>>s;      int len = strlen(s);      int l = 0,r = n/2 - 1;      if(n/2 <= pos) pos = n - pos-1;      while(l < n/2 && s[l] == s[n-1-l]) l++;      while(r >=0 && s[r] == s[n-1-r] ) r--;      int ans = 0;      for(int i = l; i <= r; i++)      {        int temp = abs(s[i] - s[n-1-i]);        ans += min(temp,26 - temp);      }      if(l < r)      {        ans += min(abs(pos - l), abs(r - pos)) + r- l;      }      else if(l == r)      {          ans += abs(pos - r);      }      cout<<ans<<endl;    }    return 0;}

D:

树形DP，目前还不会，等打完广州区域赛在学习下树形DP再补上