T1 美丽校园
标准解法
很容易想到:从 \(1\) 出发向 \(t\) 走的路径不容易得到,而从 \(t\) 向 \(1\) 的路径只需要每次走到当前点的父节点。
因此问题转化为:
求从 \(t\) 向根节点走 \(dis_t - \frac{d}{2}\) 能到达的最远位置。
若最后走到点 \(x\) 上,则 \(x\) 即为答案,若最后走到一条边 \(e: x \rightarrow pnt_x\) 上,则 \(pnt_x\) 即为答案。
其中: \(dis_t\) 表示从 \(t\) 到 \(1\) 的距离,\(pnt_x\) 表示 \(x\) 的父节点。
预处理出 \(f_{p,i}\) 表示节点 \(p\) 的 \(2^i\) 辈祖先和 \(d_{p,i}\) 表示 \(p\) 到 \(f_{p,i}\) 的距离,倍增求解即可。
时空复杂度
时间复杂度:\(\mathcal{O}\left(\left(n+m\right)\log n\right)\)
空间复杂度:\(\mathcal{O}\left(n\log n\right)\),常数约为 \(2\)
特殊性质与部分分
前 60%
时间复杂度小于等于 \(\mathcal{O}\left(nm\right)\) 的暴力能够通过。
特殊性质 1
「图是 \(1\) 为一个端点的链」,将树上问题弱化为序列问题。
特殊性质 0,2
「图随机生成」或「图是 \(1\) 为根的满二叉树」,树的深度为 \(\log n\) 级别,时间复杂度小于等于 \(\mathcal{O}\left(m\cdot\max\left(depth\right)\right)\) 的暴力能够通过。
T2 生成序列
60分做法
60分的\(O(n^3)\) DP应该是比较好写, 略
标准解法
考虑固定一个 \(T_n\),求出包含其的 \(n\) 元组数量。
对于 \(T_n\) 中的每一个元素,可以发现其与若干个元素形成了依赖关系,并且其可以简化为一棵树。具体而言:
- 对于一个 \(1\) 或 \(m\),其依赖左边最后一个 \(1\) 或 \(m\);
- 对于其它合法值,其依赖右边第一个 \(1\) 或 \(m\);
因为 \(n\) 元组数量即为生成 \(T_n\) 的方案数,所以其等同于依赖关系树的拓扑序数量。一棵树的拓扑序数量为 \({siz_{root}! \over \prod siz_u}\),因为对于每一个节点 \(u\),其排在其子树中的节点前面的概率为 \(1 \over siz_u\)。
然后可以用一个 DP 求出所有 \(T_n\) 的方案数之和。设 \(f_i\) 表示当前考虑到 \(i\) 且末尾元素为 \(1\) 或 \(m\) 的方案数,转移分两种,一种是从 \(i-1\) 转移过来,另一种是从 \(j(\le i-2)\) 中间插入一些数,方程较简单,留给你自己思考 (想不通再看 std)。时间复杂度 \(\Theta(n^2)\)。
T3 奶茶分配
标准解法
线段树维护矩阵乘法,Plozia在线段树总结里写得很清楚, 好好看看题解 哈
https://www.cnblogs.com/Plozia/p/16142252.html
T4 吃豆豆
CCPC-Wannafly Winter Camp Day1 B题吃豆豆,wls出的题,当时wls来义乌中学讲了这题感觉很不错
30分解法
如果你上网搜一下这题的题解,基本上都是 30分的做法,暴力跑DP,状态定义如下:
定义状态 f[i][j][t] 表示在t秒时 i,j位置最多可以获得的豆豆数量,
标准解法
C 这里很大,\(10^{18}\), 显然跟 时间有关的状态基本上就寄了
仔细观察 \(T_{i, j}\) 最大是10, 而 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 的 LCM 只有2520
所以我们对时间每 2520 进行分段,显然 dp的状态只需要求解 f[i][j][t <= 2520] 即可。
那么 S -> T 的路径就可以拆分成 S -> M (经过2520的整数倍 E 秒),再由 M -> T
那么我们预处理
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j) M[0][i][j] = f[i][j][2520];
M[i] 表示 时间过了 \(2^i\) 倍的 2520, 任意两点i 到 j 最多吃到的糖果数量
通过倍增我们可以计算出 M[1], M[2], M[3] .... M[51]
最后一步通过倍增 和 枚举剩余时间 (不足一个2520的)来确定答案
for (int i = 51; ~i; --i) {
tmp = R * M[i];
if (tmp[S][T] < C)
R = tmp, ans += 1ull << i;
}
for (int i = 1; i <= 2520; ++i)
for (int j = 1; j <= N; ++j)
if (f[j][T][i] > 0)
if (R[S][j] + f[j][T][i] >= C)
return printf("%llu\n", ans * 2520 + i), 0;
标签:right,2520,题解,复杂度,2023,CCF,节点,left
From: https://www.cnblogs.com/Mysterious-Cat/p/17134608.html