比赛传送门
前言
做出来 7 题，第一次做出 Ex，感觉还不错。
上一次做出 7 题还是在很久以前呢 /wx
为啥 ABC 前几题越来越难了啊，感觉 C 都有 D 的水平了。
交错程序一发，可真有我的。
题解
E - Lucky Numbers
题意
有一个未知的长度为 $N$ 的数列 $A$ 满足 $A_i+A_{i+1}=S_i$，给定 $S$ 和一个大小为 $M$ 的集合 $X$，求最多有多少个 $i$ 满足 $A_i \in X$。
$N \le 10^6,M \le 10,-10^9 \le S_i,X_i \le 10^9$
做法
Tag: 数学
先钦定 $A_1=0$，推出整个 $A$。
容易得到，如果 $A_1+1$，那么必定会有 $A_2-1,A_3+1,A_4-1,A_5+1\dots$，即奇数下标的 $+1$，偶数下标的 $-1$。
对于每个奇数的 $i$ 处理出所有 $X_j-A_i$，对于每个偶数的 $i$ 处理出所有 $A_i-X_j$，这样就可以统计出 $A_1+W$ 后的答案，即为 $W$ 在统计中出现的次数。在左右出现次数中取最大值即可。
Code
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
| ll n, m, s[100005], x[20], a[100005], ans = 0;
vector<ll>v;
void solve() {
cin >> n >> m;
rep(i, n - 1)cin >> s[i];
rep(i, m)cin >> x[i];
forr(i, 1, n - 1)a[i] = s[i - 1] - a[i - 1];
rep(i, n) {
rep(j, m) {
ll tmp;
if (i % 2 == 0)tmp = a[i] - x[j];
else tmp = x[j] - a[i];
v.pb(tmp);
}
}
sort(v.begin(), v.end());
ll l, r = 0;
while (r < (ll)v.size()) {
l = r;
while (r + 1 < (ll)v.size() && v[r + 1] == v[l])r++;
ans = max(ans, r - l + 1);
r++;
}
cout << ans;
}
|
F - Pre-order and In-order
题意
给出一棵树的前序遍历 $P$ 和中序遍历 $I$，求这棵树的形态，或判断无解。
$N \le 2\times 10^5$
做法
CSP 初赛经典题了属于是。
考虑 $P_{l\dots r}$ 匹配 $I_{L\dots R}$。
显然 $P_l$ 为根，所以就可将 $I$ 划分成两段，即 $P_l$ 的左边和右边。知道左右子树大小后，就可以将 $P_{L+1\dots R}$ 划分成两段，递归即可。
如果 $P_l$ 在 $I_{L\dots R}$ 中没有出现则判断无解。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int n, a[200005], b[200005], p[200005];
int son[200005][2];
bool ans = 1;
void dfs(int l, int r, int L, int R) {
if (l > r || L > R || !ans)return;
int x = a[l], y = p[a[l]], lenl = y - L, lenr = R - y;
if (y<L || y>R)ans = 0;
if (lenl > 0)son[x][0] = a[l + 1] + 1, dfs(l + 1, l + lenl, L, y - 1);
if (lenr > 0)son[x][1] = a[l + lenl + 1] + 1, dfs(l + lenl + 1, r, y + 1, R);
}
void solve() {
cin >> n;
rep(i, n)cin >> a[i], a[i]--;
rep(i, n)cin >> b[i], b[i]--, p[b[i]] = i;
if (a[0]) {
cout << -1;
return;
}
dfs(0, n - 1, 0, n - 1);
if (!ans)cout << -1;
else rep(i, n)cout << son[i][0] << ' ' << son[i][1] << endl;
}
|
G - Constrained Nim
没看。
Ex - Range Harvest Query
题意
有 $N$ 棵树，第 $0$ 天它们都没有果子，每天晚上，第 $i$ 棵树会结出 $i$ 个果子。
共有 $Q$ 次采摘，第 $i$ 次在第 $D_i$ 天晚上，采走第 $L_i$ 到 $R_i$ 棵树上所有的果子。
对于每次采摘，输出采到了多少果子，对 $998244353$ 取模。
$N,D_i \le 10^{18},Q \le 2 \times 10^5,D_i<D_{i+1}$
做法
Tag: 数据结构，珂朵莉树
珂朵莉树模板题。
感谢 lxl！
维护每棵树最后被采摘的区间，每次用等差数列求和处理区间贡献，再区间赋值即可。
由于每次操作只会 split 出 至多 $2$ 个区间，所以区间总数是 $O(Q)$ 的，并且查询复杂度和包含的区间个数有关，查询后会将这些区间全部合并到一起，所以最多只会查询 $O(Q)$ 个区间，算上 set 复杂度，总时间复杂度为 $O(Q \log Q)$。
Code
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
| struct Node {
ll l, r;
mutable ll val;
Node(ll a = -1, ll b = -1, ll c = 0) {
l = a, r = b, val = c;
}
bool operator < (const Node& a) const {
return l < a.l;
}
};
set<Node>s;
bool cmp(pair<ll, ll>x, pair<ll, ll>y) {
return x.first < y.first;
}
set<Node>::iterator split(ll pos) {
set<Node>::iterator it = s.lower_bound(Node(pos));
if (it != s.end() && it->l == pos)return it;
--it;
Node tmp = *it;
s.erase(it);
s.insert(Node(tmp.l, pos - 1, tmp.val));
return s.insert(Node(pos, tmp.r, tmp.val)).first;
}
void assign(ll l, ll r, ll val) {
set<Node>::iterator itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(Node(l, r, val));
}
ll qpow(ll a, ll x, ll y) {
ll ans = 1;
a %= y;
while (x) {
if (x & 1)ans = (ans * a) % y;
a = (a * a) % y;
x >>= 1;
}
return ans;
}
ll e_2;
ll query(ll l, ll r, ll d) {
set<Node>::iterator itr = split(r + 1), itl = split(l);
ll ans = 0;
for (set<Node>::iterator it = itl; it != itr; it++) {
ll L = it->l, R = it->r, lst = it->val;
ll sum = (L % MOD + R % MOD) % MOD * ((R - L + 1) % MOD) % MOD * e_2 % MOD;
ans = (ans + (d % MOD - lst) % MOD * sum % MOD) % MOD;
}
return (ans + MOD) % MOD;
}
ll n, q, d, l, r;
void solve() {
e_2 = qpow(2, MOD - 2, MOD);
cin >> n >> q;
s.insert(Node(1, n, 0));
while (q--) {
cin >> d >> l >> r;
cout << query(l, r, d) << endl;
assign(l, r, d);
}
}
|
后记
赛后难度出来了，果然 G>Ex 呢 /hx