H. Genshin Impact’s Fault(模拟)

时间复杂度：$O(|S|)$

题意

    有四种许愿结果：3星武器，4星武器，5星非促销武器和5星促销武器，分别用字符$’3’、’4’、’5’$和$’U’$表示,给定愿望清单，必须满足以下规则：

  1. 对于每个连续的10个愿望，不能只存在3星武器
  2. 对于每个连续的90个愿望，至少存在一件5星武器，不管是否促销
  3. 对于每两个相邻的5星武器之中，必须有一个是促销武器

    给定愿望清单的字符串，请问是否符合所有规则？若满足，输出”$valid$”，反之则输出”$invalid$”.

数据范围

  • $c \in [‘3’,’4’,’5’,’U’]$
  • $\sum |S| \le 10^6$

思路

    设字符串长度为$n$,对三个规则进行转化：

  • 当$n \ge 10$时，每个长度为10的连续区间是否满足不止存在字符$’3’$
  • 所有$’5’$或$’U’$的间隔距离，必不超过90，记得特判开头第一个和最后一个
  • 相邻的两个五星武器，不能出现连续的两个$’5’$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--){
        string str;cin >> str;
        int n = str.length();
        str = " " + str;
        vector<int> pre(n + 1);
        vector<int> v;
        bool ok = 1;
        for (int i = 1; i <= n;i++){
            pre[i] = pre[i - 1];
            if(str[i]=='3')
                pre[i] += 3;
            else if(str[i]=='4')
                pre[i] += 4;
            else if(str[i]=='5')
                pre[i] += 5, v.emplace_back(i);
            else
                pre[i] += 6, v.emplace_back(i);
        }
        //愿望1
        if(n>=10){
            for (int i = 10; i <= n;i++)
                if(pre[i]-pre[i-10]==30) //说明出现了连续的10个'3'
                    ok = 0;
        }
        //愿望2
        int cur = 0;
        for(auto it:v){
            if(it-cur>90)
                ok = 0;
            cur = it;
        }
        if(cur+90-1<n)
            ok = 0;
        //愿望3
        if(v.size()>=2){
            for (int i = 1; i < v.size();i++)
                if(str[v[i]]==str[v[i-1]]&&str[v[i]]=='5')
                    ok = 0;
        }
        cout << (ok ? "valid" : "invalid") << endl;
    }
    return 0;
}

B.Cake2

时间复杂度：$O(1)$

题意

    蛋糕的形状是一个正多边形，边数为$n$，现在按照逆时针顺序标记顶点为0至$n-1$，选择一个正整数$k$，依次连接顶点$i$和顶点$(i+k) \: mod \: n$来切蛋糕，请问蛋糕最终切完的块数是多少？

数据范围

  • $4 \le n \le 10^6$
  • $2 \le k \le n-2$

思路

    打表找规律，不难发现，当$2 \times k == n$时，此时所有连接线都是正对角线，分割的块数一定是$n$;当$k < \lfloor \frac{n}{2} \rfloor$时，块数等于$n \cdot k+1$，当$k > \lfloor \frac{n}{2} \rfloor$时，与前者答案恰好对称.

tips:别忘了开long long！！！

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, k;
    cin >> n >> k;
    i64 ans;
    if(k*2==n)
        ans = n;
    else{
        if (k > n / 2)
            k = n - k;
        ans = 1LL * n * k + 1;
    }
    cout << ans << endl;
    return 0;
}

A. Cake(博弈/树形dp)

时间复杂度：$O(n)$

题意

​ ​ ​ ​ Grammy和Oscar在一棵树上进行操作，树上有 $n$ 个点，每两个点之间的边的边权为0或1。起始以 $1$ 作为树的根，字符串 $S$ 是空串，每移动到一个点，两点间的边权将加到字符串 $S$ 的末尾。Grammy作为先手，两人交替移动，直到移动到叶子节点，操作结束。此时将长度为 $m$ 的字符串 $S$ 分成 $m$ 块蛋糕，由Oscar进行切蛋糕操作，取其前缀，然后Grammy取 $1$ 的，Oscar取 $0$ ，两者都会以最优的策略最大化分到的蛋糕数，求最终Grammy获得的最大蛋糕数量（ $1$ ）的比例 .

数据范围

  • $2 \le n \le 200000$
  • $1 \le x,y \le n,0 \le k \le 1$
  • $\sum n \le 500000$

思路

​​ ​ ​ ​ 首先，两者从根节点交替进行移动，最终一定会移动到叶子节点，且每个叶子节点的字符串是固定的，也就是在该点Oscar的分割答案也是固定的，所以每个点的后继节点的答案一定是可预见的，考虑使用叶子到根的树形dp，使用递归求解 .

​​ ​ ​ ​ 不难想到，每个点由先手还是后手操作，只与该点的深度有关，即每一点的操作对象已知。对于先手Grammy而言，它期望的是后继节点中 $1$ 的比例更大，后手则反之；设当前结点 $u$ 的前缀 $0$ 的最大比例为 $dp[u]$ , 显然，当Grammy操作时，对后继节点取$max$ ,当Oscar操作时，对后继节点取 $min$ 即可 ，同时对叶子节点进行特判 .

​​ ​ ​ ​ 对于叶子节点中求解前缀 $0$ 的比例最大值，注意到每一次向下深搜时匹配到的就是前缀，所以直接设一个数组维护当前字符串中 $0$ 的数量和字符串长度，维护最大值即可 .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector<vector<pair<int,int>>> e(n + 1);
    vector<double> rt(n + 1), mx(n + 1); 
    // rt[i]表示i号点前缀0的占比,mx[u]表示到达u节点的前缀0比例最大值
    for (int i = 1; i < n;i++){
        int x, y, k;
        cin >> x >> y >> k;
        e[x].emplace_back(y, k);
        e[y].emplace_back(x, k);
    }
    auto dfs = [&](auto dfs, int u, int fa, int depth, int cnt) -> double
    {
        if(u!=1)
            mx[u] = max(mx[fa], (cnt * 1.0) / (depth - 1)); //维护前缀0比例最大值
        //cout << u << ' ' << depth << ' ' << cnt << ' ' << mx[u] << endl;
        if (fa != 0 && e[u].size() == 1) // 叶子节点
            rt[u] = mx[u];
        else{
            rt[u] = ((depth & 1) ? 1.0 : 0.0);
            for (auto x:e[u]){
                if(x.first==fa)
                    continue;
                if (depth & 1) // 轮到Grammy
                    rt[u] = min(rt[u], dfs(dfs, x.first, u, depth + 1, cnt + (!x.second)));
                else  //轮到Oscar
                    rt[u] = max(rt[u], dfs(dfs, x.first, u, depth + 1, cnt + (!x.second)));
            }
        }
        return rt[u];
    };
    double ans = 1.0 - dfs(dfs, 1, 0, 1, 0); //前缀1的比例
    cout << fixed << setprecision(12) << ans << endl;
}
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

典题

https://codeforces.com/contest/1970/problem/C2