ABC043

要开始加训了！！！不然太菜找不到队友了┭┮﹏┭┮

[ABC043A] キャンディーとN人の子供イージー

题面翻译

幼儿园有N个孩子。教授决定给孩子们糖果，第一个人要一个糖果，第二个人要两个糖果…… ，第N个人要N个糖果。总共需要多少糖果？

题目描述

競プロ幼稚園には$ N $人の子供がいます。えび先生は、子供たちを一列に並べ、一人目にはキャンディーを$ 1 $個,二人目には$ 2 $個,...,$ N $人目には$ N $個あげることにしました。必要なキャンディーの個数の合計は何個でしょう?

输入格式

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

$ N $

输出格式

必要なキャンディーの個数の合計を出力せよ。

样例 #1

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

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

样例输入 #3
1
样例输出 #3
1
提示

制約

$ 1≦N≦100 $

Sample Explanation 1

$ 1+2+3=6 $が答えになります。

Sample Explanation 2

$ 1 $から$ 10 $までの和は$ 55 $です。

Sample Explanation 3

子供は一人しかいません。この時答えは$ 1 $になります。

思路

等差数列计算即可

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

[ABC043B] バイナリハックイージー

题面翻译

$Sig$已经打造了他自己的键盘。为了设计最简单，在这个键盘上面只有$3$个按键：$0$号键，$1$号键和退格键。

首先，他正在用他的键盘使用纯文本编辑器。这个编辑器总是显示一个字符串（可能为空）。就在编辑开始的时候，这个字符串是空的。当键盘上的任意按键被按下时，字符串将发生以下变化：

$0$号键：一个文字$0$将被插入到字符串的右边。

$1$号键：一个文字$1$将被插入到字符串的右边。

退格键：如果字符串是空的，什么都不会发生。否则字符串最右边的文字将被删除。

$Sig$已经开始了编辑，并且按下了这些按键几次。你将被给予一个他敲击键盘的顺序字符串s。在这个字符串中，文字$0$代表$0$号键，文字$1$代表$1$号键，而字母$B$则代表退格键。请问现在编辑器上会显示什么字符串呢？

题目描述

しぐはキーボードを製作しました。シンプルさを極限まで追求したこのキーボードには、0 キー、1 キー、バックスペースキーの $ 3 $ つしかキーがありません。

手始めに、しぐはこのキーボードで簡単なテキストエディタを操作してみることにしました。このエディタには常に一つの文字列が表示されます（文字列が空のこともあります）。エディタを起動した直後では、文字列は空です。キーボードの各キーを押すと、文字列が次のように変化します。

0 キー: 文字列の右端に文字 0 が挿入される。

1 キー: 文字列の右端に文字 1 が挿入される。

バックスペースキー: 文字列が空なら、何も起こらない。そうでなければ、文字列の右端の $ 1 $ 文字が削除される。

しぐはエディタを起動し、これらのキーを何回か押しました。しぐが押したキーを順番に記録した文字列 $ s $ が与えられます。$ s $ の中の文字 0 は 0 キー、文字 1 は 1 キー、文字 B はバックスペースキーを表します。いま、エディタの画面にはどのような文字列が表示されているでしょうか？

输入格式

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

$ s $

输出格式

最終的にエディタに表示されている文字列を出力せよ。（「制約」セクションで述べたように、この文字列が空になるような入力は与えられない）

样例 #1

样例输入 #1
01B0
样例输出 #1
00
样例 #2

样例输入 #2
0BB1
样例输出 #2
1
提示

制約

$ 1 ≦ |s| ≦ 10 $ ($ |s| $ は $ s $ の長さを表す)

$ s $ は文字 0, 1, B のみからなる。

正解は空文字列ではない。

Sample Explanation 1

キーが押されるたびに、エディタの文字列は 0, 01, 0, 00 と変化します。

Sample Explanation 2

キーが押されるたびに、エディタの文字列は 0, (空文字列), (空文字列), 1 と変化します。

思路

使用deque模拟即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
int main(){
    ios::sync_with_stdio(0);
    deque<char> q;
    string s;cin>>s;
    for(int i=0;i<s.length();i++){
        if(s[i]=='B'&&q.size())q.pop_back();
        if(s[i]=='0'||s[i]=='1')q.push_back(s[i]);
    }
    while(q.size()){
        cout<<q.front();
        q.pop_front();
    }
    return 0;
}

[ARC059C] いっしょ

题面翻译

Evi有$n$个整数，分别为$a_1$，$a_2$，直到$a_n$。

他的目标是通过改变其中的一些数来使所有数相等。

对于每个整数，他最多可以变换一次。

将一个整数$x$转换为一个整数$y$会花费他$\left(x-y\right)^2$美元。

即使第$i$个数$a_i$与第$j$个数$a_j$ $\left(i!=j\right)$相等，他仍需为了改变它们中的每个数分别花费代价(请见样例2)。

请找到能够实现他目标的最小花费。

题目描述

$ N $ 個の整数 $ a_1,a_2,..,a_N $ が与えられます。えび君はこれらを書き換えて全て同じ整数にしようとしています。各$ a_i (1≦i≦N) $は高々一回しか書き換えられません(書き換えなくても良い)。整数$ x $を整数$ y $に書き換えるとき、コストが$ (x-y)^2 $かかります。仮に$ a_i=a_j (i≠j) $だとしても、ひとつ分のコストで同時に書き換えることは出来ません(入出力例$ 2 $ を参照)。えび君が目的を達成するのに必要なコストの総和の最小値を求めてください。

输入格式

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

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

输出格式

えび君が全てを同じ整数に書き換えるのに必要なコストの総和の最小値を出力せよ。

样例 #1

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

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

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

样例输入 #4
4
-100 -100 -100 -100
样例输出 #4
0
提示

制約

$ 1≦N≦100 $

$ -100≦a_i≦100 $

Sample Explanation 1

全てを$ 6 $に書き換えると、コストの総和は$ (4-6)^2+(8-6)2=8 $となり、これが最小です。

Sample Explanation 2

全てを$ 2 $に書き換えると$ (1-2)^2+(1-2)2+(3-2)^2=3 $となります。各$ a_i $ごとに書き換えるので、二つの$ 1 $を一度にコスト$ (1-2)^2 $で書き換えられるわけではないことに注意してください。

Sample Explanation 3

$ 4 $は書き換えずに、$ 2 $と$ 5 $を共に$ 4 $に書き換えることで$ (2-4)^2+(5-4)2=5 $が達成できて、これが最小です。

Sample Explanation 4

何も書き換えなくともえび君は目的を達成しています。よってこの場合コストは$ 0 $です。

思路

因为范围实在是太小了，所以直接暴力枚举即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
int a[110];
int main(){
    ios::sync_with_stdio(0);
    int n;cin>>n;
    int MIN=200,MAX=-200;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        MIN=min(a[i],MIN);
        MAX=max(a[i],MAX);
    }
    ll ans=1e9;
    for(int i=MIN;i<=MAX;i++){
        ll tmp=0;
        for(int j=1;j<=n;j++){
            tmp+=(a[j]-i)*(a[j]-i);
        }
        ans=min(tmp,ans);
    }
    cout<<ans;
    return 0;
}

其实这里是有规律的，答案只可能是平均值，或者离平均值最近的两个数（也就是是这三者中的其中一个），原理大概是利用均值不等式吧。

[ARC059D] アンバランス

题面翻译

给出字符串$s$,求区间$[l,r]$,使得该子串中有一种字母出现的次数严格大于该子串长度的一半.
如果没有符合条件的子串,输出两个-1.

由 @Fuko_Ibuki 提供翻译

题目描述

文字列 $ t $ について、$ t $ の長さが $ 2 $ 以上であり、かつ $ t $ の中の文字のうち過半数が同じ文字であるとき、$ t $ をアンバランスであると呼ぶことにします。例えば、voodoo や melee はアンバランスであり、noon や a はアンバランスではありません。

小文字のアルファベットからなる文字列 $ s $ が与えられます。$ s $ にアンバランスな (連続する) 部分文字列が存在するか判定してください。存在する場合は、$ s $ の中でそのような部分文字列が存在する位置を一つ示してください。

输入格式

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

$ s $

输出格式

$ s $ にアンバランスな部分文字列が存在しない場合は、-1 -1 と出力せよ。

$ s $ にアンバランスな部分文字列が存在する場合は、そのような部分文字列の一つを $ s_a s_{a+1} ... s_{b} $ $ (1 ≦ a < b ≦ |s|) $ として、$ a $ $ b $ と出力せよ。そのような部分文字列が複数存在する場合は、いずれも正解とみなされる。

样例 #1

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

样例输入 #2
atcoder
样例输出 #2
-1 -1
提示

制約

$ 2 ≦ |s| ≦ 10^5 $

$ s $ は小文字のアルファベットのみからなる。

部分点

$ 2 ≦ |s| ≦ 100 $ を満たすデータセットに正解した場合は、$ 200 $ 点が与えられる。

Sample Explanation 1

文字列 $ s_2 s_3 s_4 s_5 $ $ = $ eede はアンバランスな文字列です。他にもアンバランスな部分文字列は存在し、例えば 2 6 と出力しても正解となります。

Sample Explanation 2

文字列 atcoder はアンバランスな部分文字列を持ちません。

思路

思维题吧，反正我是没什么思维qwq。

引用这位大佬的文章：[题解 AT2020 【ARC059B] アンバランス / Unbalanced】 - 洛谷专栏 (luogu.com.cn)

思路大致如下，与其它题解的差不多：

从字符串的开头搜索到结尾，如果该字符串与后面一个或者后面第二个是相同的，那么该字符与跟它相同的就是一个符合题目要求的子序列。

例如$IIIAM$，虽然$IIIAM$是一个符合要求的子序列，但是$II$也符合，所以直接输出$II$就可以了。

再举一个例子：$IOIII$，它本身就是一个符合要求的子序列，但是，最前面的是$IOI$ ，所以可以得出结论，答案不是两个长度的子序列就是三个长度的子序列。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
int main(){
    ios::sync_with_stdio(0);
    int n=0;
    string s;cin>>s;
    for(int i=0;i<s.length();i++){
        //判断第i项与第i+1项是否相同
        if(s[i]==s[i+1]){
            cout<<i+1<<" "<<i+2;
            return 0;
        }
        //判断第i项与第i+2项是否相同
        if(s[i]==s[i+2]){
            cout<<i+1<<" "<<i+3;
            return 0;
        }
    }
    cout<<-1<<" "<<-1;
    return 0;
}