ABC046

[ABC046A] AtCoDeerくんとペンキ

题面翻译

题目描述：

AtCoDeer先生最近买了三个油漆罐。两天前他买的那一种颜色是A，他昨天买的颜色是B，他今天买的颜色是C。每个颜料的颜色可以用1到100之间的正整数来表示。

由于AtCoDeer先生出生健忘村，AtCoDeer先生可能买了一个以上的油漆罐颜色相同。计算这些油漆罐的不同颜色的数量并告诉AtCoDeer先生。

范围：

1<=(a,b,c)<=100

输入格式：三个正整数a,b,c

输出格式：一个正整数，表示不同颜色数量

题目描述

シカのAtCoDeerくんはペンキをこれまでに$ 3 $つ買いました。おととい買ったペンキの色は $ a $ , 昨日買ったペンキの色は $ b $ , 今日買ったペンキの色は $ c $ です。各ペンキの色は$ 1 $以上$ 100 $以下の整数で表されます。 AtCoDeerくんはわすれんぼうなため、同じ色のペンキを買ってしまっていることがあります。AtCoDeerくんが買ったペンキの色の種類の個数を教えてあげてください。

输入格式

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

$ a $ $ b $ $ c $

输出格式

AtCoDeerくんが買ったペンキの色の種類の個数を出力せよ。

样例 #1

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

样例输入 #2
3 3 33
样例输出 #2
2
提示

制約

$ 1≦a,b,c≦100 $

Sample Explanation 1

色 $ 1 $,$ 3 $,$ 4 $ の $ 3 $ 種類です。

Sample Explanation 2

色 $ 3 $,$ 33 $ の $ 2 $ 種類です。

思路

直接模拟即可，可以用map

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
map<int,int> m;
int main(){
    ios::sync_with_stdio(0);
    for(int i=0;i<3;i++){
        int x;cin>>x;
        if(m[x])continue;
        else m[x]++;
    }
    cout<<m.size();
    return 0;
}

[ABC046B] AtCoDeerくんとボール色塗り

题面翻译

你有N个球，K种颜料

你要把N个球涂上颜料，但是为了美观相邻的两个球不能是一样颜色的。

问有多少种涂色方法？

样例1：输入 2 2 输出 2 样例解释：只有01和10这两种涂色方法

样例2:输入 1 10 输出 10 样例解释：有0,1,2,3,4,5,6,7,8和9这些方法

感谢@RioBlu 提供的翻译

题目描述

シカのAtCoDeerくんは一列に並んだ $ N $ 個のボールをそれぞれ $ K $ 色のペンキの色のうちのどれかで塗ろうとしています。見栄えが悪くならないように、隣り合ったボールは別の色で塗ることにします。ボールの塗り方としてあり得るものの個数を求めてください。

输入格式

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

$ N $ $ K $

输出格式

ボールの塗り方としてあり得るものの個数を出力せよ。

样例 #1

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

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

样例输入 #3
10 8
样例输出 #3
322828856
提示

制約

$ 1≦N≦1000 $

$ 2≦K≦1000 $

答えは $ 2^{31}-1 $ 以下

Sample Explanation 1

色を$ 0 $,$ 1 $で表すと、左のボールを$ 0 $で塗り、右のボールを$ 1 $で塗るという方法と、左のボールを$ 1 $で塗り、右のボールを$ 0 $で塗るという方法の$ 2 $通りがあります。

Sample Explanation 2

ボールは一つしか無いため,$ 10 $色のうちどれを使っても良いので答えは$ 10 $通りです。

思路

简单的组合数学

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
map<int,int> m;
int main(){
    ios::sync_with_stdio(0);;
    int n,k;cin>>n>>k;
    ll ans=k;
    for(int i=2;i<=n;i++){
        ans*=(k-1);
    }
    cout<<ans;
    return 0;
}

[ABC046C] AtCoDeerくんと選挙速報

题面翻译

给定 $n$ 和 $n$ 对正整数 $T_i,A_i$，已知正整数数列 $t_i,a_i$ 满足以下条件：

$t_i\le t_{i+1}$，$a_i\le a_{i+1}$

$t_i/a_i=T_i/A_i$

求 $t_n+a_n$ 的最小值，保证答案不超过 $10^{18}$。

题目描述

シカのAtCoDeerくんは選挙速報を見ています。選挙には二人の候補高橋くんと青木くんが出ています。速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。AtCoDeerくんは $ N $ 回画面を見て、 $ i(1≦i≦N) $ 回目に見たときに表示されている比は $ T_i:A_i $ でした。ここで、AtCoDeerくんが選挙速報の画面を$ 1 $回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。 $ N $ 回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち最小となるものを求めてください。ただし、得票数が途中で減ることはありません。

输入格式

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

$ N $ $ T_1 $ $ A_1 $ $ T_2 $ $ A_2 $ $ : $ $ T_N $ $ A_N $

输出格式

$ N $ 回目に画面を見たときの投票数として考えられる最小値を出力せよ。

样例 #1

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

样例输入 #2
4
1 1
1 1
1 5
1 100
样例输出 #2
101
样例 #3

样例输入 #3
5
3 10
48 17
31 199
231 23
3 2
样例输出 #3
6930
提示

制約

$ 1≦N≦1000 $

$ 1≦T_i,A_i≦1000 (1≦i≦N) $

$ T_i $ と $ A_i $ は互いに素 $ (1≦i≦N) $

答えが $ 10^{18} $ 以下になることは保証されている

Sample Explanation 1

二人の得票数が $ 2,3 $ -> $ 3,3 $ -> $ 6,4 $ と動くと投票数は $ 10 $ になって、これが最小値です。

Sample Explanation 2

一度画面を見てからもう一度画面を見るまでに一票も入ってないことがありえます。

思路

有意思的一道题。

思路参考自AT2140题解 - 洛谷专栏 (luogu.com.cn)

设$u,v$为目前两个人的得票数，需要保证在以后的每一步中都有$u:v=T_i:A_i$

先设$u,v$分别为$T_i,A_i$的倍数。注意到总票数不会减少，所以$u,v$应该变为大于他们的最小的$T_i$或者$A_i$的倍数。

所以接下来这一步：$u=T_i*\lceil\frac{u}{T_i}\rceil，u=A_i*\lceil\frac{v}{A_i}\rceil$。

因为要一直保证$u:v=T_i:A_i$，所以接下来需要比较$\frac{u}{T_i}$和$\frac{v}{A_i}$的大小：

$\frac{u}{T_i}$小，根据比例的基本性质，$u=\frac {vT_i}{A_i}$。同理可得其他情况。

答案即$u+v$。

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

[ABC046D] AtCoDeerくんと変なじゃんけん

题面翻译

你和对手都只有两种出拳方式：石头（$g$）和布（$p$），规则一样，赢了得一分，平局不得分，输了减一分。现给你对手的出拳方式，设你到 $i$ 位置共出了 $x_i$ 次石头，$y_i$ 次布，在对于任意位置 $i$ 满足 $x_i \geq y_i$ 的条件下，输出你能得到的最大分数。

题目描述

シカのAtCoDeerくんは友達のTopCoDeerくんとあるゲームをして対戦しています。このゲームは $ N $ ターンからなります。各ターンではそれぞれのプレイヤーはじゃんけんのグーかパーを出します。ただし、各プレイヤーは次の条件を満たす必要があります。

(※) 各ターンの後で、(今までにパーを出した回数)$ ≦ $(今までにグーを出した回数) を満たす

このゲームでの各プレイヤーの得点は、(勝ったターンの数) $ - $ (負けたターンの数) です。 AtCoDeerくんは特殊能力を持っているので、ゲームが始まる前にTopCoDeerくんの出す $ N $ ターンの手を全て知ることが出来ました。 AtCoDeerくんの各ターンでの手を決めて、AtCoDeerくんの得点を最大化してください。 TopCoDeerくんの出す手の情報は文字列 $ s $ で与えられます。 $ s $ の $ i(1≦i≦N) $ 文字目が gのときは $ i $ ターン目でTopCoDeerくんがグーを出すことを、 pのときはパーを出すことを表します。

输入格式

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

$ s $

输出格式

AtCoDeerくんの得点の最大値を出力せよ。

样例 #1

样例输入 #1
gpg
样例输出 #1
0
样例 #2

样例输入 #2
ggppgggpgg
样例输出 #2
2
提示

制約

$ 1≦N≦10^5 $

$ N=|s| $

$ s $ の各文字はgかp

$ s $ で表される手は、条件(※)を満たしている

Sample Explanation 1

常に相手とあいこになるように手を出すことで、$ 0 $点を取ることができて、これが最大値です。

Sample Explanation 2

例えばグー,パー,グー,パー,グー,グー,パー,パー,グー,パーと出すことで、 $ 3 $回勝って$ 1 $回負けているので得点は$ 2 $点になり、これが最大値です。

思路

直接模拟，判断$p$是否大于$max_p$。再处理即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
int a[1010],t[1010];
int main(){
    ios::sync_with_stdio(0);;
    string s;cin>>s;
    ll p=0,g=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='p')p++;
    }
    ll lose=0,win=0;
    ll max_p=s.length()/2;
    if(p>=max_p)lose+=(p-max_p);
    else win+=(max_p-p);
    cout<<win-lose;
    return 0;
}