天天看點
傳回

【AtCoder】AtCoder Beginner Contest 110題解AtCoder Beginner Contest 110題解

AtCoder Beginner Contest 110題解

文章目錄

  • AtCoder Beginner Contest 110題解
    • A - Maximize the Formula
      • 題目大意
      • 思路
      • 代碼
    • B - 1 Dimensional World's Tale
      • 題目大意
      • 思路
      • 代碼
    • C - String Transformation
      • 題目大意
      • 思路
      • 代碼
    • D - Factorization
      • 題目大意
      • 思路
      • 代碼

A - Maximize the Formula

◇題目傳送門◆

題目大意

給定三個數字 A , B , C A,B,C A,B,C，要求使用這三個數字組成一個兩位數及一個一位數，使得他們的和最大

思路

似乎沒有什麼可以講的，直接給出代碼吧。

代碼 

#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	int a[3];
	scanf("%d %d %d",&a[0],&a[1],&a[2]);
	sort(a,a+3);
	printf("%d\n",a[2]*10+a[1]+a[0]);
	return 0;
}

B - 1 Dimensional World’s Tale

◇題目傳送門◆

題目大意

給定兩個數 N , M N,M N,M和數軸上的兩個點 X , Y X,Y X,Y與 N N N個點 x 1 , x 2 , x 3 , … , x N x_1,x_2,x_3,\ldots,x_N x1​,x2​,x3​,…,xN​和 M M M個點 y 1 , y 2 , y 3 , … , y M y_1,y_2,y_3,\ldots,y_M y1​,y2​,y3​,…,yM​，要求找出一個點 Z Z Z，使得它滿足以下條件：

  • X &lt; Z ≤ Y X&lt;Z\le Y X<Z≤Y
  • x 1 , x 2 , x 3 , … , x N &lt; Z x_1,x_2,x_3,\ldots,x_N&lt;Z x1​,x2​,x3​,…,xN​<Z
  • y 1 , y 2 , y 3 , … , y M ≥ Z y_1,y_2,y_3,\ldots,y_M\ge Z y1​,y2​,y3​,…,yM​≥Z

思路

我們記 x 0 = X , y 0 = Y x_0=X,y_0=Y x0​=X,y0​=Y，仔細分析題目可以發現，當存在 max ⁡ { x 0 , x 1 , x 2 , … , x N } &lt; min ⁡ { y 0 , y 1 , y 2 … , y M } \max\{x_0,x_1,x_2,\ldots,x_N\}&lt;\min\{y_0,y_1,y_2\ldots,y_M\} max{x0​,x1​,x2​,…,xN​}<min{y0​,y1​,y2​…,yM​}時，就會有 Z Z Z存在。

是以直接給出代碼：

代碼 

#include<cstdio>
#include<algorithm>
using namespace std;

const int Maxn=100;
int N,M,X,Y;
int A[Maxn+5],B[Maxn+5];

int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	scanf("%d %d %d %d",&N,&M,&A[0],&B[0]);
	for(int i=1;i<=N;i++)
		scanf("%d",&A[i]);
	for(int i=1;i<=M;i++)
		scanf("%d",&B[i]);
	int maxa=*max_element(A,A+N+1);
	int minb=*min_element(B,B+M+1);
	if(maxa<minb)
		puts("No War");
	else puts("War");
	return 0;
}

C - String Transformation

◇題目傳送門◆

題目大意

給定兩個串 S , T S,T S,T，保證兩串長度相等。要求使用如下操作，使得 S , T S,T S,T相同：

操作：從26個字母中選擇兩個字母 c 1 , c 2 c_1,c_2 c1​,c2​，在 S S S中，将所有的 c 1 c_1 c1​替換為 c 2 c_2 c2​，所有的 c 2 c_2 c2​替換為 c 1 c_1 c1​。

思路

不難發現在串 S S S中，每個字母和串 T T T中的每個字母是有一一對應的關系。是以我們考慮在串 S S S中是否滿足這個對應關系，在串 T T T中是否滿足對應關系。想到這個即可過掉此題。

代碼 

#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int Maxn=2*1e5;

char s[Maxn+5],t[Maxn+5];
int c[256+5];

int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	scanf("%s %s",s,t);
	int len=strlen(s);
	memset(c,-1,sizeof c);
	set<char> cnt;
	for(int i=0;i<len;i++)
		cnt.insert(s[i]);
	for(int i=0;i<len;i++) {
		if(c[t[i]]!=-1&&c[t[i]]!=s[i]) {
			if(t[i]==s[i]&&cnt.size()<26)
				continue;
			puts("No");
			return 0;
		}
		c[t[i]]=s[i];
	}
	memset(c,-1,sizeof c);
	for(int i=0;i<len;i++) {
		if(c[s[i]]!=-1&&c[s[i]]!=t[i]) {
			if(t[i]==s[i]&&cnt.size()<26)
				continue;
			puts("No");
			return 0;
		}
		c[s[i]]=t[i];
	}
	puts("Yes");
	return 0;
}

D - Factorization

◇題目傳送門◆

題目大意

給定兩個數 N , M N,M N,M，要求找出 N N N個數，使得這 N N N個數的乘積等于 M M M。輸出方案數模 1 0 9 + 7 10^9+7 109+7。

思路

仔細分析可發現，這 N N N個數要麼是 1 1 1，要麼就是 N N N的質因數的乘積。

很自然的就扯到了唯一分解群組合數學上去。

記 M = p 1 a 1 p 2 a 2 ⋯ p m a m M=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m} M=p1a1​​p2a2​​⋯pmam​​，其中 p 1 , p 2 , … , p m p_1,p_2,\ldots,p_m p1​,p2​,…,pm​為質數。

當我們将 a i a_i ai​個質數 p i p_i pi​（其中 1 ≤ i ≤ m 1\le i\le m 1≤i≤m）加入到 N N N個數中，就相當于将 N + a i − 1 N+a_i-1 N+ai​−1個數分成 N − 1 N-1 N−1塊的組合數。

是以我們就可以得到：此時的方案數為 C ( N + a i − 1 , N − 1 ) C(N+a_i-1,N-1) C(N+ai​−1,N−1)。而由于在兩個方案之間，有一個數不同即被視為不同，是以，我們隻需要将所有的方案數乘上即可。

即方案數為 ∏ i = 1 m C ( N + a i − 1 , N − 1 ) \prod_{i=1}^{m}C(N+a_i-1,N-1) i=1∏m​C(N+ai​−1,N−1)

注意此時若 M ≠ 1 M\ne1 M̸​=1時，答案是還需乘上 N N N的。（請讀者自己思考）

特别注意：由于這道題要求取模，而組合數計算需要除法，是以我們必須使用逆元！不知道逆元的讀者請點這裡

接下來分析時間複雜度：

預處理階乘和逆元需要 O ( N log ⁡ 2 M o d ) O(N\log_2Mod) O(Nlog2​Mod)。

唯一分解所需要的時間為 O ( M ) O(\sqrt{M}) O(M

​)。

計算答案需要 O ( 1 ) O(1) O(1)。

又由于 N N N遠小于 M M M，是以，總時間複雜度為 O ( M ) O(\sqrt{M}) O(M

​)。

代碼 

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int Mod=1e9+7;
const int Maxn=1.5*1e5;

int N,M;

ll PowMod(ll a,int b) {
    ll ret=1;
    while(b) {
        if(b&1)ret=ret*a%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return ret;
}

ll f[Maxn+5];
ll inv[Maxn+5];

void Prepare() {
	f[0]=1;
	for(int i=1;i<=Maxn;i++)
	    f[i]=f[i-1]*i%Mod;
	inv[0]=1;
	inv[Maxn]=PowMod(f[Maxn],Mod-2);
	for(int i=Maxn-1;i>0;i--)
	    inv[i]=inv[i+1]*(i+1)%Mod;
}

ll F(int a,int b) {
    return f[a+b-1]*inv[a-1]%Mod*inv[b]%Mod;
}//C(a+b-1,a-1)

int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	scanf("%d %d",&N,&M);
	Prepare();
	int lim=sqrt(M);
	ll ans=1;
	for(int i=2;i<=lim;i++)
		if(M%i==0) {
			int cnt=0;
			while(M%i==0)
				M/=i,cnt++;
			ans=ans*F(N,cnt)%Mod;
		}
	if(M!=1)ans=ans*N%Mod;
	printf("%lld",ans);
	return 0;
}

最後給出我的排名：

【AtCoder】AtCoder Beginner Contest 110題解AtCoder Beginner Contest 110題解
# AtCoder atcoder AtCoder Beginner Contest 110
上一篇: 【Android】Scrollview傳回頂部，快速傳回頂部的功能實作，詳解代碼。
下一篇: Atcoder beginner contest 115D Christmas

繼續閱讀