XJOI200812 题解

模拟赛

丧心病狂，打了两场提（n）高（o）组（i）模拟赛。。。一天就这么没了【哭】

赛1 赛2

1A

不用 Boruvka，直接 Kruskal，从大到小枚举边权然后能连则连。

1B

神仙题！（也可能只是我不会线性代数¯\_(ツ)_/¯）原题是 CF388D

考虑异或 一般来说 就是 Trie 和线性基

诶？线性基好像可以！本题相当于给一组线性基就能产生一堆异或值，线性基和异或值共同组成集合

一组线性基对应一个集合，但一个集合可以有多组线性基，如果能让集合和线性基一一对应，集合的计数就转化成了线性基的计数

根据“特征点”的思想，我们对每组线性基高斯消元。可以证明高消后，不同的线性基生成的集合一定不同。

接下来对线性基做 dp 就好了。注意，高消后线性基能异或出来的最大值就是所有元素的异或值

dp 的状态设计：dp[i, j, k] 表示从最高位到第 i 位选了 j 个基，异或得到的最大值是否顶到上界（是则 k = 1，否则 k = 0）有点类似于数位 dp

细节

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int mod = 1e9 + 7;
typedef long long ll;
ll n, dp[32][32][2], ans;

void add(ll &x, ll y) { x = (x + y) % mod; }

int main() {
    cin >> n;
    dp[30][0][1] = 1;
    for (int i = 30; i >= 1; i--) {
        rep(j, 0, 30 - i + 1) {
            // k = 0
            add(dp[i - 1][j][0], dp[i][j][0] * (1 << j) % mod);
            add(dp[i - 1][j + 1][0], dp[i][j][0]);
            // k = 1
            ll x = (j == 0 ? 1 : (1 << (j - 1))), y = (j == 0 ? 0 : (1 << (j - 1)));
            if ((n >> (i - 1)) & 1) {
                add(dp[i - 1][j][0], x * dp[i][j][1] % mod);
                add(dp[i - 1][j][1], y * dp[i][j][1] % mod);
                add(dp[i - 1][j + 1][1], dp[i][j][1]);
            } else {
                add(dp[i - 1][j][1], x * dp[i][j][1] % mod);
            }
        }
    }
    rep(i, 0, 30) add(ans, (dp[0][i][0] + dp[0][i][1]) % mod);
    printf("%lld\n", ans);
    return 0;
}

1C

先决题目是 [ZJOI2016]-旅行者，这里写一下题解

网格图可以分治！找到矩形的长边，用一条中轴线切成两半，当前分治的区间是 (lx, ly) (rx, ry)，处理的询问是 (ql, qr)（类似于整体二分）。对于每个询问：

  • 起始点在中轴线两侧，对于中轴线上每个点跑最短路更新答案
  • 起始点在一侧，可能最短路也经过中轴线，也更新一波，再递归分治

卡了小常，加了玄学头文件
复杂度是 O(S logS sqrt(S))
如果没看懂这里还有一个（还是不懂。。

—-分割线—-

本题的区别就是有修改啦。我们可以知道每个格子变为不能走的时间（这个整体二分做），定义一条路径的值为这条路径上格子不能走时间的最小值，那我们就需要找一条值最大的路径看这个值是否大于询问的时间。离线，用旅行者的 分治 + dp 做。然而不会写代码，我只会咕咕

2A

只会 16 分 O(nT)，告辞（咕咕

正解是斯特林数相关？？？我谔谔

最后就是个卷积形式了。

2B

莫反就有 60 分，可惜 T 了一个点

正解 要用 ODT 维护？？？我谔谔

2C

神仙计算几何题，咕咕