11.22 日校内模拟赛总结 + 题解(矩阵加速dp, 分块)
文章目录
- 时间安排
- 成绩
- 总结
- 题解
- T3.三等分
- T4. 二叉树遍历
T4 没时间的一场
时间安排
- 7 : 40 − 8 : 00 7:40 - 8:00 7:40−8:00 花了 20 m i n 20min 20min 先把题目看了一遍。 T 1 T1 T1是糖题, T 2 T2 T2 看起来很神秘但是 n n n 的上界是 1 0 7 10^7 107 说明肯定是一道推一个性质就可以 O ( n ) O(n) O(n) 复杂度的题,应该不会太难。 T 3 T3 T3 看起来有点困难??但是很熟悉。 T 4 T4 T4 应该是个根号数据结构。
- 8 : 00 − 8 : 25 8:00 - 8:25 8:00−8:25 推了一会儿 T 1 T1 T1 细节, 然后写了 15 m i n 15min 15min,大样例都过了,就直接跳了。
- 8 : 25 − 9 : 00 8:25 - 9:00 8:25−9:00,想了一会儿 T 2 T2 T2,发现了有一个字符串是确定的,然后想让剩下的第一个 0 0 0 变成 1 1 1,这个也是可以做到。又想到了应该在不影响前面的 1 1 1 的基础上尽量将前面的 0 0 0 变成 1 1 1。那么这时候选哪一个字符串就确定了。因此扫一遍就行。然后很快写完了,大样例太大了导致比对两个文件夹比对了 20 m i n 20min 20min。
- 9 : 00 − 9 : 10 9:00 - 9:10 9:00−9:10,看了一会儿 T 3 T3 T3,感觉好像是代码源的原题???回去看了一下,发现就是,而且还是弱化版。然后给学长说了一声,他换了一道题。
- 9 : 10 − 11 : 20 9:10 - 11:20 9:10−11:20 推 T 3 T3 T3,中间很快想到了矩阵乘法,但是有一些问题:比如说如何去重。想了一会儿发现会去重了。但是又发现我的状态数是 7 2 = 49 7^2 = 49 72=49 的,那么矩阵乘法的复杂度就是 4 9 3 49^3 493,但是还要乘上 1000 1000 1000 和 60 60 60,过不掉。有点急,上个厕所。路上发现状态数可以缩小至 28 28 28,回去算了一下发现还是过不了。然后突然想到在我的转移方式下,第一个状态大小不会超过 3 3 3,第二个状态不会比第一个状态大 超过 3 3 3,那状态数就只有 3 × 3 = 9 3 \times 3 = 9 3×3=9 的了,这样就很宽松了。然后就去写, 30 m i n 30min 30min 写完了没有过样例,然后就开始查错,一点一点查,最后将错都改完了。然后就过了大样例。
- 11 : 20 − 12 : 00 11:20 - 12:00 11:20−12:00 只剩下 40 m i n 40min 40min,感觉不是很能花费一半时间去推正解之类的。就决定先把最简单的暴力写了。发现有 25 p t s 25pts 25pts 是简单的。就直接去写了。写完之后还剩下 10 m i n 10min 10min,想了另一个性质分,但是应该写不完了。
成绩
期望得分:100 + 100 + 100 + 25 = 325
实际得分:100 + 100 + 100 + 25 = 325
没有挂分。
总结
- 感觉T3的思考过程还是挺不错的。一步一步的向正解迈进,挺喜欢这样思考的感觉。
- 前面的题没有挂分,因为我在写的时候比较小心,情况考虑的比较全面。希望这样的状态能保持住。
- T4 再思考思考应该还是有不少分的,最起码 45 p t s 45pts 45pts 都是不难的。但是没有时间了。下次应该更紧张一些
题解
T3.三等分
原题链接
题意:
有
n
n
n 种数, 分别是
1
,
2
,
.
.
.
,
n
1,2,..., n
1,2,...,n,每种共
C
C
C 个。故总共有
n
C
nC
nC 个数。
三个相连的数
(
i
,
i
+
1
,
i
+
2
)
(i, i + 1,i + 2)
(i,i+1,i+2) 或三个相同的数
(
i
,
i
,
i
)
(i, i, i)
(i,i,i) 可以组成一个 三元组。
如果一组数可以划分成若干(包括零个)三元组,那称其为好的。
你现在从这些数字中选了一些出来构成可重数字集合
S
S
S,其中值为
k
i
k_i
ki 的选了
a
i
a_i
ai 个。
你需要从剩下的数字中选出一些加入
S
S
S,使得
S
S
S 是好的。
问有多少种可能组成的
S
S
S ?答案对
998244353
998244353
998244353 取模。
两组
S
S
S 相同当且仅当它们含有的每一种数字的个数都相同。
1 ≤ n ≤ 1 0 18 1 \leq n \leq 10^{18} 1≤n≤1018, 0 ≤ a i ≤ C ≤ 1000 0 \leq a_i \leq C \leq1000 0≤ai≤C≤1000, 0 ≤ X ≤ 1000 0 \leq X \leq 1000 0≤X≤1000。
分析:
考试时候的思路是:
首先将
(
i
,
i
+
1
,
i
+
2
)
(i, i + 1, i + 2)
(i,i+1,i+2) 定义为一操作,
(
i
,
i
,
i
)
(i, i, i)
(i,i,i) 定义为二操作。
考虑一个 S S S 是好的 等价于 我们可以对每种数字使用若干一操作和二操作将这种数字变成 0 0 0。
发现对于一种数 k k k 而言,最多用一操作消掉它 6 6 6 次。如果大于 6 6 6 次可以替换成若干二操作。
然后就是我们对一操作使用的次数 d p dp dp 出来一个数组 b b b, b i b_i bi 表示 i i i 这种数字使用一操作消掉的数量。然后对于一个合法的 b b b,乘上每种数的系数就是对答案的贡献。 ( 0 ≤ b i ≤ 6 ) (0 \leq b_i \leq 6) (0≤bi≤6),其中系数 c i = ( C − b i ) / 3 + 1 c_i = (C - b_i) / 3 +1 ci=(C−bi)/3+1 表示能够接几个二操作。那么就记 d p i , j , k dp_{i, j, k} dpi,j,k 表示考虑到了第 i i i 个位置, i − 1 i - 1 i−1 的一操作还剩下 j j j 个, i i i 的一操作还剩下 k k k 个的方案数。转移就是直接枚举一个 l l l,表示钦定第 i + 1 i + 1 i+1 个位置使用几次一操作,然后转移给 d p i + 1 , k − j , l − j dp_{i + 1, k - j, l - j} dpi+1,k−j,l−j,乘上一个 c i + 1 c_{i + 1} ci+1。
但是这样会有重复。考虑将转移唯一化,就不会重复了。注意到当 l l l 取 { 0 , 3 , 6 } \{0, 3, 6\} {0,3,6} 或 { 1 , 4 } \{ 1, 4\} {1,4} 或者 { 2 , 5 } \{2, 5\} {2,5} 时,内部转移会重复。因为要保证 l ≥ k ≤ j l \geq k \leq j l≥k≤j,那么我们钦定 对于每一组转移给最小的可以转移的。例如对于 { 0 , 3 , 6 } \{0, 3, 6\} {0,3,6},如果 0 0 0 能转移就转给 0 0 0,然后不给 3 , 6 3, 6 3,6 转移,如果不能再考虑 3 3 3,最后考虑 6 6 6。这样转移首先不会有重复。但是会不会出现原来钦定是 6 6 6 才能成立,现在是 3 3 3 不能成立的情况呢?发现不会。因为钦定是 6 6 6 的话在 i + 1 i + 1 i+1 这个位置需要往后连续多使用 3 3 3 次操作一,不如直接对着三个位置各加一次操作二。
然后发现状态数比较少可以直接矩阵乘法,但是状态数为 7 × 7 = 49 7 \times 7 = 49 7×7=49,矩乘的复杂度是 4 9 3 49^3 493,乘上 X X X 和 log 2 n \log_2n log2n 是不能通过的。虽然因为 j ≤ k j \leq k j≤k 可以将状态数减到 28 28 28,但也是过不了的。
然后就是注意到在去重后的转移下,每次转移 j j j 是 小于 3 3 3 的。因为如果大于等于 3 3 3,那么钦定它的时候就比前面的大超过 2 2 2 了。这种状态是不会转移的。然后就是 0 ≤ k − j < 3 0 \leq k - j < 3 0≤k−j<3 的。这个与上边的同理。因此将状态改成 d p i , j , k dp_{i, j, k} dpi,j,k 表示 i − 1 i - 1 i−1 还剩下 j j j, i i i 比 i − 2 i - 2 i−2 还大 k k k 的方案数。那么状态数就变成了 9 9 9,可以矩乘加速了。
实际上还有一个trick: 对于这种需要多次对同一个矩阵跑快速幂的问题,可以通过预处理这个矩阵的 2 2 2 的若干次幂来降低复杂度。因为矩阵乘矩阵是 n 3 n^3 n3 的,但是向量乘矩阵是 n 2 n^2 n2 的。那么有了这个 t r i c k trick trick 感觉状态数 28 28 28 也能过了。
CODE:
// 首先考虑到对于每个位置操作1不会使用超过 6 次
// 然后如果我们能够dp出来一个操作 1 数量的数组,那么乘上系数就可以计数
// 操作1数量的取值为 [0, 6], 系数就是上界减去这个数量之后 / 3 的数量, 表示能够补多少操作2
// 但是这样有一个问题,就是一个位置上填同一个数可能对应好多种方案
// 注意到会重复的是 {0, 3, 6}, {1, 4}, {2, 5}, 如果我们知道了前面还剩下的操作1数量为 j, k, 那么需要满足 j <= k <= l, 取 l 最小的那个, l大的可以, l小的也一定可以
// 设 (j, k) 表示 i 比 i - 1 多了 k, 当前 i - 1 是 j 的方案数。 那么 0 <= j < 3 0 <= k < 3, 根据 (j, k) 就可以转移
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long LL;
const LL mod = 998244353;
struct matrix {
LL mt[10][10];
friend matrix operator * (matrix a, matrix b) {
matrix c; memset(c.mt, 0, sizeof c.mt);
for(int i = 0; i < 10; i ++ )
for(int j = 0; j < 10; j ++ )
for(int k = 0; k < 10; k ++ )
c.mt[i][j] = (c.mt[i][j] + a.mt[i][k] * b.mt[k][j] % mod) % mod;
return c;
}
}Mt[N]; // 每一种的矩阵
LL n, C;
int X;
LL K[N], A[N]; // A[i] 个 K[i] K[i] 位置上至少 A[i] 个
int ID(int x, int y) {
return x * 3 + y;
}
void build(int x) { // 对 x 的限制构建矩阵
for(int i = 0; i <= 2; i ++ ) {
for(int j = 0; j <= 2; j ++ ) {
for(int k = 0; k <= 2; k ++ ) { // (i, j) -> (j, k)
LL c = i + j + k; // 这一位上的数字
if(x == 0) {
if(C >= c) Mt[x].mt[ID(i, j)][ID(j, k)] = (C - c) / 3LL + 1;
else Mt[x].mt[ID(i, j)][ID(j, k)] = 0;
}
else {
if(C >= c) {
LL r = ((C - c) / 3LL); // k 的上界
LL l;
if(A[x] - c > 0) l = ((A[x] - c - 1) / 3LL + 1LL); // k 的下界
else l = 0;
Mt[x].mt[ID(i, j)][ID(j, k)] = (l <= r ? 1LL * (r - l + 1) : 0);
}
else Mt[x].mt[ID(i, j)][ID(j, k)] = 0; // 根本不够
}
}
}
}
}
matrix Pow(matrix x, LL y) {
matrix res, k = x;
for(int i = 0; i < 10; i ++ )
for(int j = 0; j < 10; j ++ )
res.mt[i][j] = (i == j);
while(y) {
if(y & 1) res = res * k;
y >>= 1;
k = k * k;
}
return res;
}
int main() {
freopen("three.in", "r", stdin);
freopen("three.out", "w", stdout);
scanf("%lld%lld", &n, &C);
scanf("%d", &X);
for(int i = 1; i <= X; i ++ ) {
scanf("%lld%lld", &K[i], &A[i]);
}
for(int i = 0; i <= X; i ++ ) {
build(i);
}
matrix f; memset(f.mt, 0, sizeof f.mt);
f.mt[0][ID(0, 0)] = 1LL;
LL now = 0; // 乘到了 now
for(int i = 1; i <= X; i ++ ) {
f = f * Pow(Mt[0], K[i] - now - 1);
f = f * Mt[i];
now = K[i];
}
f = f * Pow(Mt[0], n - K[X]);
printf("%lld\n", f.mt[0][ID(0, 0)]); // 必须消完
return 0;
}
T4. 二叉树遍历
题意:
分析:
首先求一个点
x
x
x 在
d
f
n
dfn
dfn 序列的位置等价于有多少点
y
y
y 在
x
x
x 的前面。
那么可以把
y
y
y 分成三类:
- 存在一个 z z z,满足 x x x 在 z z z 的右子树, y y y 在 z z z 的左子树。
- y y y 在 x x x 的子树中。
- y y y 是 x x x 的祖先。
发现对于第一类点,每次询问对于一个点而言贡献都是固定的。可以直接预处理出来。
对于第二类点,每次询问只需要知道
x
x
x 的状态 和
x
x
x 的左右子树中节点的数量。这个也是简单的。
现在的问题在于如何处理第三类点:
下面有两种做法:
1. 珂朵莉树:
发现每次是将一段 编号区间 染成某个颜色,使用 o d t odt odt 维护相同颜色段,每次询问枚举每个颜色段,考虑一段相同状态的区间对询问点 x x x 的第三类点贡献:
- 区间状态为 − 1 -1 −1,那么只需要知道区间中有多少点 y y y 是 x x x 的祖先。
- 区间状态为 0 0 0,只需要知道区间中有多少点 y y y,满足 x x x 在 y y y 的右子树中。
- 区间状态为 1 1 1,那么这段区间对 x x x 没有贡献。
如何快速求出 一段编号区间中有多少点是 x x x 的祖先 以及 x x x 在它的右子树中, 这个可以对每个点维护一棵向上延伸到根的 主席树,在值域线段树的每个位置维护信息。那么只需要查询一棵线段树的区间和即可。
这样在数据随机的情况下复杂度是 O ( n log log n × l o g 2 n ) O(n \log \log n \times log_2n) O(nloglogn×log2n) 的。
但是数据不是随机的,珂朵莉树可以卡掉。好像直接交珂朵莉树可以过掉 90 p t s 90pts 90pts。
2. 分块:
考虑使用分块维护三类点对每个点的贡献。
我们将块分为两类:颜色相同的块和颜色不同的块。前者称作一类块,后者称作二类块。
那么每次查询点
x
x
x 可以枚举每个块,对这两类块分别求贡献:
- 对于一类块:只需要知道块内有多少点是 x x x 的祖先 以及 有多少点满足 x x x 在它的右子树中。可以 O ( n n ) O(n \sqrt{n}) O(nn) 预处理,然后枚举到一类块 O ( 1 ) O(1) O(1) 查询。
- 对于二类块:发现每次修改最多只会增加 2 2 2 个二类块,那么一共最多有 q q q 个二类块。那么可以对每个点 x x x 维护出 f x f_{x} fx 表示 当前 所有二类块对 x x x 的贡献。然后修改如果一个二类块整段被改成某个值,就暴力扫描块内每个点修改它的状态,并把块的状态标记成一类块。然后把两个三块标记成二类块。单点改一个点的状态的影响是 子树加减,也就是 d f n dfn dfn 序列上的区间加减。我们有 O ( q n ) O(q\sqrt{n}) O(qn) 次修改, O ( q ) O(q) O(q) 次查询。写一个分块维护差分标记的和就可以做到 O ( 1 ) O(1) O(1) 修改, O ( n ) O(\sqrt{n}) O(n) 查询。
总复杂度 O ( q n ) O(q\sqrt{n}) O(qn)
CODE:
// 感觉是很妙的题
// 首先要求 x 在 dfn 序列的位置, 那么就相当于求有多少个 y 在 x 前面
// 分三类: 1. x 在 某个 z 右子树, y 在 z 的左子树。 2. y 在 x 的子树中 3. y 是 x 的祖先
// 第 1 类是固定的。 第 2 类可以根据 x 现在的 op 快速算出来。 关键是 3 类贡献
// 因为修改是在编号序列上连续, 所以对编号序列分块。 那么可以分为两类块:块内状态都一样, 块内状态不一样
// 对于第一类:只需要关注块内有多少 y 是 x 的祖先 和 有多少y满足x在y的右子树, 这个可以预处理。 复杂度O(n√n)
// 对于第二类:发现一次修改最多增加两个二类块, 因此最多有 q 个二类块。 那么每次遇到一个二类块可以暴力修改, 然后把二类块改成一类块
// 这样有 q√n 次修改, O(q) 次查询, 那么差分均摊即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int B = 320;
int n, q;
int ls[N], rs[N];
int cnt[N]; // 有多少个 y 满足存在一个 z, x 在 z 的右子树, y 在 z 的左子树
int Tp[B], tp[N]; // 块的状态, 单点的状态 Tp 等于 2 表示 二类块
int dfn[N], ID[N], dfc, L[N], R[N]; // 左右区间
int bel[N], v[N], sv[B];
int f[B][N], g[B][N]; // f[i][x] 表示 i 号块里面有多少个点是 x 的 祖先, g[i][x] 表示 i 号块里面有多少个点满足 x 在它的的右子树里
int b[N], c[N];
void dfs0(int x) {
dfn[x] = L[x] = ++ dfc; ID[dfc] = x;
if(ls[x]) dfs0(ls[x]);
if(rs[x]) dfs0(rs[x]);
R[x] = dfc;
}
void dfs1(int x, int sum) {
cnt[x] = sum;
if(ls[x]) dfs1(ls[x], sum);
if(rs[x]) {
int c = (ls[x] ? R[ls[x]] - L[ls[x]] + 1 : 0);
dfs1(rs[x], sum + c);
}
}
void Add(int x) {
if(x <= n) {
v[x] ++;
sv[bel[x]] ++;
}
}
void Del(int x) {
if(x <= n) {
v[x] --;
sv[bel[x]] --;
}
}
void add(int x) { // O(1) 加入 x 的贡献
if(tp[x] == -1) {
if(ls[x]) Add(L[ls[x]]), Del(R[ls[x]] + 1);
if(rs[x]) Add(L[rs[x]]), Del(R[rs[x]] + 1);
}
else if(tp[x] == 0) {
if(rs[x]) Add(L[rs[x]]), Del(R[rs[x]] + 1);
}
}
void del(int x) { // O(1) 删去 x 的贡献
if(tp[x] == -1) {
if(ls[x]) Del(L[ls[x]]), Add(R[ls[x]] + 1);
if(rs[x]) Del(L[rs[x]]), Add(R[rs[x]] + 1);
}
else if(tp[x] == 0) {
if(rs[x]) Del(L[rs[x]]), Add(R[rs[x]] + 1);
}
}
void get(int x) { // 把 x 块改成 2 类块
if(Tp[x] == 2) return ;
else {
for(int i = (x - 1) * B + 1; i <= min(x * B, n); i ++ ) {
tp[i] = Tp[x];
add(i);
}
Tp[x] = 2;
}
}
void modify(int x, int c) { // 把 x 改成 c
del(x); // 首先把 x 原来的贡献删去
tp[x] = c;
add(x); // 加上现在的贡献
}
void change(int l, int r, int x) { // 区间赋值成 x
if(bel[l] == bel[r]) {
get(bel[l]); // 首先把这个块变成2类点, 把这个块的贡献算到所有点上
for(int i = l; i <= r; i ++ ) modify(i, x); // 单点改 x
}
else {
get(bel[l]); get(bel[r]);
for(int i = l; i <= min(bel[l] * B, n); i ++ ) modify(i, x);
for(int i = (bel[r] - 1) * B + 1; i <= r; i ++ ) modify(i, x);
for(int i = bel[l] + 1; i < bel[r]; i ++ ) {
if(Tp[i] != 2) { // 整块一样
Tp[i] = x;
}
else { // 暴力修改
for(int j = (i - 1) * B + 1; j <= min(n, i * B); j ++ ) { // 暴力删去原来的贡献
del(j);
tp[j] = x;
}
Tp[i] = x;
}
}
}
}
int asks(int x) {
int res = 0;
for(int i = 1; i < bel[x]; i ++ ) res += sv[i];
for(int i = (bel[x] - 1) * B + 1; i <= x; i ++ ) res += v[i];
return res;
}
int ask(int x) { // 查询 x 的答案
int res = 0;
for(int i = 1; i <= bel[n]; i ++ ) {
if(Tp[i] != 2) {
if(Tp[i] == -1) res += f[i][x];
else if(Tp[i] == 0) res += g[i][x];
}
}
res += asks(dfn[x]);
int ttp = (Tp[bel[x]] != 2 ? Tp[bel[x]] : tp[x]);
if(ttp == 0) {
if(ls[x]) res += R[ls[x]] - L[ls[x]] + 1;
}
if(ttp == 1) {
if(ls[x]) res += R[ls[x]] - L[ls[x]] + 1;
if(rs[x]) res += R[rs[x]] - L[rs[x]] + 1;
}
return res;
}
int main() {
freopen("traversing.in", "r", stdin);
freopen("traversing.out", "w", stdout);
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i ++ ) {
scanf("%d%d", &ls[i], &rs[i]);
}
dfs0(1);
dfs1(1, 0);
for(int i = 1; i <= n; i ++ ) bel[i] = (i - 1) / B + 1;
for(int i = 1; i <= bel[n]; i ++ ) {
for(int j = (i - 1) * B + 1; j <= min(i * B, n); j ++ ) {
if(ls[j]) {
b[L[ls[j]]] ++; b[R[ls[j]] + 1] --;
}
if(rs[j]) {
b[L[rs[j]]] ++; b[R[rs[j]] + 1] --;
c[L[rs[j]]] ++; c[R[rs[j]] + 1] --;
}
}
for(int j = 1; j <= n; j ++ ) {
b[j] += b[j - 1]; c[j] += c[j - 1];
f[i][ID[j]] = b[j]; g[i][ID[j]] = c[j];
}
for(int j = 1; j <= n; j ++ ) b[j] = c[j] = 0;
}
for(int i = 1; i <= n; i ++ ) tp[i] = -1;
for(int i = 1; i <= bel[n]; i ++ ) Tp[i] = -1;
for(int i = 1; i <= q; i ++ ) {
int opt, l, r, x;
scanf("%d", &opt);
if(opt == 1) {
scanf("%d%d%d", &l, &r, &x);
change(l, r, x); // 区间赋值
}
else {
scanf("%d", &x);
printf("%d\n", cnt[x] + ask(x) + 1);
}
}
return 0;
}
/*
5 5
3 4
0 0
5 2
0 0
0 0
2 2
1 1 3 1
2 5
1 3 3 0
2 3
*/