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

link

链接：https://ac.nowcoder.com/acm/contest/81603

A

考虑两人都操作完会形成怎样的局面，会增加多少个数，然后根据增加的数的数量的奇偶来判断先手赢还是后手赢。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

constexpr int N = 1E5;

void solve() {
    int n;
    cin >> n;
    vector<int> v(N + 1);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v[x] = 1;
    }
    
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int g = 0;
        for (int j = i; j <= N; j += i) {
            if (v[j]) {
                g = gcd(g, j);
            }
        }
        if (g == i) {
            ans++;
        }
    }
    cout << ((ans - n) % 2 ? "dXqwq" : "Haitang") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

E

发现 小于等于 ，考虑枚举 ，对 分解因子，这里使用了 pollard_rho 分解质因子后，dfs 求因子。

量级因子数量不会太多，故正确。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;
using i128 = __int128;
  
i64 power(i64 a, i64 b, i64 m) {
    i64 res = 1;
    for (; b; b >>= 1, a = i128(a) * a % m) {
        if (b & 1) {
            res = i128(res) * a % m;
        }
    }
    return res;
}
  
bool isprime(i64 p) {
    if (p < 2) {
        return false;
    }
    i64 d = p - 1, r = 0;
    while (!(d & 1)) {
        r++;
        d >>= 1;
    }
    int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (auto a : prime) {
        if (p == a) {
            return true;
        }
        i64 x = power(a, d, p);
        if (x == 1 || x == p - 1) {
            continue;
        }
        for (int i = 0; i < r - 1; i++) {
            x = i128(x) * x % p;
            if (x == p - 1) {
                break;
            }
        }
        if (x != p - 1) {
            return false;
        }
    }
    return true;
}
  
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
  
i64 pollard_rho(i64 x) {
    i64 s = 0, t = 0;
    i64 c = i64(rng()) % (x - 1) + 1;
    i64 val = 1;
    for (int goal = 1; ; goal <<= 1, s = t, val = 1) {
        for (int step = 1; step <= goal; step++) {
            t = (i128(t) * t + c) % x;
            val = i128(val) * abs(t - s) % x;
            if (step % 127 == 0) {
                i64 g = gcd(val, x);
                if (g > 1) {
                    return g;
                }
            }
        }
        i64 g = gcd(val, x);
        if (g > 1) {
            return g;
        }
    }
}
 
unordered_map<i64, int> getprimes(i64 x) {
    unordered_map<i64, int> p;
    function<void(i64)> get = [&](i64 x) {
        if (x < 2) {
            return;
        }
        if (isprime(x)) {
            p[x]++;
            return;
        }
        i64 mx = pollard_rho(x);
        get(x / mx);
        get(mx);
    };
    get(x);
    return p;
}
  
vector<i64> getfac(i64 x) {
    vector<i64> fac;
    auto primes = getprimes(x);
    vector<pair<i64, int>> tmp(primes.begin(), primes.end());
    int SIZE = tmp.size();
    function<void(int, i64)> dfs = [&](int id, i64 x) {
        if (id == SIZE) {
            fac.push_back(x);
            return;
        }
        i64 p = 1;
        for (int i = 0; i <= tmp[id].second; i++) {
            if (i != 0) {
                p *= tmp[id].first;
            }
            dfs(id + 1, x * p);
        }
    };
    dfs(0, 1);
    return fac;
}

void solve() {
    i64 n;
    cin >> n;

    vector<i64> ans;
    for (int S = 1; S < 109; S++) {
        if (S > n) {
            break;
        }
      
        auto v = getfac(n - S);
        for (auto &m : v) {
            string s = to_string(m);
            int sum = 0;
            for (auto &si : s) {
                sum += si - '0';
            }
            if (n % m == sum) {
                ans.push_back(m);
            }
        }
    }

    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    
    cout << ans.size() << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

J

发现除 ，相邻三个数字能构成三角形，考虑构造最后数组 相邻三个数无法构成三角形， 相邻三个数能构成三角形。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

K

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; ) {
        if (s.substr(i, 5) == "avava") {
            i += 5;
        } else if (s.substr(i, 3) == "ava") {
            i += 3;
        } else {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}