ABC042

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

---

[ABC042A] 和風いろはちゃんイージー

题面翻译

给出三个数\(A,B,C\)，\(1≤A,B,C≤10\)，判断\(A,B,C\)是否能重新排列为\(575\)。

翻译由\(@PCT2506\)提供

题目描述

日本の誇る美しいリズムとして、五七五というものがあります。いろはちゃんは五七五が大好きです。

$ 3 $ つの文節の並びの長さがそれぞれ $ 5,7,5 $ となるようにこの順番で並んでいるとき、その $ 3 $ つの文節の並びは五七五であると言います。

並び替えたい $ 3 $ つの文節の長さを表す整数 $ A,B,C $ が与えられるので、それらの文節を並び替えて五七五にできるか判定してください。

输入格式

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

$ A $ $ B $ $ C $

输出格式

文節の並びを五七五にすることができるなら YES 、そうでないなら NO を出力せよ。

样例 #1

样例输入 #1

5 5 7

样例输出 #1

YES

样例 #2

样例输入 #2

7 7 5

样例输出 #2

NO

提示

制約

• $ 1≦A,B,C≦10 $

Sample Explanation 1

与えられる文節の長さはそれぞれ $ 5,5,7 $ であり、$ 5,7,5 $ となるように文節を並び替えることができます。したがって、文節の並びを五七五にすることは可能といえます。

思路

直接统计5和7的个数判断即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
int main(){
    ios::sync_with_stdio(0);
    int cnt5=0,cnt7=0;
    for(int i=1;i<=3;i++){
        int x;cin>>x;
        if(x==5)cnt5++;
        if(x==7)cnt7++;
    }
    if(cnt5==2&&cnt7==1)cout<<"YES\n";
    else cout<<"NO\n";
    return 0;
}

[ABC042B] 文字列大好きいろはちゃんイージー

题面翻译

题目描述： 有n个长为L的字符串

要求把他们按照字典序进行排序并在一行内输出

输入格式： 第一行两个正整数n，L 以下n行每行一个字符串

输出格式： 仅一行：排序过后的字符串

（注 ： 这次岛国的题末尾可以不换行）

输入输出不敲了

说明：约定：

1，1 <= n,L <= 100且n，L 都是正整数

2，对于第i(1 <= i <= n)个字符串，保证长度为L

3，所有字符串都由小写字母构成

感谢@lsy263 提供的翻译

题目描述

いろはちゃんは 長さ $ L $ の文字列を $ N $ 個持っており、それぞれ $ S_1, S_2, ..., S_N $ です。

それらの文字列を好きな順番で全て結合してできる文字列のうち、もっとも辞書順で小さいものを求めてください。

なお、ある文字列 $ s=s_1s_2s_3 \(...\) s_n $ と $ t=t_1t_2t_3 \(...\) t_m $ について、以下のどちらかを満たすとき、辞書順比較で $ s < t $ であるといいます。

• ある整数 $ i(1≦i≦min(n,m)) $ に関して、 $ 1≦j < i $ を満たす任意の整数 $ j $ において $ s_j = t_j $ が成立し、かつ $ s_i < t_i $ が成立する。
• 任意の整数 $ i(1≦i≦min(n,m)) $ に関して $ s_i = t_i $ が成立し、かつ $ n < m $ が成立する。

输入格式

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

$ N $ $ L $ $ S_1 $ $ S_2 $ : $ S_N $

输出格式

与えられる文字列を好きな順番で全て結合してできる文字列のうち、もっとも辞書順で小さいものを出力せよ。

样例 #1

样例输入 #1

3 3
dxx
axx
cxx

样例输出 #1

axxcxxdxx

提示

制約

• $ 1 ≦ N, L ≦ 100 $
• 全ての $ i (1≦i≦N) $ に対し、$ S_i $ の長さは $ L $ に等しい。
• 各 $ i $ について, $ S_i $ は全て半角英小文字のみから成る文字列である。

Sample Explanation 1

与えられた文字列を axx,cxx,dxx という順番に並び替えてから結合することで、辞書順最小を達成できます。

思路

直接排序即可，其实cmp函数可以不用写的

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
string s[110];
bool cmp(string a,string b){
    return a<b;
}
int main(){
    ios::sync_with_stdio(0);
    int n=0,l=0;cin>>n>>l;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s+1,s+1+n);
    for(int i=1;i<=n;i++)cout<<s[i];
    return 0;
}

看到题解区有大佬用了优先队列，可以看看qwq

[题解 AT1978 【ABC042B] 文字列大好きいろはちゃんイージー / Iroha Loves Strings (ABC Edition)】 - 洛谷专栏 (luogu.com.cn)

[ARC058C] こだわり者いろはちゃん

题面翻译

买家想买一个价格为N的物品，但他又讨厌k个数字，分别为D_1，D_2，……，D_K。问他最少出多少钱，才能在保证买下这个物品的同时使自己出的钱不包括自己讨厌的数字。

题目描述

いろはちゃんはこだわりもので、嫌いな数字が $ K $ 個あり、それぞれ $ D_1, D_2, ..., D_K $ です。

いろはちゃんはお店でお買い物をしていて、 $ N $ 円の品物を買おうとしています。 もちろん、この品物は $ N $ 円以上のお金を支払えば買うことができます。 しかし、先ほど述べたようにいろはちゃんは強いこだわりがあるので、自分がお店に支払う金額の $ 10 $ 進表記にいろはちゃんの嫌いな数字が出現しないような最も少ない金額を支払おうとします。

いろはちゃんが支払う金額を求めてください。

输入格式

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

$ N $ $ K $ $ D_1 $ $ D_2 $ … $ D_K $

输出格式

いろはちゃんが支払う金額を出力せよ。

样例 #1

样例输入 #1

1000 8
1 3 4 5 6 7 8 9

样例输出 #1

2000

样例 #2

样例输入 #2

9999 1
0

样例输出 #2

9999

提示

制約

• $ 1 ≦ N < 10000 $
• $ 1 ≦ K < 10 $
• $ 0 ≦ D_1 < D_2 < … < D_K≦9 $
• $ {D_1,D_2,...,D_K} ≠ {1,2,3,4,5,6,7,8,9} $

Sample Explanation 1

嫌いでない数字は $ 0 $ と $ 2 $ のみです。 $ N=1000 $ 以上の整数で、桁に $ 0 $ と $ 2 $ のみが含まれる最小の整数は $ 2000 $ なのでそれを出力してください。

思路

这题想复杂了，其实直接枚举即可，从\(n\)开始向上枚举，并将其进行逐位拆分，判断其中是否出现讨厌的数字即可。注意如果出现0的话，直接退出循环，输出\(num\)即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
int a[10],b[10];
int main(){
    ios::sync_with_stdio(0);
    int n,k;cin>>n>>k;
    for(int i=1;i<=k;i++){
        int x;cin>>x;
        //开个桶记录一下讨厌的数字
        a[x]=1;
    }
    int num=0;
    while(1){
        num=n;
        //进行逐位拆分，判断是否出现讨厌的数字
        while(num){
            if(a[num%10])break;
            num/=10;
        }
        //如果为0，说明拆分完毕，满足要求
        if(num==0)break;
        //否则，说明存在讨厌的数字，继续向上枚举
        n++;
    }
    cout<<n;
    return 0;
}

[ARC058D] いろはちゃんとマス目

题面翻译

题意

有一个 \(H\times W\) 的矩阵, 现在你正位于左上角的格子, 并且你只能向右移动或向下移动, 不幸的是, 矩阵的左下角 \(A\times B\) 的地方被划为了禁区, 即你不能在此行走, 那么现在你有多少种方法从左上角走到右下角的格子呢?

输入

一行四个整数 \(H,W,A,B\).

输出

方案数. 由于方案数很大, 请对 \(10^9+7\) 取模.

感谢@凌幽 提供的翻译

题目描述

縦 $ H $ マス、横 $ W $ マスのマス目があります。 いろはちゃんは、今一番左上のマス目にいます。 そして、右か下に1マス移動することを繰り返し、一番右下のマス目へと移動します。 ただし、下から $ A $ 個以内、かつ左から $ B $ 個以内のマス目へは移動することは出来ません。

移動する方法は何通りあるか求めてください。

なお、答えは非常に大きくなることがあるので、答えは $ 10^9+7 $ で割ったあまりを出力してください。

输入格式

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

$ H $ $ W $ $ A $ $ B $

输出格式

移動する方法の数を $ 10^9+7 $ で割ったあまりを出力せよ。

样例 #1

样例输入 #1

2 3 1 1

样例输出 #1

2

样例 #2

样例输入 #2

10 7 3 4

样例输出 #2

3570

样例 #3

样例输入 #3

100000 100000 99999 99999

样例输出 #3

1

样例 #4

样例输入 #4

100000 100000 44444 55555

样例输出 #4

738162020

提示

制約

• $ 1 ≦ H, W ≦ 100,000 $
• $ 1 ≦ A < H $
• $ 1 ≦ B < W $

Sample Explanation 1

$ 2×3 $ マスありますが、左下の $ 1 $ マスには移動することができません。「右右下」、「右下右」という $ 2 $ つの移動の仕方があります。

Sample Explanation 2

移動できないマスが $ 12 $ マスあります。

思路

其实是一道数学题，思路不难想，大致有两种：

1、从\((1,1)\)到\((a-1,b)\)，再从\((a-1,b+1)\)到\((h,w)\)走，具体怎么算？其实就是高中的组合数学。

2、先考虑从\((1,1)\)到\((h,w)\)的所有路径数，记作\(ans1\)，不考虑任何要求。然后我们再考虑可能经过禁区的路径数：这时，问题相当于在前\(a+b-2\)步中，向下走的步数大于或等于\(b-2\)步，那我们只需要计算对应的每种情况：当走完向下走完\(i\)步时，且走完前\(a+b-2\)步时的所有路径数，并从当前位置开始，重新计算到\((h,w)\)的所有路径数，注意两者需要一一对应相乘，然后把所有不合法的情况统计起来，记作\(ans2\)。那么答案就是\(ans1-ans2\)。

这里先贴上大佬的代码，自己写的没过qwq，而且大佬们的板子也挺漂亮的，可以整理作为自己的板子。

思路1

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const int mod=1e9+7;
ll fac[MAXN],inv[MAXN];
//快速幂
ll qpower(ll a,ll p){
    ll ans=1;
    while(p){
        if(p&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        p>>=1;
    }
    return ans;
}
//计算组合数
ll C(int n,int m){
  if(n==m||m==0)return 1;
  return ((fac[n]*inv[m])%mod*inv[n-m]%mod);
}

ll get(int x1,int y1,int x2,int y2){
    return C(x2+y2-x1-y1,x2-x1);
}
int main(){
    int h,w,a,b;cin>>h>>w>>a>>b;
    ios::sync_with_stdio(false);
    //注意记得初始化哦
    fac[1]=1;
    //计算阶乘
    for(int i=2;i<=200000;i++){
        fac[i]=(i*fac[i-1])%mod;
    }
    //费马小定理求逆元
    inv[200000]= qpower(fac[200000],mod-2);
    //递推方法求逆元
    for(int i=199999;i>=1;i--){
        inv[i]=(inv[i+1]*(i+1))%mod;
    }
    ll ans=0;
    for(int i=1;i<=h-a;i++){
        ans+=get(1,1,i,b)*get(i,b+1,h,w)%mod;
        //注意这里还需要取模哦
        ans%=mod;
    }
    cout<<ans;
    return 0;
}

思路2

//快速幂
inline int qpow(int a, int b)
{
	int res = 1;
	for(register int i = b; i; i >>= 1)
	{
		if(i & 1) res = (long long)res * a % mod;
		a = (long long)a * a % mod;
	}
	return res;
}

//计算组合数
inline int c(int n, int m)
{
	if(n < m) return 0;
	if(n == m || m == 0) return 1;
	return (long long)jc[n] * inv[m] % mod * inv[n - m] % mod;
}

int main()
{
	n = read() - 1; m = read() - 1;
	a = n - read() + 1; b = read() - 1;
	jc[0] = inv[0] = 1; k = n + m + 1;
    
    //求阶乘
	for(register int i = 1; i <= k; ++i)
		jc[i] = (long long)jc[i - 1] * i % mod;
	
    //费马小定理求逆元
    inv[k] = qpow(jc[k], mod - 2);
    
    //递推方法求逆元
	for(register int i = k - 1; i; --i)
		inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
	
    //计算所有的情况
    ans = c(n + m, n);
    
    //减去走入禁区的情况
	for(register int i = 0; i <= b; ++i)
		ans = (ans - (long long)c(a + b, i) * c(n + m - a - b, m - i) % mod * now + mod) % mod;
    
	write(ans); 
    return 0;
}