比赛总结

正常发挥 + 题目过水，AK虐全场。

由于题目过水，赛时题目总结略。

CSP-S 2022 Solution

T1 - 假期计划（Holiday）

形式化题意

给出一个有 $n$ 个节点的无向图。求从 $1$ 号点出发，在路上选择经过的四个不同的景点，最后回到 $1$ 号点后，选择的四个节点权值之和。选择的点之间距离最多的长度不可以超过 $k$ 。

思路

直接 BFS 得到两个点是否可达，和距离前 3 的节点。最后合并答案即可。（这个蓝题评的名不副实，一下子就想出来了）

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/**
 * @file T1.cpp
 * @author Zhoumouren
 * @brief 
 * @version 0.1
 * @date 2024-08-16
 * 
 * @copyright Copyright (c) 2024

We can Bfs from All the point calc the point a and b can or cannot come to each other
Also we need calc the 3 maxinum of weight of the point who can come to b

then we just need enumerate b and c , then choose a and d.

*/

#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    char buf[1 << 20], *p1, *p2;
    #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
    inline void read(char *s) {
        scanf("%s", s + 1);
    }
};
using namespace FastIO;

const int N = 2510;
const int M = 10010;

struct Edge {
    int to, nt;
    Edge() {}
    Edge(int to, int nt) : to(to), nt(nt) {}
}e[M << 1];
int hd[N], cnte;
void AddEdge(int u, int v) {
    e[++cnte] = Edge(v, hd[u]);
    hd[u] = cnte;
}

int n, m, k;
ll a[N];

bool can[N][N];
vector<int >v[N];
int dis[N];

inline void Input() {
    read(n, m, k);
    a[1] = 0;
    for(int i = 2; i <= n; i++) {
        read(a[i]);
    }
    int u, v;
    for(int i = 1; i <= m; i++) {
        read(u, v);
        AddEdge(u, v);
        AddEdge(v, u);
    }
}

inline void Bfs(int st) {
    memset(dis, -1, sizeof(dis));
    queue<int >q;
    q.push(st);
    dis[st] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        if(u != st) {
            can[st][u] = 1;
            if(u != 1 && can[1][u]) {
                v[st].push_back(u);
                std :: sort(v[st].begin(), v[st].end(), [](int u, int v) {
                    return a[u] > a[v];
                }); 
                if (v[st].size() > 3) v[st].pop_back();
            }
        }
        if(dis[u] > k) {
            continue ;
        }
        for(int i = hd[u]; i ; i = e[i].nt) {
            int v = e[i].to;
            if(dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
}

inline void Work() {
    for(int i = 1; i <= n; i++) {
        Bfs(i);
    }
    ll ans = 0;
    for(int B = 2; B <= n; B++) {
        for(int C = 2; C <= n; C++) {
            if(B == C) continue;
            if(!can[B][C]) continue;
            for(int A : v[B]) {
                for(int D : v[C]) {
                    if(A == D || A == C || A == B) continue;
                    if(D == A || D == B || D == C) continue;
                    ans = max(ans, a[A] + a[B] + a[C] + a[D]);
                }
            }
        }
    }
    printf("%lld", ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

T2 - 策略游戏（Game）

形式化题意

小 L 和小 Q 在玩一个策略游戏。

有一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$，在此基础上定义一个大小为 $n \times m$ 的矩阵 $C$，满足 $C_{i j} = A_i \times B_j$。所有下标均从 $1$ 开始。

游戏一共会进行 $q$ 轮，在每一轮游戏中，会事先给出 $4$ 个参数 $l_1, r_1, l_2, r_2$，满足 $1 \le l_1 \le r_1 \le n$、$1 \le l_2 \le r_2 \le m$。

游戏中，小 L 先选择一个 $l_1 \sim r_1$ 之间的下标 $x$，然后小 Q 选择一个 $l_2 \sim r_2$ 之间的下标 $y$。定义这一轮游戏中二人的得分是 $C_{x y}$。

小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

请问：按照二人的最优策略，每轮游戏的得分分别是多少？

思路

首先这个数据结构一眼就可以看出来，ST表或者线段树。又因为这个是静态的数组，所以说这个就是ST表的板子题，最后对于选出的数的正负等因数分类讨论即可。

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/**
 * @file T2.cpp
 * @author Zhoumouren
 * @brief 
 * @version 0.1
 * @date 2024-08-16
 * 
 * @copyright Copyright (c) 2024

Easy. just a RMQ or SegTree

*/

#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    char buf[1 << 20], *p1, *p2;
    #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
    inline void read(char *s) {
        scanf("%s", s + 1);
    }
};
using namespace FastIO;

const int N = 1e5 + 10;
const int INF = 1e9 + 10;

int n, m, Q;
int a[N], b[N], c[N];

int mia[N][20], mxa[N][20];
int mib[N][20], mxb[N][20];
int fia[N][20], zia[N][20];
int lg[N];

inline void Input() {
    read(n, m, Q);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
        mia[i][0] = mxa[i][0] = a[i];
        fia[i][0] = (a[i] < 0 ? a[i] : -INF);
        zia[i][0] = (a[i] >= 0 ? a[i] : INF);
    }
    for(int i = 1; i <= m; i++) {
        read(b[i]);
        mib[i][0] = mxb[i][0] = b[i];
    }
}

inline void Init() {
    for (int i = 2; i <= max(n, m); i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int j = 1; j <= lg[n]; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            int p = i + (1 << (j - 1));
            mxa[i][j] = max(mxa[i][j - 1], mxa[p][j - 1]);
            fia[i][j] = max(fia[i][j - 1], fia[p][j - 1]);
            mia[i][j] = min(mia[i][j - 1], mia[p][j - 1]);
            zia[i][j] = min(zia[i][j - 1], zia[p][j - 1]);
        }
    }
    for (int j = 1; j <= lg[m]; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= m; ++i) {
            int p = i + (1 << (j - 1));
            mxb[i][j] = max(mxb[i][j - 1], mxb[p][j - 1]);
            mib[i][j] = min(mib[i][j - 1], mib[p][j - 1]);
        }
    }
}

inline int getmax(int st[N][20], int l, int r) {
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}
inline int getmin(int st[N][20], int l, int r) {
    int k = lg[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

inline void Work() {
    Init();
    int la, ra, lb, rb;
    while(Q--) {
        read(la, ra, lb, rb);
        int amax = getmax(mxa, la, ra);
        int amin = getmin(mia, la, ra);
        int afmx = getmax(fia, la, ra);
        int azmn = getmin(zia, la, ra);
        int bmax = getmax(mxb, lb, rb);
        int bmin = getmin(mib, lb, rb);
        int ans = -INF;
        ans = max(ans, amax * (amax >= 0 ? bmin : bmax));
        ans = max(ans, amin * (amin >= 0 ? bmin : bmax));
        if (afmx != -INF) {
            ans = max(ans, afmx * (afmx >= 0 ? bmin : bmax));
        }
        if (azmn != INF) {
            ans = max(ans, azmn * (azmn >= 0 ? bmin : bmax));
        }
        printf("%lld\n", ans);
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

T3 - 星战（Galaxy）

形式化题意

给出一张有 $n$ 个点，$m$ 条边的无向图。有如下几种操作。

  1. 摧毁一条边
  2. 修复一条边
  3. 摧毁一个点以及其所有的边
  4. 修复一个点以及它所有的边

思路

暂无