2024牛客暑期多校训练营8 题解

# A - Haitang and Game

# Question

给定一个集合 $\textstyle S$ ，dXqwq 和海棠轮流进行以下运算，dXqwq 先进行：

找出一对 $\textstyle (x,y)$ ，使得 $\textstyle x,y\in S$ 和 $\textstyle \gcd(x,y)\notin S$ 。
将 $\textstyle \gcd(x,y)$ 插入 $\textstyle S$ 。

无法下棋的棋手输掉对局。当两位棋手都以最佳方式下棋时，您需要输出赢家。

# Solution

其实这里是一个假博弈， $S$ 是最终结果是固定的，关键在于 $|S|$ 是奇数还是偶数，考虑求 $S$ 的大小

由于 $a_i$ 不大，假设 $a_i$ 的最大值为 $M$ ，从 $M$ 到 $1$ 枚举每个数 $x$

设 $x$ 的倍数集合 $T$ 如果 $T$ 中所有数的 $\gcd$ 为 $x$ ，那么说明 $x$ 存在在 $S$ 中

# Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    int M = *max_element(A.begin(), A.end());
    vector<int> cnt(M + 1, 0);
    for (auto &a : A) cnt[a] = 1;
    int num = 0;
    for (int i = M; i >= 1; i--) {
        int g = 0;
        for (int j = i; j <= M; j += i) {
            if (cnt[j]) g = __gcd(g, j);
        }
        if (g == i) {
            if (cnt[i] == 0) {
                num += 1;
                cnt[i] = 1;
            }
        }
    }
    if (num & 1)
        cout << "dXqwq" << '\n';
    else 
        cout << "Haitang" << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    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

# E - Haitang and Math

# Question

海棠将正整数 $\textstyle m$ 的 $\textstyle S(m)$ 定义为 $\textstyle m$ 中的数字之和。

例如， $\textstyle S(154)=1+5+4=10$ ， $\textstyle S(147)=1+4+7=12$ 。

给定一个正整数 $\textstyle n$ ，数一数有多少个正整数 $\textstyle m\le n$ 使得 $\textstyle n\bmod m=S(m)$ 。

$n\le 10^{12}, T \le 100$

# Solution

考到了一个我以前不会的东西，然后就去学了一下

考虑到 $S(m)$ 其实很小，最大为 $12\times 9=108$ ，那么枚举 $S(m)$

\textstyle n\bmod m=S(m)\Longleftrightarrow n-S(m)=km

我们需要找到 $n-S(m)$ 的每个因数 $m$ ，然后去查看是否满足这个式子

容易想到把 $n-S(m)$ 质因数分解，然后用 dfs 枚举每个质因数出现的次数，从而达到高效枚举因数

思考如何质因数分解，朴素来说，质因数分解就是

for (p : prime)
    int cnt = 0
    while (x % p == 0)
        x /= p, cnt += 1

1
2
3
4

这样的时间复杂度是 $O(\sqrt x)$ 的

我们这里的 $x$ 实在区间 $[n-108, n]$ 的范围内的，这里就需要一种区间筛的东西

考虑区间内 $p_i|x$ 那么，我们很容易能得出下一个被 $p_i$ 整除的数，即 $p_i+x$ ，直到超出区间右边界

那么，如何才能找到第一个 $p_i|x$ 的 $x$ ，假设区间为 $[L,R]$ ，则 $x=\lceil\frac{L}{p_i}\rceil p_i$

这样就能把 $[L,R]$ 中的每个数进行质因数分解了

关于这个的时间复杂度，我不知道怎么计算，题解给出是 $O(T(\frac{\sqrt{n}}{\log n}+d(n)\log n))$

# Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 1e6 + 5;
constexpr int M = 108;

vector<int> prime;

int s(int x) {
    int ret = 0;
    while (x) {
        ret += x % 10;
        x /= 10;
    }
    return ret;
}

vector<int> get_prime() {
    vector<int> prime;
    vector<int> vis(maxn, 0);
    for (int i = 2; i < maxn; i++) {
        if (vis[i] == 0) {
            prime.push_back(i);
            for (int j = i + i; j < maxn; j += i)
                vis[j] = 1;
        }
    }
    return prime;
}

void solve() {
    int n; cin >> n;
    const int L = max(n - M, 1ll), R = n, len = R - L + 1;
    vector<int> a(len);
    vector<vector<pair<int, int>>> p(len, vector<pair<int, int>>(0));
    for (int i = L; i <= R; i++) a[i - L] = i;
    for (auto v : prime) {
        int pos = (L + v - 1) / v * v - L; 
        if (pos >= len) continue;
        for (int i = pos; i < len; i += v) {
            int cnt = 0;
            while (a[i] % v == 0) {
                a[i] /= v; cnt += 1;
            }
            if (cnt) p[i].push_back({v, cnt});
        }
    }
    for (int i = 0; i < len; i++) {
        if (a[i] > 1) p[i].push_back({a[i], 1});
    }
    
    set<int> ans;
    
    auto dfs = [&] (auto &&dfs, int pos, int now, vector<pair<int, int>> &p) -> void {
        auto [pr, cnt] = p[pos];
        if (pos == (int)p.size()) {
            int Sm = s(now);
            if (n % now == Sm) ans.insert(now);
            return;
        }
        for (int i = 0; i <= cnt; i++) {
            dfs(dfs, pos + 1, now, p);
            now *= pr;
        }
    };

    for (int i = 0; i < len; i++) {
        if (p[i].empty()) continue;
        dfs(dfs, 0, 1, p[i]);
    }

    cout << ans.size() << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    prime = get_prime();
    while (T--) solve();
    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
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

# J - Haitang and Triangle

# Question

给定两个整数 $\textstyle n,m$ ，构造一个长度为 $\textstyle n$ 的排列组合，它满足以下条件。

恰好有 $\textstyle m$ 个长度为 $\textstyle 3$ 的子区间，使得这些子区间中的数字构成一个（非退化的）三角形。
$0\le m \le n-2$

# Solution

雨巨说：构造题就要多手玩，然后找到一些规律和性质，其实没有想象的那么难

我们先考虑极端情况，显然 $m=n-2$ 肯定是无解，因为 $1$ 不能和其他的构成三角形

我们能构造出一种 $m=n-3$ 的方法： $[1,2,3,\cdots,n]$

然后考虑 $m=0$ 的情况，我们三个为一组，用大的数作为每组中的右端点，然后用两个小的数来尽量平衡的填在大的数之中，假设 $n=9$ ，那么一种可行的方法就是 $[3,4,7,2,5,8,1,6,9]$

通过观察可以发现， $i\%3=1$ 的位置递增， $i\%3=2,i\%3=0$ 的位置递减

然后思考 $0<m<n-2$ 的情况，其实只需要把两种方案拼起来就好了

用 $n-m$ 个拼 $m=0$ 的情况，用剩下的 $m$ 个和 $n-m$ 的后两个最大的一共 $m+2$ 个组成 $m$ 个三角形

# Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m; cin >> n >> m;
    if (m == n - 2) {cout << -1 << '\n'; return;}
    int p = n - m;
    vector<int> res(n + 1, 0);
    int l = 1, r = p;
    for (int i = p - 0; i >= 1; i -= 3) res[i] = r--;
    for (int i = p - 1; i >= 1; i -= 3) res[i] = r--;
    for (int i = p - 2; i >= 1; i -= 3) res[i] = l++;
    for (int i = p + 1; i <= n; i++) res[i] = i;
    for (int i = 1; i <= n; i++) cout << res[i] << " \n"[i == n];
    return ;
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    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

# K - Haitang and Ava

# Question

Ava 会在直播开始时说一段开场白。

有效开场白的条件如下：

空字符串是有效的开场白。
如果 $\textstyle S$ 是有效的开场白，那么 $\textstyle S+\texttt{ava}$ 和 $\textstyle \texttt{ava}+S$ 也是有效的开场白。
如果 $\textstyle S$ 是有效的开场白，那么 $\textstyle S+\texttt{avava}$ 和 $\textstyle \texttt{avava}+S$ 也是有效的开场白。
任何不能用上述方法构造的字符串都不是有效的开场白。

给定一个字符串 $\textstyle S$ ，你需要确定它是否是一个有效的开头语句。

# Solution

如果有 $avava$ 把 $avava$ 删去，有 $ava$ 把 $ava$ 删去，如果最后为一个空串，则是 Yes，否则是 No

# Code

#include <bits/stdc++.h>
using namespace std;

bool solve() {
    string s; cin >> s;
    while (!s.empty()) {
        if (s.size() >= 5 && s.substr(0, 5) == "avava") s = s.substr(5);
        else if (s.size() >= 3 && s.substr(0, 3) == "ava") s = s.substr(3);
        else break;
    }
    return s.empty();
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) cout << (solve() ? "Yes" : "No") << '\n
    return 0;
}

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

上次更新: 2025/04/08, 18:03:31

← 2024牛客暑期多校训练营7 题解 2024牛客暑期多校训练营9 题解→