比赛日期: 2025-02-27

Educational Codeforces Round 175 (Rated for Div. 2)

比赛链接: https://codeforces.com/contest/2070

糖丸的一把。。。D只是个基础的bfs或者观察一下就好了，但是没写出来。

跟状态有关系吧，也是基本没咋写过bfs了，也是菜了。但是无所谓，无论如何，都要打比赛，掉分没有任何影响，做题永远是比 rating 和其他东西重要的。感觉这种实时的比赛，确实很不一样啊。

题写多了，变强是必然事件。只要写题写得够多，积累够多，那么上分、比赛体验变好，这些都是自然而然的事情。

A

没啥好说的，观察一下，发现每15个数字会出现3个满足的。

void solve()
{
    //0 1 2,15 16 17,30 31 32
    int n;
    cin>>n;
    int ans=n/15*3;
    for(int i=0;i<=min(2,n%15);i++)
        ans++;
    cout<<ans<<'\n';
}

B

这个就很明显吧，显然判开始能不能到0，如果能到，看后面一次回到0要多长时间。

void solve()
{
    int n, x;
    long long k;
    cin >> n >> x >> k;
    // 看-x有没有出现过
    // 然后再看 0 出现一次要多久
    string s;
    cin >> s;
    vector<int> pre(n + 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1];
        if (s[i - 1] == 'L')
            pre[i]--;
        else
            pre[i]++;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (pre[i] == -x && i <= k) {
            ans++;
            k -= i;
            break;
        }
    }
    if(!ans){
        cout<<"0\n";
        return;
    }
    for (int i = 1; i <= n; i++) {
        if(pre[i]==0){
            ans+=k/i;
            break;
        }
    }
    cout<<ans<<'\n';
}

C

可以考虑二分。因为这个肯定是一个单调的。

检查的时候，如果是蓝色且值大于我们检查的值 \(x\) ，那么肯定需要用一次机会。如果是红色，如果我们前一个是包含在我们选的段里面，我们肯定希望这个段能尽量的长。

void solve()
{
    int n, k;
    cin >> n >> k;
    vi a(n + 1);
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    s = " " + s;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'B' && s[i] != s[i - 1]){
            cnt++;
        }
    }
    if (cnt <= k) {
        cout << "0\n";
        return;
    }
    auto check=[&](int val){
        int res=0;
        bool use=false;
        for(int i=1;i<=n;i++){
            if(s[i]=='B'){
                if(use){
                    continue;
                }else{
                    if(a[i]>val){
                        res++;
                        use=true;
                    }
                }
            }else{
                if(a[i]>val) use=false;
            }
        }
        return res<=k;
    };
    int lo = 0, hi = INF+1;
    while(lo<hi-1){
        int mid=(lo+hi)>>1;
        if(check(mid)) hi=mid;
        else lo=mid;
    }
    cout<<hi<<'\n';
}

D

...最无语的一集。唉唉，起码做出来了。。。

最开始一直wa，但是没想到哪wa了，状态不太好哈。。。

而且bfs直接把相连的子节点加入队列就行啊。我太唐了。

不用bfs也可以写，因为其实每一层的每一个点，它们对答案的贡献一定是相同的。

constexpr int mod = 998244353; // 998244353

void solve()
{
    int n;
    cin >> n;
    vi p(n + 1);
    vector<vi> adj(n + 1, vi());
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
        adj[p[i]].push_back(i);
    }
    vi d(n + 1);
    // vector<vi> g(n + 1, vi());
    vi cnt(n+1);
    auto dfs1 = [&](auto&& self, int u) -> void {
        // g[d[u]].push_back(u);
        cnt[d[u]]++;
        for (auto v : adj[u]) {
            d[v] = d[u] + 1;
            self(self, v);
        }
    };
    dfs1(dfs1, 1);
    vector<ll> res(n + 1);
    ll ans = 1;
    res[1] = 1;
    // auto dfs = [&](auto&& self, int u) -> void {
    //     for (auto v : g[d[u] + 1]) {
    //         if ((u != 1) && (p[v] == u))
    //             continue;
    //         // ans=(ans+res[u])%mod;
    //         res[v] = (res[v] + res[u]) % mod;
    //         // self(self, v);

    //     }
    // };
    // dfs(dfs, 1);
    // for(int i=0;i<n;i++){
    //     if(g[i].empty()) break;
    //     for(auto v:g[i])
    //         dfs(dfs,v);
    // }

    //每一层其实都是固定的 只要深度相同 那么贡献一定相同

    //
    ans+=cnt[1];
    res[2]=1;
    for(int i=2;i<=n;i++){
        //每一个深度为i的点 到达的方式数都为 cnt[i-1]*res[i-1]
        res[i]=(cnt[i-1]-1)*res[i-1]%mod;
        ans=(ans+res[i]*cnt[i]%mod)%mod;
    }
    cout << ans << '\n';
}

没事，写出来就好。