【NAC2025】2025 拼题A XCPC 系统测试赛

这场相当于 vp 了一下 NAC2025，最大的感受就是看英文体面太折磨了，看不懂不致命，理解错了自以为看懂了最致命。

结束之后 OMS 客户端直接自己退了代码看不到了，之前做过的题的代码也是根据记忆重写的，下面的题是按照难度顺序排列的。

K. SLA Tomography#

这道题题目特别难读，里面一大堆的专业的词汇，读了好半天理解了之后发现就是一个简单的贪心，对每个单调不增的子段新开辟一块宽度为当前子段最大值 - 上一个子段最小值 + 1 的空间存多出来的，直接就秒了。

1
#include <iostream>
2

3
using namespace std;
4
typedef long long LL;
5

6
int main() {
7
    int n;
8
    scanf("%d", &n);
9
    LL cur, pre = 0, res = 1;
10
    for (int i = 1; i <= n; ++i) {
11
        scanf("%lld", &cur);
12
        if (cur > pre) res += cur - pre + 1;
13
        pre = cur;
14
    }
15
    printf("%lld\n", res);
16
    return 0;
17
}

H. Ornaments on a Tree#

按我的理解，这是一道略简单一点的树形 dp，洛谷上题解说是贪心，但是说的其实是一个意思。当时我翻译的这道题，然后想出来思路之后讲了一下，没问题就去写了，期间想错，改状态转移方程少改一个 WA 一发。

我维护了一个 f_i 表示当前点的固定答案，当前点可以随意填时当前填 0，否则当前填固定值；r_i 表示孩子都尽可能往大了填时当前点自己最大还能填到多少，如果是固定值那么 r = 0。

状态转移也简单，让孩子都贪心的填最大，特判溢出的情况，如果没有调整空间就输出 -1，如果还有就调到能填的最大值。

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
const int N = 200010;
5
typedef long long LL;
6
vector<int> ed[N];
7
LL a[N], f[N], r[N];
8
int n, k;
9

10
bool dp(int x, int fa) {
11
    LL ls = 0, rs = 0;
12
    for (int y : ed[x]) {
13
        if (y == fa) continue;
14
        if (!dp(y, x)) return false;
15
        ls += a[y] == -1 ? 0 : a[y];
16
        rs += r[y];
17
        f[x] += f[y];
18
    }
19
    if (ls + a[x] > k) return false;
20
    if (a[x] != -1) f[x] += min(a[x] + rs, k - ls); // 第一发的这里的 k 没有减 ls
21
    else if (rs >= k - ls) f[x] += k - ls, r[x] = 0;
22
    else f[x] += rs, r[x] = k - ls - rs;
23
    return true;
24
}
25

26
int main() {
27
    scanf("%d%d", &n, &k);
28
    for (int i = 1; i <= n; ++i) {
29
        scanf("%lld", &a[i]);
30
    }
31
    for (int i = 1; i < n; ++i) {
32
        int x, y;
33
        scanf("%d%d", &x, &y);
34
        ed[x].emplace_back(y);
35
        ed[y].emplace_back(x);
36
    }
37
    if (!dp(1, 0)) printf("-1\n");
38
    else printf("%lld\n", f[1] + r[1]);
39
    return 0;
40
}

B. Circle of Leaf ^队友#

他们在研究 A 的时候我往后读题，发现这个似乎可做，队友先研究明白了，思路刚开始就是对的，而且很完整，低级错误 WA 三发。

后来还发生了

下午	我 : “你怎么不取模”
晚上	洛谷 : “Wrong Answer.wrong answer On line 1 column 1, read -, expected 3.”

现在唯一的心理安慰是：我至少没把模数抄错。

f_{i, 0} 表示当前连通块到根节点除了 leaf path 还有连边的方案数，f_{i, 1} 表示当前连通块只能通过通过 leaf path 连接根节点的方案数。

枚举删 leaf path 还是指向父亲的边进行状态转移。

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

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 200010;
8
const int MOD = 998244353;
9
vector<int> ed[N];
10
LL f[N][2]; // 0：没有额外的边 1：有额外的边
11

12
void dp(int x) {
13
    f[x][0] = f[x][1] = 1;
14
    vector<LL> s1, suf, s0;
15
    for (int y : ed[x]) {
16
        dp(y);
17
        s1.emplace_back(f[y][1]);
18
        s0.emplace_back((f[y][0] + f[y][1]) % MOD);
19
        f[x][0] = (f[x][0] * ((f[y][0] + f[y][1]) % MOD)) % MOD;
20
    }
21
    if (s0.empty()) return;
22
    suf = s0;
23
    suf.emplace_back(1LL);
24
    for (int i = suf.size() - 2; i >= 0; --i) {
25
        suf[i] = (suf[i] * suf[i + 1]) % MOD;
26
    }
27
    f[x][1] = 0;
28
    LL pre = 1;
29
    for (int i = 0; i < s0.size(); ++i) {
30
        f[x][1] = (f[x][1] + (pre * s1[i] % MOD * suf[i + 1] % MOD)) %MOD;
31
        pre = (pre * s0[i]) % MOD;
32
    }
33
}
34

35
int main() {
36
    int n;
37
    scanf("%d", &n);
38
    for (int i = 1; i < n; ++i) {
39
        int x, y;
40
        scanf("%d%d", &x, &y);
41
        ed[x].emplace_back(y);
42
    }
43
    dp(1);
44
    printf("%lld\n", f[1][0]);
45
    return 0;
46
}

L. Solar Farm ^补#

这道题通过率低的可怜,当时我们都感觉在正方形周围暴力一个小区间能过……然而没有，WA 了好几发，后来调大了一下区间长度，然后就莫名其妙的过了。

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

4
using namespace std;
5
typedef long long LL;
6

7
int main() {
8
    int T;
9
    scanf("%d", &T);
10
    while (T--) {
11
        LL r, w, h;
12
        scanf("%lld%lld%lld", &r, &w, &h);
13
        if (w < h) swap(w, h);
14
        LL res = 0;
15
        LL w_cnt = ((long double)r * sqrtl(2) / w);
16
        for (LL i = max(1LL, w_cnt - 1000); i <= w_cnt + 1000; ++i) {
17
            if ((__int128_t)i * w * i * w + h * h > (__int128_t)r * r * 4) break;
18
            LL j = floorl(sqrtl(r * r * 4 - i * i * w * w) / h);
19
            if ((__int128_t)i * i * w * w + (__int128_t)j * j * h * h > (__int128_t)r * r * 4) j--;
20
            res = max(res, i * j);
21
        }
22
        printf("%lld\n", res);
23
    }
24
    return 0;
25
}

D. Geometry Rush ^补#

这道很可惜，难度还行，属于是相见恨晚了，最后四十分钟发现他的时候已经来不及了，当时情急之下想麻烦了，又写线段交又写特判的，最后挂了没调出来。

实际上甚至线段交都不用写，遍历每个小于 w 的 i，求一下两条折线中间夹的两个整数边界，然后和上一次维护的边界取 max 和 min 更新。测试表明数据没有专门卡这种一个竖线分多段的情况，如果处理不当也会挂掉（比如我洛谷上过了，然后被自己卡掉了）。

其他小细节也容易挂，比如一定要找最后一条终点在 i 的线段，判断奇偶性是否合法……

1
#include <iostream>
2
#define x first
3
#define y second
4
using namespace std;
5
typedef long long LL;
6
typedef pair<LL, LL> PLL;
7
const int N = 100010;
8

9
PLL a[N], b[N]; // 上下边界
10

11
PLL operator -(PLL a, PLL b) {
12
    return {a.x - b.x, a.y - b.y};
13
}
14

15
LL operator *(PLL a, PLL b) {
16
    return a.x * b.y - a.y * b.x;
17
}
18

19
int area(PLL a, PLL b, PLL c) {
20
    LL prod = (b - a) * (c - a);
21
    if (prod == 0) return 0;
22
    else if (prod < 0) return -1;
23
    else return 1;
24
}
25

26
int main() {
27
    int n, m, l1 = 0, l2 = 0;
28
    LL w, h;
29
    scanf("%d%d%lld%lld", &n, &m, &w, &h);
30
    for (int i = 1; i <= n; ++i) {
31
        PLL p;
32
        scanf("%lld%lld", &p.x, &p.y);
33
        if (l1 >= 2 && p.x == a[l1].x && p.x == a[l1 - 1].x) a[l1] = p; // 竖线只留两端
34
        else a[++l1] = p;
35
    }
36
    for (int i = 1; i <= m; ++i) {
37
        PLL p;
38
        scanf("%lld%lld", &p.x, &p.y);
39
        if (l2 >= 2 && p.x == b[l2].x && p.x == b[l2 - 1].x) b[l2] = p;
40
        else b[++l2] = p;
41
    }
42
    LL lt = 0, rt = 0;
43
    for (int i = 1, j = 1, k = 1; i <= w; ++i) {
44
        while (j < l1 - 1 && a[j + 1].x < i) j++;
45
        while (j < l1 - 1 && a[j + 2].x == i) j++;
46
        while (k < l2 - 1 && b[k + 1].x < i) k++;
47
        while (k < l2 - 1 && b[k + 2].x == i) k++;
48
        LL L, R, l, r;
49
        if (a[j].x == a[j + 1].x) R = min(a[j].y, a[j + 1].y) - 1; // 特判共线
50
        else {
51
            l = -h, r = h;
52
            while (l < r) {
53
                LL mid = l + r + 1 >> 1;
54
                if (area(a[j], a[j + 1], {(LL)i, mid}) == -1) l = mid; // 上边界右侧
55
                else r = mid - 1;
56
            }
57
            R = l;
58
        }
59
        if (b[k].x == b[k + 1].x) L = max(b[k].y, b[k + 1].y) + 1;
60
        else {
61
            l = -h, r = h;
62
            while (l < r) {
63
                LL mid = l + r >> 1;
64
                if (area(b[k], b[k + 1], {(LL)i, mid}) == 1) r = mid; // 下边界左侧
65
                else l = mid + 1;
66
            }
67
            L = l;
68
        }
69
        if (i & 1) { // 奇偶性
70
            if (!(L & 1)) L++;
71
            if (!(R & 1)) R--;
72
        }
73
        else {
74
            if (L & 1) L++;
75
            if (R & 1) R--;
76
        }
77
        lt = max(lt - 1, L);
78
        rt = min(rt + 1, R);
79
        if (lt > rt) {
80
            printf("impossible\n");
81
            return 0;
82
        }
83
    }
84
    printf("%lld %lld\n", lt, rt);
85
    return 0;
86
}

还差个 A 题数学题🤯

Star's Blog

K. SLA Tomography#

H. Ornaments on a Tree#

B. Circle of Leaf 队友#

L. Solar Farm 补#

D. Geometry Rush 补#

B. Circle of Leaf ^队友#

L. Solar Farm ^补#

D. Geometry Rush ^补#