最后一舞--算法竞赛

牛客#

牛客暑假多校第一场#

A#

其实就是非常简单的模拟

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
void slove(){
5
    string s;
6
    cin >> s;
7
    bool t1 = 1;
8
    if(s.size() != 8) t1 = 0;
9
    string s1 = "aeiou";
10
    for(int i = 0; i < 8; i++){
11
        if(i % 2){
12
            if(s1.find(s[i]) == string::npos){
13
                t1 = 0;
14
            }
15
        }else{
16
            if(s1.find(s[i]) != string::npos){
17
                t1 = 0;
18
            }
19
        }
20
    }
21
    if(!t1){
22
        cout << "Well-Being" << endl;
23
    }else{
24
        cout << "Suspected Virus" << endl;
25
    }
26
}
27
signed main(){
28
    int t = 1;
29
    cin >> t;
30
    while(t--){
31
        slove();
32
    }
33
}

C#

这道题我认为很有意思，其实就是带权并查集 + 连通块的问题：有一个 $n\times m$ 的网格，鱼会不断加入。鱼只能在上下左右移动：

遇到大小 $\le$ 自己的鱼，可以吃掉，自己大小 $+1$
遇到更大的鱼，不能通过
障碍物也不能通过题目有两种操作：

加入一条新鱼，问它最多能吃多少条鱼
对某条已有鱼，允许一开始给它增加体型，问为了吃完整个当前连通块，最少要增加多少

解决思路：

首先操作1 其实就是维护一个连通块的size，但是这里要注意一个问题，就是你左边的方块可能和右边的方块是联通的
对于操作二，我们要找到一个关键的性质: $s \ge last - size[s] + 1$ , 如果我要往上吃，应该满足的性质，所以如果我要吃完连通块，就相当于 $max(\sum_{now...root}(last - size + 1))$ ,所以我们其实可以维护每一个节点到根节点的 dp(吃完需要的最小体积)，放到操作二处理，其实如何维护这个 dp，主要就是更新根节点的时候维护每一个连通块向上吃的最小体积，dp 向上传播的过程在find(并查集中实现就可以了)

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5

6
int dx[4] = {1,0,-1,0};
7
int dy[4] = {0,1,0,-1};
8

9
void slove(){
10
    int n,m,q;
11
    cin >> n >> m >> q;
12
    vector<int> dp(n * m + 10 ,0);
13
    vector<int> fa(n * m + 10, 0), sz(n * m + 10, 1), dj(n * m + 10, 0);
14
    vector<bool> vis(n * m + 10, 0);
15
    auto ID = [&](int x, int y) -> int {
16
        return (x - 1) * m + y;
17
    };
18
    for(int i = 1; i <= n*m; i++){
19
        fa[i] = i;
20
    }
21
    auto find = [&](int i) -> int {
22
        vector<int> r;
23
        int t1 = i;
24
        while(t1 != fa[t1]){
25
            r.push_back(t1);
26
            t1 = fa[t1];
27
        }
28
        int root = t1;
29
        int ed = r.size() - 1;
30
        int cur = 0;
31
        for(int k = ed; k >= 0; k--){
32
            int id = r[k];
33
            dp[id] = max(cur, dp[id]);
34
            cur = dp[id];
35
            fa[id] = root;
36
        }
37
        return root;
38
    };
39
    int l = 0;
40
    for(int i = 1; i <= q; i++){
41
        int op;
42
        cin >> op;
43
        if(op == 1){
44
            int x, y, v;
45
            cin >> x >> y >> v;
46
            x ^= l; y ^= l;
47
            dj[ID(x, y)] = v;
48
            int root1 = ID(x, y);
49
            vis[root1] = 1;
50
            vector<int> ro;
51
            for(int i = 0; i < 4; i++){
52
                int x1 = x + dx[i], y1 = y + dy[i];
53
                if(x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;
54
                int id1 = ID(x1,y1);
55
                if(!vis[id1]) continue;
56
                int r = find(id1);
57
                bool flag = 1;
58
                for(auto tt : ro){
59
                    if(tt == r) flag = 0;
60
                }
61
                if(flag) ro.push_back(r);
62
            }
63
            for(auto x : ro){
64
                dp[x] = max(0ll, v - sz[x] + 1);
65
                fa[x] = root1;
66
                sz[root1] += sz[x];
67
            }
68
            l = sz[root1] - 1;
69
            cout << sz[root1] - 1 << endl;
70
        }else if(op == 2){
71
            int x, y;
72
            cin >> x >> y;
73
            x ^= l; y ^= l;
74
            int root1 = ID(x, y);
75
            find(root1);
76
            l = max(0ll, dp[root1] - dj[root1]);
77
            cout << max(0ll, dp[root1] - dj[root1]) << endl;
78
        }
79
    }
80
}
81

82
signed main(){
83
    int t = 1;
84
    // cin >> t;
85
    while(t--){
86
        slove();
87
    }
88
}

E#

非常简单的一道题目，看规律都能看出来

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5

6
void slove(){
7
    int n;
8
    cin >> n;
9
    vector<int> a(n + 1, 0);
10
    for(int i = 1; i <= n; i++){
11
        cin >> a[i];
12
    }
13
    int ans = 0;
14
    for(int i = 1; i <= n; i++){
15
        ans += (a[i] * i) - (a[i] * (n - i + 1));
16
    }
17
    cout << ans << endl;
18
}
19

20
signed main(){
21
    int t = 1;
22
    // cin >> t;
23
    while(t--){
24
        slove();
25
    }
26
}

F#

解法：作为构造题，我们的想法不能过于复杂，从公式中

P_j - P_i

的形式，为了保证这个 f(P) 不变，所以根据这种形式，我们能不能从循环的形式去刻画这个问题，所以我们要去验证这个循环是不是 f(P) 是否不变

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5

6
void slove(){
7
    int n, k, x;
8
    cin >> n >> k >> x;
9
    vector<int> a(n, 0);
10
    for(int i = 0; i < n; i++){
11
        cin >> a[i];
12
    }
13
    int pos = 0;
14
    for(int i = 0; i < n; i++){
15
        if(a[i] == x){
16
            pos = i;
17
            break;
18
        }
19
    }
20
    int t1 = (k - pos + n) % n;
21
    vector<int> ans(n);
22
    for(int i = 0; i < n; i++){
23
        ans[(i + t1) % n] = a[i];
24
    }
25
    for(auto &x : ans) cout << x << " ";
26
    cout << endl;
27

28
}
29

30
signed main(){
31
    int t = 1;
32
    // cin >> t;
33
    while(t--){
34
        slove();
35
    }
36
}

G#

考虑这个误差 $\theta \le 0.01$ 去考虑，发现计算，就是节点直接距离看成1，可以用一个正方向包裹 100 个以上，所以我们在高度为一的上下两个平面去构建两个正方形就可以

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5

6
void slove(){
7
    //  cout << sqrt(1.01 * 1.01-1) / 0.0101 << endl;
8
    int m;
9
    cin >> m;
10
    int t1 = m;
11
    cout << 2 * m << endl;
12
    for(int i = 0; i < 10; i++){
13
        for(int j = 0; j < 10; j++){
14
            cout << (i) * 0.0101 << " " << j * 0.0101 << " " << 0 << endl;
15
            t1 --;
16
            if(t1 == 0) break;
17
        }
18
        if(t1 == 0) break;
19
    }
20
    for(int i = 0; i < 10; i++){
21
        for(int j = 0; j < 10; j++){
22
            cout << (i) * 0.0101 << " " << j * 0.0101 << " " <<  1 << endl;
23
            m --;
24
            if(m == 0) break;
25
        }
26
        if(m == 0) break;
27
    }
28
    // cout << "------------" << endl;;
29
}
30

31
signed main(){
32
    int t = 1;
33
    cin >> t;
34
    while(t--){
35
        slove();
36
    }
37
}

H#

图片说明这道题目如果赛时的话只能通过打表的形式去找规律了，不然很难想到只要模拟前 100 轮，后面每轮的变化量差不多，其实就是打表观察差分是否收敛的现象，然后再去模拟这个过程:

首先当前步骤是依靠后面步骤的最高收益，所以可以采用 DP，从后面的步骤开始往前面的步骤模拟，然后去模拟 A，B 的出牌选择就可以了

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5
vector<vector<double>> dp(101, vector<double>(101, 0.00));
6
map<array<int,3>,int> id;
7
vector<array<int,3>> hand;
8
void slove(){
9
    int k;
10
    cin >> k;
11
    string s1,s2;
12
    cin >> s1 >> s2;
13
    array<int,3> t1 = {0,0,0};
14
    array<int,3> t2 = {0,0,0};
15
    for(int i = 0; i < 3; i++){
16
        if(s1[i] == 'R') t1[0] ++;
17
        else if(s1[i] == 'S') t1[1] ++;
18
        else if(s1[i] == 'P') t1[2] ++;
19
    }
20
    for(int i = 0; i < 3; i++){
21
        if(s2[i] == 'R') t2[0] ++;
22
        else if(s2[i] == 'S') t2[1] ++;
23
        else if(s2[i] == 'P') t2[2] ++;
24
    }
25
    int ID1 = id[t1];
26
    int ID2 = id[t2];
27
    int state = ID1 * 10 + ID2;
28
    cout << fixed << setprecision(10);
29
    // cout << dp[k][state] << endl;
30
    double ans = 0;
31
    if(k <= 100){
32
        cout << dp[k][state] << endl;
33
    }else{
34
        double d = dp[100][state] - dp[99][state];
35
        cout << dp[100][state] + (k - 100) * d << endl;
36
    }
37
}
38

39
void init(){
40

41
    int id1 = 0;
42
    for(int i = 0; i <= 3; i++){
43
        for(int j = 0; j + i <= 3; j++){
44
            int k = 3 - i - j;
45
            array<int,3> temp = {i, j, k};
46
            id[temp] = id1 ++;
47
            hand.push_back(temp);
48
        }
49
    }
50
    auto score = [&](int x1, int y1) -> double {
51
        if((x1 == 0 && y1 == 1) || (x1 == 1 && y1 == 2) || (x1 == 2 && y1 == 0)){
52
            return 3;
53
        }else if((x1 == y1)){
54
            return 1;
55
        }else return 0;
56
    };
57

58
    for(int T = 1; T <= 100; T++){
59
    // A 牌的种类
60
        for(int i = 0; i < 10; i++){
61
            // B 牌的种类
62
            for(int j = 0; j < 10; j++){
63
                int state = i * 10 + j;
64
                // A 打哪张牌
65
                double best = 0;
66
                for(int i1 = 0; i1 < 3; i1++){
67
                    if(hand[i][i1] == 0) continue;
68
                    // B 打哪张牌
69
                    double worst = (double)1e9;
70
                    for(int j1 = 0; j1 < 3; j1++){
71
                        auto tt2 = hand[j];
72
                        auto tt1 = hand[i];
73
                        if(tt2[j1] == 0) continue;
74
                        tt2[j1] --;
75
                        tt1[i1] --;
76
                        double cur = score(i1, j1);
77

78
                        // 补牌环节
79
                        double s1 = 0;
80
                        for(int add1 = 0; add1 < 3; add1 ++){
81
                            for(int add2 = 0; add2 < 3; add2++){
82
                                auto temp1 = tt1;
83
                                auto temp2 = tt2;
84
                                temp1[add1] ++;
85
                                temp2[add2] ++;
86
                                int p1 = id[temp1];
87
                                int p2 = id[temp2];
88
                                int ID = p1 * 10 + p2;
89
                                s1 += dp[T-1][ID];
90
                            }
91
                        }
92
                        cur += (s1 / (9.0));
93
                        worst = min(worst, cur);
94
                    }
95
                    best = max(best, worst);
96
                }
97
                dp[T][state] = best;
98
            }
99
        }
100
    }
101
}
102

103
signed main(){
104
    ios::sync_with_stdio(false);
105
    cin.tie(0);
106
    cout.tie(0);
107
    init();
108
    int t = 1;
109
    cin >> t;
110
    while(t--){
111
        slove();
112
    }
113
}

牛客#

牛客暑假多校第一场#

A#

C#

E#

F#

G#

H#

牛客暑假多校第二场#

B#

杭电 HDU#

HDU 多校第一场#

评论

Color Your Night