2024 牛客多校(6)

8 月了，月更博主继续更新。
比赛链接

H Genshin Impact's Fault

原神题我不看，队友 10 分钟过了。

B Cake 2

画了几个图之后找了下规律，炜神猜了个公式直接交，WA 了两发之后发现没有特判我强调的 \(k=\frac{2}{n}\) 的情况... 我改了改 43 分钟过了。

D Puzzle: Wagiri

第一感觉和之前 VP 浙江省赛的这个题 很像，想了下这题不就是把 切 删掉之后剩下的 輪 是一些环，那反过来找出环之后判断是不是联通就行了。有人分不清是边双还是点双，问了下队友之后套了个边双板子 100 分钟过了。

A Cake

不会做，队友交流之后三发罚时 107 分钟切了。

I Intersecting Intervals

写完 D 之后炜神拉我去看这个题，并给我讲了一个 DP，但是他只知道定义状态，甚至连转移式都不会写！然后交流了一会儿发现我连题都读错了，我以为是所有行的交集非空，结果只用保证相邻两行... 卡 F 的时候我又细想了一下发现确实是那个 DP 状态，硬点选某个数，枚举和上一行的交点就可以很容易写出一个 \(O(nm^2)\) 的 DP 方程，然后这东西显然可以用前后缀最大值优化成 \(O(nm)\) 难以置信这么简单... 217 分钟 0 罚时过了

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
//#pragma GCC optimize(2,"Ofast","inline")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e6 + 5;

void MAIN() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> a(n + 1, vector<ll>(m + 1, 0));
    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    vector<ll> sum(m + 1, 0), mx(m + 1, 0), mn(m + 1, 0), suf(m + 1, 0), pre(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) sum[j] = sum[j - 1] + a[i][j];
        for (int j = 1; j <= m; j++) mn[j] = min(mn[j - 1], sum[j]);
        mx[m] = sum[m];
        for (int j = m - 1; j >= 0; j--) mx[j] = max(mx[j + 1], sum[j]);
        suf[m] = dp[i - 1][m] + mx[m];
        for (int k = m - 1; k >= 1; k--) {
            ll tmp = dp[i - 1][k] + mx[k];
            suf[k] = max(suf[k + 1], tmp);
        }
        pre[1] = dp[i - 1][1] - mn[0];
        for (int k = 2; k <= m; k++) {
            ll tmp = dp[i - 1][k] - mn[k - 1];
            pre[k] = max(pre[k - 1], tmp);
        }
        for (int k = 1; k <= m; k++) {
            dp[i][k] = max(suf[k] - mn[k - 1], pre[k] + mx[k]);
        }
    }
    ll ans = -1e18;
    for (int i = 1; i <= m; i++) ans = max(ans, dp[n][i]);
    cout << ans << '\n';
}

int main() {
//#ifdef DEBUG
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//#endif
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) MAIN();
    return 0;
}

F Challenge NPC 2

看到哈密尔顿图，搭配这个题目名字，本来觉得是一个超难图论题，结果是个模拟/乱搞... 稍微画了一下提出一个假想法被 hack 后，杰哥说判掉菊花图之外的森林，有很多合法方案，遂直接爆搜，很快就写出了天才的排序代码并 RE 两发。 

1
sort(p + 1, p + 1 + n, [&](int x, int y) {return du[p[x]] > du[p[y]]; });
修改后本地测了下随机大数据，很快啊，平均 500 ms 就能跑出答案。交上去 TLE。

没有思路...赶快把另一个队友拉过来想 F，我发现了层数大于 4 就可以分奇偶层走，扔下这个结论之后我就去想 I 了。炜神有想法之后写了个 F 的分类讨论，但是处理层数较小的树的时候始终有问题。

已经封榜了我们还没有过这个几百人的题，担心过不了，我过 I 之后一直在开新题和帮他们看 F 之间摇摆...xsj 发现可以把森林连成一棵树就可以解决这个问题，并且很快写出了代码，但是他的实现太过抽象，每次接的时候树高不增，导致处理一些情况的时候还是有问题。时间紧急，我让他赶快把爆搜拼上去搞这种情况。在他写的时候我又细想了一下如果每次连树都增加树高的话，只需要特判一种情况。我告诉杰哥之后他竟然给我说懒得改了！！拼上暴力之后还是 TLE，很乐的是另一个队友几乎同时交的代码 AC 了，贡献一发罚时之后，最后以 9 发的罚时惊险拿下此题。

赛后 xsj 发现只需要 random_shuffle 就跑得飞快。what can i say，感觉他做这种乱搞题很厉害，周一 hdu 多校 claris 场的两个随机数题都是他切的，随机数大神！

J Stone Merging

感觉 F 做快点这题三个人想说不定就出来了啊。当时我也想了从最后一步考虑，如果机器编号全有就寄了，但感觉操作步骤太难考虑了。结果题解就是选出一个没出现的机器 \(x\)，先预处理一步之后全用这个机器处理!这一步需要合并的石子数是 \(y=(n-1)\mod (x-1)+1\)，发现 \(y\) 小于等于一半的 \(n\)，再考虑号码为 \(y\) 的石子个数无论小于一半或者大于一半都可以做第一步，那就完了。

花絮

比赛最后二十分钟感觉出不来题了，开始摆烂。抽卡！帮队友十连出佩佩，什么水平？什么水平？什么水平？什么水平？什么水平？什么水平？什么水平？什么水平？什么水平？什么水平？什么水平？

ACM
#多校
2024 牛客多校(6)
https://widsnoy.top/posts/b95d/
作者
widsnoy
发布于
2024年8月1日
许可协议