竞赛讨论区 > 【题解】2023年第六届传智杯复赛第一场题解
头像
神崎兰子
发布于 2023-12-18 16:21
+ 关注

【题解】2023年第六届传智杯复赛第一场题解

补题链接：https://ac.nowcoder.com/acm/contest/72647#question

作为复赛，本场比赛难度略高于初赛，且都是原创题，总体比赛强度还是比初赛高一个档次的。复赛第一场一共8题，其中A组使用6题：BDEFGH；B组使用6题：ACDEFG

A 小红劈字符串

alt

比赛通过率：87.79%

知识点：字符串，模拟

思路：签到题。只需要判断字符串长度是否是3的倍数即可。如果是3的倍数，则在的地方添加一个空格；否则无解。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int 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 赝品

alt

比赛通过率：82.33%

知识点：数组、哈希、模拟

思路：建议使用map等哈希容器（java为HashMap，python为dict），这样可以比较方便统计每个元素的次数。另外也可以通过排序等方式来达成目的。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int 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 小红的数字分裂

alt

比赛通过率：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 小红的字符串同构

alt

比赛通过率：26.21%

知识点：组合数学

思路：我们可以先计算出满足第一个条件的字符串数量：用乘法原理计算，答案为。

然后我们需要减去和原字符串同构的情况，答案为最大的字符减去最小的字符这么多。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int 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 小红的树上赋值方案

alt

比赛通过率：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 小红的区间查询

alt

比赛通过率：5.03%

知识点：线段树、离散化

思路：直接维护区间的相交情况比较困难。我们可以首先进行离散化，然后在值域上开线段树进行维护区间和。当添加一个区间时，我们进行区间加1；删除一个区间时，我们进行区间减1。这样，问题可以转化为，如果存在一个大于1的值，则意味着存在两个区间相交。这样我们可以通过询问全局最大值解决。

参考代码：

#include <bits/stdc++.h>

using ll = long long;

template<class Info, class Tag, class Merge = std::plus<Info>>
class LazySegmentTree {
private:
    int n;
    const Merge merge{};
    std::vector<Info> info;  // data of segment tree, 1-index
    std::vector<Tag> tag;  // lazy tag of segment tree

    /* [x, y) and val: Add val to each element in range of [x, y)
     * p: The id of subtree, which is an index of vector 'info'.
     * [l, r): The range of p.
     */
    void innerPull(int p) {
        info[p] = merge(info[p << 1], info[p << 1 | 1]);
    }
    void innerApply(int p, const Tag &v, int l, int r) {
        // TODO: update the apply function
        auto applyInfo = [&](Info &a, const Tag &b, int l, int r) {
            a.min += b;
            a.max += b;
        };
        auto applyTag = [&](Tag &a, const Tag &b, int l, int r) {
            a += b;
        };
        applyInfo(info[p], v, l, r);
        applyTag(tag[p], v, l, r);
    }
    void push(int p, int l, int r) {
        if (tag[p] != Tag()) {
            int m = (l + r) / 2;
            innerApply(p << 1, tag[p], l, m);
            innerApply(p << 1 | 1, tag[p], m, r);
            tag[p] = Tag();
        }
    }
    void update_(int p, int x, int y, const Tag &v, int l, int r) {
        if (x <= l && r <= y) {
            innerApply(p, v, l, r);
            return;
        }
        int m = (l + r) / 2;
        push(p, l, r);
        if (x < m) update_(p << 1, x, y, v, l, m);
        if (y > m) update_(p << 1 | 1, x, y, v, m, r);
        innerPull(p);
    }
    /* Query the sum-up value of range [x, y). */
    Info query_(int p, int x, int y, int l, int r) {
        if (x <= l && r <= y) return info[p];
        if (x >= r || y <= l) return Info();
        int m = (l + r) / 2;
        push(p, l, r);
        return merge(query_(p << 1, x, y, l, m), query_(p << 1 | 1, x, y, m, r));
    }

public:
    LazySegmentTree(int n = 0) { init(n); }
    LazySegmentTree(std::vector<Info> &init) : LazySegmentTree(init.size()) {
        std::function<void(int, int, int)> build_ = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build_(p << 1, l, m);
            build_(p << 1 | 1, m, r);
            innerPull(p);
        };
        build_(1, 0, n);
    }
    void init(int n) {
        this->n = n;
        info.assign(4 << std::__lg(n), Info(0, 0));
        // info.resize(4 << std::__lg(n));
        tag.resize(4 << std::__lg(n));
    }
    /* Add val to each element in range of [x, y) */
    void update(int x, int y, Tag v) {
        update_(1, x, y, v, 0, n);
    }
    /* Query the sum-up value of range [x, y) */
    Info query(int x, int y) {
        return query_(1, x, y, 0, n); 
    }
};

struct MinMax {
    static constexpr int inf = 1e9;
    int min, max;
    MinMax(int min = inf, int max = -inf) : min(min), max(max) {}
    MinMax operator+(const MinMax &rhs) const {
        return MinMax(std::min(min, rhs.min), std::max(max, rhs.max));
    }
    MinMax &operator+=(const MinMax &rhs) {
        return *this = *this + rhs;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int m;
    std::cin >> m;
    std::set<std::pair<int, int>> st;
    std::vector<std::tuple<char, int, int>> ops;
    while (m--) {
        char op;
        int l, r;
        std::cin >> op >> l >> r;
        ops.emplace_back(op, l, r);

        if (op == '+') {
            assert(st.find(std::pair(l, r)) == st.end());
            st.emplace(l, r);
        } else {
            assert(st.find(std::pair(l, r)) != st.end());
            st.erase(std::pair(l, r));
        }
    }

    std::vector<int> a;
    for (auto [op, l, r] : ops) {
        a.push_back(l);
        a.push_back(r);
    }

    std::sort(a.begin(), a.end());
    a.erase(std::unique(a.begin(), a.end()), a.end());
    for (auto &[op, l, r] : ops) {
        l = std::lower_bound(a.begin(), a.end(), l) - a.begin();
        r = std::lower_bound(a.begin(), a.end(), r) - a.begin();
    }

    LazySegmentTree<MinMax, int> seg(a.size());
    for (auto [op, l, r] : ops) {
        if (op == '+') {
            seg.update(l, r, 1);
        } else {
            seg.update(l, r, -1);
        }
        if (auto [min, max] = seg.query(0, a.size()); min < 0 || max > 1) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }

    return 0;
}

G 小红和小紫的取数游戏

alt

比赛通过率：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 Hashing

int 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 小红的红色段数量

alt

比赛通过率：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;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
云从科技2020校招软件测试笔试题
美团2024年春招第一场笔试【硬件综合.软件服务方向】
2021届阅文Android方向笔试卷
全部 >
面经
面试常考问题整理
0928携程笔试题解
22届-国企上岸经验分享
面试真题：经典海量数据处理题最详解析（下）
全部 >
内推
员工内推码获取
同花顺算法内推开启！24、25届同学注意啦！
【精】拼多多2024官方校招 && 2025届实习生招聘
【TP-LINK内推】2025届提前批启动，戳我获取内推码！
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(18) 回帖
加载中...
话题 回帖
返回全部帖子

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”