ABC048

[ABC048A] AtCoder *** Contest

题面翻译

输入三个字符串，求这三个字符串的首字母并输出。

翻译提供者：一条小鱼

题目描述

すぬけ君は、AtCoder $ s $ Contest という名前のコンテストを開こうとしています。ここで、$ s $ は長さ $ 1 $ 以上の文字列であり、$ 1 $ 文字目は英大文字、$ 2 $ 文字目以降は英小文字です。

すぬけ君は、このコンテストの略称を A$ x $C に決めました。ここで、$ x $ は $ s $ の先頭の英大文字です。

コンテストの名前が与えられるので、コンテストの略称を出力してください。

输入格式

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

AtCoder $ s $ Contest

输出格式

コンテストの略称を出力せよ。

样例 #1

样例输入 #1
AtCoder Beginner Contest
样例输出 #1
ABC
样例 #2

样例输入 #2
AtCoder Snuke Contest
样例输出 #2
ASC
样例 #3

样例输入 #3
AtCoder X Contest
样例输出 #3
AXC
提示

制約

$ s $ の長さは $ 1 $ 以上 $ 100 $ 以下である。

$ s $ の $ 1 $ 文字目は英大文字である。

$ s $ の $ 2 $ 文字目以降は英小文字である。

Sample Explanation 1

今あなたが参加しているコンテストです。

Sample Explanation 2

このコンテストは存在しません。

思路

直接模拟即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
ll b[MAXN];
int main(){
    ios::sync_with_stdio(false);
    string s1,s2,s;cin>>s1>>s>>s2;
    if('a'<=s[0]&&s[0]<='z'){
        s[0]=s[0]-32;
    }
    cout<<"A"<<s[0]<<"C";
    return 0;
}

[ABC048B] Between a and b ...

题面翻译

题目描述

给出两个非负整数a，b（a≤b）和一个正整数x。请在 a 以上 b 以下（包含a，b）的整数中，找出可被 x 整除的数数量。

输入输出格式

输入格式：

三个数，a b x

输出格式：

一行，一个整数，在 a 以上 b 以下（包含a，b）的整数中可被 x 整除的数数量。

输入输出样例

输入样例#1: 4 8 2
输出样例#1: 3

输入样例#2: 0 5 1
输出样例#2: 6

输入样例#3: 9 9 2
输出样例#3: (无)

输入样例#4: 1 1000000000000000000 3 输出样例#4: 333333333333333333

数据范围：

0 ≤ a ≤ b ≤ 10^18 1 ≤ x ≤ 10^18

样例说明1:

4 6 8 可以

样例说明2:

0 1 2 3 4 5 可以

样例说明3:

没有能被2整除的

样例说明4:

请注意溢出

感谢@2x6_81和 @曾熠辰提供的翻译

题目描述

非負の整数 $ a $, $ b $ ($ a < = b $) と、正の整数 $ x $ が与えられます。 $ a $ 以上 $ b $ 以下の整数のうち、$ x $ で割り切れるものの個数を求めてください。

输入格式

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

$ a $ $ b $ $ x $

输出格式

$ a $ 以上 $ b $ 以下の整数のうち、$ x $ で割り切れるものの個数を出力せよ。

样例 #1

样例输入 #1
4 8 2
样例输出 #1
3
样例 #2

样例输入 #2
0 5 1
样例输出 #2
6
样例 #3

样例输入 #3
9 9 2
样例输出 #3
0
样例 #4

样例输入 #4
1 1000000000000000000 3
样例输出 #4
333333333333333333
提示

制約

$ 0 < = a < = b < = 10^{18} $

$ 1 < = x < = 10^{18} $

Sample Explanation 1

$ 4 $ 以上 $ 8 $ 以下の整数のうち $ 2 $ で割り切れるものは、$ 4 $, $ 6 $, $ 8 $ です。

Sample Explanation 2

$ 0 $ 以上 $ 5 $ 以下の整数のうち $ 1 $ で割り切れるものは、$ 0 $, $ 1 $, $ 2 $, $ 3 $, $ 4 $, $ 5 $ です。

Sample Explanation 3

$ 9 $ 以上 $ 9 $ 以下の整数のうち $ 2 $ で割り切れるものはありません。

Sample Explanation 4

オーバーフローに注意してください。

思路

数据范围很大，所以肯定不能暴力枚举。

我们只需要找到最小的大于$a$的数，同时也是$x$的倍数，最大的小于$b$的数，同时也是$x$的倍数。

然后简单算一下即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
int main(){
    ios::sync_with_stdio(false);
    ll a,b,x;cin>>a>>b>>x;
    ll ans1=(a/x+(a%x==0?0:1))*x;
    ll ans2=(b/x)*x;
    ll ans=0;
    ans=(ans2-ans1)/x;
    cout<<ans+1;
    return 0;
}

[ABC048C] Boxes and Candies

题面翻译

$N$个箱子横排成一列，左边第$i$个箱子里装着$a_i$个糖果。

Snuke可以多次执行以下操作：

选一个里面不少于$1$个糖果的箱子，从那个箱子里吃一个糖果。

他的目标：

任何$2$个相邻的箱子都不多于$x$个糖果。

请确定实现他的目标所需的最小操作次数。

题目描述

$ N $ 個の箱が横一列に並んでいます。最初、左から $ i $ 番目の箱には $ a_i $ 個のキャンディが入っています。

すぬけ君は次の操作を好きな回数だけ行うことができます。

キャンディが $ 1 $ 個以上入っている箱をひとつ選び、その箱のキャンディを $ 1 $ 個食べる。

すぬけ君の目標は次の通りです。

どの隣り合う $ 2 $ つの箱を見ても、それらの箱に入っているキャンディの個数の総和が $ x $ 以下である。

目標を達成するために必要な操作回数の最小値を求めてください。

输入格式

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

$ N $ $ x $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

输出格式

目標を達成するために必要な操作回数の最小値を出力せよ。

样例 #1

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

样例输入 #2
6 1
1 6 1 2 0 4
样例输出 #2
11
样例 #3

样例输入 #3
5 9
3 1 4 1 5
样例输出 #3
0
样例 #4

样例输入 #4
2 0
5 5
样例输出 #4
10
提示

制約

$ 2 < = N < = 10^5 $

$ 0 < = a_i < = 10^9 $

$ 0 < = x < = 10^9 $

Sample Explanation 1

$ 2 $ 番目の箱のキャンディを $ 1 $ 個食べればよいです。すると、各箱のキャンディの個数は $ (2, 1, 2) $ となります。

Sample Explanation 2

たとえば、$ 2 $ 番目の箱のキャンディを $ 6 $ 個食べ、$ 4 $ 番目の箱のキャンディを $ 2 $ 個食べ、$ 6 $ 番目の箱のキャンディを $ 3 $ 個食べればよいです。すると、各箱キャンディの個数は $ (1, 0, 1, 0, 0, 1) $ となります。

Sample Explanation 3

最初から目標が達成されているので、操作を行う必要はありません。

Sample Explanation 4

すべてのキャンディを食べなければなりません。

思路

贪心题，和前一个盒子进行判断是否大于$x$，简单的模拟即可，注意一下当前盒子数目情况的判断。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
ll a[MAXN];
int main(){
    ios::sync_with_stdio(false);
    ll n,x;cin>>n>>x;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll ans=0;
    for(int i=2;i<=n;i++){
        if(a[i-1]+a[i]>x){
            ans+=(a[i-1]+a[i]-x);
            if(a[i]>=a[i-1]+a[i]-x){
                a[i]-=a[i-1]+a[i]-x;
            }
            else{
                a[i]=0;
            }
        }
    }
    cout<<ans;
    return 0;
}

[ABC048D] An Ordinary Game

题面翻译

给定一个长度大于等于3的字符串$S$,$S$中没有相邻的两个字符相等。

玩法:

玩家$1$和玩家$2$交替进行操作——从$S$中删除一个字符,但删除后$S$不能有相邻的两个字符相等,否则另一位玩家获胜(两人都很聪明)

现在玩家$1$先操作,请问谁可以获得胜利?

输入一个字符串$S$

若玩家$1$胜利,输出first;玩家$2$获胜,输出Second

题目描述

長さ $ 3 $ 以上の文字列 $ s $ があります。 $ s $ の中に同一の文字が隣り合う箇所はありません。

高橋君と青木君がゲームで勝負します。二人は交互に次の操作を行います。高橋君が先手です。

$ s $ から両端以外の文字をひとつ取り除く。ただし、その文字を取り除くことで、$ s $ の中に同一の文字が隣り合う箇所ができる場合、その文字を取り除くことはできない。

先に操作を行えなくなった人が負けです。二人が最適に行動したとき、どちらが勝つかを判定してください。

输入格式

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

$ s $

输出格式

先手の高橋君が勝つならば First を、後手の青木君が勝つならば Second を出力せよ。

样例 #1

样例输入 #1
aba
样例输出 #1
Second
样例 #2

样例输入 #2
abc
样例输出 #2
First
样例 #3

样例输入 #3
abcab
样例输出 #3
First
提示

制約

$ 3 < = |s| < = 10^5 $

$ s $ は英小文字のみからなる。

$ s $ の中に同一の文字が隣り合う箇所はない。

Sample Explanation 1

先手の高橋君は操作を行うことができません。なぜならば、$ s $ から両端以外の文字の b を取り除くと、$ s $ は aa となって a が隣り合うからです。

Sample Explanation 2

先手の高橋君が $ s $ から b を取り除くと、$ s $ は ac となります。すると、後手の青木君は操作を行うことができません。なぜならば、$ s $ には両端以外の文字が存在しないからです。

思路

应该是博弈论。

推导过程看这里：[题解 AT2153 【ARC064B] An Ordinary Game】 - 洛谷专栏 (luogu.com.cn)

我就直接贴代码了qwq

好的，我来补思路了uwu

其实从样例中可以比较明显地发现，结果与字符串的长度、首尾是否相同有关。

引用$DPair$大佬思路：

首先我们发现一个及其显然的结论：删除到无法删除时，字符串情况只可能是这样的：

\[ababababa···ababab\]

即字符串中出现且只出现两种不同的字符，并交替出现（或只剩两个，但也可以看作这种情况）。

字符不可能只有一个，否则就违背题意了，而且由于首尾不能被删除，因此最后至少剩下两个字符，即不可能出现只有一个字符的情况。

排除这种可能性后，只出现两种不同字符的原因在于，由于相邻字符保证不同，且我要保证我现在的状态是一个死局，那么字符串$s$中$s_{i-1}=s_{i+1}$，即所有奇数下标位置的字符相同，所有偶数下标位置的字符相同，且这两种字符不同。故只有两种字符，且奇偶交替出现。

然后我们发现，若字符串长度为奇数，则首尾下标都为奇数，故要使该状态成为死局必须保证首尾相同，反之，即首尾不同，则绝对安全，不可能死局，也就是必胜，那么对手也就必败（这一步好像是博弈论的一个经典思考环节）。所以当字符串长度为偶数且首尾不同时，我的下一步操作一定会使对手进入必胜态，那么我就必败（因为本游戏没有平局）。

首尾相同的情况也类似，只不过此时字符串长度为偶数时是安全的必胜态，奇数才为必败态。

因此当首尾相同且长度偶数或首尾不同且长度奇数时，先手必胜，反之后手必胜。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
int main(){
    ios::sync_with_stdio(false);
    string s;cin>>s;
    ll len=s.length();
    //ababababa
    if(s[0]==s[len-1]){
        if(len%2==1)cout<<"Second";
        else cout<<"First";
    }
    else{
        if(len%2==1)cout<<"First";
        else cout<<"Second";
    }
    return 0;
}