ABC059

[ABC059A] Three-letter acronym

题面翻译

输入三个由小写英文字母组成的字符串，以大写字母的方式输出它们的首字母。

题目描述

英小文字からなる $ 3 $ つの単語 $ s_1 $, $ s_2 $, $ s_3 $ が空白区切りで与えられるので、単語の先頭の文字をつなげ、大文字にした略語を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ s_1 $ $ s_2 $ $ s_3 $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1
atcoder beginner contest
样例输出 #1
ABC
样例 #2

样例输入 #2
resident register number
样例输出 #2
RRN
样例 #3

样例输入 #3
k nearest neighbor
样例输出 #3
KNN
样例 #4

样例输入 #4
async layered coding
样例输出 #4
ALC
提示

制約

$ s_1 $, $ s_2 $, $ s_3 $ は英小文字からなる。

$ 1 ≦|s_i|≦ 10 (1≦i≦3) $

Sample Explanation 1

atcoder beginner contest の先頭の文字はそれぞれa b cなので、ABCが答えになります。

思路

为什么会写这道题解？因为经常忘了ASCII码大小写字母转换差32。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e11;
int main(){
    ios::sync_with_stdio(false);
    string s[4];
    for(int i=0;i<3;i++){
        cin>>s[i];
    }
    for(int i=0;i<3;i++){
        if('a'<=s[i][0]&&s[i][0]<='z')cout<<char(s[i][0]-32);
        else cout<<s[i][0];
    }
    return 0;
}

[ABC059B] Comparison

题面翻译

题目描述

给定两个正整数 $a, b$，比较他们的大小。

输入格式

输入有两行，第一行为数 $a$，第二行为数 $b$。

输出格式

如果 $a > b$，输出 "GREATER"；如果 $a = b$，输出 "EQUAL"，如果 $a < b$，输出 "LESS"。

数据范围

$1 \le a, b \le 10^{100}$，保证 $a, b$ 均无前导零。

题目描述

$ 2 $ つの正整数 $ A, B $ が与えられるので、その大小を比較してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ A $ $ B $

输出格式

$ A > B $ のときGREATER、$ A < B $ のときLESS、$ A=B $ のときEQUALと出力せよ。

样例 #1

样例输入 #1
36
24
样例输出 #1
GREATER
样例 #2

样例输入 #2
850
3777
样例输出 #2
LESS
样例 #3

样例输入 #3
9720246
22516266
样例输出 #3
LESS
样例 #4

样例输入 #4
123456789012345678901234567890
234567890123456789012345678901
样例输出 #4
LESS
提示

制約

$ 1≦A, B ≦ 10^{100} $

入力の $ A, B $ の先頭は0でない。

Sample Explanation 1

$ 36 > 24 $ なので、答えはGREATERです。

思路

这题还WA了两次。

注意字符串比较的是字典序，所以得看长度是否相等。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e11;
int main(){
    ios::sync_with_stdio(false);
    string a,b;cin>>a>>b;
    //长度相等，比较字典序。
    if(a.length()==b.length()){
        for(int i=0;i<a.length();i++){
            if(a[i]>b[i]){
                cout<<"GREATER";
                return 0;
            }
            if(b[i]>a[i]){
                cout<<"LESS";
                return 0;
            }
        }
        cout<<"EQUAL";
        return 0;
    }
    //否则直接比较字典序即可
    else if(a.length()>b.length())cout<<"GREATER";
    else cout<<"LESS";
    return 0;
}

[ABC059C] Sequence

题面翻译

给定一个长度为 $N$ 的序列 $A$，每次操作可以选择一个 $i$ 使得 $A_i$ 大小减 $1$ 或加 $1$。

记 $S_i = \sum\limits_{j = 1} ^ i A_j$，求最少的操作次数使得：

$\forall i \in [1, n], S_i \ne 0$

$\forall i \in [1, n - 1], S_i \times S_{i + 1} < 0$

题目描述

長さ $ N $ の数列があり、$ i $ 番目の数は $ a_i $ です。あなたは $ 1 $ 回の操作でどれか $ 1 $ つの項の値を $ 1 $ だけ増やすか減らすことができます。

以下の条件を満たすために必要な操作回数の最小値を求めてください。

すべての$ i (1≦i≦n) $ に対し、第 $ 1 $ 項から第 $ i $ 項までの和は $ 0 $ でない

すべての$ i (1≦i≦n-1) $ に対し、$ i $ 項までの和と $ i+1 $ 項までの和の符号が異なる

输入格式

入力は以下の形式で標準入力から与えられる。

$ n $ $ a_1 $ $ a_2 $ $ ... $ $ a_n $

输出格式

必要な操作回数の最小値を出力せよ。

样例 #1

样例输入 #1
4
1 -3 1 0
样例输出 #1
4
样例 #2

样例输入 #2
5
3 -6 4 -5 7
样例输出 #2
0
样例 #3

样例输入 #3
6
-1 4 3 2 -5 4
样例输出 #3
8
提示

制約

$ 2≦ n ≦ 10^5 $

$ |a_i| ≦ 10^9 $

$ a_i $ は整数

Sample Explanation 1

例えば、数列を $ 1, -2, 2, -2 $ に $ 4 $ 回の操作で変更することができます。この数列は $ 1, 2, 3, 4 $ 項までの和がそれぞれ $ 1, -1, 1, -1 $ であるため、条件を満たしています。

Sample Explanation 2

はじめから条件を満たしています。

思路

不难想到，有两种情况：

1、$+-+-+-······$

2、$-+-+-+······$

我们可以分别计算这两种情况，这里注意$+-$号代表的分别是$+1、-1$。如果是其他数字，那么代价只会更大，这个不难想到（其实就是贪心）。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=1e5+10;
const ll mod=1e9+7;
const ll INF=1e11;
ll a[MAXN],sum;
int main(){
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    ll ans1=0,ans2=0;
    
    //先讨论+-+-的情况
    for(int i=1;i<=n;i++){
        cin>>a[i];
        
        //这里直接用sum即可，没必要开前缀和数组，否则还得维护，更麻烦
        //sum这里其实只维护了a_i与a_i-1之间的关系，下面也一样
        sum+=a[i];
        
        //奇数位应该为+，但这里却是-
        if(sum<=0&&i%2){
            ans1-=sum-1;
            sum=1;
        }
        
        //偶数位应该为-，这里却为+
        else if(i%2==0&&sum>=0){
            ans1+=sum+1;
            sum=-1;
        }
    }
    sum=0;
    
    //再讨论-+-+的情况
    for(int i=1;i<=n;i++){
        sum+=a[i];
        
        //偶数位应该为+，这里却为-
        if(sum<=0&&i%2==0){
            ans2-=sum-1;
            sum=1;
        }
        
        //奇数位应该位-，这里却为+
        else if(sum>=0&&i%2){
            ans2+=sum+1;
            sum=-1;
        }
    }
    
    //选出两种方案中的最小情况
    cout<<min(ans1,ans2);
    return 0;
}

[ABC059D] Alice&Brown

题面翻译

大意：

现有两堆石子，Alice和Brown以此进行游戏，规则如下：

Alice先手，两方分别按照回合制取石子

每个人每回合可以任意从任一堆中取出2的倍数个石子（前提是该堆里有这么多石子），扔掉其中的一半，将另一半放入另一堆中。

当一方无法进行取石子操作时视作此方失败。

现给出石子数量n,m$(0≤n,m≤10^{18})$，请你输出胜方名称(Alice|Brown)。

题目描述

AliceとBrownはゲームをするのが好きです。今日は以下のゲームを思いつきました。

$ 2 $つの山があり、はじめに$ X, Y $個の石が置かれています。 AliceとBrownは毎ターン以下の操作を交互に行い、操作を行えなくなったプレイヤーは負けとなります。

片方の山から $ 2i $ 個の石を取り、そのうち $ i $ 個の石を捨て、残りの $ i $ 個の石をもう片方の山に置く。ここで、整数 $ i (1≦i) $ の値は山に十分な個数の石がある範囲で自由に選ぶことができる。

Aliceが先手で、二人とも最適にプレイすると仮定したとき、与えられた $ X, Y $ に対しどちらのプレイヤーが勝つか求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ X $ $ Y $

输出格式

Aliceが勝つときAliceと、Brownが勝つときBrownと出力せよ。

样例 #1

样例输入 #1
2 1
样例输出 #1
Brown
样例 #2

样例输入 #2
5 0
样例输出 #2
Alice
样例 #3

样例输入 #3
0 0
样例输出 #3
Brown
样例 #4

样例输入 #4
4 8
样例输出 #4
Alice
提示

制約

$ 0≦ X, Y ≦ 10^{18} $

Sample Explanation 1

Aliceは $ 2 $ 個石のある山から $ 2 $ 個取るしかありません。その結果、山の石の数はそれぞれ $ 0, 2 $ 個となり、Brownは $ 2 $ 個の石を取り、山の石の数はそれぞれ $ 1, 0 $ 個となります。 Aliceはこれ以上操作を行うことができないので、Brownの勝ちです。

思路

博弈论。

不难发现，当$n=0,m=0$或$n=1,m=0$或$n=0,m=1$或$n=1,m=1$时，也就是$abs(n-m)<=1$时，先手必输，~~于是这题就结束了~~。

分析一下$why$。我们假设$abs(n-m)\leq 1$时，先手先从第一堆中取出$2x$个石子。

于是$n'=n-2x,m'=m+x$，接下来轮到后手。

后手执行相同的操作，那么$n''=n'+x=n-x,m''=m'-2x=m-x$。发现还是$abs(m''-n'')\leq 1$.

这样一直持续下去，直到最基础的四种情况，所以先手必输。

那么$abs(n-m)> 1$呢？先手可以反客为主！先手可以很简单地将$abs(n-m)>1$转换为$abs(n-m)\leq1$.

所以原来的先手变成了后手，原来的后手变成了先手

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=1e5+10;
const ll mod=1e9+7;
const ll INF=1e11;
ll a[MAXN],sum;
int main(){
    ios::sync_with_stdio(false);
    ll a,b;cin>>a>>b;
    if(abs(a-b)<2)cout<<"Brown";
    else cout<<"Alice";
    return 0;
}