2026“钉耙编程”中国大学生算法设计春季联赛（2）

CubeCat

网站公告

欢迎访问我的博客！

Learn More

标签

Algorithm

CubeCat

网站公告

欢迎访问我的博客！

Learn More

标签

Algorithm

CubeCat

网站公告

欢迎访问我的博客！

Learn More

标签

Algorithm

2133 字

5 分钟

2026“钉耙编程”中国大学生算法设计春季联赛（2）

2026-03-27

杭电

Algorithm

这个网站是雨沐ネブラ (Amekai_nebula) 的个人博客网站

未来这个网站会更新若干内容，包括不局限于题解、感悟等内容

1001-湖上午后 #

题意： 给出两个非负整数 $s$ 和 $t$ , 求出方程 $a \times b = (a \text{ or } b) \times (a \text{ and } b)$ 在 $a, b$ 都取 $[s, t]$ 中整数时一共有多少组解。答案对 998244353 取模。

有一个经典的等式是 $a + b = (a \& b) + (a | b)$ , 知道了这个之后可以记 $x = a \& b, y = a | b$

这样两个式子组合就是 $a \times b = x \times y, a + b = x + y$ 。最后只有 $a = x, b = y$ 或者 $a = y, b = x$ 两种解。但是只需要求一种就行，另外一部分可以直接乘2得到

假设这里是 $a = x$ ， $a$ 的二进制为1的位就必须是 $b$ 的子集，这里就要用到数位dp了，定义 dp[i][j][k][r] (i : 当前是从高到低第几位，j : 是否紧贴最小值，k : 是否紧贴最大值，r : 是否有 a < b) 这个dp第一维度可以压掉，所以后面代码中下标 $i$ 代表这里的 $j$ ，剩下的一次对应。初始值也就是紧贴上下界，没有 $a < b$ 关系 dp[1][1][0] = 1

之前有提到子集的关系，所以 $a_i, b_i$ 的情况只有三种 {0, 0}, {0, 1}, {1, 1}。这里转移只说一下 $j$ 的变化，其他也是类似的。如果 $j = true$ 说明此时挨着下界，所以 $a_i$ 的这一位不能小于 $s_i$ if(i == 1 && ai < si) continue; 如果当前依然有 $a_i = s_i$ 那么 $j$ 就还是 1 ，否则就变化为0 int ii = (i == 1 && ai == si) ? 1 : 0;

你可能会好奇为什么会有一个 $k$ 用来表示 $a < b$ 。但这其实是题目要求是这个，我们已有的限制只能保证 $a \le b$

详细转移看下面代码，数位dp一般都从最高位开始，方便确定大小关系。数位dp还是太难写了！

1
void solve(){
2
    string s, t;
3
    cin >> s >> t;
4
    int tt = 0, ss = 0;
5
    for(char c : s) {
6
        ss = (ss * 2 + c - '0') % mod;
7
    }
8
    for(char c : t) {
9
        tt = (tt * 2 + c - '0') % mod;
10
    }
11
    int ans = (tt - ss + 1 + mod) % mod;
12

13
    if (s.size() < t.size()) {
14
        s = string(t.size() - s.size(), '0') + s;
15
    } else if (t.size() < s.size()) {
16
        t = string(s.size() - t.size(), '0') + t;
17
    }
18
    int n = s.length();
19

20
    int dp[2][2][2] = {0};
21
    vector<pii> ch = {{0, 0}, {0, 1}, {1, 1}};
22
    dp[1][1][0] = 1;
23
    fore(_, 0, n) {
24
        int si = s[_] - '0', ti = t[_] - '0';
25
        int ndp[2][2][2] = {0};
26
        fore(i, 0, 2) fore(j, 0, 2) fore(k, 0, 2) {
27
            for(auto[ai, bi] : ch) {
28
                if(i == 1 && ai < si) continue;
29
                int ii = (i == 1 && ai == si) ? 1 : 0;
30

31
                if(j == 1 && bi > ti) continue;
32
                int jj = (j == 1 && bi == ti) ? 1 : 0;
33

34
                int kk = (k == 0 && ai == bi) ? 0 : 1;
35
                ndp[ii][jj][kk] += dp[i][j][k];
36
                ndp[ii][jj][kk] %= mod;
37
            }
38
        }
39
        memcpy(dp, ndp, sizeof(dp));
40
    }
41
    int S = 0;
42
    fore(i, 0, 2) fore(j, 0, 2) {
43
        S = (S + dp[i][j][1]) % mod;
44
    }
45
    S = S * 2 % mod;
46
    ans = (ans + S) % mod;
47
    cout << ans << endl;
48
}

1002-庭扫落樱 #

题意： 在坐标系的第一象限有 $n$ 个激光发射器，每个位于 $x_i, y_i$ 每个都有一个方向 $d \in \{0, 1, 2, 3\}$ 分表代表上右下左。输出最少放置多少个障碍物可以阻挡所有射线，保证不会有两个发射器互相照射，障碍物可以放在发射器那个点上

容易发现有些发射器不用单独去管，如果两个发射器方向相同并且一个发射器光线在另一个的光线上，后面那个发射器就可以排除开

这样排除一些之后最少障碍物数量 = 总数 - 重合的点数

尽量省就要一个障碍物覆盖多个光线，这里删掉一些后最多就是覆盖两个，这就有点像二分图了，上下和左右作为二分图左侧和右侧，两个光线有交点就把他们连线。结果就是总数减去最大匹配数

1
class BP {
2
public:
3
    vector<int> vis, link;
4
    vector<vector<int>> p;
5
    int n, m;
6
    BP(int n, int m) : n(n), m(m) {
7
        p.resize(n + 1);
8
        vis.resize(m + 1, false), link.resize(m + 1, -1);
9
    }
10
    inline void add(int u, int v) { p[u].emplace_back(v); };
11
    bool dfs(int s) {
12
        for(int to : p[s]) {
13
            if(vis[to]) continue;
14
            vis[to] = true;
15
            if(link[to] == -1 || dfs(link[to])) {
16
                link[to] = s;
17
                return true;
18
            }
19
        }
20
        return false;
21
    }
22
    int match() {
23
        int ans = 0;
24
        fore(i, 1, n + 1) {
25
            fill(vis.begin() + 1, vis.end(), false);
26
            if(dfs(i)) ans++;
27
        }
28
        return ans;
29
    }
30
};
31

32
void solve(){
33
    int n;
34
    cin >> n;
35
    map<int, int> mp1, mp2, mp3, mp4;
36
    vector<pii> up, down, right, left;
37
    int x, y, d;
38
    fore(i, 1, n + 1) {
39
        cin >> x >> y >> d;
40
        if(d == 0) {
41
            if(!mp1.count(x)) mp1[x] = y;
42
            else mp1[x] = max(mp1[x], y);
43
        }else if(d == 1) {
44
            if(!mp2.count(y)) mp2[y] = x;
45
            else mp2[y] = max(mp2[y], x);
46
        }else if(d == 2) {
47
            if(!mp3.count(x)) mp3[x] = y;
48
            else mp3[x] = min(mp3[x], y);
49
        }else {
50
            if(!mp4.count(y)) mp4[y] = x;
51
            else mp4[y] = min(mp4[y], x);
52
        }
53
    }
54
    for(auto[x, y] : mp1) up.emplace_back(x, y);
55
    for(auto[x, y] : mp3) down.emplace_back(x, y);
56
    for(auto[y, x] : mp2) right.emplace_back(x, y);
57
    for(auto[y, x] : mp4) left.emplace_back(x, y);
58

59
    BP bp(up.size() + down.size(), right.size() + left.size());
60
    int l = 0;
61
    for(int i = 0; i < up.size(); i++) {
62
        l++;
63
        x = up[i].first, y = up[i].second;
64
        int r = 0;
65
        for(auto[xx, yy] : right) {
66
            r++;
67
            if(xx <= x && yy >= y) bp.add(l, r);
68
        }
69
        for(auto[xx, yy] : left) {
70
            r++;
71
            if(xx >= x && yy >= y) bp.add(l, r);
72
        }
73
    }
74
    for(int i = 0; i < down.size(); i++) {
75
        l++;
76
        x = down[i].first, y = down[i].second;
77
        int r = 0;
78
        for(auto[xx, yy] : right) {
79
            r++;
80
            if(xx <= x && yy <= y) bp.add(l, r);
81
        }
82
        for(auto[xx, yy] : left) {
83
            r++;
84
            if(xx >= x && yy <= y) bp.add(l, r);
85
        }
86
    }
87
    cout << up.size() + down.size() + right.size() + left.size() - bp.match() << endl;
88
}

1003-竹林清韵 #

题意： 给出一个有 $n$ 个数的数组，铃仙每次可以选取任意一个数，因幡帝会固定选择数组的前 $m$ 个数，对所有的 $m = 1, 2, 3, 4 ... n - 1$ 最大化铃仙所选数的和

题目条件翻译一下就是数组的前 $k \times (m + 1)$ 个数中最多只能选择 $k$ 个数。如果 $m$ 是固定的，那这个直接用小根堆即可，每次碰到新的数都尝试加入堆中，如果容量超出可选数的限制就 pop 掉一个，最后统计和即可

但这里是所有的 $m$ 这么做就是 $n^2log(n)$ 肯定不行了，关键是从前面开始这个至多选几个很处理，从后开始往往会得到比较好的性质: 假设最后总共要选 $k$ 个数，从 $(k - i) \times (m + 1) + 1$ 到 $n$ 至少选 $i$ 个数，这个至少选多少个就容易处理的多，因为这里已经选择出来的数之后不会被替代了，之前已经选的是可能被后面更大的数更换的

每次只需要知道某个区间最大值即可，这个可以用线段树维护，当某个数被选择时就将其替换为最小值就等同删除了。总共选择的数的个数是一个调和级数，每次查询修改是 $log(n)$ 最终复杂度是 $nlog^2n$

1
class SegTree{
2
private:
3
    int n;
4
    vector<int> a;
5
    vector<pii> info;
6
    pii bet(pii x, pii y) {
7
        if(x.first != y.first) return x.first > y.first ? x : y;
8
        return x.second < y.second ? x : y;
9
    }
10

11
    void build(int i, int l, int r) {
12
        if(l == r)
13
            info[i] = {a[l], l};
14
        else {
15
            int mid = (l + r) >> 1;
16
            build(i << 1, l, mid);
17
            build(i << 1 | 1, mid + 1, r);
18
            info[i] = bet(info[i << 1], info[i << 1 | 1]);
19
        }
20
    }
21
    void set(int pos, int val, int l, int r, int i) {
22
        if(pos < 1 || pos > n) return;
23
        if(l == r) {
24
            a[pos] = val;
25
            info[i] = {val, pos};
26
            return;
27
        }
28
        int mid = (l + r) >> 1;
29
        if(pos <= mid) set(pos, val, l, mid, i << 1);
30
        else set(pos, val, mid + 1, r, i << 1 | 1);
31
        info[i] = bet(info[i << 1], info[i << 1 | 1]);
32
    }
33
    pii query(int jobl, int jobr, int l, int r, int i) {
34
        if(jobl <= l && r <= jobr) return info[i];
35
        int mid = (l + r) >> 1;
36
        pii ans = {-1, -1};
37
        if(jobl <= mid) ans = bet(query(jobl, jobr, l, mid, i << 1), ans);
38
        if(jobr > mid) ans = bet(query(jobl, jobr, mid + 1, r, i << 1 | 1), ans);
39
        return ans;
40
    }
41
public:
42
    SegTree(int n, vector<int>& arr) : n(n), info((n << 2) + 1), a(n + 1) {
43
        fore(i, 1, n + 1) a[i] = arr[i];
44
        build(1, 1, n);
45
    }
46
    void set(int pos, int val) { set(pos, val, 1, n, 1);}
47
    pii query(int jobl, int jobr) {return query(jobl, jobr, 1, n, 1);}
48
    int get(int pos) {return a[pos];}
49
};
50

51
void solve(){
52
    int n;
53
    cin >> n;
54
    vector<int> val(n + 1);
55
    fore(i, 1, n + 1) cin >> val[i];
56
    SegTree seg(n, val);
57
    for(int len = 1; len <= n - 1; len++) {
58
        int ans = 0;
59
        vector<int> used;
60
        for(int k = n / (len + 1); k >= 0; k--) {
61
            if(k * (len + 1) + 1 > n) continue;
62
            auto[maxn, pos] = seg.query(k * (len + 1) + 1, n);
63
            ans += maxn;
64
            used.emplace_back(pos);
65
            seg.set(pos, -inf);
66
        }
67
        for(int c : used) seg.set(c, val[c]);
68
        cout << ans << ' ';
69
    }
70
    cout << endl;
71
}

1004-三途川畔 #

题意： 给定两个非负整数 $n$ 和 $k$ ，请你构造 $n$ 个正整数，使得这些数的乘积大于或等于它们的和，并且两者的差恰好等于 $k$

合乘积有关那就是1越多越好，所以假设有 $n - 2$ 个 1，剩下一下 $x, y$ 。所以目前要满足的关系就是 $x \times y = x + y + n - 2 + k$

一定要化简！化简得到 $(x - 1)(y - 1) = n + k + 1$ 显然 $x = 2$ 时 $y$ 一定有解 $n + k$ 构造完毕

1
void solve(){
2
    int n, k;
3
    cin >> n >> k;
4
    fore(i, 1, n - 2 + 1) cout << 1 << ' ';
5
    cout << 2 << ' ' << n + k << endl;
6
}

1007-云端航迹 #

题意： 给出一个有 $n$ 个数的数组，Alice和Bob轮流在任意一个子数组中玩游戏，Alice先手，每次可以选择任意一个数删除，任何时候集合中所有数的异或和为0，则最后一次操作数组的人输掉游戏，问在所有的子数组中两人分别获胜的次数

Alice 先手想要赢子数组大小必须是偶数，(如果是奇数，对手面对的就是偶数，此时一直总的异或和是 S 且不为 0 ，对方只需要在这个数组中选一个数满足 $a_i != S$ 即可一直拖下去，直到最后Alice选完最后一个数。并且这个事对手一定做得到，假设所有位置的值都是 S ，又因为元素个数是偶数，出现这种Alice已经输了，所以对手一定找得到这个数)。

其次开始这个异或和不是0，这里同样和上面一样思考，我要找一个 $a_i != S$ ，但是是一定找得到的，可以一直拖到对手走到必败态或者最后全部取完

具体实现就是维护前缀异或和，对左边按奇偶分类，并且用cnt数组记录所有前缀中为某个值的位置有多少个

1
void solve(){
2
    int n;
3
    cin >> n;
4
    vector<int> val(n + 1);
5
    vector<int> pre(n + 1);
6
    fore(i, 1, n + 1) {
7
        cin >> val[i];
8
        pre[i] = pre[i - 1] ^ val[i];
9
    }
10
    vector<int> cnt1(4e5 + 5), cnt2(4e5 + 5);
11
    int even = 0, odd = 0;
12
    int ans = 0;
13
    fore(i, 0, n + 1) {
14
        if(i & 1) {
15
            ans += odd;
16
            odd += 1;
17
            ans -= cnt1[pre[i]];
18
            cnt1[pre[i]]++;
19
        }else {
20
            ans += even;
21
            even += 1;
22
            ans -= cnt2[pre[i]];
23
            cnt2[pre[i]]++;
24
        }
25
    }
26
    cout << ans << ' ' << (n + 1) * n / 2 - ans << endl;
27
}

1009-微缩庭园 #

题意： 给出一个 $n \times m$ 的网格，你可以随意填充黑色，但是必须保证任意两个黑色单元格不共享一条边，并且这个最终的图是对称的，问最多填充多少个黑色方块

网格图有个结论是最多选出 $\lceil nm / 2 \rceil$ 个不相邻的单元格

如果 $n, m$ 中有一个是奇数，那么交替填充就可以到达这个上界，问题是都是偶数怎么办，这时候就必须舍弃掉一行或者一列，结果就是 $nm / 2 - min(n, m)$

1
void solve(){
2
    int n, m;
3
    cin >> n >> m;
4
    if(n % 2 || m % 2) {
5
        cout << (n * m + 1) / 2 << endl;
6
    }else {
7
        cout << n * m / 2 - min(n, m) << endl;
8
    }
9
}

1010-静海拾光 #

题意： 每个测试用例的共一行，两个数 $x$ 和 $k$ ，表示查询所有元素和不超过 $x$ 的非空正整数序列按字典序升序排序后的第 $k$ 个序列。保证一定存在

这种问题我们首先要知道的是 $f(x)$ ，总和是 $x$ 时的序列一共有多少个，官方题解用的是类似数学归纳法证明的，优点是证明过程简单，但是你得观察出规律，这里有一个更好的证明方式

采用递推思想假设 $f(x - 1)$ 是已知的来求 $f(x)$ ，f(x) 中以1开头的序列可以由 $f(x - 1)$ 的所有序列最前面加1得到，不以1开头的我们把每一个序列的第一个元素数值减一，发现得到的就是所有的 $f(x - 1)$ 中的序列，所以 $f(x) = 2f(x - 1)$ 可以发现虽然 $x$ 可能很大，但数列个数是指数增长的，超过的部分就不用统计了

由等比数列求和可以得到总和小于等于 $x$ 的数组数量是 $2^x - 1$ 。 $g(x)$ 中以1开头的序列个数是 $g(x - 1) + 1 = 2^{x - 1}$ 这个递推和之前是同一个思想，所以 $k \leq 2^{x - 1}$ 时就可以确定这一位就是1了，接着找序列的剩余部分元素之和不超过 $x − 1$ ，字典序排名为 $k − 1$ 的序列。如果大于1就把所有的序列最高位都减一，这样相对大小是不变的，接着找序列剩余部分元素之和不超过 $x − 1$ ，字典序排名为 $k − 2^{x - 1}$ 的序列。这和原问题是类似的，一次递推即可，复杂度 $O(x)$

1
void solve(){
2
    int x, k, n = 1;
3
    cin >> x >> k;
4
    vector<int> ans(x + 5);
5
    auto dfs = [&](auto&& dfs, int x, int k) -> void {
6
        // cerr << x << ' ' << k << endl;
7
        ans[n]++;
8
        if(k == 1) {
9
            n++; return;
10
        }
11
        if(x > 60 || k <= p[x - 1]) {
12
            n++;
13
            dfs(dfs, x - 1, k - 1);
14
        }else {
15
            dfs(dfs, x - 1, k - p[x - 1]);
16
        }
17
    };
18
    dfs(dfs, x, k);
19
    fore(i, 1, n) cout << ans[i] << " \n"[i == n - 1];
20
}

如果这篇文章对你有帮助，欢迎分享给更多人！

部分信息可能已经过时

2026“钉耙编程”中国大学生算法设计春季联赛（4）

CubeCat's Blog

1001-湖上午后 #

1002-庭扫落樱 #

1003-竹林清韵 #

1004-三途川畔 #

1007-云端航迹 #

1009-微缩庭园 #

1010-静海拾光 #

目录

CubeCat's Blog

1001-湖上午后#

1002-庭扫落樱#

1003-竹林清韵#

1004-三途川畔#

1007-云端航迹#

1009-微缩庭园#

1010-静海拾光#

目录

1001-湖上午后 #

1002-庭扫落樱 #

1003-竹林清韵 #

1004-三途川畔 #

1007-云端航迹 #

1009-微缩庭园 #

1010-静海拾光 #