AtCoder Beginner Contest 110 题解

AtCoder Beginner Contest 110

A - Maximize the Formula

题目大意

给出三个正整数$A,B,C \leq 9$,可以任意排列,然后在其中一个位置插入一个$+$号。可以得到一个两位数和一个一位数的和。求出这个最大和。

题解

简单的入门题。枚举两位数的十位、个位以及一位数分别是哪个即可。

分别算出答案,取max。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
inline int read () {
int num = 0;
char c = ' ';
bool flag = true;
for (;c > '9' || c < '0';c = getchar())
if (c == '-')
flag = false;
for (;c >= '0' && c <= '9';num = (num << 1) + (num << 3) + c - 48, c = getchar());
return flag ? num : -num;
}
int main () {
int a = read();
int b = read();
int c = read();
int t1 = a * 10 + b + c;
int t2 = b * 10 + a + c;
int t3 = c * 10 + a + b;
printf("%d",max(max(t1, t2), t3));
return 0;
}

B - 1 Dimensional World’s Tale

题目大意

给出两个正整数$X,Y$和长度分别为$N$和$M$的序列${x_i}$和${y_i}$。要求我们判断是否存在这样一个整数$Z$,满足

$X<Z\leq Y$

$x_1,x_2,…,x_N<Z$

$y_1,y_2,…,x_M\geq Z$

只需要判断存在性即可。

题解

我们知道满足下面两个条件,只要满足$\max {x_i} \leq Z \leq \min {y_i}$即可。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
inline int read () {
int num = 0;
char c = ' ';
bool flag = true;
for (;c > '9' || c < '0';c = getchar())
if (c == '-')
flag = false;
for (;c >= '0' && c <= '9';num = (num << 1) + (num << 3) + c - 48, c = getchar());
return flag ? num : -num;
}
const int maxn = 120;
int n,m,X,Y,x[maxn],y[maxn];
void init () {
n = read(); m = read();
X = read(); Y = read();
for (int i = 1;i <= n;i ++)
x[i] = read();
for (int i = 1;i <= m;i ++)
y[i] = read();
sort(x + 1,x + 1 + n);
sort(y + 1,y + 1 + m);
}
bool work () {
if (X >= Y) return false;
if (x[n] >= y[1]) return false;
if (x[n] >= Y) return false;
if (y[1] <= X) return false;
return true;
}
int main () {
init ();
if (!work ()) printf("War\n");
else printf("No War\n");
return 0;
}

C - String Transformation

题目大意

给出两个字符串$S$和$T$(满足长度相同)。现在有一种操作:选定两个字符$c_1$和$c_2$,把$S$中的所有$c_1$变成$c_2$,所有的$c_2$变成$c_1$。现在问,能否通过若干次这样的操作,使$S$能变化到$T$。

题解

这道题目肯定不需要去求出操作中间的每一个步骤什么的……那就是搜索题了。我们只要判断哪些情况有解,哪些情况无解即可。这道题目大概需要满足两个条件:

我们先考虑每一次变换:假设字符$c_1$的出现次数是$x_1$,字符$c_2$的出现次数是$x_2$,对于一次交换操作,是把$x_1$和$x_2$的值进行了交换。所以我们设想这么一个集合$X={x_i}$,里面记录了所有字符的出现个数,那么$S$的集合$X$和$T$的集合$X$应该拥有相同的元素。这就是第一个条件。

我们继续考虑:如果对于$S$,两个位置上有相同的字母,那么$T$上这两个位置也应该有相同的字母;反之亦然。这就是第二个条件。

所以我们只要对每一个字符串的每一个位置进行这样的编号:每一次碰到一个字母,首先看它有没有在之前出现过,如果没有出现过,那么先给这个字母编号,然后在这个位置填上这个字母的编号;如果它已经出现过了,那么直接在这个位置上填上这个字母的编号。时间复杂度$O(n)$。随后我们得到了这个字符串的一个“特征序列”,如果$S$和$T$的特征序列相同,那么有解,反之无解。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
inline int read () {
int num = 0;
char c = ' ';
bool flag = true;
for (;c > '9' || c < '0';c = getchar())
if (c == '-')
flag = false;
for (;c >= '0' && c <= '9';num = (num << 1) + (num << 3) + c - 48, c = getchar());
return flag ? num : -num;
}
const int maxn = 200020;
char s[maxn],t[maxn];
int n;
void init () {
scanf("%s",s + 1);
scanf("%s",t + 1);
n = strlen(s + 1);
}
int a[maxn],map1[maxn],cnt1 = 0;
//a是特征序列,map记录了每个字母的编号
//cnt是时间戳
void work1 () {
for (int i = 1;i <= n;i ++) {
int c = (int)s[i];
if (map1[c] == 0)//如果没有出现过
map1[c] = ++ cnt1;
//给字母编号
a[i] = map1[c];
//填上编号
}
}
int b[maxn],map2[maxn],cnt2 = 0;
void work2 () {
for (int i = 1;i <= n;i ++) {
int c = (int)t[i];
if (map2[c] == 0)
map2[c] = ++ cnt2;
b[i] = map2[c];
}
}
int main () {
init ();
work1 ();
work2 ();
for (int i = 1;i <= n;i ++)
if (a[i] != b[i]) {
printf("No\n");
return 0;
}
printf("Yes\n");
return 0;
}

D - Factorization

题目大意

给出两个正整数$N(N\leq 1e5)$ ,$M(M\leq 1e9)$。求出满足下述条件的序列的方案数(模1000000007):

$a_1\times a_2 \times …\times a_N = M$

其中所有的$a_i$都是正整数。

题解

先把$M$标准分解,得到$M=p_1^{q_1}\times p_2^{q_2}\times p_3^{q_3}\times …\times p_k^{q_k}$那么原问题就转化为了:有$\sum_{i=1}^k q_i$个物品放到$N$个箱子里(允许有空箱子),其中有$q_1$个、$q_2$个……$q_k$个是分别相同的。

我们很容易发现,每一个质因子的方案是互不干扰的,所以我们最后可以通过每个质因子的方案数乘法原理连乘得到。

我们根据数学知识知道,如果$n$个相同的物品放到$m$个不同的箱子里,不允许有盒子是空的,方案数是$C_{n - 1} ^{m - 1}$。原问题可以先转化为$n + m$个物品放到$m$个不同的箱子里,但是不允许有盒子是空的;那么就是$C_{n + m - 1} ^{m - 1}$。

我们考虑每一个质因子。也就是$p_i$个相同的物品放到$N$个不同的箱子里面的方案数。用上述结论可以轻易算出是$C_{q[i] + n - 1}^{n - 1}$,然后再连乘即可。

随后有一个问题:如何快速求出组合数?

方法一:$lucas$定理。难实现。

方法二:递推(杨辉三角)。我们知道$C_{q_i + n - 1}^{n - 1} = C_{q_i + n - 1}^{q_i}$,而因为$1e9< 2^{31}$,所以$q_i < 31$,所以只要求出前$n$行前$31$列的杨辉三角即可,时间复杂度$O(n)$.

总时间复杂度$O(sqrt(m) + n)$

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
inline int read () {
int num = 0;
char c = ' ';
bool flag = true;
for (;c > '9' || c < '0';c = getchar())
if (c == '-')
flag = false;
for (;c >= '0' && c <= '9';num = (num << 1) + (num << 3) + c - 48, c = getchar());
return flag ? num : -num;
}
int n,m;
const int maxn = 102000;
const int p = 1000000007;
namespace get_apart {
int q[maxn],cnt;
void work (int x) {
for (int i = 2;i <= sqrt (x);i ++)
if (x % i == 0) {
cnt ++;
while (x % i == 0) {
q[cnt] ++;
x /= i;
}
}
if (x != 1)
q[++ cnt] = 1;
}
} using namespace get_apart;
long long C[maxn][50];
void pre_work () {
C[0][0] = C[1][0] = C[1][1] = 1;
for (int i = 0;i <= n;i ++) {
C[i][0] = 1 ;
if (i <= 40) C[i][i] = 1;
}
for (int i = 2;i <= n + 40;i ++)
for (int j = 1;j <= min(i + 1,40);j ++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
C[i][j] %= p;
}
}
int main () {
n = read(); m = read();
get_apart :: work (m);
pre_work ();
long long ans = 1;
for (int i = 1;i <= cnt;i ++) {
ans *= C[q[i] + n - 1][q[i]];
ans %= p;
}
cout << ans << endl;
return 0;
}
文章目录
  1. 1. AtCoder Beginner Contest 110
    1. 1.1. A - Maximize the Formula
      1. 1.1.1. 题目大意
      2. 1.1.2. 题解
      3. 1.1.3. code
    2. 1.2. B - 1 Dimensional World’s Tale
      1. 1.2.1. 题目大意
      2. 1.2.2. 题解
      3. 1.2.3. code
    3. 1.3. C - String Transformation
      1. 1.3.1. 题目大意
      2. 1.3.2. 题解
      3. 1.3.3. code
    4. 1.4. D - Factorization
      1. 1.4.1. 题目大意
      2. 1.4.2. 题解
      3. 1.4.3. code