补题链接：https://ac.nowcoder.com/acm/contest/72647#question作为复赛，本场比赛难度略高于初赛，且都是原创题，总体比赛强度还是比初赛高一个档次的。复赛第一场一共8题，其中A组使用6题：BDEFGH；B组使用6题：ACDEFGA 小红劈字符串比赛通过率：87.79%知识点：字符串，模拟思路：签到题。只需要判断字符串长度是否是3的倍数即可。如果是3的倍数，则在的地方添加一个空格；否则无解。参考代码：#include<bits/stdc++.h>using namespace std;#define int long longint a[101026],sum[101010];signed main(){    int n,m,i,j,k,x,y,c=0;    string s;    cin>>s;    if(s.length()%3!=0)return cout<<-1,0;    for(i=0;i<s.length();i++){        if(i*3==s.length()*2)cout<<" ";        cout<<s[i];    }}B 赝品比赛通过率：82.33%知识点：数组、哈希、模拟思路：建议使用map等哈希容器（java为HashMap，python为dict），这样可以比较方便统计每个元素的次数。另外也可以通过排序等方式来达成目的。参考代码：#include<bits/stdc++.h>using namespace std;#define int long longint a[101026],sum[101010];signed main(){    int n,i,j,k,x,y,c=0;    cin>>n;    map<int,int>m;    for(i=0;i<n;i++)cin>>x,m[x]++;    vector<int>v;    for(auto i:m){        if(i.second==1)v.push_back(i.first);    }    cout<<v.size()<<'\n';    for(auto i:v)cout<<i<<" ";}C 小红的数字分裂比赛通过率：36.61%知识点：数论、贪心思路：一个比较显然的结论是，最终需要将数组的元素变成所有元素的gcd（最大公约数）。因此每个元素需要分裂的次数可以直接求出来。这个结论的证明可以结合辗转相除法的性质，请大家自行思考。参考代码：#include <bits/stdc++.h>using namespace std;int a[101010];int main() {    int n,i,g=0;    cin>>n;    for(i=0;i<n;i++){        cin>>a[i];        g=__gcd(a[i],g);    }    long long s=0;    for(i=0;i<n;i++){        s+=a[i]/g-1;    }    cout<<s;}D 小红的字符串同构比赛通过率：26.21%知识点：组合数学思路：我们可以先计算出满足第一个条件的字符串数量：用乘法原理计算，答案为。然后我们需要减去和原字符串同构的情况，答案为最大的字符减去最小的字符这么多。参考代码：#include<bits/stdc++.h>using namespace std;#define int long longint a[101026],sum[101010];int suma[101010],sumb[101010];int pow2[101010];int mod=1e9+7;signed main(){    int n,i,j=0,k,x,y,c=0;    string s;    cin>>s;    int ma=0,mi=1e9;    int res=1;    for(auto i:s){        ma=max(ma,(int)(i-'a'));        mi=min(mi,(int)(i-'a'));        res=res*25%mod;    }    cout<<res-(26-(ma-mi+1));    }E 小红的树上赋值方案比赛通过率：4.53%知识点：树形dp思路：我们记录dp[u][i][j]代表以u节点的子树，当u节点赋值为的时候，该子树权值和模3等于的方案数。在dfs的时候转移即可。参考代码：#include <bits/stdc++.h>using ll = long long;template <typename T, auto f = std::multiplies<T>()>constexpr static T power(T a, int64_t b) {    assert(b >= 0);    T res;    if constexpr (std::is_arithmetic_v<T>) {        res = 1;    } else {        res = a.identity();    }    while (b) {        if (b & 1) {            res = f(res, a);        }        b >>= 1;        a = f(a, a);    }    return res;}template <typename T, T MOD>struct ModInt {    using prod_type = std::conditional_t<std::is_same_v<T, int>, int64_t, __int128>;    T val;    constexpr ModInt(const int64_t v = 0) : val(v % MOD) { if (val < 0) val += MOD; }    constexpr ModInt operator+() const { return ModInt(val); }    constexpr ModInt operator-() const { return ModInt(MOD - val); }    constexpr ModInt inv() const { return power(*this, MOD - 2); }    constexpr friend ModInt operator+(ModInt lhs, const ModInt rhs) { return lhs += rhs; }    constexpr friend ModInt operator-(ModInt lhs, const ModInt rhs) { return lhs -= rhs; }    constexpr friend ModInt operator*(ModInt lhs, const ModInt rhs) { return lhs *= rhs; }    constexpr friend ModInt operator/(ModInt lhs, const ModInt rhs) { return lhs /= rhs; }    constexpr ModInt &operator+=(const ModInt x) {        if ((val += x.val) >= MOD) val -= MOD;        return *this;    }    constexpr ModInt &operator-=(const ModInt x) {        if ((val -= x.val) < 0) val += MOD;        return *this;    }    constexpr ModInt &operator*=(const ModInt x) {        val = prod_type(val) * x.val % MOD;        return *this;    }    constexpr ModInt &operator/=(const ModInt x) { return *this *= x.inv(); }    bool operator==(const ModInt b) const { return val == b.val; }    bool operator!=(const ModInt b) const { return val != b.val; }    friend std::istream &operator>>(std::istream &is, ModInt &x) noexcept { return is >> x.val; }    friend std::ostream &operator<<(std::ostream &os, const ModInt x) noexcept { return os << x.val; }    constexpr static ModInt identity() { return 1; }    constexpr ModInt pow(int64_t p) { return power(*this, p); }};using Z = ModInt<int, 1'000'000'007>;int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n;    std::cin >> n;    std::string s;    std::cin >> s;    std::vector<std::vector<int>> g(n);    for (int i = 1; i < n; i++) {        int f;        std::cin >> f;        f--;        g[f].push_back(i);    }    std::vector dp(n, std::vector(3, std::vector<Z>(3)));    auto dfs = [&](auto &&self, int u) -> void {        dp[u][1][1] = 1;        dp[u][2][2] = 1;        for (auto v : g[u]) {            self(self, v);            for (int i = 1; i <= 2; i++) {                std::vector<Z> tmp(3);                for (int j = 0; j < 3; j++) {                    for (int k = 0; k < 3; k++) {                        tmp[(j + k) % 3] += dp[u][i][j] * (dp[v][1][k] + dp[v][2][k]);                    }                }                dp[u][i] = tmp;            }        }        if (s[u] == 'R') {            for (int i = 1; i <= 2; i++) {                dp[u][i][1] = 0;                dp[u][i][2] = 0;            }        }    };    dfs(dfs, 0);    auto get = [&](int u) -> Z {        Z res = 0;        for (int i = 1; i <= 2; i++) {            for (int j = 0; j < 3; j++) {                res += dp[u][i][j];            }        }        return res;    };    std::cout << get(0) << "\n";    return 0;}F 小红的区间查询比赛通过率：5.03%知识点：线段树、离散化思路：直接维护区间的相交情况比较困难。我们可以首先进行离散化，然后在值域上开线段树进行维护区间和。当添加一个区间时，我们进行区间加1；删除一个区间时，我们进行区间减1。这样，问题可以转化为，如果存在一个大于1的值，则意味着存在两个区间相交。这样我们可以通过询问全局最大值解决。参考代码：#include<bits/stdc++.h>using namespace std;struct node{    int l,r;    int ma,lz;};node t[802020];void pushup(int p){    t[p].ma=max(t[p*2].ma,t[p*2+1].ma);}void build(int p,int l,int r){    t[p].l=l;    t[p].r=r;    t[p].lz=t[p].ma=0;    if(l==r)return;    int mid=l+r>>1;    build(p*2,l,mid);    build(p*2+1,mid+1,r);    pushup(p);}void pushdown(int p){    int x=t[p].lz;    t[p*2].ma+=x;    t[p*2].lz+=x;    t[p*2+1].ma+=x;    t[p*2+1].lz+=x;    t[p].lz=0;}void add(int p,int l,int r,int x){    if(t[p].l>=l&&t[p].r<=r){        t[p].lz+=x;        t[p].ma+=x;        return;    }    if(t[p].lz)pushdown(p);    int mid=t[p].l+t[p].r>>1;    if(mid>=l)add(p*2,l,r,x);    if(mid+1<=r)add(p*2+1,l,r,x);    pushup(p);}int ask(int p,int l,int r){    if(t[p].l>=l&&t[p].r<=r){        return t[p].ma;    }    if(t[p].lz)pushdown(p);    int mid=t[p].l+t[p].r>>1,res=-1e9;    if(mid>=l)res=max(res,ask(p*2,l,r));    if(mid+1<=r)res=max(res,ask(p*2+1,l,r));    pushup(p);    return res;}vector<vector<int>>v;int main(){    int n,i,j;    cin>>n;    map<int,int>mp;    for(i=0;i<n;i++){        char c;        int x,y;        cin>>c>>x>>y;        v.push_back({c=='+',x,y});        mp[x]=mp[y]=0;    }    j=1;    for(auto &[x,y]:mp){        y=j++;    }    build(1,1,j);    for(auto i:v){        if(!i[0])add(1,mp[i[1]],mp[i[2]],-1);        else add(1,mp[i[1]],mp[i[2]],1);        if(ask(1,1,j)>1)cout<<"Yes\n";        else cout<<"No\n";    }    }G 小红和小紫的取数游戏比赛通过率：1.26%知识点：博弈，数论，哈希思路：首先我们将该博弈问题进行抽象，可以比较轻松得出以下结论：如果初始所有元素乘积为完全平方数，那么小紫获胜；否则小红获胜。因此我们可以先用的根号分解，对于次数和为奇数的素因子，我们需要使得该素因子的次数变成偶数即可。那么这道题等价为：给定一个数组，询问有多少个连续子数组满足子数组所有元素中，出现次数为奇数素因子的乘积恰好等于。（为初始给定的数的奇数次数因子乘积）。要解决这个问题，我们可以首先使用筛法，预处理出每个元素的素因子次数。然后使用哈希批量维护区间信息。在处理过程中，我们可以对初始的因子进行特殊标记，减少哈希中需要处理的不同因子数论，避免出现tle或者mle。参考代码：#include <bits/stdc++.h>using ll = long long;struct EulerSieveSimple {    const int N;    std::vector<int> minp, primes;    std::map<int, int> prime_id;    EulerSieveSimple(int n) : N(n), minp(n + 1) {        for (int i = 2; i <= N; ++i) {            if (!minp[i]) {                minp[i] = i;                prime_id[i] = primes.size();                primes.push_back(i);            }            for (auto p : primes) {                if (i * p > n) break;                minp[i * p] = p;                if (i % p == 0) break;            }        }    }    std::vector<std::pair<int, int>> prime_factors(int n) {        std::vector<std::pair<int, int>> factors;        while (n > 1) {            int p = minp[n], cnt = 0;            while (n % p == 0) {                cnt++;                n /= p;            }            factors.emplace_back(p, cnt);        }        return factors;    }} sieve(1'000'000);template <typename T, auto f = std::multiplies<T>()>constexpr static T power(T a, int64_t b) {    assert(b >= 0);    T res;    if constexpr (std::is_arithmetic_v<T>) {        res = 1;    } else {        res = a.identity();    }    while (b) {        if (b & 1) {            res = f(res, a);        }        b >>= 1;        a = f(a, a);    }    return res;}template <typename T, T MOD>struct ModInt {    using prod_type = std::conditional_t<std::is_same_v<T, int>, int64_t, __int128>;    T val;    constexpr ModInt(const int64_t v = 0) : val(v % MOD) { if (val < 0) val += MOD; }    constexpr ModInt operator+() const { return ModInt(val); }    constexpr ModInt operator-() const { return ModInt(MOD - val); }    constexpr ModInt inv() const { return power(*this, MOD - 2); }    constexpr friend ModInt operator+(ModInt lhs, const ModInt rhs) { return lhs += rhs; }    constexpr friend ModInt operator-(ModInt lhs, const ModInt rhs) { return lhs -= rhs; }    constexpr friend ModInt operator*(ModInt lhs, const ModInt rhs) { return lhs *= rhs; }    constexpr friend ModInt operator/(ModInt lhs, const ModInt rhs) { return lhs /= rhs; }    constexpr ModInt &operator+=(const ModInt x) {        if ((val += x.val) >= MOD) val -= MOD;        return *this;    }    constexpr ModInt &operator-=(const ModInt x) {        if ((val -= x.val) < 0) val += MOD;        return *this;    }    constexpr ModInt &operator*=(const ModInt x) {        val = prod_type(val) * x.val % MOD;        return *this;    }    constexpr ModInt &operator/=(const ModInt x) { return *this *= x.inv(); }    bool operator==(const ModInt b) const { return val == b.val; }    bool operator!=(const ModInt b) const { return val != b.val; }    friend std::istream &operator>>(std::istream &is, ModInt &x) noexcept { return is >> x.val; }    friend std::ostream &operator<<(std::ostream &os, const ModInt x) noexcept { return os << x.val; }    constexpr static ModInt identity() { return 1; }    constexpr ModInt pow(int64_t p) { return power(*this, p); }};namespace Hashing {constexpr uint64_t mod = 1'000'000'000'000'000'003ULL;using hash_t = ModInt<int64_t, mod>;const hash_t base = std::mt19937_64(std::chrono::steady_clock::now().time_since_epoch().count())() % mod;static std::vector<hash_t> pow{1};static void expand_pow(size_t sz) {    if (pow.size() - 1 >= sz) {        return;    }    auto old_size = pow.size();    pow.resize(sz * 2 + 1);    for (auto i = old_size; i <= sz * 2; i++) {        pow[i] = pow[i - 1] * base;    }}static void flip(uint64_t &h, int p) {    if (p >= pow.size()) {        expand_pow(p);    }    h ^= pow[p].val;}}  // namespace Hashingint main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    ll n, x;    std::cin >> n >> x;    std::vector<ll> a(n);    for (auto &i : a) {        std::cin >> i;    }    uint64_t hash_x = 0;    for (auto p : sieve.primes) {        int c = 0;        while (x % p == 0) {            x /= p;            c++;        }        if (c % 2 == 1) {            Hashing::flip(hash_x, sieve.prime_id[p]);        }    }    if (x != 1) {        std::cout << "0\n";        return 0;    }    std::vector<uint64_t> hash_a;    for (auto &i : a) {        uint64_t hash = 0;        for (auto [p, c] : sieve.prime_factors(i)) {            if (c % 2 == 1) {                Hashing::flip(hash, sieve.prime_id[p]);            }        }        hash_a.push_back(hash);    }    std::map<uint64_t, int> cnt{std::pair(0ULL, 1)};    ll ans = 0;    uint64_t cur = 0;    for (int i = 0; i < n; i++) {        cur ^= hash_a[i];        if (cnt.count(cur ^ hash_x)) {            ans += cnt[cur ^ hash_x];        }        cnt[cur]++;    }    std::cout << ans << "\n";    return 0;}H 小红的红色段数量比赛通过率：5.48%知识点：启发式合并思路：本题其实只需要求出每个节点染红后，最终排列中“红色段”数量是多少即可。该方案可以用树上启发式合并来解决：首先使用set维护子树节点信息，当添加/删除节点时，需要同时在set中查询红色段的数量影响。随后将小的子树的set合并到大的上面即可。参考代码：#include <bits/stdc++.h>using ll = long long;struct HLD {    int n;    std::vector<int> a, pos;    std::vector<int> sz, fa;    std::vector<std::vector<int>> g;    std::vector<bool> exist;    std::vector<int> ans;    int res;        HLD() {}    HLD(int n) {        init(n);    }    void init(int n) {        this->n = n;        a.resize(n);        pos.resize(n);        sz.resize(n);        fa.resize(n);        g.assign(n, {});        exist.assign(n, false);        ans.resize(n);        res = 0;    }    void addEdge(int u, int v) {        g[u].push_back(v);        g[v].push_back(u);    }    void work(int root = 0) {        fa[root] = -1;        dfs1(root);        for (int i = 0; i < n; i++) {            pos[a[i]] = i;        }        solve(root, true);    }    void dfs1(int u) {        if (fa[u] != -1) {            g[u].erase(std::find(g[u].begin(), g[u].end(), fa[u]));        }                sz[u] = 1;        for (auto &v : g[u]) {            fa[v] = u;            dfs1(v);            sz[u] += sz[v];            if (sz[v] > sz[g[u][0]]) {                std::swap(v, g[u][0]);            }        }    }    void add_subtree(int u, int ignore = -1) {        exist[pos[u]] = true;        res++;        if (pos[u] - 1 >= 0 && exist[pos[u] - 1]) {            res--;        }        if (pos[u] + 1 < n && exist[pos[u] + 1]) {            res--;        }        for (auto v : g[u]) {            if (v == ignore) continue;            add_subtree(v);        }    }    void delete_subtree(int u) {        exist[pos[u]] = false;        res--;        if (pos[u] - 1 >= 0 && exist[pos[u] - 1]) {            res++;        }        if (pos[u] + 1 < n && exist[pos[u] + 1]) {            res++;        }        for (auto v : g[u]) {            delete_subtree(v);        }    }    void solve(int u, bool keep) {        for (auto v : g[u]) {            if (v == g[u].front()) continue;            solve(v, false);        }        if (g[u].size()) {            solve(g[u].front(), true);        }        add_subtree(u, g[u].size() ? g[u].front() : -1);        ans[u] = res;        if (!keep) {            delete_subtree(u);        }    }};int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n;    std::cin >> n;    HLD hld(n);    for (auto &i : hld.a) {        std::cin >> i;        i--;    }    for (int i = 0; i < n - 1; i++) {        int u, v;        std::cin >> u >> v;        u--, v--;        hld.addEdge(u, v);    }    hld.work();    std::cout << std::fixed << std::setprecision(10);    std::cout << std::accumulate(hld.ans.begin(), hld.ans.end(), 0.) / n << '\n';    return 0;}