2025牛客暑期多校训练营2

当时我们都在家，所以是回学校之后 vp 的，大概情况是这样的

STATUS	COUNT
AC	5
赛后补	3

重现赛排名 514，中途出了一些情况，当时三个人都相当红温，最后一人卡一道愣是一个都没调出来😡

A. Another Day of Sun#

这道是我写的，比较简单的线性 dp，本场唯二没有罚时的题之一。

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5
const int N = 500010;
6
const int MOD = 998244353;
7

8
int a[N];
9
long long f[N][2], g[N][2];
10

11
int main() {
12
    int T;
13
    scanf("%d", &T);
14
    while (T--) {
15
        int n;
16
        scanf("%d", &n);
17
        for (int i = 1; i <= n; ++i) {
18
            g[i][0] = g[i][1] = 0;
19
            f[i][0] = f[i][1] = 0;
20
            scanf("%d", &a[i]);
21
        }
22
        f[0][0] = 1;
23
        for (int i = 1; i <= n; ++i) {
24
            if (a[i] == -1) {
25
                f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
26
                f[i][1] = (f[i - 1][1] + f[i - 1][0]) % MOD;
27
                g[i][0] = (g[i - 1][0] + g[i - 1][1]) % MOD;
28
                g[i][1] = (g[i - 1][0] + f[i - 1][0] + g[i - 1][1]) % MOD;
29
            }
30
            else if (a[i] == 1) {
31
                f[i][1] = (f[i - 1][1] + f[i - 1][0]) % MOD;
32
                g[i][1] = (g[i - 1][0] + f[i - 1][0] + g[i - 1][1]) % MOD;
33
            }
34
            else {
35

36
                f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
37
                g[i][0] = (g[i - 1][0] + g[i - 1][1]) % MOD;
38
            }
39
        }
40
        printf("%lld\n", (g[n][0] + g[n][1]) % MOD);
41
    }
42
    return 0;
43
}

B. Bitwise Perfect ^队友#

这道当时出现了离谱的问题，其实刚开始队友想到的结论就是对的，但是挂在了一个知识盲区，看下面的代码

1
#include <iostream>
2
using namespace std;
3

4
int main() {
5
    int a = 512, t = 32;
6
    cout << (a >> t) << endl;
7
    return 0;
8
}

你以为他会是 0，实际上他移了一圈又回去了，输出了 512，错的代码就是是因为这个地方右移越界了。

代码量很小，除了上面那个坑别的地方不容易错，所以没自己写。

D. Donkey Thinks… ^补#

在背包的基础上增加了如果留空了，就每个物体扣 d_i，切入点是 v 很小，能放进去的物品数就很少，对于容量 v - u，最多就只能放 $\sum_{i = 1}^{v - u}\frac{v - u}{i} \approx \ln \left(u - v\right)$ 个，死去的高数还在追我。

当时主要的问题应该是 n 是 1e5，V 是 500，不敢相信 $\Theta(nV + V^3\log V)$ 能过。

另外还学到了一点优化的小方法

vector 的 emplace_back 比 push_back 快很多；
用 nth_element 可以近似 $\Theta(n)$ 把第 k 小的数放到第 k 位，然后再遍历一遍就可以近似线性的找出来前 k 个元素。

1
#include <iostream>
2
#include <vector>
3
#include <cstring>
4
#include <algorithm>
5

6
using namespace std;
7

8
typedef long long LL;
9
const int N = 510;
10
LL f[N];
11
vector<pair<LL, LL>> a[N]; // first 是快乐，second 是易碎
12

13
int main() {
14
    int T;
15
    scanf("%d", &T);
16
    while (T--) {
17
        int n, v;
18
        scanf("%d%d", &n, &v);
19
        for (int i = 1; i <= v; ++i) {
20
            a[i].clear();
21
        }
22
        for (int i = 1; i <= n; ++i) {
23
            int h, s, d;
24
            scanf("%d%d%d", &h, &s, &d);
25
            a[s].emplace_back(h, d);
26
        }
27
        LL res = 0;
28
        for (int u = 0; u < v; ++u) {
29
            fill(f + 1, f + v - u + 1, -2500000000000000);
30
            for (int i = 1; i <= v - u; ++i) {
31
                int k = (v - u) / i;
32
                LL mid = -2500000000000000;
33
                if (a[i].size() > k) {
34
                    nth_element(a[i].begin(), a[i].begin() + k - 1, a[i].end(), [&u](pair<LL, LL> a, pair<LL, LL> b) {
35
                        return a.first - a.second * u > b.first - b.second * u;
36
                    });
37
                    mid = a[i][k - 1].first - a[i][k - 1].second * u;
38
                    for (int j = v - u; j >= i; --j) {
39
                        f[j] = max(f[j], f[j - i] + mid);
40
                    }
41
                }
42
                for (pair<LL, LL> item : a[i]) {
43
                    if (item.first - item.second * u > mid) {
44
                        for (int j = v - u; j >= i; --j) {
45
                            f[j] = max(f[j], f[j - i] + item.first - item.second * u);
46
                        }
47
                    }
48
                }
49
            }
50
            res = max(res, f[v - u]);
51
        }
52
        printf("%lld\n", res);
53
    }
54
    return 0;
55
}

F. Field of Fire#

题很水，我写的，而且 -3，我在反思了……

挂掉的原因也很离谱

开区间 (l, r) 长度我写的 r - l + 1，应该是 r - l - 1;
特殊情况需要把整个区间全覆盖了，我写的是 s[1]++, s[n]—，然而应该是是 s[n + 1]—，另外，赛后发现这个统计是比较多余的，而且还有很大的犯错风险，如果在下面的循环里一并统计风险会小很多。

1
#include <iostream>
2
#include <vector>
3
#include <cstring>
4
using namespace std;
5

6
const int N = 500010;
7
int a[N], s[N];
8
vector<int> fire;
9

10
int main() {
11
    int T;
12
    scanf("%d", &T);
13
    while (T--) {
14
        fire.clear();
15
        int n, t;
16
        scanf("%d%d", &n, &t);
17
        memset(s, 0, sizeof(int) * (n + 1));
18
        for (int i = 1; i <= n; ++i) {
19
            scanf("%1d", &a[i]);
20
            if (a[i] == 1) fire.push_back(i);
21
        }
22
        for (int i : fire) {
23
            int l = i - t, r = i + t;
24
            if (r - l + 1 >= n) {
25
                s[1]++;
26
                break;
27
            }
28
            if (l <= 0) {
29
                s[1]++, s[r + 1]--;
30
                s[n + l]++;
31
            }
32
            else if (r > n) {
33
                s[l]++;
34
                s[1]++, s[r - n + 1]--;
35
            }
36
            else {
37
                s[l]++, s[r + 1]--;
38
            }
39
        }
40
        int cur_cnt = 0;
41
        s[0] = 0;
42
        for (int i = 1; i <= n; ++i) {
43
            s[i] += s[i - 1];
44
            if (s[i]) cur_cnt++;
45
        }
46
        if (fire.size() == 1) {
47
            printf("%d\n", max(0, n - t - 2));
48
        }
49
        else {
50
            int d = 0;
51
            for (int i = 0; i < (int)fire.size(); ++i) {
52
                int l = fire[i], r = fire[(i + 1) % fire.size()];
53
                if (l + 1 == r) continue;
54
                if (l > r) r += n;
55
                d = max(d, min(r - l - 1, t * 2) - min(t + 1, r - l - 1));
56
            }
57
            printf("%d\n", n - (cur_cnt - d));
58
        }
59
    }
60
    return 0;
61
}

G. Geometry Friend ^补#

这道题当时也是差一点，队友的思路是对的，但是发生了

循环内外变量重名（不致命）
被卡精度（致命）

大概有这几点经验和教训

能用 long long 不用 double
用 atan2 比 acos 算出来的更精准一点

原理上问题不是很大。

1
#include <iostream>
2
#include <vector>
3
#include <cmath>
4

5
using namespace std;
6
typedef long long LL;
7
const int N = 500010;
8

9
LL x[N], y[N];
10

11
LL cha(LL x1, LL y1, LL x2, LL y2) {
12
    return x1 * y2 - x2 * y1;
13
}
14

15
LL p(LL x) {
16
    return x * x;
17
}
18

19
int main() {
20
    int T;
21
    scanf("%d", &T);
22
    while (T--) {
23
        int n;
24
        LL px, py, mx = 0;
25
        scanf("%d%lld%lld", &n, &px, &py);
26
        for (int i = 1; i <= n; ++i) {
27
            scanf("%lld%lld", &x[i], &y[i]);
28
        }
29
        bool f = false;
30
        for (int i = 1; i <= n; ++i) {
31
            int j = i % n + 1;
32
            if (cha(x[i] - px, y[i] - py, x[j] - px, y[j] - py) < 0) {
33
                f = true;
34
                break;
35
            }
36
            mx = max(mx, p(x[i] - px) + p(y[i] - py));
37
        }
38
        if (f) {
39
            printf("%.15f\n", acos(0) * 4);
40
        }
41
        else {
42
            vector<pair<LL, LL>> a;
43
            for (int i = 1; i <= n; ++i) {
44
                if (mx == p(x[i] - px) + p(y[i] - py)) {
45
                    a.emplace_back(x[i], y[i]);
46
                }
47
            }
48
            a.emplace_back(a[0]);
49
            double res = 0;
50
            for (int i = 0; i < a.size() - 1; ++i) {
51
                int j = i + 1;
52
                double t = atan2(cha(a[i].first - px, a[i].second - py, a[j].first - px, a[j].second - py), (a[i].first - px) * (a[j].first - px) + (a[i].second - py) * (a[j].second - py));
53
                if (t <= 0) t += acos(0) * 4;
54
                res = max(res, t);
55
            }
56
            printf("%.15f\n", res);
57
        }
58
    }
59
    return 0;
60
}

H. Highway Upgrade ^补#

这道也是我的锅，想的和题解完全一样，做法也完全一样，但是写挂了，挂的原因

因为要建反图，和边相关的数组应该开两倍，因为一些数组开 int 一些数组开 long long，不知道什么情况边权的数组被挤下去了，然后没看到，忘记 * 2；
读入循环边界写错，似乎是把边数 m 写成了 n，恰好样例的 n = m，没有发现问题，后续检查的时候也没发现；
算直线交点用了 double 疑似精度不够出了点问题；

之后要注意的地方

无效点（不可达点）需要剔除，第一版没注意到，后面改了；
凸包题解的做法是按照斜率排序，而我按照截距排的，可能需要多加限制条件（但是我加对了，没挂在这儿）。

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
#include <queue>
5

6
using namespace std;
7
typedef long long LL;
8

9
const int N = 100010, M = 300010;
10

11
int head[N], head_rev[N], ver[M * 2], ne[M * 2], tot;
12
LL dis[N], dis_rev[N];
13
bool vis[N];
14
LL t[M * 2], w[M * 2];
15
pair<LL, LL> f[M];
16
int g[M];
17
pair<int, int> qu[M];
18
LL res[M];
19

20
void add(int *head, int x, int y, LL z, LL a) {
21
  ver[++tot] = y;
22
  ne[tot] = head[x];
23
  head[x] = tot;
24
  t[tot] = z;
25
  w[tot] = a;
26
}
27

28
void dijkstra(int *head, LL *dis, int s) {
29
  priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> q;
30
  q.push({0LL, s});
31
  dis[s] = 0;
32
  while (!q.empty()) {
33
    int x = q.top().second;
34
    q.pop();
35
    if (vis[x]) continue;
36
    vis[x] = true;
37
    for (int i = head[x]; i; i = ne[i]) {
38
      int y = ver[i];
39
      if (dis[y] > dis[x] + t[i]) {
40
        dis[y] = dis[x] + t[i];
41
        q.push({dis[y], y});
42
      }
43
    }
44
  }
45
}
46

47
int main() {
48
  ios::sync_with_stdio(0);
49
  cin.tie(0), cout.tie(0);
50
  int T;
51
  cin >> T;
52
  while (T--) {
53
    int n, m, q;
54
    cin >> n >> m;
55
    memset(head, 0, sizeof(int) * (n + 1));
56
    memset(head_rev, 0, sizeof(int) * (n + 1));
57
    memset(dis, 0x3f, sizeof(LL) * (n + 1));
58
    memset(dis_rev, 0x3f, sizeof(LL) * (n + 1));
59
    memset(vis, 0, sizeof(bool) * (n + 1));
60
    tot = 0;
61
    for (int i = 1; i <= m; ++i) {
62
      int x, y;
63
      LL z, a;
64
      cin >> x >> y >> z >> a;
65
      add(head, x, y, z, a);
66
      add(head_rev, y, x, z, a);
67
    }
68

69
    cin >> q;
70
    memset(res, 0x3f, sizeof(LL) * (q + 1));
71
    for (int i = 1; i <= q; ++i) {
72
      cin >> qu[i].first;
73
      qu[i].second = i;
74
    }
75
    sort(qu + 1, qu + q + 1);
76

77
    dijkstra(head, dis, 1);
78
    memset(vis, 0, sizeof(bool) * (n + 1));
79
    dijkstra(head_rev, dis_rev, n);
80
    int ttt = 0;
81
    for (int x = 1; x <= n; ++x) {
82
      for (int i = head[x]; i; i = ne[i]) {
83
        int y = ver[i];
84
        if (dis[x] == dis[0] || dis_rev[x] == dis[0]) continue;
85
        else f[++ttt] = {dis[x] + dis_rev[y] + t[i], w[i]};
86
      }
87
    }
88

89
    sort(f + 1, f + ttt + 1, [](pair<LL, LL> a, pair<LL, LL> b) {
90
      return a.first == b.first ? a.second > b.second : a.first < b.first;
91
    });
92
    int len = 0;
93
    for (int i = 1; i <= ttt; ++i) {
94
      if (i != 1 && f[i].first == f[g[len]].first) continue;
95
      while (len > 1 && (__int128_t)(f[i].first - f[g[len]].first) * (f[g[len]].second - f[g[len - 1]].second)  <= (__int128_t)(f[g[len]].first - f[g[len - 1]].first) * (f[i].second - f[g[len]].second)) {
96
                len--;
97
      }
98
      g[++len] = i;
99
    }
100
    for (int i = 1, j = 1; i <= q; ++i) {
101
      res[qu[i].second] = f[g[j]].first - f[g[j]].second * qu[i].first;
102
      while (j < len && res[qu[i].second] > f[g[j + 1]].first - f[g[j + 1]].second * qu[i].first) {
103
        j++;
104
        res[qu[i].second] = f[g[j]].first - f[g[j]].second * qu[i].first;
105
      }
106
    }
107
    for (int i = 1; i <= q; ++i) {
108
      cout << res[i] << '\n';
109
    }
110
  }
111
  return 0;
112
}

I. Identical Somehow ^队友#

这个签到题非常水，就两行。

L. Love Wins All ^队友#

这道也简单，我刚开始看错条件，以为是基环树 dp (题解上也提了一嘴)，但是无所谓，它被队友秒了。

~~要是真成基环树 dp 了，那就有意思了.~~

1
#include <iostream>
2
#include <vector>
3
#include <cstring>
4

5
using namespace std;
6

7
const int N = 500010;
8
const int MOD = 998244353;
9
bool vis[N];
10
int ne[N];
11
long long pre[N], suf[N];
12

13
int main() {
14
    int T;
15
    scanf("%d", &T);
16
    while (T--) {
17
        int n;
18
        scanf("%d", &n);
19
        memset(vis, 0, sizeof(int) * (n + 1));
20
        for (int i = 1; i <= n; ++i) {
21
            scanf("%d", &ne[i]);
22
        }
23
        vector<int> cir;
24
        int odd = 0;
25
        for (int i = 1; i <= n; ++i) {
26
            if (!vis[i]) {
27
                int x = i, cnt = 0;
28
                do {
29
                    vis[x] = true;
30
                    cnt++;
31
                    x = ne[x];
32
                } while (!vis[x]);
33
                cir.emplace_back(cnt);
34
                odd += cnt & 1;
35
            }
36
        }
37
        if (odd > 2) printf("0\n");
38
        else if (odd == 2) {
39
            long long res = 1;
40
            for (int cnt : cir) {
41
                if (cnt & 1) res = res * cnt % MOD;
42
                else res = res * (cnt > 2 ? 2 : 1) % MOD;
43
            }
44
            printf("%lld\n", res);
45
        }
46
        else {
47
            long long res = 0;
48
            pre[0] = 1;
49
            for (int i = 1; i <= cir.size(); ++i) {
50
                pre[i] = pre[i - 1] * (cir[i - 1] > 2 ? 2 : 1) % MOD;
51
            }
52
            suf[cir.size() + 1] = 1;
53
            for (int i = cir.size(); i; --i) {
54
                suf[i] = suf[i + 1] * (cir[i - 1] > 2 ? 2 : 1) % MOD;
55
            }
56
            for (int i = 1; i <= cir.size(); ++i) {
57
                res = (res + pre[i - 1] * suf[i + 1] % MOD * ((long long)cir[i - 1] * cir[i - 1] / 4)) % MOD;
58
            }
59
            printf("%lld\n", res);
60
        }
61
    }
62
    return 0;
63
}

Star's Blog

A. Another Day of Sun#

B. Bitwise Perfect 队友#

D. Donkey Thinks… 补#

F. Field of Fire#

G. Geometry Friend 补#

H. Highway Upgrade 补#

I. Identical Somehow 队友#

L. Love Wins All 队友#