ABC045

[ABC045A] 台形

题面翻译

一个梯形，给出上底a，下底b，高h的长度，求它的面积~~~

题目描述

上底の長さが $ a $、下底の長さが $ b $、高さが $ h $ の台形があります。

台形の例

この台形の面積を求めてください。

输入格式

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

$ a $ $ b $ $ h $

输出格式

台形の面積を整数で出力せよ。面積が整数になることは保障されている。

样例 #1

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

样例输入 #2
4
4
4
样例输出 #2
16
提示

制約

$ 1  a  100 $

$ 1  b  100 $

$ 1  h  100 $

入力で与えられる値はすべて整数

$ h $ は偶数

Sample Explanation 1

上底の長さ $ 3 $、下底の長さ $ 4 $、高さ $ 2 $ の台形の面積は、 $ (3+4)×2/2 = 7 $ です。

Sample Explanation 2

この例で与えられるのは平行四辺形ですが、平行四辺形も台形です。

思路

直接模拟即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
ll a[55],f[55][2510];
bool palindrome(ll n) {//判定回文，不懂请参考数字反转
    ll sum = 0;
    ll k = n;
    while (n != 0) {
        sum = sum * 10 + n % 10;
        n /= 10;
    }
    if (sum == k)//判断是否回文
        return 1;
    else
        return 0;
}
int main(){
    ios::sync_with_stdio(0);
    ll a,b,h;cin>>a>>b>>h;
    cout<<(a+b)*h/2;
    return 0;
}

[ABC045B] 3人でカードゲームイージー

题面翻译

题面描述

Alice、Bob 和 Charlie 在玩 Card Game for Three。

开始时，每名玩家有一叠由卡牌组成的牌堆。每张牌上有一个字母 $\texttt a, \texttt b$ 或 $\texttt c$。卡牌的顺序不能被改变。

Alice 先开始游戏。

玩家的牌堆中至少有一张牌，当前玩家从牌堆顶抽出一张牌，这张牌代表的玩家进行下一回合（$\texttt a$ 代表 Alice，$\texttt c$ 代表 Bob，$\texttt c$ 代表 Charlie）。

从左往右抽牌（牌堆顶在左边）。

如果当前玩家的牌堆空了，游戏结束，这名玩家胜利。

你得到了每名玩家最初的牌堆 $S_a, S_b, S_c$，求出胜者。

数据范围

对于 $100 \%$ 的数据，保证 $1 \leq |S_a|, |S_b|, |S_c| \leq 100$ 且 $S_a, S_b, S_c$ 仅由 $\texttt{abc}$ 三个小写拉丁字母组成。

题目描述

A さん、B さん、C さんの $ 3 $ 人が以下のようなカードゲームをプレイしています。

最初、$ 3 $ 人はそれぞれ a、b、c いずれかの文字が書かれたカードを、何枚か持っている。これらは入力で与えられた順番に持っており、途中で並べ替えたりしない。

$ A $ さんのターンから始まる。

現在自分のターンである人がカードを $ 1 $ 枚以上持っているならば、そのうち先頭のカードを捨てる。その後、捨てられたカードに書かれているアルファベットと同じ名前の人 (例えば、カードに a と書かれていたならば A さん) のターンとなる。

現在自分のターンである人がカードを $ 1 $ 枚も持っていないならば、その人がゲームの勝者となり、ゲームは終了する。

$ 3 $ 人が最初に持っているカードがそれぞれ先頭から順に与えられます。具体的には、文字列 $ S_A $、$ S_B $、$ S_C $ が与えられます。文字列 $ S_A $ の $ i $ 文字目 ( $ 1 i |S_A| $ ) に書かれている文字が、A さんの持っている中で先頭から $ i $ 番目のカードに書かれている文字です。文字列 $ S_B $、 $ S_C $ についても同様です。

最終的に誰がこのゲームの勝者となるかを求めてください。

输入格式

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

$ S_A $ $ S_B $ $ S_C $

输出格式

A さんが勝つなら A、B さんが勝つなら B、C さんが勝つなら C と出力せよ。

样例 #1

样例输入 #1
aca
accc
ca
样例输出 #1
A
样例 #2

样例输入 #2
abcb
aacb
bccc
样例输出 #2
C
提示

制約

$ 1  S_A  100 $

$ 1  S_B  100 $

$ 1  S_C  100 $

$ S_A $、$ S_B $、$ S_C $ に含まれる文字はそれぞれ a、b、c のいずれか

Sample Explanation 1

ゲームは以下のように進行します。 - A さんが、持っている中で最初のカード a を捨てる。次は A さんの番となる。 - A さんが、持っている中で最初のカード c を捨てる。次は C さんの番となる。 - C さんが、持っている中で最初のカード c を捨てる。次は C さんの番となる。 - C さんが、持っている中で最初のカード a を捨てる。次は A さんの番となる。 - A さんが、持っている中で最初のカード a を捨てる。次は A さんの番となる。 - A さんはもう持っているカードがない。よって A さんの勝利となり、ゲームは終了する。

思路

其实是到模拟题，感觉有点像链表。

用$p$代表每个字符串对应的指针，不断按照题意进行移动操作，直到当前牌堆空为止。

思路参考自[题解 AT2066 ABC045B] 3人でカードゲームイージー / Card Game for Three (ABC Edit) - 洛谷专栏 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
string s[3];
ll len[3],p[4],k;
int main(){
    ios::sync_with_stdio(0);
    for(int i=0;i<3;i++)cin>>s[i],len[i]=s[i].length();
    while(p[k]<len[k]){
        k=s[k][p[k]++]-'a';
    }
    cout<<(char)(k+'A');
    return 0;
}

[ABC045C] たくさんの数式

题面翻译

Translated by aoweiyin

题意翻译

有一个仅由字符1到9构成的字符串$S(1\leq |S|\leq 10)$，让你在中间添加+，使其变成一个加式。求所有方案的和值（详见样例解释）。

样例解释1：

输入125,输出176.

有4种：

125

1+25=26

12+5=17

1+2+5=8

题目描述

1 以上 9 以下の数字のみからなる文字列 $ S $ が与えられます。この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。一つも入れなくてもかまいません。ただし、+ が連続してはいけません。

このようにして出来る全ての文字列を数式とみなし、和を計算することができます。

ありうる全ての数式の値を計算し、その合計を出力してください。

输入格式

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

$ S $

输出格式

ありうる全ての数式の値の総和を $ 1 $ 行に出力せよ。

样例 #1

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

样例输入 #2
9999999999
样例输出 #2
12656242944
提示

制約

$ 1|S| $

$ S $ に含まれる文字は全て 1 〜 9 の数字

Sample Explanation 1

考えられる数式としては、 125、1+25、12+5、1+2+5 の $ 4 $ 通りがあります。それぞれの数式を計算すると、 - $ 125 $ - $ 1+25=26 $ - $ 12+5=17 $ - $ 1+2+5=8 $ となり、これらの総和は $ 125+26+17+8=176 $ となります。

思路

用DFS就可以解决了，将每一位进行拆分，用数组记录下来。

$+$的插入有两种情况：

DFS数字的每一位，可以将这一位与上一个数进行结合，也可以在中间加上一个$+$，具体看代码。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
ll a[15],ans,n;
//k表示当前是第几位数字，sum表示的是当前的总和，num表示的是当前新开的数字
void dfs(ll k,ll sum,ll num){
    //如果大于n位，则结束
    if(k>n){
        //加上答案和当前数字
        ans+=sum+num;
        return;
    }
    num=num*10+a[k];
    //对应+
    dfs(k+1,sum+num,0);
    //对应没有+
    dfs(k+1,sum,num);
}
int main(){
    ios::sync_with_stdio(0);
    string s;cin>>s;
    //分离每一位数字
    for(int i=0;i<s.length();i++){
        a[i+1]=s[i]-'0';
    }
    n=s.length();
    //开始DFS
    dfs(1,0,0);
    //注意答案要除以2
    cout<<ans/2;
    return 0;
}

其实有更好的方法：看看这篇文章

[题解 AT2067 【ARC061A] たくさんの数式 / Many Formulas】 - 洛谷专栏 (luogu.com.cn)

[ABC045D] すぬけ君の塗り絵

题面翻译

给定一个 $H$ 行 $W$ 列的矩形，再给定矩形上 $N$ 个黑格子的坐标。对于每个 $0\le j\le9$ ，求出有多少个 $3\times3$ 的子矩阵包含有恰好 $j$ 个黑格子。

题目描述

縦 $ H $ 行、横 $ W $ 列のマス目からなる盤があります。最初、どのマス目も白く塗られています。

すぬけ君が、このうち $ N $ マスを黒く塗りつぶしました。$ i $ 回目 ( $ 1  i  N $ ) に塗りつぶしたのは、上から $ a_i $ 行目で左から $ b_i $ 列目のマスでした。

すぬけ君がマス目を塗りつぶした後の盤の状態について、以下のものの個数を計算してください。

各整数 $ j $ ( $ 0  j  9 $ ) について、盤の中に完全に含まれるすべての $ 3 $ 行 $ 3 $ 列の連続するマス目のうち、黒いマスがちょうど $ j $ 個あるもの。

输入格式

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

$ H $ $ W $ $ N $ $ a_1 $ $ b_1 $ : $ a_N $ $ b_N $

输出格式

出力は $ 10 $ 行からなる。 $ j+1 $ 行目 ( $ 0  j  9 $ ) には、盤の中に完全に含まれるすべての $ 3 $ 行 $ 3 $ 列の連続するマス目のうち、黒いマスがちょうど $ j $ 個あるものの総数を出力せよ。

样例 #1

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

样例输入 #2
10 10 20
1 1
1 4
1 9
2 5
3 10
4 2
4 7
5 9
6 4
6 6
6 7
7 1
7 3
7 7
8 1
8 5
8 10
9 2
10 4
10 9
样例输出 #2
4
26
22
10
2
0
0
0
0
0
样例 #3

样例输入 #3
1000000000 1000000000 0
样例输出 #3
999999996000000004
0
0
0
0
0
0
0
0
0
提示

制約

$ 3  H  10^9 $

$ 3  W  10^9 $

$ 0  N  min(10^5,H×W) $

$ 1  a_i  H $ $ (1  i  N) $

$ 1  b_i  W $ $ (1  i  N) $

$ (a_i, b_i)  (a_j, b_j) $ $ (i  j) $

Sample Explanation 1

![](https://atcoder.jp/img/arc061/30326702be007759dce81231012a8353.png) この盤に含まれる $ 3×3 $ の正方形は全部で $ 6 $ 個ありますが、これらのうち $ 2 $ 個の内部には黒いマスが $ 3 $ 個、残りの $ 4 $ 個の内部には黒いマスが $ 4 $ 個含まれています。

思路

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

直接开数组模拟肯定喜提TLE,MLE。

这时候就要想到贡献法，就是每输入一个格子，计算它对包含它的九宫格的贡献（记得判边界）

所以我们只需维护一个答案数组，每次计算新格子对它的影响就行了

但是，又有个新问题：如何记录新加进来的格子所在的九宫格原来黑格子的个数呢？

显然我们可以用 map 来解决，用它来维护以$x,y$为中心的九宫格黑格子个数

完结撒花！

#include<bits/stdc++.h>
using namespace std;
long long  ans[10];
typedef pair<int,int> pii;//用pair来维护二元组 
map<pii,int> mp;
int main()
{
	long long h,w;
	int n;
	cin>>h>>w>>n;
	ans[0]=(h-2)*(w-2);//初始化，一开始一个黑格子都没有 
	for(int i=1;i<=n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		for(int j=-1;j<=1;j++)
		{
			for(int k=-1;k<=1;k++)//遍历计算影响 
			{
				int x=a+j,y=b+k;//九宫格的中心 
				if(x>1&&x<h&&y>1&&y<w)//判断边界 
				{
					int now;//now表示现在这个九宫格的黑格子的数量 
					now=++mp[{x,y}];
                    //now++,那么now-1肯定就是要--啦
					ans[now]++,ans[now-1]--;
				}
			}
		}
	}
	for(int i=0;i<10;i++) cout<<ans[i]<<endl;
}