距离 Kyy008 参加蓝桥杯省赛还有3个月，但是经过第一次训练赛的拷打后发现什么都不会，遂记录总结。qwq

B. Sign of Friendship(通过人数 54/69)#

题目描述#

你现在站在一座高塔的底部（高度为 0）。在距离塔 $D$ 的位置，空中有个高度为 $H$ 的 UFO。

塔和 UFO 之间有 $N$ 个障碍物。第 $i$ 个障碍物位于距离塔 $d_i$ 的位置，高度为 $h_i$ 。

你需要爬到塔上的某个高度，使得你与 UFO 之间的连线不穿过任何障碍物。求你需要爬升的最小高度。

假设地面是平坦的，塔和障碍物垂直于地面。如果障碍物的顶点恰好在连线上，视为不阻挡。

输入格式#

第一行包含三个整数 $N, D, H$ 。接下来 $N$ 行，每行包含两个整数 $d_i, h_i$ 。

$1 \leqslant N \leqslant 100$
$1 \leqslant d_i < D \leqslant 1000$
$1 \leqslant h_i < H \leqslant 1000$

题解#

简答几何。思考对于每一个障碍物，如果视线要越过它，我们在塔上至少需要多高？假设视线刚好经过第 $i$ 个障碍物的顶点 $(d_i, h_i)$ 射向 UFO $(D, H)$ 。计算两点连成的一次函数。

斜率：
$k = \frac{H - h_i}{D - d_i}$
截距：

根据直线方程 $y - y_0 = k(x - x_0)$ ，令 $x=0$ ，即塔的位置：
$y - H = k(0 - D) \implies y = H - k \times D$
代入 $k$ 可得该障碍物要求的最小高度 $b_i$ ：
$b_i = H - \frac{H - h_i}{D - d_i} \times D$

为了避开所有障碍物，我们需要的高度必须大于等于所有 $b_i$ 。因此，最终答案是所有 $b_i$ 中的最大值。同时，高度不能为负数，初始化答案为 0 即可。

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

4
#define int long long
5
#define endl '\n'
6
#define rep(i, f, l) for(int i(f); i <= l; ++i)
7
#define per(i, f, l) for(int i(f); i >= l; --i)
8

9
const int N = 2e5 + 5;
10

11
void work() {
12
    double n, d, h;
13
    cin >> n >> d >> h;
14
    double ans = 0;
15
    while(n--){
16
        double x, y;
17
        cin >> x >> y;
18
        double b = h - (h - y) / (d - x) * d;
19
        ans = max(ans, b);
20
    }
21
    cout << fixed << setprecision(12) << ans << endl;
22
    return;
23
}
24

25
signed main() {
26
    ios::sync_with_stdio(0);
27
    cin.tie(0);
28
    cout.tie(0);
29
    int t = 1;
30
    // cin >> t;
31
    while (t--) {
32
        work();
33
    }
34
    return 0;
35
}

D. UFO Invasion(通过人数 48/69)#

题目描述#

给定一个长度为 12 的字符串 $S$ ，判断其中包含多少个子串 “ZONe”。

输入格式#

输入包含一个长度为 12 的字符串 $S$ 。

题解#

字符串模拟。遍历字符串，使用 substr 方法检查所有长度为 4 的子串是否等于 “ZONe” 即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 2e5 + 5;
8
void work() {
9
  string s;
10
    cin >> s;
11
    int ans = 0;
12
    rep(i, 0, (int)s.size() - 4) {
13
        if (s.substr(i, 4) == "ZONe") {
14
            ans++;
15
        }
16
    }
17
  cout << ans << endl;
18
  return;
19
}
20
signed main() {
21
  ios::sync_with_stdio(0);
22
  cin.tie(0);
23
  cout.tie(0);
24
  int t = 1;
25
//  cin >> t;
26
  while (t--) {
27
    work();
28
  }
29
  return 0;
30
}

C. Message from Aliens(通过人数 21/69)#

题目描述#

给定一个加密字符串 $S$ ，解密规则如下：

初始时， $T$ 为空字符串。
从左到右遍历 $S$ $S$ 的每个字符：
- 如果是 ‘R’，反转 $T$ 。
- 如果不是 ‘R’，将该字符追加到 $T$ 的末尾。
操作完成后，如果 $T$ 中存在两个连续相同的字符，将它们删除。重复此操作直到无法删除为止。

输入格式#

输入包含一个字符串 $S$ ，由小写英文字母和 ‘R’ 组成。

$1 \leqslant |S| \leqslant 5 \times 10^5$

题解#

首先考虑暴力解法。模拟解密规则，遇到 ‘R’ 时直接进行反转操作。经分析，最坏情况下时间复杂度会达到 $O(|S|^2)$

我们发现上述解法在反转字符串操作上浪费了大量时间，而反转一次字符串后在串尾追加字符与直接在串头追加字符的操作等价，因此反转整个字符串的操作事实上是冗余的。考虑使用双端队列 deque 来维护字符串 $T$ ，并用一个布尔变量 f 记录当前的翻转状态：

当遇到 ‘R’ 时，切换翻转状态 f ^= 1。
当遇到普通字符时：
- 如果 f == 0，字符应加在队尾。
- 如果 f == 1，字符应加在队首。

同时，题目要求删除连续相同的字符。利用栈的思想，在加入新字符前，先检查加入端的字符是否与新字符相同：

如果相同，则弹出原有字符。
如果不相同，则将新字符推入。

最后，根据最终的翻转状态 f，决定是从头到尾还是从尾到头输出队列中的字符。即经过奇数次反转后倒序输出，偶数次反转后顺序输出。算法时间复杂度 $O(|S|)$

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 2e5 + 5;
8
deque<char> q;
9
void work() {
10
    string s;
11
    cin >> s;
12
    bool f = 0;
13
    rep(i, 0, (int)s.size() - 1) {
14
        if(s[i] == 'R'){
15
            f ^= 1;
16
            continue;
17
        }
18
        if(!f){
19
            if(!q.empty() && q.back() == s[i]) {
20
                q.pop_back();
21
            } else {
22
                q.push_back(s[i]);
23
            }
24
        } else {
25
            if(!q.empty() && q.front() == s[i]) {
26
                q.pop_front();
27
            } else {
28
                q.push_front(s[i]);
29
            }
30
        }
31
    }
32
    string ans = "";
33
    for(auto c : q) ans += c;
34
    if (f) {
35
        reverse(ans.begin(), ans.end());
36
    }
37
    cout << ans << endl;
38
    return;
39
}
40

41
signed main() {
42
    ios::sync_with_stdio(0);
43
    cin.tie(0);
44
    cout.tie(0);
45
    int t = 1;
46
//  cin >> t;
47
    while (t--) {
48
        work();
49
    }
50
    return 0;
51
}

A. MAD TEAM(通过人数 13/69)#

题目描述#

从 $N$ 个候选人中选出 3 人组成一个团队。每个人有 5 个能力值：力量、速度、技巧、知识、创造力。

团队的各项能力值定义为成员中该项能力值的最大值。团队的综合实力定义为团队 5 项能力值中的最小值。

求团队综合实力的最大可能值。

输入格式#

第一行包含一个整数 $N$ 。接下来 $N$ 行，每行 5 个整数，表示每个人的 5 项能力值。

题解#

首先考虑暴力解法：直接从 $N$ 个人中枚举 3 个人组成队伍。从中选出 3 个人的组合数为 $C_N^3 = O(N^3)$ 。由于 $N \le 3000$ ，计算量为 $4.5 \times 10^9$ ，显然会超时。

但我们可以显然发现答案具有单调性：如果能组成综合实力为 $x$ 的队伍，那么一定能组成综合实力小于 $x$ 的队伍，因此考虑使用二分答案。

假设我们要检查是否能组成综合实力至少为 $mid$ 的队伍：

在 check(mid) 时，我们只关心某项能力值是否达到 mid，而不关心具体数值。因此，对于每个人，可以将他的 5 项能力值转化为一个 5 位的二进制数 val。如果某项能力值 $\ge mid$ ，则对应二进制位为 1，否则为 0。
问题转化为：是否存在 3 个不同或相同的 val，它们的按位或运算结果为 11111

由于 val 的取值范围只有 $0 \sim 31$ ，我们可以记录所有出现过的 val。枚举这 3 个 val 的所有组合，检查它们的或运算结果是否为 31。综合时间复杂度 $O(\log(10^9) \cdot (N + 32^3))$

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 3005;
8
struct person{
9
    int a;
10
    int b;
11
    int c;
12
    int d;
13
    int e;
14
};
15
person p[N];
16
int n;
17
bool check(int x){
18
    vector<int> exist;
19
    bool vis[32] = {0};
20
    rep(i, 1, n){
21
        int val = 0;
22
        if(p[i].a >= x) val |= (1 << 4);
23
        if(p[i].b >= x) val |= (1 << 3);
24
        if(p[i].c >= x) val |= (1 << 2);
25
        if(p[i].d >= x) val |= (1 << 1);
26
        if(p[i].e >= x) val |= (1 << 0);
27
        if(!vis[val]){
28
            vis[val] = 1;
29
            exist.push_back(val);
30
        }
31
    }
32
    int m = exist.size();
33
    rep(i, 0, m - 1){
34
        rep(j, i, m - 1){
35
            rep(k, j, m - 1){
36
                int comb = exist[i] | exist[j] | exist[k];
37
                if(comb == 31){
38
                    return 1;
39
                }
40
            }
41
        }
42
    }
43
    return 0;
44
}
45

46
void work() {
47
    cin >> n;
48
    rep(i, 1, n) {
49
        cin >> p[i].a >> p[i].b >> p[i].c >> p[i].d >> p[i].e;
50
    }
51
    int l = 1, r = 1e9;
52
    while(r - l >= 5){
53
        int mid = (l + r) >> 1;
54
        if(check(mid)){
55
            l = mid;
56
        } else {
57
            r = mid;
58
        }
59
    }
60
    per(i, r, l){
61
        if(check(i)){
62
            cout << i << endl;
63
            return;
64
        }
65
    }
66
    return;
67
}
68
signed main() {
69
    ios::sync_with_stdio(0);
70
    cin.tie(0);
71
    cout.tie(0);
72
    int t = 1;
73
    // cin >> t;
74
    while (t--) {
75
        work();
76
    }
77
    return 0;
78
}

F. Fly to the UFO(通过人数 10/69)#

题目描述#

在一个二维平面上，你现在位于坐标 $(1, 1)$ ，想要到达 UFO 的坐标 $(R, C)$ 。

当你位于 $(r, c)$ 时，可以进行以下四种移动：

从 $(r, c)$ 移动到 $(r, c+1)$ ，花费 $A_{r,c}$ 。条件： $c < C$ 。
从 $(r, c)$ 移动到 $(r, c-1)$ ，花费 $A_{r,c-1}$ 。条件： $c > 1$ 。
从 $(r, c)$ 移动到 $(r+1, c)$ ，花费 $B_{r,c}$ 。条件： $r < R$ 。
选择一个整数 $i$ ( $1 \le i < r$ )，从 $(r, c)$ 移动到 $(r-i, c)$ ，花费 $1 + i$ 。

求从 $(1, 1)$ 移动到 $(R, C)$ 的最小花费。

输入格式#

第一行包含两个整数 $R, C$ 。接下来 $R$ 行，每行 $C-1$ 个整数，表示 $A_{i,j}$ 。接下来 $R-1$ 行，每行 $C$ 个整数，表示 $B_{i,j}$ 。

$2 \leqslant R, C \leqslant 500$
$0 \leqslant A_{i,j} < 10^3$
$0 \leqslant B_{i,j} < 10^3$

题解#

不难发现这是一个单源最短路问题。我们可以将网格中的每个点视为一个节点，边的权重即为移动的代价。

首先考虑暴力建图：

对于向左、向右、向下都是邻项移动，建边数 $O(R \times C)$ 。对于向上跳跃，可以从 $(r, c)$ 可以跳到 $(r-1, c), (r-2, c), \dots, (1, c)$ ，即第 $r$ 行的点需要向建 $r-1$ 个边，建边数 $O(C \times R^2)$ ，使用 $Dijkstra$ 算法会导致超时。

考虑优化向上跳跃的建图方式：

注意到从 $(r, c)$ 跳到 $(r-i, c)$ 的代价是 $1+i$ ，而假设这个代价是 $i$ ，我们很容易可以想到对于每个点建一个代价为 $1$ 的到上一个点的边即可。推而广之，我们用类似的思路，引入分层图/虚拟节点的思想来优化建图。

对于每个点 $(r, c)$ ，我们引入一个“向上跳跃状态”的虚拟节点 $(r, c)'$

由此，从 $(r, c)$ 到 $(r-i, c)$ 的代价是 $1+i$ 便可以分解为：

花费 1 的代价进入“向上跳模式”的虚拟节点 $(r, c)'$ 。
在“向上跳模式”的这个虚拟图中，每向上走一步花费 1。
随时可以花费 0 的代价退出“向上跳模式”的虚拟图，回到普通图。

不难得到全部连边规则：

普通移动：
- $(r, c) \to (r, c+1)$ ，权值 $A_{r,c}$
- $(r, c) \to (r, c-1)$ ，权值 $A_{r,c-1}$
- $(r, c) \to (r+1, c)$ ，权值 $B_{r,c}$
从普通层进入虚拟层：
- $(r, c) \to (r, c)'$ ，权值 1。
在虚拟层向上：
- $(r, c)' \to (r-1, c)'$ ，权值 1。
从虚拟层回到普通层：
- $(r, c)' \to (r, c)$ ，权值 0。

总节点数 $2 \times R \times C$ ，总边数 $O(R \times C)$ 。采用 $Dijkstra$ 算法的总时间复杂度为 $O(RC \log(RC))$ 。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 3 * 500 * 500;
8
const int M = 10 * 500 * 500;
9
int a[505][505];
10
int b[505][505];
11
struct edge{
12
    int nxt;
13
    int to;
14
    int w;
15
};
16
edge e[M];
17
struct node{
18
    int id;
19
    int dis;
20
    bool operator < (const node &x) const{
21
        return dis > x.dis;
22
    }
23
};
24
int r, c;
25
int head[N];
26
bool vis[N];
27
int dis[N];
28
int cnt = 0;
29
void add(int u, int v, int w){
30
    e[++cnt].to = v;
31
    e[cnt].w = w;
32
    e[cnt].nxt = head[u];
33
    head[u] = cnt;
34
}
35
priority_queue<node> q;
36
void dij(int s){;
37
    dis[s] = 0;
38
    q.push(node{s, 0});
39
    while(!q.empty()){
40
        node tmp = q.top();
41
        q.pop();
42
        int x = tmp.id;
43
        if(vis[x]) continue;
44
        vis[x] = 1;
45
        for(int i = head[x]; i; i = e[i].nxt){
46
            int y = e[i].to;
47
            if(dis[y] > dis[x] + e[i].w){
48
                dis[y] = dis[x] + e[i].w;
49
                q.push((node){y, dis[y]});
50
            }
51
        }
52
    }
53
}
54

55
void work() {
56
    cin >> r >> c;
57
    rep(i, 1, r){
58
        rep(j, 1, c - 1){
59
            cin >> a[i][j];
60
        }
61
    }
62
    rep(i, 1, r - 1){
63
        rep(j, 1, c){
64
            cin >> b[i][j];
65
        }
66
    }
67
    rep(i, 1, r){
68
        rep(j, 1, c){
69
            int id = (i - 1) * c + j;
70
            if(j < c) add(id, id + 1, a[i][j]);
71
            if(j > 1) add(id, id - 1, a[i][j - 1]);
72
            if(i < r) add(id, id + c, b[i][j]);
73
            if(i > 1) add(id + r * c, id + r * c - c, 1);
74
            add(id, id + r * c, 1);
75
            add(id + r * c, id, 0);
76
        }
77
    }
78
    memset(dis, 0x3f, sizeof(dis));
79
    dij(1);
80
    cout << dis[r * c] << endl;
81
    return;
82
}
83

84
signed main() {
85
    ios::sync_with_stdio(0);
86
    cin.tie(0);
87
    cout.tie(0);
88
    int t = 1;
89
//     cin >> t;
90
    while (t--) {
91
        work();
92
    }
93
    return 0;
94
}

わたしの部屋

B. Sign of Friendship(通过人数 54/69)#

题目描述#

输入格式#

题解#

D. UFO Invasion(通过人数 48/69)#

题目描述#

输入格式#

题解#

C. Message from Aliens(通过人数 21/69)#

题目描述#

输入格式#

题解#

A. MAD TEAM(通过人数 13/69)#

题目描述#

输入格式#

题解#

F. Fly to the UFO(通过人数 10/69)#

题目描述#

输入格式#

题解#