Luobuyu's Blog

0%

hdu多校(第九场)

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 4.1k 阅读时长 ≈ 4 分钟
2020年hdu暑期多校训练(第九场)，题目还挺难的，博弈论还需要研究。

A. Tree

题目描述：

一棵有根树，每次移动都可以从一个节点到达他的孩子结点。在任意两个节点之间添加一条边，使 $ (x,y) $ （表示 $ x $ 可以到达 $ y $ ），数对数量最多。注意 $ (x,x) $ 也是正确的。

数据范围：
$ 1\le T \le 10^5 \\ 1\le n \le 5 \times 10^5 \\ \sum n \le 10^6 $

题解：

最优解一定是从某个叶子结点连向根节点，那么这条边上的点可以到达树上的任意一个点。直接可以 $ dfs $ 搞一遍，首先求出，不加边的情况下，每个点可以和他的子节点构成的对数。然后再次每个节点都试试，取最值。

代码：

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
#define ll long long
namespace FAST_IO
{
    template <class T>
    inline void read(T &x)
    {
        T flag = 1;
        x = 0;
        char ch = getchar();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-')
                flag = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
        {
            x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
        }
        x *= flag;
    }

    template <class T, class... _T>
    inline void read(T &x, _T &... y)
    {
        return read(x), read(y...);
    }

} // namespace FAST_IO
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
vector<int> g[maxn];
int size[maxn];
ll ans;
void dfs1(int u)
{
    size[u] = 1;
    for(int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        dfs1(v);
        size[u] += size[v];
    }
}

void dfs2(int u, ll k)
{
    ans = max(ans, k);
    for(int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        dfs2(v, k + n - size[v]);
    }
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif

    int tcase;
    read(tcase);
    while (tcase--)
    {
        read(n);
        int x;
        for(int i = 0; i <= n; i++)
        {
            g[i].clear();
        }
        for (int i = 2; i <= n; i++)
        {
            read(x);
            g[x].push_back(i);
        }

        ans = 0;
        dfs1(1);
        dfs2(1, 0);
        for (int i = 1; i <= n; i++)
        {
            ans += size[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

B.

题目描述：

数据范围：

题解：

代码：

1
2


C. Slime and Stones

题目描述：

【博弈论】给出两堆石子，每次可以单独拿一堆中的任意值，或者两堆都拿，但是两堆拿的值需满足 $ |x - y| \le k $

数据范围：
$ 1\le T \le 10^5\\ 1\le a,b, k \le 10^8 $

题解：

听说是扩展威佐夫博弈

威佐夫博弈：

两堆物品，每次可以单独拿一堆中的任意值，或者从两堆中拿相同数目的物品。（就是 $ k = 0 $ 的情况）

威佐夫博弈必败态公式推导：

【贝蒂定理（Betty Theorem）】： $ \frac{1}{a}+\frac{1}{b}=1 $ ，这里的 $ a,b $ 都是正的无理数，那么我们就有 $ P={[ma]|m为正整数},Q={[mb]|m为正整数} $ ，此时 $ P $ 与 $ Q $ 的交为空集， $ P $ 与 $ Q $ 的并正好就是 $ Z^+ $ 这个集合。证明

实际上威佐夫博弈公式来自 $ \frac{1}{a} + \frac{1}{a+1} = 1 $ ，解得 $ a = \frac{1+\sqrt{5}}{2} $ ，威佐夫博弈必败态为 $ a_n = \lfloor n \times \frac{1+\sqrt{5}}{2} \rfloor, b_n = a_n + n，b_n - a_n = n \times 1 $

猜测，本题为 $ \frac{1}{a} + \frac{1}{a+k+1} = 1 $ ，解得 $ a = \frac{1-k + \sqrt{k^2 + 2k + 5}}{2} $ ，扩展威佐夫博弈必败态为 $ a_n = \lfloor n \times \frac{1-k + \sqrt{k^2 + 2k + 5}}{2} \rfloor, \\b_n = a_n + n \times (k+1) = \lfloor n \times \frac{3 + k + \sqrt{k^2 + 2k + 5}}{2} \rfloor $

打一下表发现是正确的.

首先 $ b_n - a_n = n \times (k + 1) $ 求出 $ n $ ，数列的第 $ n $ 项。注意需要使用 $ double $ ，最后再取整

代码：

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
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define ll long long
namespace FAST_IO
{
    template <class T>
    inline void read(T &x)
    {
        T flag = 1;
        x = 0;
        char ch = getchar();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-')
                flag = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
        {
            x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
        }
        x *= flag;
    }

    template <class T, class... _T>
    inline void read(T &x, _T &... y)
    {
        return read(x), read(y...);
    }

} // namespace FAST_IO
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
ll t, n, m, k;
ll a, b;
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif

    int tcase;
    read(tcase);
    while (tcase--)
    {
        read(a, b, k);
        if(a > b)
            swap(a, b);
        ll n = b - a;
        n /= (k + 1);
        double tmp = sqrt(k * k + 2 * k + 5);
        double a1 = (1 - k + tmp) / 2.0;
        double b1 = (3 + k + tmp) / 2.0;
        if((ll)(a1 * n) != a || (ll)(b1 * n) != b)
        {
            printf("1\n");
        }
        else
        {
            printf("0\n");
        }
    }
    return 0;
}

D.

题目描述：

数据范围：

题解：

代码：

1
2


E.

题目描述：

数据范围：

题解：

代码：

1
2


F.

题目描述：

数据范围：

题解：

代码：

1
2


G.

题目描述：

数据范围：

题解：

代码：

1
2


H.

题目描述：

数据范围：

题解：

代码：

1
2


I.

题目描述：

数据范围：

题解：

代码：

1
2


J.

题目描述：

数据范围：

题解：

代码：

1
2


K.

题目描述：

数据范围：

题解：

代码：

1
2