做题顺序：B → A → C暴力

预期得分：100 + 100 + 25 + 0 = 225

实际得分：100 + 50 + 25 + 0 = 175

A. 前端

预期 100 实际 100

考点：逆向思维、带权并查集

题意简述：有一张 $n$ 个点 $m$ 条边的图，给出一个删除序列，求每次删除一个点之后各个连通图中最大的权值和。

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
#include <bits/stdc++.h>
#define int long long // 不开 long long 会挂 40pts，还好我开了（）
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 29;

int n, m, k;
int w[N], fa[N], sum[N], del[N], ans[N], x[N], y[N], app[N];
bool now[N];
vector<int> a[N];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    sum[fy] += sum[fx]; // 带权并查集：存集合的权值和
    sum[fx] = 0;
    fa[fx] = fy;
}

void tbcinit() {
    rep (i, 1, n) {
        fa[i] = i;
        now[i] = false;
    }
}

void tbcsolve() {
    cin >> n >> m;
    rep (i, 1, n) cin >> w[i];
    tbcinit();
    rep (i, 1, m) cin >> x[i] >> y[i];
    rep (i, 1, n) {
        cin >> del[i];
        app[del[i]] = i;
    }
    rep (i, 1, m) { 
        if (app[x[i]] > app[y[i]]) // 优化：从先删除的边向后删除的边建边，可以大大降低时间复杂度
            a[y[i]].pb(x[i]);
        else a[x[i]].pb(y[i]);
    }
    per (i, n, 1) { // 逆向思维：将点的逐个删除改为逐个加入
        int u = del[i]; 
        now[u] = true; // 表示该点已经被添加到图上，但其实在优化后可以省去
        sum[u] = w[u];
        for (auto v : a[u]) {
            if (now[v]) merge(u, v);
        }
        ans[i] = max(ans[i + 1], sum[find(u)]); // 状态转移：将答案存起来
    }
    rep (i, 2, n + 1) cout << ans[i] << endl;
}

signed main() {
    freopen ("qd.in", "r", stdin);
    freopen ("qd.out", "w", stdout);
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int SHENSELF = 1;
    // cin >> SHENSELF;
    while (SHENSELF--) {
        tbcsolve();
    }
    return 0;
}
/*
    9:12 打算从这个题下手
    如果一个一个的删的话，每次都要判连通，显然是不优的
    所以可以考虑一个一个的增加点
    那么我们要怎么增加点呢？？？
    我也不知道。
    所以来让我们手搓一下样例【好臭的样例

    9:16 好笑吗，手搓了样例看到最后一行
    才发现已经给了删除顺序了
    那我还在纠结什么。。。
    我还以为要我自己给删除序列呢。。。
    显然是要用带权并查集的
    但是带权并查集的题我做的太少了只能说尽力吧

    9:33 写完了
    but，小样例不过。
    我要祭出很经典的那句话：“那我的代码哪里有问题呢？？？那它凭什么错了呢？？？”
    手搓ing。。。

    9:41 发现是自己又读错题了……
    是每个集合的权值和最大的。。。不是权值最大值最大。。。
    这样就过了小样例了

    9:43 大样例挂了？？？那凭啥呢
    输出里面夹了几个比较小的数字， 那凭啥呢？？？
    
    9:44 好笑吗。。。
    状态转移写成了 ans[i] = max(ans[i - 1], sum[find(u)])
    但是因为是倒序跑的数组所以应该从 ans[i + 1] 转移过来。。。
    这样大样例就过啦！！！
    期望得分100pts【但是有句古话说得好，过了大样例相当于你的得分在[0,100]之间

    9:55 突然意识到可以优化
    建边的时候我们只存比当前点先出现的点
    这样可以大大降低时间复杂度
    所以需要先把读入的边的信息保存起来

    10:00 OK没有问题
*/

B. 导航神器

预期 100 实际 50

考点：离散化、缩点、图的遍历

题意简述： 给出一个 $n \times m$ 的图，. 表示空地，# 表示障碍物，可以向上下左右四个方向移动，另有 $k$ 条有向边，给出 $q$ 对由坐标表示的起始点，求能否从起点到达终点。

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
148
149
150
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int N = 5e4 + 29;

int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};
int n, m, k, q, cnt;
string str[N];
map<pii, int> mp;
vector<int> a[N], g[N];
int dfn[N], low[N], ts, scc_cnt, id[N];
bool st[N];
stack<int> s;

void tarjan(int u) { // 缩点：在一个强连通分量里的点可以互相到达
    dfn[u] = low[u] = ++ts;
    s.push(u);
    st[u] = true;
    for (auto v : a[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], dfn[v]); // 挂了50分的原因在这里，应该是 else if (st[v]) 而非直接 else
    }
    if (dfn[u] == low[u]) {
        int t;
        scc_cnt++;
        do {
            t = s.top(); s.pop();
            st[t] = false;
            id[t] = scc_cnt;
        } while (u ^ t);
    }
}

bool bfs(int s, int t) { // 由于缩点后的图是森林，不存在环，所以不用打标记
    queue<int> q;
    q.push(s);
    while (q.size()) {
        int u = q.front(); q.pop();
        if (u == t) return true; // 如果到达了就直接返回
        for (auto v : g[u]) q.push(v); 
    }
    return false; // 到达不了，返回 false
}

void tbcsolve() {
    cin >> n >> m >> k >> q;
    rep (i, 1, n) {
        cin >> str[i];
        str[i] = '~' + str[i];
        rep (j, 1, m) mp[{i, j}] = ++cnt; // 离散化：将只有坐标的点编号
    }
    rep (i, 1, n) {
        rep (j, 1, m) {
            if (str[i][j] == '#') continue;
            rep (o, 1, 4) {
                int x = i + dx[o], y = j + dy[o];
                if (x < 1 || x > n || y < 1 || y > m || str[x][y] == '#') continue; // 处理边界和障碍
                a[mp[{i, j}]].pb(mp[{x, y}]);
            }
        }
    }
    while (k--) {
        int x_1, y_1, x_2, y_2;
        cin >> x_1 >> y_1 >> x_2 >> y_2;
        a[mp[{x_1, y_1}]].pb(mp[{x_2, y_2}]);
    }
    rep (i, 1, cnt) if (!dfn[i]) tarjan(i);
    rep (i, 1, cnt) {
        for (auto j : a[i]) {
            if (id[i] == id[j]) continue;
            g[id[i]].pb(id[j]); // 缩点后建新图
        }
    }
    while (q--) {
        int x_1, y_1, x_2, y_2;
        cin >> x_1 >> y_1 >> x_2 >> y_2;
        cout << bfs(id[mp[{x_1, y_1}]], id[mp[{x_2, y_2}]]) << endl; 
        // 因为强连通分量内的点可以互相到达，所以我们只需要判断能否从起点的强连通分量跑到终点的强连通分量即可
    }
}

void tbcinit() {
    
}

signed main() {
    freopen ("map.in", "r", stdin);
    freopen ("map.out", "w", stdout);
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int SHENSELF = 1;
    // cin >> SHENSELF;
    while (SHENSELF--) {
        tbcinit();
        tbcsolve();
    }
    return 0;
}
/*
    7:55 一眼看中这道题
    一眼建图 → tarjan缩点 → 再建图 → 简单bfs
    做缩点做多了导致的。

    8:02 发现我们知道的是 n*m 的数据范围
    那应该怎么建图呢，不能直接开 5e4 的二维啊……
    有了！离散化！！祭出我的 map！！！

    8:21 写完代码
    但是小样例没过
    手搓了一下发现是建边的地方错了

    8:27 这也太唐了，dx和dy数组写成了：
        int dx[5] = {0, 1, -1, 1, -1};
        int dy[5] = {0, 1, 1, -1, -1};
    怎么能唐成这样
    但是怎么还是过不了小样例

    8:36 卧槽不是怎么能有人唐成这样啊
    65行的位置写成了 int x = i + dx[o], y = j + dx[o];
    dy：我免费了？！！
    但是大样例怎么不过啊 o(TヘTo)

    8:51 通过大样例
    居然输出的地方写成了 bfs(id[mp[{x_1, y_1}]], id[mp[{x_1, y_1}]])
    导致输出全是 1
    怎么能有人唐成这样。。。
    期望得分100pts【但是有句古话说得好，过了大样例相当于你的得分在[0,100]之间

    10:16 反应过来这题好像不用缩点
    并查集一下连通部分然后跑就完了
    但是不管了我爱缩点缩点爱我
    缩都缩了就这样吧。
    四处观望了一下发现有好多用AI的用各种聊天软件的
    打开WLAN列表发现一堆手机热点
    忘记收手机是这样的。。。
    还有挨着悄悄讨论的
    搞不懂有什么意义，真以为AI做出来的QQ聊到的成绩就是自己的了吗
    是平时刷题看题解还不够吗。。。
    上次考稀烂也没见老师制裁人啊……
    爆零了又能如何毕竟我是省选花了不止 300r 罚坐 9h 还冒雪回家最后爆零的选手
    可能是他们教练对他们模拟赛成绩有要求吧。。。
*/

总结

是的只有这道题有总结，没有别的原因，就是因为只有这道题挂分了。

还是在我个人认为我最擅长的 tarjan 缩点上挂的分

找找理由的话应该是昨天晚上一直在研究割点和桥，

而边双的代码和缩点的代码区别就是访问过的话不需要判是否在栈中，

然后今天就写顺手了。。。

痛失 50pts。

C. 均衡区间

预期 25 实际 25

此题用了 st 表的方法打了暴力分

题意简述： 原题面已经非常简练了所以直接 copy 过来

给定序列 ${an}$，定义一个区间 $[l, r]$ 是“均衡区间”当且仅当 $\min\limits{l\leq i\leq r}{ai} \neq \min\limits{1\leq i\leq n}{ai}$ 且 $\max\limits{l\leq i\leq r}{ai} \neq \max\limits{1\leq i\leq n}{a_i}$，需要对所有的 $i(1\leq i\leq n)$ 分别求出以 $i$ 为左端点和右端点的均衡区间的个数。

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
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int N = 1e6 + 29;

int n, m, k, id, ans1[N], ans2[N], f1[N][32], f2[N][32];
int a[N];

// st表预处理区间最大最小值
void stmax() {
    rep (k, 1, __lg(n))
        rep (i, 1, n - (1 << k) + 1) 
            f1[i][k] = max(f1[i][k - 1], f1[i + (1 << (k - 1))][k - 1]);
}

void stmin() {
    rep (k, 1, __lg(n))
        rep (i, 1, n - (1 << k) + 1) 
            f2[i][k] = min(f2[i][k - 1], f2[i + (1 << (k - 1))][k - 1]);
}

int findmax(int l, int r) {
    int s = __lg(r - l + 1);
    return max(f1[l][s], f1[r - (1 << s) + 1][s]);
}

int findmin(int l, int r) {
    int s = __lg(r - l + 1);
    return min(f2[l][s], f2[r - (1 << s) + 1][s]);
}

void tbcsolve() {
    cin >> n >> id;
    rep (i, 1, n) cin >> a[i];
    int ma = 0, mi = INF;
    rep (i, 1, n) {
        f1[i][0] = a[i];
        f2[i][0] = a[i];
        ma = max(ma, a[i]);
        mi = min(mi, a[i]);
    }
    stmax(); stmin();
    rep (i, 1, n - 3) {
        if (a[i] == ma || a[i] == mi) continue; // 如果端点为全序列最大值或最小值的话答案必为 0
        rep(j, i + 3, n) {
            if ((max(a[i], a[j]) ^ findmax(i, j)) && (min(a[i], a[j]) ^ findmin(i, j))) { // 模拟题意
                ans1[i]++;
                ans2[j]++;
            }
        }
    }
    rep (i, 1, n) cout << ans1[i] << " ";
    cout << endl;
    rep (i, 1, n) cout << ans2[i] << " ";
    cout << endl;
}

void tbcinit() {
    
}

signed main() {
    freopen ("interval.in", "r", stdin);
    freopen ("interval.out", "w", stdout);
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int SHENSELF = 1;
    // cin >> SHENSELF;
    while (SHENSELF--) {
        tbcinit();
        tbcsolve();
    }
    return 0;
}
/*
    11:09 想了很久正解真的想不出来了，饿了，困了，累了。
    写暴力！！！
    然后慢慢优化优化优化

    11:20 优化不动了
    感觉自己已经燃尽了。。。困得要死。。。
    休息！！！
    跟科技哥打模拟赛有什么意思。。。

    11:26 突然想到可以用st表再优化！！

    11:38 优化完毕，期望得分25pts
    特殊性质感觉要二分（？
    不会写。
*/

D. 数位

这题一看就不是我能做得了的题。

仔细看了看部分分，emmm，部分分也不是我能拿到的