JSOISC2022模拟3
update 2022-07-17
前言
打暴力使我快乐。
wssb。
T1
这题不难，就是我太菜了，正解想了一个多小时。
一开始所有点都标记为 \(1\) ，每次操作 \(1\) 可以把 \(x\) 子树中所有节点的标记变换为原来的标记与 \(x\) 中深度较大的一个。
如果暴力标记的话操作 \(1\) 是 \(O(n)\) 的，操作 \(2\) 是 \(O(1)\) 的，总复杂度为 \(O(q \times n)\)。
正解可以用 dfs 序加线段树区间修改单点查询。开一个线段树维护每个点的标记，一个节点的子树的 dfs 序是连续的，所以操作 \(1\) 可以转化为线段树区间修改。这样总时间复杂度为 \(O(q \log_{2} n)\)，可以拿到 \(100 pts\)。
但是！线段树要开4倍空间！（寄
但是这题，开了之后 \(TLE\) 了两个点！于是加了 #pragma GCC optimize(2) #define int long long ,就过了。
（但是为什么暴力都能过？我不理解）
人生忠告：不需要 #define int long long 的题不要 #define int long long 。
但是在洛谷上交的话加 #pragma GCC optimize(2) 会 CE！不吸氧会 TLE ！（寄
T2
一个矩阵快速幂优化递推。
很久之前学的矩阵快速幂，现在都快忘了（
发现可以把原数列切成若干个长度为 \(1-\log_{2}m\) 的子串。
可以求出 \(dp[i][j]\) 表示长度为 \(i\)，最后一个数为 \(j\) 的不同子串的数量，然后把子串拼接起来。
令 \(b[i]\) 表示长度为 \(i\) 的不同子串（最后一个数 \(> \lfloor \frac{m}{2} \rfloor\)）的数量，\(f[i]\) 表示以第 \(i\) 个数作为某一个子串结尾的数列的数量。（由于此题 \(2 a_{n} > m\)，所以答案就是 \(f[n]\)）
(大概就是这个
然后就可以用矩阵快速幂优化求出 \(f[n]\) 了。
T3
T4
去学换根 \(dp\) 了（咕咕咕