AtCoder Beginner Contest 198 A~E 题解

English

A - Div

题目大意

两个男孩要分$N$颗糖。问一共有几种分法（每个男孩都必须分到糖）？

$1\le N\le 15$

输入格式

$N$

输出格式

将答案输出为一个整数。

样例

$N$输出
$2$$1$
$1$$0$
$3$$2$

分析

这题说白了就是将$N$分成$A$和$B$两个正整数的和（$A+B$和$B+A$是两种分法），所以列表如下：

$A$$B$
$1$$N-1$
$2$$N-2$
$\dots$$\dots$
$N-1$$1$
这个表一共有$N-1$项，所以我们直接输出$N-1$即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", n - 1);
    return 0;
}

B - Palindrome with leading zeros

题目大意

给定一个整数$N$。
是否可以在$N$的十进制表示的前面填上任意（可以为$0$）个0，使得$N$变成一个回文数？

$0\le N\le 10^9$

输入格式

$N$

输出格式

输出Yes或者No。

样例

$N$输出
$1210$Yes
$777$Yes
$123456789$No

分析

如果能在$N$的前面加上一些0使得$N$变成一个回文数，那么将$N$去掉末尾的所有0后也一定能得到一个回文数。所以，我们只需将$N$末尾的0去掉后，再判断它是不是一个回文数即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <cstdio>
using namespace std;

char s[10];

int main()
{
    char c;
    int len = 0;
    while((c = getchar()) != '\n')
        s[len++] = c;
    while(len > 0 && s[--len] == '0');
    for(int i=0; i<=len; i++)
        if(s[i] != s[len - i])
        {
            puts("No");
            return 0;
        }
    puts("Yes");
    return 0;
}

C - Compass Walking

题目大意

在一个二维的平面上，一个人每一步都只能走正好$R$个距离单位。
这个人从$(0,0)$走到$(X,Y)$至少需要多少步？
注意：在二维平面上，两个点$(x_1, y_1)$和$(x_2,y_2)$的距离是$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

$1\le R\le 10^5$
$0\le X,Y\le 10^5$
$(X,Y)\ne(0,0)$

输入格式

$R~X~Y$

输出格式

输出一行，即最少需要的步数。

样例

$R$$X$$Y$输出
$5$$15$$0$$3$
$5$$11$$0$$3$
$3$$4$$4$$2$

分析

我们可以先定义$d=\sqrt{X^2+Y^2}$，即$(X,Y)$到$(0,0)$的距离，则有如下解法：

  • 如果$d = R$，则总共只需要$1$步。
  • 如果$d < R$，则总共需要$2$步。
  • 如果$d > R$，总共需要$\lceil\frac d r\rceil$步。

这样，我们就可以写代码了。

代码

这题很容易出现精度问题，但我用long double居然卡过去了……

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

int main()
{
    int r, x, y;
    scanf("%d%d%d", &r, &x, &y);
    long double dist = hypotl(x, y);
    if(dist == r) puts("1");
    else if(dist < r) puts("2");
    else printf("%d\n", int(ceill(dist / r)));
    return 0;
}

D - Send More Money

题目大意

注意：本题的时间限制是$5$秒。
给定三个由小写字母组成的字符串$S_1,S_2,S_3$。
在这里，相同的字母表示相同的数字，不同的字母表示不同的数字。
我们要找到一种每个字母对应的数字，并将它们分别填入$S_1,S_2,S_3$，变成三个无前导$0$的正整数$N_1,N_2,N_3$，使得$N_1+N_2=N_3$。如果有多组解，找到任意一组即可。

$1\le |S_1|,|S_2|,|S_3|\le 10$

输入格式

$S_1$
$S_2$
$S_3$

输出格式

如果有解，输出三行，即$N_1,N_2$和$N_3$；如果无解，输出UNSOLVABLE。

样例

$S_1$$S_2$$S_3$输出
abc1 2 3
xxy1 1 2
pqpUNSOLVABLE

分析

很容易想到，因为每位能填的数字只有$0$到$9$（一共$10$个），所以如果$S_1,S_2$和$S_3$中总共不同的字母个数超过$10$个，我们就可以直接认为这个等式无解。
现在，由于这道题时间限制较长，我们就可以暴力枚举每一种字母对应的数字（一共最多有$10!=3628800$种可能），再逐个填入并验证即可。

代码

这里的枚举我是用全排列做的，当然也可以用回溯法等，方法不限。

 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
56
57
58
59
60
61
62
63
64
65
66

#include <cstdio>
#include <set>
#include <algorithm>
#define maxl 15
using namespace std;

using LL = long long;

char s1[maxl], s2[maxl], s3[maxl], ch[maxl];

set<char> chars;
int pos[26], num[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

#define N (num[pos[str[i] - 'a']])
inline LL parse(const char* str)
{
    LL res = 0LL;
    for(int i=0; str[i]; i++)
        res = res * 10LL + N;
    return res;
}

inline void print(const char* str)
{
    for(int i=0; str[i]; i++)
        putchar(N + '0');
    putchar('\n');
}
#undef N

inline void add(const char* str)
{
    for(int i=0; str[i]; i++)
        chars.insert(str[i]);
}

inline bool isok(const char* str)
{
    return num[pos[str[0] - 'a']] != 0;
}

int main()
{
    scanf("%s%s%s", s1, s2, s3);
    add(s1), add(s2), add(s3);
    if(chars.size() > 11)
    {
        puts("UNSOLVABLE");
        return 0;
    }
    int cnt = 0;
    for(char x: chars)
        pos[x - 'a'] = cnt++;
    do
    {
        if(isok(s1) && isok(s2) && isok(s3) && (parse(s1) + parse(s2) == parse(s3)))
        {
            print(s1);
            print(s2);
            print(s3);
            return 0;
        }
    } while(next_permutation(num, num + 10));
    puts("UNSOLVABLE");
    return 0;
}

P.S. 这段代码的运行速度不可思议的快…… 居然只花了$109$ms……

E - Unique Color

题目大意

给你一棵由编号为$1,2,~\dots,N$的$N$个顶点组成的树。其中，第$i$条边连接着顶点$A_i$和$B_i$。第$i$个顶点的颜色是$C_i$（在这里，颜色用一个整数表示）。
我们定义一个顶点$x$是好的，仅当如下条件成立：

  • 从顶点$1$到顶点$x$的最短路径上，没有与顶点$x$颜色相同的点（顶点$x$本身除外）。

找到所有的好的顶点。

$2\le N\le 10^5$
$1\le C_i\le 10^5$
$1\le A_i,B_i\le 10^5$

输入格式

$N$
$C_1~\dots~C_N$
$A_1~B_1$
$\vdots$
$A_{N-1}~B_{N-1}$

输出格式

输出所有的好的顶点，按升序排序，每行一个。

样例

略，请自行前往AtCoder查看

分析

其实这题用最朴素的$\text{DFS}$算法就能解决。
我们在搜索的同时，维护一个$\text{used}$数组，记录每个颜色在路径上是否已经用过。这样，我们就能$\mathcal O(1)$地判断每个点是否是一个好的点，最后排序并输出即可。

代码

 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

#include <cstdio>
#include <vector>
#include <set>
#define maxn 100005
using namespace std;

vector<int> G[maxn];
bool used[maxn];
int color[maxn];

set<int> res;

void dfs(int v, int par)
{
    if(used[color[v]])
    {
        for(int u: G[v])
            if(u != par)
                dfs(u, v);
        return;
    }
    used[color[v]] = true;
    res.insert(v);
    for(int u: G[v])
        if(u != par)
            dfs(u, v);
    used[color[v]] = false;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", color + i);
    while(--n)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, -1);
    for(int v: res)
        printf("%d\n", v);
    return 0;
}
© 2020 - 2026 GoodCoder's Blog
使用 Hugo 构建
主题 Stack 由 Jimmy 设计