【AtCoder】AtCoder Beginner Contest 110题解

AtCoder Beginner Contest 110题解

A - Maximize the Formula

◇题目传送门◆

题目大意

给定三个数字$A,B,C$，要求使用这三个数字组成一个两位数及一个一位数，使得他们的和最大

思路

似乎没有什么可以讲的，直接给出代码吧。

代码

#include<cstdio> #include<algorithm> using namespace std;int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint 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$和数轴上的两个点$X,Y$与$N$个点$x_1,x_2,x_3,\dots ,x_N$和$M$个点$y_1,y_2,y_3,\dots ,y_M$，要求找出一个点$Z$，使得它满足以下条件：

• $X<Z\le Y$
• $x_1,x_2,x_3,\dots ,x_N<Z$
• $y_1,y_2,y_3,\dots ,y_M\ge Z$

思路

我们记$x_0=X,y_0=Y$，仔细分析题目可以发现，当存在max?{x0,x1,x2,…,xN}&lt;min?{y0,y1,y2…,yM}\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$存在。

所以直接给出代码：

代码

#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 LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%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$相同：

操作：从26个字母中选择两个字母$c_1,c_2$，在$S$中，将所有的$c_1$替换为$c_2$，所有的$c_2$替换为$c_1$。

思路

不难发现在串$S$中，每个字母和串$T$中的每个字母是有一一对应的关系。所以我们考虑在串$S$中是否满足这个对应关系，在串$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 LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%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$个数，使得这$N$个数的乘积等于$M$。输出方案数模$10^9+7$。

思路

仔细分析可发现，这$N$个数要么是$1$，要么就是$N$的质因数的乘积。

很自然的就扯到了唯一分解和组合数学上去。

记$M=p_1^{a_1}{p}_2^{a_2}?p_m^{a_m}$，其中$p_1,p_2,\dots ,p_m$为质数。

当我们将$a_i$个质数$p_i$（其中$1\le i\le m$）加入到$N$个数中，就相当于将$N+a_i?1$个数分成$N?1$块的组合数。

所以我们就可以得到：此时的方案数为$C(N+a_i?1,N?1)$。而由于在两个方案之间，有一个数不同即被视为不同，所以，我们只需要将所有的方案数乘上即可。

即方案数为$$\prod _{i=1}^{m}C(N+a_i?1,N?1)$$

注意此时若$M?=1$时，答案是还需乘上$N$的。（请读者自己思考）

特别注意：由于这道题要求取模，而组合数计算需要除法，所以我们必须使用逆元！不知道逆元的读者请点这里

接下来分析时间复杂度：

预处理阶乘和逆元需要$O(N{\log }_{2}Mod)$。

唯一分解所需要的时间为$O(\sqrt{M})$。

计算答案需要$O(1)$。

又由于$N$远小于$M$，所以，总时间复杂度为$O(\sqrt{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 LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%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; } 

最后给出我的排名：