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

A - Haitang and Game

Question

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

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

• 将$gcd(x,y)$插入$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;
}

E - Haitang and Math

Question

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

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

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

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

Solution

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

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

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

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

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

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

这样的时间复杂度是 $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;
}

J - Haitang and Triangle

Question

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

• 恰好有 $m$个长度为 $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\mathrm{\%}3=1$ 的位置递增，$i\mathrm{\%}3=2,i\mathrm{\%}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;
}

K - Haitang and Ava

Question

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

有效开场白的条件如下：

• 空字符串是有效的开场白。

• 如果$S$是有效的开场白，那么$S+\mathtt{\text{ava}}$和$\mathtt{\text{ava}}+S$也是有效的开场白。

• 如果$S$是有效的开场白，那么$S+\mathtt{\text{avava}}$和$\mathtt{\text{avava}}+S$也是有效的开场白。

• 任何不能用上述方法构造的字符串都不是有效的开场白。

给定一个字符串 $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;
}