2021.10.3 QBXT

没有摘要的摘要

10.3

目录

• • 补题
    • 得分情况
    • T1 3627: 可持久化数组
    • T2 3628: 树上的点集
    • T3 3629: 括号序列
    • T4 3630: 拼图游戏
  • 动态规划

100 + 20 + 50 + 10 = 180

板子题??

标程: vector + 二分

直接写主席树可过

代码

数组下标越界挂成 \(20\) /kk

对于点集中的点按照 \(dfs\) 序排序 设 \(dis_u\) 表示 \(u\) 到根的距离 \(s_i\) 表示点集中按照 \(dfs\) 序排序后第 \(i\) 个点 这些点到根覆盖的路径的边权和为

\[\sum_{i = 1}^k dis_{s_i} - \sum_{i = 2}^k dis_{lca_{s_i, s_{i - 1}}}

\]

提前对点集进行排序 预处理相邻点的 \(lca\) 枚举选的点的状态 可以做

复杂度 \(O(2^K \times K)\)

枚举状态的时候用 \(dfs\) 枚举 复杂度可以降到 \(O(2^K)\) 可过

数据没有卡 把上界 \(O(n^2)\) 的写法放过去了

\(3 \times 3\) 八数码问题

\(4 \times 4\)

一行一行的爆搜

\(n = 2\)

每次考虑将最左边两个数归位

如果位置恰好相反 利用 \(2 \times 3\) 的矩阵进行换位 当只剩最后一个 \(2 \times 2\) 的矩阵的时候 旋转 判断是否有解

一般情况

....

弃疗++

原谅 BS 不想补这个题

贴一下标程

ABC159F

考虑正常的 \(dp\)

大概 \(f_{i, j}\) 表示前 \(i\) 个数 选若干个 和为 \(j\)

对于确定的选数方案 考虑其被多少区间包含 对已有区间 \([l, r]\) 包含这个区间的区间为 \(l \times (n - r + 1)\)

把 \(n - r + 1\) 提出 考虑固定右端点 对 \(l\) 求和再乘上 \(n - r + 1\)

设 \(f_{i, j}\) 表示前 \(i\) 个数 选若干个数 和为 \(j\) 的左端点之和

这样 \(dp\) 出来 对于一个 \(r\) 考虑该位置必须选 该点前的左端点之和就是 \(f_{r, s} - f_{r - 1, s}\)

这个东西是前 \(r\) 个数和为 \(s\) 减去 \(r - 1\) 个数和为 \(s\) 的方案 统计下来就是答案

转移方程:

\[f_{i, a_i} += i \\ f_{i, j} += f_{i - 1, j} \\ f_{i, j} += f_{i - 1, j - a_i} \\ ans += (f_{i, s} - f_{i - 1, s}) \times (n - i + 1)

最后得到的 \(ans\) 就是答案

CF815C

首先有一个朴素的 \(dp\)

\(f_{i, j, 0/1}\) 表示第 \(i\) 个节点的子树中买了 \(j\) 个物品 第 \(i\) 个物品是否使用优惠券 所用的钱数的最小值

转移枚举子节点的子树中购买物品的个数 背包合并

CF1093F

z状态 \(f_{i, j}\) 表示前 \(i\) 个数 最后一个为 \(j\) 合法的方案数

转移的时候减去强制 \(len\) 个数字相同的方案数

\[f_{i, j} = \sum_{l = 1}^k f_{i - 1, k}, a_i = -1\\f_{i, a_i} = \sum_{l = 1}^k f_{i - 1, l}, a_i \ne -1

容斥的话考虑能不能把 \(len\) 的区间全部变成 \(j\)

如果能将 \(i - len + 1\) 到 \(i\) 之间全变为同一个数 将 \(f_{i, j}\) 减去 \(\sum_{x \ne j}f_{i - len, j}\) 即可

CF613E

道路分为三部分 两端的 \(U\) 型 中间的折返向某一方向

设 \(f_{i, j}\) 表示 在第 \(i\) 列 \(0\) 表示在上面那行 \(1\) 表示在下面那行 \(j\) 表示当前走过的路径中匹配前 \(j\) 个字符

转移考虑匹配几个字符 强制状态向右走 向右走或向右走完向下走

条件转移 转移的条件是第 \(j\) 或 \(j + 1\) 个字符刚好匹配 \(s\)

\[f_{i, j, 0/1} \to f_{i + 1, j + 1, 0/1} \\f_{i, j, 0/1} \to f_{i + 1, j + 2, 1/0}

考虑两端的 \(U\) 型 暴力枚举 判断 \(s\) 是否可以匹配 哈希

中间一段 \(dp\) 两端 \(U\) 型哈希

CF303E

考虑 \(n\) 个人的成绩落在同一个区间的情况 第 \(i\) 个人考第 \(j\) 名的概率为 \(\frac 1n\)

设 \(f_{j, k, l}\) 表示去掉 \(i\) 个人以外 剩下的人有 \(k\) 个人落在 \(i\) 前面 \(l\) 个人与 \(i\) 落在同一个区间里面...???

PKUSC2019D1T2

考虑确定一个同学的位置

选某个人 用 \(X\) 表示 其他人用 \(0/1\) 表示 其他所有桌只有 \(00, 11, 01\) 三种状态

设 \(f_{i, S}\) 表示 其他桌的状态为 \(S\)

...???

CF599E

设 \(f_{u, S}\) 表示以 \(u\) 为根的子树中 点集为 \(S\) 的连边方案数

转移考虑从这个点集里面拎出一棵子树

\[f_{u, S} = f_{v, T} \times f_{v', S - T}

转移的过程中需要判断条件是否满足

JOISC2020 D3T1

最小化删去星星的权值和 即 最大化剩余星星的权值和

对 \(h_i\) 建笛卡尔树 对于一棵星星 将其转化为笛卡尔树上的一条链 链的一段为节点 \(x_i\) 另一端为 \(x_i\) 不断向父亲

...

???

设 \(f_{i, j}\) 表示以 \(i\) 为根节点的子树中里面选的链从 \(i\) 到深度为 \(j\) 的点的边都被覆盖过的选的情况的权值的最大值

转移:

线段树维护???

转移向上合并???

... 线段树合并维护 dp