2023 年 6 月做题记录

题解/做题记录
34k 词

前言

会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是 Ad-hoc 或构造或结论题，标 + 的是比较有意思的思维题。根据牛牛程度会增减数量。

CF1037G A Game on Strings [!!!]

观察发现，如果某次我选择了字符 cc，则剩下的子串要么左边是 cc，要么右边是 cc。
也就是说，对于每个字符 cc，设其出现的位置为 posc,1,posc,2,…,posc,kpos _ {c, 1}, pos _ {c, 2}, \ldots, pos _ {c, k}，那么有用的串就是所有 sposc,i,posc,i+1s _ {pos _ {c, i}, pos _ {c, i + 1}} 及其所有前缀和后缀。这样的串的个数为 O(n∣Σ∣)O(n \left|\Sigma\right|)。

我们考虑预处理出所有有用的串的 SG 函数。
考虑将所有串按长度排序，对于每个串暴力转移。
很可惜，这样复杂度是不对的。我们需要寻找更优秀的方法。
我们发现，当我们第一次操作时，若选择字符 cc，则切开来的串除了前后两个都满足其左边和右边都是 cc。
于是我们考虑只对所有的 sposc,i,posc,i+1s _ {pos _ {c, i}, pos _ {c, i + 1}} 求 SG 函数，然后暴力递归求解左右两边的串。
然而这样复杂度依然是错的，但是我们发现左右两边的串为我们之前抛弃掉的前缀和后缀。于是我们再记忆化一下前缀和后缀的答案，复杂度就正确了。

对于询问，我们把询问拆成若干个连续的整串和一个前缀和一个后缀，我们预处理整串的 SG 函数的前缀和，就可以实现 O(1)O(1) 查询连续的整串。

总时间复杂度为 O(∣Σ∣2∣s∣+∣Σ∣m)O(\left|\Sigma\right| ^ 2 \left|s\right| + \left|\Sigma\right| m)。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
string s;
int cnt[26], pos[26][100005], id[100005];
int le[26][100005], ri[26][100005];
int sg[26][100005], pre[26][100005], suf[26][100005];
vector<pair<int, int>> v;

int query1(int l, int r) {
    int res = 0;
    for (int i = 0; i < 26; i++) {
        int ll = ri[i][l], rr = le[i][r];
        if (ll > rr) continue;
        int now = 0;
        for (int j = id[ll] + 1; j <= id[rr]; j++) now ^= sg[i][j];
        if (l < ll) {
            if (suf[i][l] == -1) suf[i][l] = query1(l, ll - 1);
            now ^= suf[i][l];
        }
        if (rr < r) {
            if (pre[i][r] == -1) pre[i][r] = query1(rr + 1, r);
            now ^= pre[i][r];
        }
        if (now < 26) res |= 1 << now;
    }
    for (int i = 0; i < 26; i++)
        if ((res >> i & 1) == 0) return i;
    return 26;
}
int query2(int l, int r) {
    int res = 0;
    for (int i = 0; i < 26; i++) {
        int ll = ri[i][l], rr = le[i][r];
        if (ll > rr) continue;
        int now = sg[i][id[rr]] ^ sg[i][id[ll]];
        if (l < ll) {
            if (suf[i][l] == -1) suf[i][l] = query2(l, ll - 1);
            now ^= suf[i][l];
        }
        if (rr < r) {
            if (pre[i][r] == -1) pre[i][r] = query2(rr + 1, r);
            now ^= pre[i][r];
        }
        if (now < 26) res |= 1 << now;
    }
    for (int i = 0; i < 26; i++)
        if ((res >> i & 1) == 0) return i;
    return 26;
}

int main() {
    cin >> s;
    n = s.length();
    s = " " + s;
    for (int i = 1; i <= n; i++) pos[s[i] - 'a'][id[i] = ++cnt[s[i] - 'a']] = i;
    for (int i = 0; i < 26; i++) {
        le[i][0] = 0;
        for (int j = 1; j <= n; j++)
            le[i][j] = s[j] - 'a' == i ? j : le[i][j - 1];
    }
    for (int i = 0; i < 26; i++) {
        ri[i][n + 1] = n + 1;
        for (int j = n; j >= 1; j--)
            ri[i][j] = s[j] - 'a' == i ? j : ri[i][j + 1];
    }
    for (int i = 0; i < 26; i++)
        for (int j = 2; j <= cnt[i]; j++)
            if (pos[i][j - 1] + 1 != pos[i][j]) v.emplace_back(pos[i][j - 1], pos[i][j]);
    sort(v.begin(), v.end(), [](const pair<int, int> &x, const pair<int, int> &y) {
        return x.second - x.first < y.second - y.first;
    });
    memset(pre, -1, sizeof(pre));
    memset(suf, -1, sizeof(suf));
    for (auto now : v)
        sg[s[now.second] - 'a'][id[now.second]] = query1(now.first + 1, now.second - 1);
    for (int i = 0; i < 26; i++)
        for (int j = 1; j <= cnt[i]; j++)
            sg[i][j] ^= sg[i][j - 1];
    scanf("%d", &m);
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        puts(query2(l, r) ? "Alice" : "Bob");
    }
    return 0;
}

CF23C Oranges and Apples [**]

奇妙构造。

考虑按烂苹果的数量从大到小排序，然后取所有奇数项的箱子，显然这样做烂苹果数量满足要求，但橘子数量不一定满足。

若上面这种构造不满足要求，则考虑取所有偶数项的箱子，这样橘子一定满足要求，但烂苹果不一定满足。
但是这样我们只取了 n−1n - 1 个箱子，考虑再取一个使烂苹果满足要求。显然应该取第 11 个。
这样取显然能使烂苹果满足要求。

CF346D Robot Control

先不考虑不能重复经过一个点的限制，我们设 fuf_u 表示从点 uu 走到 tt 所需的最少的命令。显然有：

fu=min⁡{min⁡(u,v)∈Efv+1,max⁡(u,v)∈Efv}f_u = \min\left\{\min\limits _ {(u, v) \in E} f _ v + 1, \max\limits _ {(u, v) \in E} f _ v\right\}

然后观察发现，最优情况下一定不会重复经过一个点，所以直接来就好了。

ABC127E Cell Distance

显然 x\text{x} 轴和 y\text{y} 轴贡献可以分开来考虑。故这里只讨论在 x\text{x} 轴上的贡献。

不妨枚举两点间的距离为 dd，设这两个点为 (x1,y1),(x2,y2)(x _ 1, y _ 1), (x _ 2, y _ 2)，则有 x2−x1=dx _ 2 - x _ 1 = d。则所有点对的方案数为 (n−d)⋅m2(n - d) \cdot m ^ 2，贡献则为方案数再乘上 dd。
确定这两个点之后剩下的点的坐标无关紧要，故方案数为 (nm−2k−2)\binom{nm - 2}{k - 2}。

故答案为：

(∑d=1n−1d⋅(n−d)⋅m2+∑d=1m−1d⋅(n−d)⋅n2)\left(\sum\limits _ {d = 1} ^ {n - 1} d \cdot (n - d) \cdot m ^ 2 + \sum\limits _ {d = 1} ^ {m - 1} d \cdot (n - d) \cdot n ^ 2\right)

CEOI2021 Diversity [!!!]

不妨转化一下贡献的式子。

设当前数为 aia _ i，上一次出现这个数的位置为 preipre _ i，则贡献为：

∑i=1n(i−prei)(n−i+1)=∑i=1n(ni−i2+i−(n−i+1)⋅prei)=n∑i=1ni−∑i=1ni2+∑i=1ni−∑i=1n(n−i+1)⋅prei\begin{array}{ll} & \sum\limits _ {i = 1} ^ n \left(i - pre _ i\right)\left(n - i + 1\right) \\ = & \sum\limits _ {i = 1} ^ n \left(ni - i ^ 2 + i - \left(n - i + 1\right) \cdot pre _ i\right) \\ = & n \sum\limits _ {i = 1} ^ n i - \sum\limits _ {i = 1} ^ n i ^ 2 + \sum\limits _ {i = 1} ^ n i - \sum\limits _ {i = 1} ^ n (n - i + 1) \cdot pre _ i \end{array}

前三个式子可以直接求出来。最后一个式子的意义即为：对于每个数，其相邻两次出现时，前一个位置从前往后数的位置和后一个位置从后往前数的位置的乘积之和。现在要使这个东西最大。

结论 1：相同的数一定放在一起。

设某个数最后两次出现位置为 a,ba, b，另一个数最开始两次出现位置为 c,dc, d，且有：

a<c<b<da < c < b < d

则此时 bb 产生的贡献为：

a⋅(n−b+1)=an−ab+aa \cdot (n - b + 1) = an - ab + a

同理 cc 产生的贡献为：

c⋅(n−d+1)=cn−cd+cc \cdot (n - d + 1) = cn - cd + c

若交换 bb 和 cc 上的数，则分别产生的贡献为：

an−ac+abn−bd+ban - ac + a \\ bn - bd + b

交换前后贡献之差为：

−ab+ac−cd+bd=a(c−b)+d(b−c)=(b−c)(d−a)>0-ab + ac - cd + bd = a(c - b) + d(b - c) = (b - c)(d - a) > 0

故这种情况下交换后更优。

同理可以求出 a<c<d<ba < c < d < b 时的贡献。结论相同。

结论 2：将所有数按出现次数排序后，一定是按顺序左右轮流放。

证明待补完。

然后发现这个东西不好直接维护，于是考虑莫队。

一个经典结论：若一个序列 a1,a2,…ana _ 1, a _ 2, \ldots a _ n 满足 ∑ai=M\sum a _ i = M，则 aa 中不同的数的种类只有 O(M)O(\sqrt{M}) 种。

于是我们可以在移动指针时只记录每个数的出现次数和数的种类数，然后每次查询按出现次数排序后合并所有出现次数相同的数并计算贡献即可。

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
62
63
64
65
66
67
68
69
70
71
72
73
// Think twice, code once.
#include <vector>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, k, sq, a[300005], p[300005];
long long ans;
struct query {int id, l, r; long long ans;} q[300005];
int b[300005], num[300005], vis[300005], idx, c[300005];

long long calc(long long a, long long b, long long k) {
    return k * a * a + a * b * k * k - a * b * k + b * b * (k * (k - 1) * (2 * k - 1)/6);
}
void update(int x) {if (!vis[x]) vis[x] = 1, c[++idx] = x;}
void add(int x) {num[b[x]]--; b[x]++; num[b[x]]++; update(b[x]); return ;}
void del(int x) {num[b[x]]--; b[x]--; if (b[x]) num[b[x]]++, update(b[x]); return ;}

long long calc(long long tot, long long l, long long x, long long c) {
    return c * (c + 1) * (c * 2 + 1) / 6 * x * x +
        l * c * (c + 1) * x +
        l * l * c +
        c * (c + 1) * (c * 2 + 1) / 6 * x * x +
        (tot - l - x * c) * c * (c + 1) * x +
        (tot - l - x * c) * (tot - l - x * c) * c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sq = sqrt(n);
    for (int i = 1; i <= n; i++) p[i] = (i - 1) / sq + 1;
    for (int i = 1; i <= k; i++) cin >> q[i].l >> q[i].r, q[i].id = i;
    sort(q + 1, q + k + 1, [](const query &x, const query &y) {
        return p[x.l] != p[y.l] ? p[x.l] < p[y.l] : (p[x.l] % 2 ? x.r < y.r : x.r > y.r);
    });
    for (int i = 1, l = 1, r = 0; i <= k; i++) {
        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
        int _idx = 0;
        for (int j = 1; j <= idx; j++) {
            vis[c[j]] = 0;
            if (num[c[j]]) c[++_idx] = c[j];
        }
        idx = _idx;
        sort(c + 1, c + idx + 1);
        for (int j = 1; j <= idx; j++) vis[c[j]] = 1;
        int len = r - l + 1, cnt = 0, _num[] = {0, 0}, lr = 0;
        long long res = 0;
        for (int j = 1; j <= idx; j++) {
            int tmp = c[j];
            cnt += num[tmp];
            res += calc(len, _num[lr], tmp, num[tmp] / 2) + calc(len, _num[lr ^ 1], tmp, (num[tmp] + 1) / 2);
            _num[lr] += tmp * (num[tmp] / 2);
            _num[lr ^ 1] += tmp * ((num[tmp] + 1) / 2);
            if (num[tmp] % 2 == 1) lr ^= 1;
        }
        q[i].ans = ((long long)cnt * len * (len + 1) - (long long)len * (cnt - 1) - res + (2ll * len * len)) / 2;
    }
    sort(q + 1, q + k + 1, [](const query &x, const query &y) {
        return x.id < y.id;
    });
    for (int i = 1; i <= k; i++) cout << q[i].ans << '\n';
    return 0;
}

CF1839E Decreasing Game [*]

牛牛构造。

结论：若可以选出某些数使得这些数的和是总和的一半，则后手必胜，否则先手必胜。

考虑构造证明。

若可以选出某些数使得这些数的和是总和的一半，则根据这一点把数分成两部分，每次选择和先手不在同一部分的数，这样每次操作会使两部分减少一个相同的数，故最后一定会使两部分都变成 00 且此时先手决策。

否则，我们发现每次操作后依然不满足可以选出某些数使得这些数的和是总和的一半。
因为假设选了 a,ba, b，则操作后变成一个数 ∣a−b∣\left|a - b\right|，若操作后可以划分，则操作前只要将 min⁡{a,b}\min\left\{a, b\right\} 划分到另一组即为一组合法的划分。
故无论怎么选最后一定会剩下一个数，然后直接取走就胜利了。

CF618F Double Knapsack [**]

北京高考数学卷压轴题打卡（

依然是牛牛构造。

结论：一定有一种方案，使得选出来的数是两段区间。

设 sai=∑j=1iaj,sbi=∑j=1ibjsa _ i = \sum\limits _ {j = 1} ^ i a _ j, sb _ i = \sum\limits _ {j = 1} ^ i b _ j。

相当于要找到 la,ra,lb,rbla, ra, lb, rb， 满足 sara−sala−1=sbrb−sblb−1sa _ {ra} - sa _ {la - 1} = sb _ {rb} - sb _ {lb - 1}。
转化后得到：sara−sbrb=sala−1=sblb−1sa _ {ra} - sb _ {rb} = sa _ {la - 1} = sb _ {lb - 1}。

不妨钦定 san<sbnsa _ n < sb _ n。
对于每个 ii，我们求出最小的 jj 使得 sai≤sbjsa _ i \le sb _ j，因为 ai,bi∈[1,n]a _ i, b _ i \in [1, n]，故 sbj−sai∈[0,n)sb _ j - sa _ i \in [0, n)。

加上 sb0−sa0=0sb _ 0 - sa _ 0 = 0，一共有 n+1n + 1 对，根据鸽巢原理，一定会有两对的差相同，这样就找到了一组合法解。

THUPC2022 初赛 造计算机 [*]

还是牛牛构造。

首先排除掉一开始就排序好的情况。

发现至少需要 22 个寄存器。

思考复原一个形如 2,3,…,n−1,n,12, 3, \ldots, n - 1, n, 1 的序列。

假设两个寄存器的编号分别为 x,yx, y，则一种合法构造为：

swap 1 xswap 2 xswap 3 x⋮swap n−1 xswap n yswap n xswap 1 y\verb|swap|\ 1\ x \\ \verb|swap|\ 2\ x \\ \verb|swap|\ 3\ x \\ \vdots \\ \verb|swap|\ n - 1\ x \\ \verb|swap|\ n\ y \\ \verb|swap|\ n\ x \\ \verb|swap|\ 1\ y \\

此时内存单元已经复位，两个寄存器编号互换，需要再 swap\verb|swap| 一次。

但是先别急，我们发现还可以继续利用两个寄存器，去复原其他的置换环。

于是我们可以得到做法：找出所有置换环，然后按照上述方法复原。若最后两个寄存器没有复原则再进行一次 swap\verb|swap|。

APIO2022 T3 排列 [*]

全是牛牛构造。

假设当前序列的上升子序列个数为 xx。

若在开头添加一个最小的数，则 x←2xx \gets 2x。
若在开头添加一个最大的数，则 x←x+1x \gets x + 1。

于是我们可以将 kk 转成二进制然后构造。

但是这样次数是 2log⁡2k2 \log _ 2 k 的，无法通过此题，于是考虑进行一些人类智慧的小小优化。

对于连续的两个 11，考虑使用更优秀的构造方法。考虑能否添加一个数使 x←x+3x \gets x + 3。

如果原序列中最大值在次大值前面，则可以在开头添加一个介于次大值和第三大值的数。

观察发现，原序列中最大值在次大值后面的情况只可能出现一次，所以这样构造是对的。

CF1764F Doremy’s Experimental Tree [*]

我们发现，如果路径 (a,b)(a, b) 在路径 (u,v)(u, v) 中，则 fu,v<fa,bf _ {u, v} < f _ {a, b}。

不妨钦定 11 为根，然后按 f1,if _ {1, i} 降序排序，依次确定每个点的父亲。

不难发现点 ii 的父亲一定满足 f1,fai>f1,if _ {1, fa _ i} > f _ {1, i}。另外，在所有满足上述要求的点中，最大的 fi,jf _ {i, j} 对应的 jj 一定与 ii 有边，故这个点就是 faifa _ i。

然后用类似于换根 DP 的方法求出边权即可。

CF1685C Bring Balance [*]

经典结论：将 (\verb|(| 视作 +1+1，)\verb|)| 视作 −1-1，括号序列合法当且仅当任意前缀和 ≥0\ge 0。

我们把前缀和画成平面上的直线，则翻转操作相当于旋转一段折线并连接两段。
容易发现翻转后最低点变最高点，最高点变最低点。

结论：答案不超过 22。

找到折线最高点，翻转左右两边。以左半部分为例，原最高点不高于右端点，故翻转后最低点不低于左端点，即 00。右半部分同理。

考虑什么时候答案是 11。

发现当且仅当能找到一个区间，满足包含所有低于 00 的点，且最高点与右端点的差小于左端点的高度，也就是左右端点高度之和大于最高点，贪心地选两个最大值即可。

CF848B Rooter’s Song

典。

首先令每个点退后 tit _ i 步，使得每个点同时出发。

将碰撞视为穿过并交换编号，容易发现若不考虑编号则最终所有球的位置确定。

考虑求出每个编号对应的最终位置，容易发现两个点若会碰撞当且仅当他们在同一条斜率为 −1-1 的直线上。
于是我们考虑依此将所有球划分到若干个集合里，集合之间显然互不影响。
同一个集合内，向上运动的球会依次碰撞第一个向右运动的球、其右侧第一个向上运动的球、第二个向右运动的球……于是可以 O(1)O(1) 算出每个球对应的最终位置，向右运动的球同理。

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
62
63
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, w, h;
struct ball { int x, y, tx, ty, ax, ay; } a[100005];
vector<int> b, vec[100005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> w >> h;
    for (int i = 1; i <= n; i++) {
        int g, p, t;
        cin >> g >> p >> t;
        if (g == 1) a[i] = { p, -t - 1, p, h, 0, 0 };
        else a[i] = { -t - 1, p, w, p, 0, 0 };
        b.push_back(a[i].x + a[i].y);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (int i = 1; i <= n; i++)
        vec[lower_bound(b.begin(), b.end(), a[i].x + a[i].y) - b.begin()].push_back(i);
    for (int cs = 0; cs < (int)b.size(); cs++) {
        sort(vec[cs].begin(), vec[cs].end(), [](int x, int y) { return a[x].x < a[y].x; });
        int p = -1;
        for (int i = 0; i < (int)vec[cs].size(); i++)
            if (a[vec[cs][i]].x < 0) p = i;
        if (p == -1 || p == (int)vec[cs].size() - 1) {
            for (int i : vec[cs]) a[i].ax = a[i].tx, a[i].ay = a[i].ty;
            continue;
        }
        for (int i = 0; i <= p; i++) {
            int id = vec[cs][i];
            int tmpa = i, tmpb = vec[cs].size() - p - 1;
            if (tmpb > tmpa) {
                a[id].ax = a[vec[cs][p + tmpa + 1]].tx;
                a[id].ay = a[vec[cs][p + tmpa + 1]].ty;
            } else {
                a[id].ax = a[vec[cs][i - tmpb]].tx;
                a[id].ay = a[vec[cs][i - tmpb]].ty;
            }
        }
        for (int i = p + 1; i < (int)vec[cs].size(); i++) {
            int id = vec[cs][i];
            int tmpa = vec[cs].size() - i - 1, tmpb = p + 1;
            if (tmpb > tmpa) {
                a[id].ax = a[vec[cs][p - tmpa]].tx;
                a[id].ay = a[vec[cs][p - tmpa]].ty;
            } else {
                a[id].ax = a[vec[cs][i + tmpb]].tx;
                a[id].ay = a[vec[cs][i + tmpb]].ty;
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << a[i].ax << ' ' << a[i].ay << '\n';
    return 0;
}

CF1553H XOR and Distance [!]

先把所有数放在一个桶里。

考虑对于任意确定的 xx 如何求出答案。
我们按照 1,2,4,8,…1, 2, 4, 8, \ldots 的长度，用类似于线段树的方法合并相邻两个区间的信息。若 xx 当前位为 11，则要交换相邻两个区间。具体地，设合并前区间长度为 2h2 ^ h，右边的区间中每个数要 −2h- 2 ^ h，左边区间每个数要 +2h+ 2 ^ h。然后计算合并后的贡献，即左区间最大值和右区间最小值的差。
于是只要维护每个区间的最大最小值即可在 O(2k)O(2 ^ k) 时间内求出任意指定 xx 的答案。

考虑在求答案过程中枚举 xx，具体地，每次枚举当前位 xx 填 11 还是 00，然后分别求解。发现在第 hh 层，有 2k−h2 ^ {k - h} 个区间，2h2 ^ h 种 xx 的取值，故每层大小均为 2k2 ^ k，故总时间复杂度为 O(2kk)O(2 ^ k k)。

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
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, k, a[1 << 19], ans[1 << 19];
struct node {
    int l, r, mn, mx;

    node() = default;
    node(int _l, int _r, int _mn, int _mx): l(_l), r(_r), mn(_mn), mx(_mx) {}
};
vector<node> v;

void solve(int h, int x, vector<node> v, int res) {
    if (h == k) { ans[x] = res; return ; }
    vector<node> tmp;
    int newres = res;
    for (int i = 0; i < (int)v.size(); i += 2) {
        newres = min(newres, v[i + 1].mn - v[i].mx);
        tmp.emplace_back(v[i].l, v[i + 1].r, min(v[i].mn, v[i + 1].mn), max(v[i].mx, v[i + 1].mx));
    }
    solve(h + 1, x, tmp, newres);
    vector<node>().swap(tmp);
    newres = res;
    for (int i = 0; i < (int)v.size(); i += 2) {
        v[i + 1].l -= 1 << h, v[i + 1].r -= 1 << h, v[i + 1].mn -= 1 << h, v[i + 1].mx -= 1 << h;
        v[i].l += 1 << h, v[i].r += 1 << h, v[i].mn += 1 << h, v[i].mx += 1 << h;
        swap(v[i], v[i + 1]);
        newres = min(newres, v[i + 1].mn - v[i].mx);
        tmp.emplace_back(v[i].l, v[i + 1].r, min(v[i].mn, v[i + 1].mn), max(v[i].mx, v[i + 1].mx));
    }
    solve(h + 1, x | 1 << h, tmp, newres);
    return ;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        a[x]++;
    }
    for (int i = 0; i < (1 << k); i++)
        if (!a[i]) v.emplace_back(i, i, 1e9, -1e9);
        else v.emplace_back(i, i, i, i);
    solve(0, 0, v, 1e9);
    for (int i = 0; i < (1 << k); i++) printf("%d ", ans[i]);
    puts("");
    return 0;
}

CF1761E Make It Connected

恶心分讨。

如果有一个独立的点，可以 11 次解决。

否则，如果有一张图不是完全图，则选择其中一个没连满的点操作，所有本来与之不相连的连通块与之相连，其本来所在的连通块也不会断开，也可以 11 次解决。

否则，若有多于 22 个连通块，只要任意操作一个点，使得仅本来与之相连的连通块裂开，其他全都连上。然后再操作原本与之不在同一连通块的任意一个点，即可使全图相连，22 次解决。

否则，只能一直操作较小的那个连通块上的点，这样每次操作都只会使操作的点与原连通块断开并进入另一个连通块。

POI2011 PRZ-Shift [*!]

两个操作结合相当于使任意相邻的三个元素置换。且一次置换相当于让第三个数往前跳 22 格，两次置换相当于让第二个数带着第三个数往前跳 11 格。

考虑插入排序，每次能跳两格就跳两格，否则跳一格。

这样最后会剩下两个元素，如果没有复位，则令其中一个一直两格两格跳使其复位。

但是如果 nn 是奇数，一直往前跳是不会复位的。大胆猜想这种情况下无解。

发现两种操作都不会改变逆序对的奇偶性，而当 nn 是奇数且最后两个没有复位时逆序对为奇数，无解。

分析一下次数，每次往前跳 22 格需要 33 次操作，跳 11 格也需要 33 次操作，使最后两个数复位需要 n+1n + 1 次操作，令 11 在序列开头需要 11 次操作。

总次数为 3n(n−1)2+n+2\dfrac{3n(n - 1)}{2} + n + 2。看起来过不去，但实际上可以通过合并相邻两次位移做到 n(n+1)2+2n+2\dfrac{n(n + 1)}{2} + 2n + 2。

代码是模拟赛时写的，只合并了跳 22 格的位移操作，但是足够了。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, a[2005];
vector<pair<int, int>> ans;

void shift() {
    for (int i = n - 1; i >= 1; i--) swap(a[i], a[i + 1]);
    return ;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    if (n == 1) { puts("0\n"); return 0; }
    if (n == 2) {
        if (a[1] == 1) { puts("0\n"); return 0; }
        else { puts("1\n1a"); return 0; }
    }
    { // 使 1 在第一个位置。
        int pos = 1;
        for (int i = 1; i <= n; i++)
            if (a[i] == 1) pos = i;
        if (pos != 1) {
            ans.emplace_back(n - pos + 1, 0);
            for (int i = 1; i <= n - pos + 1; i++) shift();
        }
    }
    for (int i = 2; i < n - 1; i++) { // 插入排序
        int pos = i;
        for (int j = i; j <= n; j++)
            if (a[j] == i) pos = j;
        if (pos == i) continue;
        if (pos == i + 1) { // 单独跳 1 格。
            ans.emplace_back(n - i + 1, 0);
            ans.emplace_back(2, 1);
            ans.emplace_back(i - 1, 0);
            swap(a[i], a[i + 1]);
            swap(a[i + 1], a[i + 2]);
            continue;
        }
       // 跳 2 格。
        ans.emplace_back(n - pos + 3, 0);
        while (pos - 2 >= i) {
            ans.emplace_back(1, 1);
            swap(a[pos], a[pos - 1]);
            swap(a[pos - 1], a[pos - 2]);
            pos -= 2;
            ans.emplace_back(2, 0);
        }
        if (pos == i + 1) { // 单独跳 1 格。
            ans.pop_back();
            ans.emplace_back(1, 0);
            ans.emplace_back(2, 1);
            ans.emplace_back(i - 1, 0);
            swap(a[i], a[i + 1]);
            swap(a[i + 1], a[i + 2]);
        } else {
            ans.pop_back();
            ans.emplace_back(i - 1, 0);
        }
    }
    if (a[n] != n) { // 复位最后两个元素。
        if (n % 2 == 1) { puts("NIE DA SIE"); return 0; }
        ans.emplace_back(3, 0);
        for (int i = 1; i <= (n - 2) / 2; i++)
            ans.emplace_back(1, 1), ans.emplace_back(2, 0);
        ans.emplace_back(1, 1);
        ans.emplace_back(n - 2, 0);
    }
    printf("%d\n", (int)ans.size());
    for (pair<int, int> i : ans)
        printf("%d%c ", i.first, i.second + 'a');
    puts("");
    return 0;
}

LibreOJ β Round #3 绯色 IOI（抵达） [*!]

以下用 f(u)f(u) 表示城市 uu 的庇护所。

不妨先考虑构造任意一组合法解。考虑随便钦定一个非叶子节点点为根。

我们从叶子开始考虑，发现对于一个叶子 uu，必然有 f(u)=fau,f(fau)=uf(u) = fa _ u, f(fa _ u) = u。然后这两个点就不能再使用了，于是可以直接把他们从树上摘掉，不影响对 ff 的构造。
故直接这样往上构造即可得到所有点的 ff，若构造过程中出现冲突则无解。

然后考虑给每个点定危险度，我们不妨钦定每一对点中，uu 的危险度比 faufa _ u 的危险度小。那么，在构造过程中，从 11 开始给每个 uu 赋危险度，从 nn 开始给每个 faufa _ u 赋危险度，这样就能构造一组合法解。

于是我们证明了只要能确定 ff，就一定合法。

然后考虑求字典序最小的解。我们发现对于一对点 (u,fau)(u, fa _ u)，uu 的危险度比所有与 faufa _ u 相连的点的危险度小，faufa _ u 的危险度比所有与 uu 相连的点的危险度小。我们根据这一点建图，然后求最小的拓扑序即可。因为每个点只会提供其度数条边，所以边数为 O(n)O(n) 级别。

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
62
63
64
65
66
67
68
69
70
71
// Think twice, code once.
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

int n, d[500005], f[500005], in[500005];
struct graph {
    int tot, hd[500005];
    int nxt[1000005], to[1000005];

    void add(int u, int v) {
        nxt[++tot] = hd[u];
        hd[u] = tot;
        to[tot] = v;
        return ;
    }
} tr, g;
priority_queue<int, vector<int>, greater<int>> q;
int idx, ans[500005];

void dfs(int now, int fa) {
    for (int i = tr.hd[now]; i; i = tr.nxt[i])
        if (tr.to[i] != fa) dfs(tr.to[i], now);
    if (!f[now]) {
        if (f[fa]) { cout << "-1\n"; exit(0); }
        for (int i = tr.hd[now]; i; i = tr.nxt[i])
            if (tr.to[i] != fa) g.add(fa, tr.to[i]), in[tr.to[i]]++;
        for (int i = tr.hd[fa]; i; i = tr.nxt[i])
            if (tr.to[i] != now) g.add(now, tr.to[i]), in[tr.to[i]]++;
        f[now] = f[fa] = 1;
    }
    return ;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tr.add(u, v);
        tr.add(v, u);
        d[u]++, d[v]++;
    }
    if (n == 1) { cout << "-1\n"; return 0; }
    if (n == 2) { cout << "1 2\n"; return 0; }
    if (n % 2 == 1) { cout << "-1\n"; return 0; }
    int rt = 1;
    for (int i = 1; i <= n; i++)
        if (d[i] >= 2) rt = i;
    f[0] = 1;
    dfs(rt, 0);
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.push(i);
    while (!q.empty()) {
        int now = q.top();
        q.pop();
        ans[++idx] = now;
        for (int i = g.hd[now]; i; i = g.nxt[i])
            if (!--in[g.to[i]]) q.push(g.to[i]);
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

CF1348F Phoenix and Memory [**]

考虑把限制视为区间，相当于要求每个区间对应一个其内部的点。

按左端点排序，每次将当前点给一个右端点最小的点，即可求出一组合法解。

考虑能否求出第二组解。

结论：如果有合法解，一定有一组可以通过交换当前解的某两个数得到。

考虑反证。假设必须要进行一个大于 22 的置换得到一个合法的排列，假设其最靠左的点为 xx，将 xx 置换到 yy，将 zz 置换到 xx。

则 yy 对应的区间包含 xx，xx 对应的区间的右端点比 yy 小，zz 在 xx 和 xx 的右端点之间。

此时可以直接移除 xx，变成一个更小的合法的置换。这样一直移除，最终一定会得到一个大小为 22 的置换。

对于每个区间，设其对应的数为 pip _ i，只要查询是否存在 i,ji, j 满足 lj≤pi<pj≤ril _ j \le p _ i < p _ j \le r _ i 即可。

我们按 pip _ i 从小到大枚举，每次添加 lj=pil _ j = p _ i 的区间 jj，然后查询已添加的区间是否有区间满足 pi<pj≤rip _ i < p _ j \le r _ i 即可。这个可以使用 set 维护。

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
// Think twice, code once.
#include <set>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, p[200005];
struct interval { int id, l, r, p; } a[200005];
vector<int> v[200005];
set<pair<int, int>> s;
int ans[2][200005];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r), p[i] = i, v[a[i].l].push_back(i);
    for (int i = 1; i <= n; i++) {
        for (int j : v[i]) s.emplace(a[j].r, j);
        a[s.begin()->second].p = i;
        s.erase(s.begin());
    }
    for (int i = 1; i <= n; i++) ans[0][i] = ans[1][i] = a[i].p;
    sort(p + 1, p + n + 1, [](const int &x, const int &y) {
        return a[x].p < a[y].p;
    });
    set<pair<int, int>>().swap(s);
    int flag = 0;
    for (int i = 1; i <= n; i++) {
        for (int j : v[a[p[i]].p]) s.emplace(a[j].p, j);
        if (s.upper_bound(make_pair(a[p[i]].p, 0)) != s.end()) {
            auto it = s.upper_bound(make_pair(a[p[i]].p, 0));
            if (it->second == p[i]) it = next(it);
            if (it == s.end()) continue;
            auto tmp = *it;
            if (tmp.first <= a[p[i]].r) {
                swap(ans[1][tmp.second], ans[1][p[i]]);
                flag = 1;
                break;
            }
        }
    }
    if (!flag) {
        puts("YES");
        for (int i = 1; i <= n; i++) printf("%d ", ans[0][i]);
        puts("");
    } else {
        puts("NO");
        for (int i = 1; i <= n; i++) printf("%d ", ans[0][i]);
        puts("");
        for (int i = 1; i <= n; i++) printf("%d ", ans[1][i]);
        puts("");
    }
    return 0;
}

CF605C Freelancer’s Dreams [!!]

将限制视为二维平面上的点 (p,q)(p, q)，工作视为向量，则题目转化为给每个向量确定一个非负系数，使得这些向量的带权和 (x,y)(x, y) 满足 x≥p,y≥qx \ge p, y \ge q，且系数之和最小。

结论：一定有一组合法解只使用了不超过 22 个向量，即剩下的向量的系数均为 00。

考虑当前如果已经确定两个向量 u⃗,v⃗\vec{u}, \vec{v}，如果再添加一个向量 w⃗\vec{w}，令 UU 为向量 u⃗\vec{u} 的终点，VV 为向量 v⃗\vec{v} 的终点，WW 为向量 w⃗\vec{w} 的终点，若 WW 在直线 UVUV 下方，则折线 UWVUWV 不优于直线 UVUV。若 WW 在直线 UVUV 上方，则折线 UWVUWV 不优于直线 UWUW 或 WVWV。

假设我们已经确定了选择的两个向量 u⃗,v⃗\vec{u}, \vec{v}，考虑如何求出答案。

相当于要求一组系数 a,ba, b，使得 au⃗+bv⃗a\vec{u} + b\vec{v} 与向量 (p,q)(p, q) 斜率相同。答案即为 p2+q2∣au⃗+bv⃗∣⋅(a+b)\dfrac{\sqrt{p ^ 2 + q ^ 2}}{\left|a\vec{u} + b\vec{v}\right| \cdot (a + b)}。

发现一个美妙的事实：我们在两个向量的顶点之间连一条线，然后画一条连接原点和 (p,q)(p, q) 的直线，令 au⃗+bv⃗a\vec{u} + b\vec{v} 的顶点为这两条线的交点，此时 a+b=1a + b = 1。

很好证，△ABC\triangle ABC 与 △EDC\triangle EDC 相似，所以 EDAB=ECAC\dfrac{ED}{AB} = \dfrac{EC}{AC}，所以 AE→+ED→=(1−ECAC)⋅AE→+EDAB⋅ED→\overrightarrow{AE} + \overrightarrow{ED} = \left(1 - \dfrac{EC}{AC}\right)\cdot\overrightarrow{AE} + \dfrac{ED}{AB}\cdot\overrightarrow{ED}，1−ECAC+EDAB=11 - \dfrac{EC}{AC} + \dfrac{ED}{AB} = 1。

于是我们只要求两条直线的交点即可。

然后考虑求最优的 u⃗,v⃗\vec{u}, \vec{v}。我们发现上面证明最优解只有两个向量的过程同时说明这两个向量一定在凸包上，所以求一下凸包就做完了。

CF1354G Find a Gift [**]

很妙的一道题。

考虑如果知道了一个石头，怎么求答案。

使用倍增结合二分的方法。

具体来说，我们不妨把确定的那个石头编号为 11，设当前确定区间 [1,l)[1, l) 内的盒子全是石头，且第一个盒子一定在 [l,r][l, r] 这个区间内。
若 2l−2≤r2l - 2 \le r，则比较 [1,l−1][1, l - 1] 和 [l,2l−2][l, 2l - 2]，然后根据结果修改 ll 和 rr。

否则，设 mid=(l+r)/2mid = (l + r) / 2，然后比较 [1,mid−l+1][1, mid - l + 1] 和 [l,mid][l, mid] 即可。

这样操作需要大约 log⁡2n\log _ 2 n 次。

问题是如何确定一个石头。

发现我们还有很多询问次数，所以不妨先钦定一个盒子，然后不断用钦定的盒子和其他盒子比较，每次选择重量较大的盒子。若询问次数为 kk，则正确概率为 1−12k1 - \dfrac{1}{2 ^ k}，取 k=30k = 30 即可。

AGC015D A or…or B Problem [++*]

结论：任何能被表示出来的数都能被至多两个数表示出来。

证明：

不妨设一个能表示出来的数 x=a1ora2ora3or…orakx = a _ 1 \mathbin{\mathrm{or}} a _ 2 \mathbin{\mathrm{or}} a _ 3 \mathbin{\mathrm{or}} \ldots \mathbin{\mathrm{or}} a _ k，其中 A≤a1<a2<a3<…<ak≤BA \le a _ 1 < a _ 2 < a _ 3 < \ldots < a _ k \le B。

对于 A≤x≤BA \le x \le B，显然可以用一个数表示出来。

对于 x>Bx > B，至少使用两个数。

设 yy 为二进制下最高的一位满足这一位在 a1…aka _ 1 \ldots a _ k 中不全为 11 且至少一个为 11。那么我们构造两个数，其中一个仅第 yy 位为 11，设为 uu，另一个为 xxorux \mathbin{\mathrm{xor}} u，设为 vv，显然 a1≤u≤ak,a1≤v≤aka _ 1 \le u \le a _ k, a _ 1 \le v \le a _ k。

得证。

然后考虑怎么求解。

考虑将 A,BA, B 二进制下最高位相同的那几位全部抹成 00 一定不影响答案。此时 A,BA, B 最高位一定不同。

不妨设 zz 为二进制下仅 BB 最高位为 11 的数，我们把区间拆成 [A,z)[A, z) 和 [z,B][z, B]。

第一个区间内部取两个数的方案为 [A,z)[A, z)。
令 ww 为仅 BB 的最高位及最高位后第一个 11 及其之后的为全为 11 的数，则第二个区间内部取两个数的方案为 [z,w][z, w]。
两个区间各取一个数的方案为 [Aorz,(z−1)orz][A \mathbin{\mathrm{or}} z, (z - 1) \mathbin{\mathrm{or}} z]。

三个区间取个并即可。

洛谷 P6217 简单数论题 [!!]

很不错的一道题。

首先将询问转化为：

∏i=lraixgcd⁡(ai,x)=xr−l+1⋅∏i=lrai(∏i=lrgcd⁡(ai,x))−1\begin{aligned} & \prod\limits _ {i = l} ^ r \dfrac{a _ i x}{\gcd(a _ i, x)} \\ = & x ^ {r - l + 1} \cdot \prod\limits _ {i = l} ^ r a _ i \left(\prod\limits _ {i = l} ^ r \gcd(a _ i, x)\right) ^ {-1} \end{aligned}

问题转化为求：

∏i=lrgcd⁡(ai,x)\prod\limits _ {i = l} ^ r \gcd(a _ i, x)

令 pip _ i 为第 ii 个质数，我们将 aia _ i 和 xx 分解质因数：

ai=∏pjeai,jx=∏pjex,ja _ i = \prod p _ j ^ {e _ {a _ i, j}} \\ x = \prod p _ j ^ {e _ {x, j}}

则：

∏i=lrgcd⁡(ai,x)=∏pi∑j=lrmin⁡{eaj,i,ex,i}\begin{aligned} & \prod\limits _ {i = l} ^ r \gcd(a _ i, x) \\ = & \prod p _ i ^ {\sum\limits _ {j = l} ^ r \min\{e _ {a _ j, i}, e _ {x, i}\}} \\ \end{aligned}

我们提出指数部分：

∑j=lrmin⁡{eaj,i,ex,i}=∑k=1([pik∣x]⋅k⋅∑j=lr[eaj,i=k])=∑k=1([pik∣x]⋅∑j=lr[eaj,i≥k])\begin{aligned} & \sum\limits _ {j = l} ^ r \min\{e _ {a _ j, i}, e _ {x, i}\} \\ = & \sum\limits _ {k = 1} \left([p _ i ^ k \mid x] \cdot k \cdot \sum\limits _ {j = l} ^ r [e _ {a _ j, i} = k]\right) \\ = & \sum\limits _ {k = 1} \left([p _ i ^ k \mid x] \cdot \sum\limits _ {j = l} ^ r [e _ {a _ j, i \ge k}]\right) \end{aligned}

于是我们对于每个 aia _ i，求出其所有质数的正整数次幂的因子，然后对于每个质数的正整数次幂存下是其倍数的 aia _ i 的 ii，询问时只需要枚举 xx 的所有质数的正整数次幂的因子然后二分求解第二个 ∑\sum 的值即可。

APIO2015 八邻旁之桥 [!!*]

首先去掉在同一侧的人。

然后在桥上的贡献可以直接算，于是问题就在到桥和从桥走到办公室。

对于 k=1k = 1 的情况，显然取所有数的中位数作为桥的坐标即可。

对于 k=2k = 2 的情况，一定是将人划分成两部分，一部分走一座桥，另一部分走另一座桥。

问题在于如何划分。
发现对于两座桥 X,YX, Y 和一个人 (a,b)(a, b)，当 a≤X,Y≤ba \le X, Y \le b 时选任意一个都一样。否则，若其中一个在 [a,b][a, b] 内，另一个在 [a,b][a, b] 外，显然选在 [a,b][a, b] 内的那座桥。否则，可以通过对称使得 b≤X,Yb \le X, Y，然后选择较小的那个。
于是可以得到结论，当且仅当 ∣X−a+b2∣<∣Y−a+b2∣\left|X - \dfrac{a + b}{2}\right| < \left|Y - \dfrac{a + b}{2}\right| 时会选择 XX。

于是我们将人按房子和办公室的坐标之和排序，则一定有一个合法的划分是一段前缀和一段后缀。

于是用对顶堆求出每个前缀和后缀的答案最后再扫一遍即可。

CF843D Dynamic Shortest Path [!]

考虑给其中某些边增加 11 的边权会使最短路发生什么变化。

令 addiadd _ i 表示点 ii 最短路的增加量，disidis _ i 表示原本点 ii 的最短路，disi′dis' _ i 表示更新后点 ii 的最短路。

显然 disi′=disi+addidis' _ i = dis _ i + add _ i。

且有 disv′=min⁡(u,v)∈E(disu′+w(u,v))dis' _ v = \min\limits _ {(u, v) \in E} \left(dis' _ u + w(u, v)\right)。即 disv+addv=min⁡(u,v)∈E(disu+addu+w(u,v))dis _ v + add _ v = \min\limits _ {(u, v) \in E} \left(dis _ u + add _ u + w(u, v)\right)。令 w′(u,v)=w(u,v)+disu−disvw'(u, v) = w(u, v) + dis _ u - dis _ v，则 addv=min⁡(u,v)∈E(addu+w′(u,v))add _ v = \min\limits _ {(u,v) \in E} \left(add _ u + w'(u, v)\right)，可以用 dijkstra 解决。
但是直接来复杂度是不对的。发现 addi≤min⁡{n,c}add _ i \le \min\left\{n, c\right\}，所以用桶代替堆即可。

CF1158B The minimal unique substring [**]

构造一个 0\verb|0| 后面跟 n−k2\dfrac{n - k}{2} 个 1\verb|1| 的字符串的循环即可。

对于子串 sn−k2+1,n+k2s _ {\frac{n - k}{2} + 1, \frac{n + k}{2}}，其只会出现一次。对于所有长度小于 kk 的子串，其往后偏移 n−k2+1\dfrac{n - k}{2} + 1 即可得到与之相同的串。

CF1158D Winding polygonal line

被诈骗了……

钦定凸包上一个点为起点，然后如果下次要左转就选最右边的点，要右转就选最左边的点。手玩一下发现是对的。

NOI Online 2022 提高组 如何正确地排序 [!]

考虑 m=3m = 3 怎么做。

这里仅考虑最大值，最小值是一样的。

令第 ii 列三行分别是 Ai,Bi,CiA _ i, B _ i, C _ i，则若在 (i,j)(i, j) 中 Ai+AjA _ i + A _ j 为最小值，则 Ai+Aj≤Bi+Bj,Ai+Aj<Ci+CjA _ i + A _ j \le B _ i + B _ j, A _ i + A _ j < C _ i + C _ j，移项可得 Ai−Bi≤−(Aj−Bj),Ai−C≤−(Aj−Cj)A _ i - B _ i \le -(A _ j - B _ j), A _ i - C \le -(A _ j - C _ j)，这是一个经典的二维数点的问题。全排列枚举一下统计答案即可。

当 m=4m = 4 时问题进化为三维偏序，当然是可做的，不过另一种做法时考虑取出三行枚举所有方案，发现最大值出现了 33 次，而次大值出现了 11 次，所以最终答案只要减掉一个总和即可。

注意细节问题，等号是否取到，以及排列的枚举。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int m, n, a[200005][5], p[200005];
long long ans = 0;
struct node {int op, x, y, id;} b[400005];
struct BIT {
	int w[400005];

#define lowbit(x) (x & -x)
	void update(int pos) {
		for (; pos < 400005; pos += lowbit(pos)) w[pos]++;
		return ;
	}
	int query(int pos) {
		int res = 0;
		for (; pos >= 1; pos -= lowbit(pos)) res += w[pos];
		return res;
	}
#undef lowbit
} tr;

long long calc() {
	sort(b + 1, b + 2 * n + 1, [](const node &x, const node &y) {
		return x.x != y.x ? x.x < y.x : (x.y != y.y ? x.y < y.y : x.op < y.op);
	});

	// for (int i = 1; i <= 2 * n; i++) printf("%d %d %d %d\n", b[i].op, b[i].x, b[i].y, b[i].id);

	memset(tr.w, 0, sizeof(tr.w));
	long long ans = 0;

	for (int i = 1; i <= 2 * n; i++)
		if (!b[i].op) tr.update(b[i].y + 200001);
		else ans += (long long)tr.query(b[i].y + 200001) * a[b[i].id][p[1]];

	return ans;
}

int main() {
	scanf("%d%d", &m, &n);
	for (int j = 1; j <= m; j++)
		for (int i = 1; i <= n; i++) scanf("%d", &a[i][j]);

	if (m == 2) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) ans += a[i][j];
		ans *= n * 2;
		printf("%lld\n", ans);
		return 0;
	}

	for (int i = 1; i <= m; i++) p[i] = i;

	do {
		if (p[2] > p[3]) continue;
		for (int i = 1; i <= n; i++)
			b[i] = {
				0, a[i][p[2]] - a[i][p[1]], a[i][p[3]] - a[i][p[1]], i
			};
		for (int i = 1; i <= n; i++)
			b[n + i] = {
				1, a[i][p[1]] - a[i][p[2]] - (p[1] > p[2]), a[i][p[1]] - a[i][p[3]] - (p[1] > p[3]), i
			};
		ans += calc();
	} while (next_permutation(p + 1, p + m + 1));

	do {
		if (p[2] > p[3]) continue;
		for (int i = 1; i <= n; i++)
			b[i] = {
				0, a[i][p[1]] - a[i][p[2]], a[i][p[1]] - a[i][p[3]], i
			};
		for (int i = 1; i <= n; i++)
			b[n + i] = {
				1, a[i][p[2]] - a[i][p[1]] - (p[1] > p[2]), a[i][p[3]] - a[i][p[1]] - (p[1] > p[3]), i
			};
		// printf("Permutation: %d %d %d\n", p[1], p[2], p[3]);
		ans += calc();
		// puts("");
	} while (next_permutation(p + 1, p + m + 1));
	// printf("%lld\n", ans);

	if (m == 3) printf("%lld\n", ans * 2);
	else {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) ans -= (long long)a[i][j] * n;
		printf("%lld\n", ans);
	}

	return 0;
}

POI2020-2021R3 Suma liczb pierwszych

牛牛题。

数据点分治，当 nn 小的时候直接处理出所有质数然后双指针。

当 nn 大的时候质数个数不会很大，枚举个数 kk，然后毛咕咕在 nk\dfrac{n}{k} 周围，于是在 nk\dfrac{n}{k} 前后取 kk 个质数双指针即可。取质数直接暴力枚举。

小技巧是第一部分的 nn 可以比你预处理质数的范围稍微大一点，不过没什么用而且很容易死透。

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
62
63
64
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

long long n;
int cnt, prime[15000005];
bool f[200000005];

int isprime(const long long &n) {
	if (n == 1) return 0;
	for (int i = 1; i <= cnt && (long long)prime[i] * prime[i] <= n; i++)
		if (n % prime[i] == 0) return 0;
	return 1;
}

int main() {
	// freopen("prime.in", "r", stdin);
	// freopen("prime.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 2; i <= 200000000; i++) {
		if (!f[i])
			prime[++cnt] = i;
		for (int j = 1; j <= cnt && (long long)prime[j] * i <= 200000000; j++) {
			f[prime[j] * i ] = 1;
			if (i % prime[j] == 0) break;
		}
	}
	cin >> n;
	if (isprime(n)) {cout << n << ' ' << n; return 0;}
	long long sum = 0;
	for (int l = 1, r = 0; l <= cnt; sum -= prime[l++]) {
		while (r < cnt && sum + prime[r + 1] <= n) sum += prime[++r];
		if (sum == n) {cout << prime[l] << ' ' << prime[r]; return 0;}
	}
	// assert(n > 200000000);
	if (n > 2000000000) {
		for (int i = 1; i <= 300; i++) {
			long long mid = n / i;
			vector<long long> v;
			for (long long j = mid, cnt = 0; cnt < i; j--)
				if (j % 2 != 0 && j % 3 != 0 && j % 5 != 0)
					if (isprime(j)) v.push_back(j), cnt++;
			reverse(v.begin(), v.end());
			for (long long j = mid + 1, cnt = 0; cnt < i; j++)
				if (j % 2 != 0 && j % 3 != 0 && j % 5 != 0)
					if (isprime(j)) v.push_back(j), cnt++;
			// cout << "debug: " << v[0] << ' ' << v.back() << '\n';
			long long sum = 0;
			for (int l = 0, r = -1; l < (int)v.size(); sum -= v[l++]) {
				while (r < (int)v.size() - 1 && sum + v[r + 1] <= n) sum += v[++r];
				if (sum == n) {cout << v[l] << ' ' << v[r]; return 0;}
			}
		}
	}
	cout << "NIE";
	return 0;
}

CF1137D Cooperative Game [*]

VP 时想的是，先让前 99 个子每个子分别在 2i2 ^ i 上，此时第 99 个一定在环上，让第 1010 个一直走，就能确定终点在哪两个子之间。

设其为 i−1i - 1 和 ii，那么我们让第 99 个子和 i−1i - 1 一起跳直到某一个到达 ii，这样就可以求出环的大小和 ii 到终点的距离，然后所有点一起往终点跳即可。总次数大概为 2t+3c2t + 3c，但是极其阴间，而且细节一车。

一怒之下查看题解发现有个东西叫 Floyd 绕圈法（（

具体见 mrsrz 的博客。

ARC044C ビーム [!]

列和行显然可以分开考虑。

设 dpidp _ i 表示第 ii 列从当前时刻开始需要移动的最小步数，然后这个东西总共只会修改 qq 个值，然后就做完了。

有点抽象……

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
62
63
64
65
66
67
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m, q;
long long dp[100005];
vector<pair<int, int>> v[2];
long long ans1 = 1e18, ans2 = 1e18;

int main() {
	scanf("%d%d%d", &m, &n, &q);
	for (int i = 1; i <= q; i++) {
		int t, d, x;
		scanf("%d%d%d", &t, &d, &x);
		v[d].emplace_back(t, x);
	}
	sort(v[0].begin(), v[0].end(), [](const pair<int, int> &x, const pair<int, int> &y) {
		return x.first != y.first ? x.first > y.first : x.second < y.second;
	});
	for (int l = 0, r = -1; l < (int)v[0].size(); l = r + 1) {
		while (r < (int)v[0].size() && v[0][r + 1].first == v[0][l].first) r++;
		// printf("[l, r] = [%d, %d]\n", l, r);
		// for (int i = 1; i <= m; i++) printf("%lld ", dp[i]);
		// puts("");
		for (int ll = l, rr; ll <= r; ll = rr + 1) {
			rr = ll;
			while (rr < r && v[0][rr].second + 1 == v[0][rr + 1].second) rr++;
			if (v[0][ll].second == 1 && v[0][rr].second == m) {puts("-1"); return 0;}
			// printf("[ll, rr] = [%d, %d]\n", v[0][ll].second, v[0][rr].second);
			long long lval, rval;
			if (v[0][ll].second == 1) lval = 1e18;
			else lval = dp[v[0][ll].second - 1];
			if (v[0][rr].second == m) rval = 1e18;
			else rval = dp[v[0][rr].second + 1];
			for (int i = v[0][ll].second; i <= v[0][rr].second; i++)
				dp[i] = min(i - v[0][ll].second + 1 + lval, v[0][rr].second - i + 1 + rval);
		}
	}
	for (int i = 1; i <= m; i++) ans1 = min(ans1, dp[i]);
	memset(dp, 0, sizeof(dp));
	sort(v[1].begin(), v[1].end(), [](const pair<int, int> &x, const pair<int, int> &y) {
		return x.first != y.first ? x.first > y.first : x.second < y.second;
	});
	for (int l = 0, r = -1; l < (int)v[1].size(); l = r + 1) {
		while (r < (int)v[1].size() && v[1][r + 1].first == v[1][l].first) r++;
		for (int ll = l, rr; ll <= r; ll = rr + 1) {
			rr = ll;
			while (rr < r && v[1][rr].second + 1 == v[1][rr + 1].second) rr++;
			if (v[1][ll].second == 1 && v[1][rr].second == n) {puts("-1"); return 0;}
			long long lval, rval;
			if (v[1][ll].second == 1) lval = 1e18;
			else lval = dp[v[1][ll].second - 1];
			if (v[1][rr].second == n) rval = 1e18;
			else rval = dp[v[1][rr].second + 1];
			for (int i = v[1][ll].second; i <= v[1][rr].second; i++)
				dp[i] = min(i - v[1][ll].second + 1 + lval, v[1][rr].second - i + 1 + rval);
		}
	}
	for (int i = 1; i <= n; i++) ans2 = min(ans2, dp[i]);
	printf("%lld\n", ans1 + ans2);
	return 0;
}
留言