正赛的几道 Easy,不是很简单,如果评为 Easy-Medium 也不过分。

热身赛 ACD 都是听群友思路补的。

5 6 快 7 快

IDDiffDescriptionSolutionCode
A已知 S=n!mS=\dfrac{n!}{m} 及 1≤m<n≤1061 \le m < n \le 10^6,求 n,mn,m。选模数 PP,枚举 nn,计算 m=n!S mod Pm=\dfrac{n!}{S} \bmod P。如果 m∈[1,n−1]m\in[1,n-1],就说明找到了答案;否则说明此时 mm 不是整数,不是答案。O(log⁡S+nlog⁡P)\mathcal{O}(\log S + n \log P)。AC
BEasy平面上整点 AA 和 BB,找到整点 CC,使三角形 ABCA B C 是直角三角形。分类:如果 ABAB 是斜着的,取 C(xA,yB)C(x_{A},y_{B});如果是垂直的,取 C(xA,yA±1)C(x_{A},y_{A}\pm 1) 或 C(xA±1,yA)C(x_{A} \pm 1,y_{A}) 之一。AC
C长度为 NN 的序列 aa,初始全为 00。设 f(k)=∑i=1klowbit⁡(i)f(k)=\sum_{i=1}^k\operatorname{lowbit}(i)。在线 MM 次操作:(1) 输出 aYa_Y;(2) 对所有 kk,置 aX+f(k)←+Wa_{X + f(k)} \xleftarrow{+} W。ff 有分形结构,分块。取块长 B=2wB=2^w,设 k=qB+rk=qB+r,r≥1r \ge 1 时有 lowbit⁡(qB+r)=lowbit⁡(r)\operatorname{lowbit}(qB+r)=\operatorname{lowbit}(r),f(qB+r)=f(qB)+f(r)f(qB+r)=f(qB)+f(r)。考虑更新 XX 对查询 YY 的影响,Y=X+f(k)=X+f(qB)+f(r)Y=X+f(k)=X+f(qB)+f(r),移项得 X+f(qB)=Y−f(r)\boxed{X+f(qB)=Y-f(r)}。更新时,对所有 q⩾0q \geqslant 0,Lazy⁡[X+f(qB)]←+W\operatorname{Lazy}[X+f(qB)] \xleftarrow{+} W;查询 YY 时,对所有 0⩽r<B0 \leqslant r < B,Ans←+Lazy⁡[Y−f(r)]\text{Ans} \xleftarrow{+} \operatorname{Lazy}[Y-f(r)]。O(MN)\mathcal{O}(M\sqrt{ N})。AC
DMedium简单多边形,平行直线系。求多边形内部被所有直线截得的线段总长度。另见 P8008。变换坐标系,使直线平行于 xx 轴,且间距为 1。考虑多边形上相邻两点 P,QP,Q,截取线段上纵坐标为整数的部分,并求这些整数纵坐标对应的横坐标之和。AC
AEasy多重集 SS,每个元素出现无穷次。求 f(k)=gcd⁡S′⊂S,∣S′∣=k∑x∈S′xf(k) = \gcd\limits_{S' \subset S, \vert S' \vert = k} \sum\limits_{x \in S'} x 的最大值及达到该最大值的最小 kk。设 D=gcd⁡(ai−aj)D=\gcd(a_{i}-a_{j}),f(k)=gcd⁡(kA1,D)f(k) = \gcd(k A_{1}, D)。
若 D=0D=0,则 f(k)=kA1f(k) = k A_{1},最大值无穷大。
否则,设 G=gcd⁡(A1,D)G = \gcd(A_{1}, D),那么 f(k)=Ggcd⁡(k,DG)f(k) = G \gcd(k, \frac{D}{G}),f(k)f(k) 最大为 f(DG)=Df(\frac{D}{G}) = D。
AC
BHard二维矩形内有点,点碰到边后会反弹。左右边向外匀速扩张,上下边向内匀速压缩。求点在压缩结束时的位置。依据 yy 坐标计算结束时间。当左右边速度都为 0 时,直接计算答案。否则,暴力模拟左右碰撞。设第 nn 次碰撞时的宽度 dnd_n,时刻 tnt_n,那么 Δtn∝dn\Delta t_n\propto d_n(追及),Δdn∝Δtn\Delta d_n\propto \Delta t_n,因此 Δdn∝dn\Delta d_n\propto d_n,得到 dn=O(en)d_{n}= \mathcal{O}(\mathrm{e}^{n}),在碰撞 O(log⁡)\mathcal{O}(\log) 次后将达到目标。AC
只包含 1 和 2 的序列,若干次选择两个相邻的数替换为一个按位或。求本质不同序列数量。保证相同数字段长度单调不降。
GEasy网格,格子有石子,数量可能为负。可以无代价将石子向右方或下方移动石子,或花 1 代价移除或添加石子。求将所有位置都变为 0 的最小代价。贪心。如果只有一行:从左向右扫,如果有个地方是负数,就贪心找左边距离它最近的正数,二者相消,如果找不到则必须添加,如果处理完毕后有剩余则必须移除。如果有多行,第一行按上述思路单独处理,把余下的正数转移给下一行,再单独处理第二行。复杂度线性。AC
NN 个集合共 2M2M 个不同元素。每轮操作将全部元素随机两两配对;对于每一对,随机选择一个元素移动到其配对元素所在的集合。求所有元素属于同一集合的期望轮数。
IMedium黑白六边形网格图,每次选择一格并翻转与其相邻的六格,自身不变。充要条件:同一斜行黑格的奇偶性不变。AC
AC
KMedium构造包含 nn 个物品的 01 背包例,满足对于所有背包的容量 2≤c≤C2 \le c \le C,按 (vi/wi,wi)(v_i/w_i, w_i) 降序贪心选取,不能得到最大总价值。需依次最小化 nn、max⁡w\max w、max⁡v\max v。(1) 按性价比排序后,若前几个物品恰好装满背包,那么贪心最优,不合题意。
(2) w1=1w_{1} = 1,即不能 w1≥2w_{1}\ge2。否则取 c=w1c=w_{1},贪心第一个就选它并装满,由 (1),贪心最优。
(3) 归纳得到,至少 CC 个物品,且 wk=kw_k=k。归纳方法:对 c=2c=2,不能出现另一个 w=1w=1。此外,有 w=2w=2,否则贪心与背包相同,都只选了一个 w=1w=1。对 c=3c=3,贪心将直接选中 w1w_{1} 和刚才的 w=2w=2,但希望这种贪心选择不如直接背包选择 w=3w=3。以此类推。
(4) 对 cc,贪心选择 w1=1w_{1}=1 和 w=c−1w=c-1 不如直接背包选 w=cw=c。于是 v1+vk−1<vkv_{1} + v_{k-1} < v_{k},化简得 vk≥(k−1)(v1+1)v_{k} \ge (k-1)(v_{1}+1)。
(5) 为使 w1=1w_{1} = 1,有 v1>vkkv_{1} > \dfrac{v_{k}}{k},即 kv1>vk=(k−1)(v1+1)k v_{1} > v_{k} = (k-1)(v_{1}+1),有 v1⩾Cv_{1} \geqslant C,于是取 v1=Cv_{1}=C。
(6) 至此,wk=kw_k=k,v1=Cv_{1}=C,vk=(k−1)(v1+1)v_{k} = (k-1)(v_{1}+1) 是唯一的构造方法。
AC
LEasy网格,起点为第 11 列,终点为第 MM 列,每次移动可向右、向上或向下。对 2K2^{K} 种障碍排布方式,分别求起点到终点的最小步数。在可以走的格子内做 BFS 求最短路。因为知道 BFS 的顺序(从左到右,再从上到下或从下到上),可直接用循环完成。O(2KMN)\mathcal{O}(2^{K} M N)。AC
正三角形网格图,每个斜行的边的方向相同,求连通的正三角形子图数量。AC

J. 幻想乡的裁判长 【Hard】(回文串)

先将所有 ww 变成两个 vv,做 Manacher。代码里只保留了相同的连续字符的数量,方便写一些。

现在有两个问题:

  • ov 串的最长回文串不一定对应 ovw 串的最长回文串,这可以枚举每个回文中心求最长半径解决。
  • ov 串的回文串在 ovw 串里不一定合法,所以如果边界是 vw 串,需要枚举所有可能的位置(如 vwv 的合法位置有 0134)

复杂度是 O(n)\mathcal{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
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
98
99
100
101
102
103
104
vector<int> Manacher(const vector<int>& t) {
const int n = t.size();
vector<int> rad(n);
for (int i = 0, j = 0; i < n; i++) {
if (2 * j - i >= 0 && j + rad[j] > i) {
rad[i] = min(rad[2 * j - i], j + rad[j] - i);
}
while (i - rad[i] >= 0 && i + rad[i] < n && t[i - rad[i]] == t[i + rad[i]]) {
rad[i]++;
}
if (i + rad[i] > j + rad[j]) {
j = i;
}
}
return rad;
}

void solve() {
int n;
cin >> n;

string s;
cin >> s;

vector<int> nums; // 相同的连续字符的数量
vector<int> lens; // 真实长度
vector<int> opts; // 字符
vector<vector<int>> strs; // 合法位置的差分,即所有虚假长度
for (int i = 0; i < n; i++) {
char c = s[i] == 'o' ? 'o' : 'v';
int len = (s[i] == 'w') + 1;
if (!opts.empty() && c == opts.back()) {
nums.back() += len;
lens.back() += 1;
strs.back().push_back(len);
} else {
nums.push_back(len);
opts.push_back(c);
lens.push_back(1);
strs.push_back({len});
}
}

auto rad = Manacher(nums);
vector<vector<int>> bucpre(lens.size()), bucsuf(lens.size());
for (int i = 0; i < rad.size(); i++) {
if (opts[i] == 'o') continue;
int siz = accumulate(strs[i].begin(), strs[i].end(), 0);
bucpre[i].resize(siz + 1); // 哪些前缀位置合法
bucsuf[i].resize(siz + 1); // 哪些后缀位置合法
int pre = 0;
int len = 0;
for (int j = 0; j < strs[i].size(); j++) {
pre += strs[i][j];
len += 1;
bucpre[i][pre] = len;
}
int suf = 0;
len = 0;
for (int j = int(strs[i].size()) - 1; j >= 0; j--) {
suf += strs[i][j];
len += 1;
bucsuf[i][suf] = len;
}
}

vector<int> prelens(lens.size() + 1);
for (int i = 0; i < lens.size(); i++) {
prelens[i + 1] = prelens[i] + lens[i];
}

int reslen = 0, resl = -1;
auto chres = [&](int len, int l) {
if (len > reslen) {
reslen = len;
resl = l;
}
};

for (int i = 0; i < rad.size(); i++) {
int l = i - rad[i];
int r = i + rad[i];
int len = prelens[r] - prelens[l + 1]; // 中间的真实长度
chres(len, prelens[l + 1]);
if (l >= 0 && r < lens.size()) {
if (opts[l] == 'o') { // 左右的类型,是 o 的话取 min
chres(len + 2 * min(lens[l], lens[r]), prelens[l + 1] - min(lens[l], lens[r]));
} else if (bucsuf[l].size() < bucpre[r].size()) { // 是 vw 的话枚举合法位置
for (int u = 0; u < bucsuf[l].size(); u++) {
if (bucsuf[l][u] && bucpre[r][u]) {
chres(len + bucsuf[l][u] + bucpre[r][u], prelens[l + 1] - bucsuf[l][u]);
}
}
} else {
for (int u = 0; u < bucpre[r].size(); u++) {
if (bucsuf[l][u] && bucpre[r][u]) {
chres(len + bucsuf[l][u] + bucpre[r][u], prelens[l + 1] - bucsuf[l][u]);
}
}
}
}
}
cout << s.substr(resl, reslen) << '\n';
}

M. 连通的正三角形 (计数)

考虑固定水平线 uu,考察左斜线 vv 和右斜线 ww 的限制,三角形合法当且仅当

{s2u=s1v=s3w(1)v⩾n−u(2)w⩾n−u(3)w+v⩾n(4)w+v≠2n−u(5)\begin{cases} s_{2u} = s_{1v} = s_{3w} & (1) \\ v \geqslant n - u & (2) \\ w \geqslant n - u & (3) \\ w + v \geqslant n & (4) \\ w + v \neq 2 n - u & (5) \\ \end{cases}

(5) 这个限制很奇怪,先暂时不考虑。

先枚举 (1)。然后我们升序枚举 uu,用两个数据结构 V,WV,W 分别存储满足 (2)(3) 的 v,wv,w,并记录满足 (4) 的 (v,w)(v,w) 数量 sum。uu 改变时,答案的增量包括

  • 已有的 sum,加入答案;
  • 对于 v=n−uv=n-u,在 WW 中查询满足 w+v⩾nw + v \geqslant n (4) 的 ww 数量,加入 sum;
  • 对于 w=n−uw=n-u,在 VV 中查询满足 w+v⩾nw + v \geqslant n (4) 的 vv 数量,加入 sum;
  • 如果 v=n−uv=n-u 和 w=n−uw=n-u 满足 (4),sum 加 1。

在查询之后,把 v,wv,w 加入数据结构。

然后考虑 (5),这是一个经典的指标和为定值的形式,用 FFT 或 bitset 做卷积就能计算。

复杂度是 O(nlog⁡n)\mathcal{O}(n\log n) 或 O(n2w)\mathcal{O}(\frac{n^{2}}{w})。

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
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ulll = unsigned __int128;

constexpr int inf = 0x3f3f3f3f;

template <typename T>
struct Fenwick {
int N;
vector<T> A;
Fenwick(int N = 0) : N(N), A(N) {}
// arr[x] += v
void add(int x, const T& v) {
for (x++; x <= N; x += x & -x) {
A[x - 1] += v;
}
}
// sum[0, x)
T operator()(int x) const {
T res{};
for (; x > 0; x -= x & -x) {
res += A[x - 1];
}
return res;
}
// sum[L, R)
T operator()(int L, int R) const {
return operator()(R) - operator()(L);
}
};

constexpr int MAXN = 200002;

void solve() {
int n;
cin >> n;

array<bitset<MAXN>, 3> s;
for (int i = 0; i < 3; i++) {
for (int j = 1; j <= n; j++) {
char c;
cin >> c;
s[i][j] = c - '0';
}
}

ll res = 0;
for (int opt = 0; opt <= 1; opt++) {
Fenwick<int> W(n + 1), V(n + 1);

ll sum = 0;
for (int u = 0; u <= n; u++) {
int v = n - u;
int w = n - u;

auto add = [&](int x) {
if (s[1][u]) res += x;
sum += x;
};
if (s[1][u]) res += sum;
if (s[0][v]) add(W(n - v, n + 1));
if (s[2][w]) add(V(n - w, n + 1));
if (s[0][v] && s[2][w]) add(v + w >= n);

if (s[0][v]) V.add(v, 1);
if (s[2][w]) W.add(w, 1);
}

bitset<MAXN> s1_rev;
for (int i = 1; i <= n; i++) {
if (s[1][i]) s1_rev[n - i] = 1;
}
for (int uv = n; uv < 2 * n; uv++) {
int w = 2 * n - uv;
if (s[2][w]) {
res -= (s[0] & (s1_rev << uv - n)).count();
}
}

for (int i = 0; i < 3; i++) {
for (int j = 1; j <= n; j++) {
s[i][j].flip();
}
}
}

cout << res << endl;
}

int main() {
cin.tie(nullptr)->sync_with_stdio(false);

int t;
cin >> t;

while (t--) {
solve();
}

return 0;
}