AtCoder ABC 239题解(A ~ E)_atcoder beginner contest 239 d - prime sum game

AtCoder ABC 239

A Horizon(语法 + 数学)

$$sqrt(a\ast b)==sqrt(a)\ast sqrt(b)$$

int main()
{
    LL n;
    scanf("%lld", &n);
    double res = sqrt(n) * sqrt(12800000 + n);//防溢出
    printf("%.2f\n", res);
    return 0;
}
1
2
3
4
5
6
7
8

B Integer Division(语法)

cpp除法默认向零取整 所以如果直接写的话 -21 / 10 = -2 但题目要求我们输出-3

因为正数不受影响 所以我们只要对负数进行特判即可

int main()
{
    ULL x;
    cin >> x;
    ULL res = (x / 10) - (x % 10 < 0);
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8

C Knight Fork(暴力枚举 + 思维)

Description:

​ 给定两个点 问是否存在一个点到这两个点的距离都为sqrt(5)

Method:

​ 样例中画的图已经明示我们了 一个点只能走日字才能到达距离自己sqrt(5)的点

​ 每个点有8个这样的点 所以枚举其中一个点周围的8个点 查看8个点里是否存在符合题意的即可

Code:

int d[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {-2, -1}, {-1, -2}, {1, 2}, {2, 1}};
 
int main()
{
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    
    int f = 0;
    for(int i = 0; i < 8; i++)
    {
        int x = x1 + d[i][0], y = y1 + d[i][1];
        if((x2 - x) * (x2 - x) + (y2 - y) * (y2 - y) == 5)  f = 1;
    }
    
    if(f)   puts("Yes");
    else puts("No");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

D Prime Sum Game(博弈论 + 题意 + 枚举)

Description:

​ 甲从[a, b]选一个数告诉乙 乙从[c, d]选一个数和甲的数相加 若为素数 乙赢 反之甲赢

​ 双方均以最优策略游戏

Method:

​ 这题题意挺坑的 因为他没有说甲是知道乙的数字的

​ 如果甲不知道乙拿的是什么数字的话 甲没有策略可言 只能随机选数 这与博弈论相悖

​ 所以该题的题意其实就是 甲已经知道了乙的数字范围 问甲是否能拿出一个数 使乙任选数字都不能组成素数

​ 因为两数和不超过200 先用埃氏筛筛出200内的素数 然后枚举甲能选的数 若甲拿出了一个使乙任选数字都不能组成素数的数字 甲直接赢 return 0 反之 甲无法赢

Code:

int prime[210];
 
int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    
    for(int i = 2; i <= 210; i++) prime[i] = 1;
    for(int i = 2; i <= 210; i++)
        if(prime[i])    for(int j = i + i; j <= 210; j += i)    prime[j] = 0;
    
    for(int i = a; i <= b; i++)
    {
        int flag = 1;
        for(int j = c; j <= d; j++)
            if(prime[i + j])    flag = 0;
        if(flag)    {puts("Takahashi"); return 0;}   
    }
    puts("Aoki");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

E Subtree K-th Max(递归)

Description:

​ 给你一棵树

​ 让你输出以a为父节点的子树的第k大个节点的值

Method:

​ 因为题目中提示k小于等于20

​ 所以我们可以通过dfs爆搜来整理出每个父节点组成的子树的前20个数并用二维矩阵记录

​ 这是一个向下递归的过程

​ 步骤就是从父节点开始向下找每一个子节点的前20个数

​ 每次递归到的节点把自己的值加入到以自己的order中 然后再进行重排

​ 父节点将子节点重排后的值全部加到自己的order里进行重排

​ 最后vector res[N]就存储了以每个节点自身为子树的大到小排序的前20个值

Code:

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int x[N];
int n, q;
vector<int> g[N], res[N];//g -- 记录边 res -- 记录以dep为头结点的前20个数

void dfs(int dep, int fa)
{
    vector<int> order;
    order.push_back(x[dep]);

    for(int i = 0; i < (int)g[dep].size(); i++)//找边
    {
        int j = g[dep][i];
        if(j == fa) continue;//不能回头连向父节点
        dfs(j, dep);

        for(int k = 0; k < (int)res[j].size(); k ++)//将递归回来的数加入父节点的集合
            order.push_back(res[j][k]);
    }

    sort(order.begin(), order.end(), greater<int>());//大到小排序
    int num = min(20, (int)order.size());
    for(int i = 0; i < num; i++)
        res[dep].push_back(order[i]);
    return ;
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> x[i];

    for(int i = 1; i <= n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    dfs(1, - 1);

    while(q--)
    {
        int a, b;
        cin >> a >> b;
        cout << res[a][b - 1] << endl;
    }
    return 0;
}
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