训练赛3 - ゆき

题目链接#

A. Submission Bait#

题解#

先考虑只有一种权值的情况。显然此时若 $n$ 为奇数，则先手必胜，否则先手必败。

然后考虑多种权值。发现若所有权值的出现次数均为偶数，则先手必败，否则先手仅需选择最大的出现次数为奇数的权值，即可令后手进入必败状态。

于是仅需检查是否有一种权值出现次数为奇数即可。

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    map<int, int> cnt;
6
    for (int i = 1; i <= n; i++) {
7
        int x;
8
        cin >> x;
9
        cnt[x]++;
10
    }
11
    if (any_of(cnt.begin(), cnt.end(), [](const pair<int, int> &x) {
12
        return x.second % 2 == 1;
13
    })) {
14
        cout << "YES\n";
15
    } else {
16
        cout << "NO\n";
17
    }
18
}

B. Array Craft#

题解#

令 $[y,x]$ 均为 $1$ ，从 $y - 1, x + 1$ 开始，分别向左右构造成 $-1/1$ 交替的形式。

前缀和满足如下形式：

$1,0,1,0,1_y,2_x,1,0,1,...$
$-1,0,-1,0_y,1_x,0,1,...$

后缀和满足如下形式：

$...,0,1,2_y,1_x,0,1,0,1$
$...,1,0,1_y,0_x,-1,0,-1$

$x, y$ 均满足要求

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    int x, y;
6
    cin >> x >> y;
7
    vector<int> ans(n + 1);
8
    for (int i = y; i <= x; i++) {
9
        ans[i] = 1;
10
    }
11
    for (int i = x + 1; i <= n; i++) {
12
        ans[i] = -ans[i - 1];
13
    }
14
    for (int i = y - 1; i >= 1; i--) {
15
        ans[i] = -ans[i + 1];
16
    }
17
    for (int i = 1; i <= n; i++) {
18
        cout << ans[i] << " \n"[i == n];
19
    }
20
}

C. Mad MAD Sum#

题解#

打表发现在第二次操作后，数组一定单调递增，且除了最大的权值外每种权值至少出现 $2$ 次，每次操作后，数组右移一位。

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    ll sum = 0;
6
    vector<int> a(n + 1);
7
    for (int i = 1; i <= n; i++) {
8
        cin >> a[i];
9
    }
10
    for (int j = 1; j <= 2; j++) {
11
        int tmp = 0;
12
        map<int, int> mp;
13
        for (int i = 1; i <= n; i++) {
14
            sum += a[i];
15
            mp[a[i]]++;
16
            if (mp[a[i]] >= 2) {
17
                tmp = max(tmp, a[i]);
18
            }
19
            a[i] = tmp;
20
        }
21
    }
22
    ll tmp = 0;
23
    for (int i = 1; i <= n; i++) {
24
        tmp += a[i];
25
    }
26
    for (int i = n; i >= 1; i--) {
27
        sum += tmp;
28
        tmp -= a[i];
29
    }
30
    cout << sum << '\n';
31
}

D. Linear Maze#

题解#

当访问到普通房间时，步数 $+ 1$ ，如果访问到特殊房间，则步数 $+ 1$ 后翻倍，显然访问到特殊房间后，回到该房间需要重新走相同的路程

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, k;
4
    cin >> n >> k;
5
    vector<int> a(n + 1);
6
    for(int i = 1;i <= k; i ++){
7
        int x;
8
        cin >> x;
9
        a[x] = 1;
10
    }
11
    ll ans = 0;
12
    for(int i = 1;i <= n; i++){
13
        ans ++;
14
        if(a[i]) ans *= 2;
15
    }
16
    cout << ans << '\n';
17
}

E. Grid Puzzle#

题解#

显然，由于 $2 \times 2$ 只能对相邻两行进行，对于 $(i, i + 1)$ 行，至多只进行 $1$ 次 $2 \times 2$ 操作，否则使用 $2$ 次覆盖行操作一定更优。

故考虑 $dp$ ，令 $dp_{i,0/1/2}$ 表示覆盖了前 $i$ 行，且第 $i$ 行用 $2 \times 2$ 覆盖了第 $i + 1$ 行的 $0 / 1-2/ 3-4$ 个格子的最小操作数

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    vector<int> a(n + 1);
6
    for (int i = 1; i <= n; i++)
7
        cin >> a[i];
8
    vector<vector<int> > dp(n + 1, vector<int>(3, INF));
9
    dp[0][0] = 0;
10
    for (int i = 1; i <= n; i++) {
11
        if (a[i] == 0) dp[i][0] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
12
        else dp[i][0] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}) + 1;
13
        if (a[i] <= 2) {
14
            dp[i][0] = min(dp[i][0], dp[i - 1][1]);
15
            dp[i][1] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}) + 1;
16
        } else if (a[i] <= 4) {
17
            dp[i][1] = dp[i - 1][2] + 1;
18
            dp[i][2] = dp[i - 1][1] + 1;
19
        }
20
    }
21
    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
22
}

F. Catch the Mole#

题解#

对于树高根号分治，目标是把老鼠逼到一条链上，最后二分找到位置

先对一个叶子节点进行 $\sqrt{5000} = 70$ 次无效询问，这样所有树高小于 $70$ 的点必然不存在老鼠
对于树高大于 $70$ 的，从根节点开始递归询问。对于一个节点的儿子，只有树高大于 $70$ 才被询问，小于 $70$ 的直接跳过即可
询问为真或者只有一个儿子的时候就直接递归进去，为假就下一个儿子因此这样的询问最多 $70$ 次。
最后二分即可完成，注意每次查询失败的时候，左右边界都要向根偏移一个位置

代码#

1
const int N = 70;
2

3
int ask(int x) {
4
    cout << "? " << x << endl;
5
    int res;
6
    cin >> res;
7
    return res;
8
}
9

10
# define answer(x) do { cout << "! " << x << endl; return;} while (0)
11

12
void idol_produce(int testCase) {
13
    /*Code Here*/
14
    int n;
15
    cin >> n;
16
    vector<vector<int>> e(n + 1);
17
    for (int i = 1; i <= n - 1; i++) {
18
        int u, v;
19
        cin >> u >> v;
20
        e[u].emplace_back(v);
21
        e[v].emplace_back(u);
22
    }
23
    vector<int> father(n + 1, 0), h(n + 1);
24
    function<void(int, int)> dfs = [&](int u, int fa) -> void {
25
        for (auto v: e[u]) {
26
            if (v == fa) {
27
                continue;
28
            }
29
            father[v] = u;
30
            dfs(v, u);
31
            h[u] = max(h[u], h[v] + 1);
32
        }
33
    };
34
    dfs(1, 0);
35
    int tmp = find(h.begin() + 1, h.end(), 0) - h.begin();
36
    for (int i = 1; i <= N; i++) {
37
        if (ask(tmp) == 1) {
38
            answer(tmp);
39
        }
40
    }
41
    function<int(int)> dfs2 = [&](int u) -> int {
42
        vector<int> son;
43
        for (auto v: e[u]) {
44
            if (v == father[u] || h[v] < N) {
45
                continue;
46
            }
47
            son.emplace_back(v);
48
        }
49
        if (son.empty()) {
50
            return u;
51
        }
52
        for (auto x: son) {
53
            if (x == son.back() || ask(x) == 1) {
54
                return dfs2(x);
55
            }
56
        }
57
        assert(false);
58
    };
59
    int end = dfs2(1);
60
    vector<int> a;
61
    for (int i = end; i != 0; i = father[i]) {
62
        a.emplace_back(i);
63
    }
64
    reverse(a.begin(), a.end());
65
    int l = 0, r = a.size() - 1;
66
    while (l < r) {
67
        int mid = (l + r + 1) >> 1;
68
        if (ask(a[mid]) == 1) {
69
            l = mid;
70
        } else {
71
            r = mid - 1;
72
            l = max(0, l - 1);
73
            r = max(0, r - 1);
74
        }
75
    }
76
    answer(a[l]);
77
}