noip2021 训练4 作题记录

2021年11月24日 阅读数:3
这篇文章主要向大家介绍noip2021 训练4 作题记录,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

P3523 [POI2011]DYN-Dynamite

Description

Luogu传送门算法

Solution

经典树上 \(dp\)数组

首先二分 \(mid\) 表示最远的距离。函数

\(f_{x}\) 表示距 \(x\) 最远的未被覆盖的关键点到 \(x\) 的距离,\(g_x\) 表示 \(x\) 到该子树中的选定点的最小距离。优化

初值显然:\(f_x = -inf\)\(g_x = inf\)spa

转移方程:\(f_x = max \{ f_y + 1 \}\)\(g_x = max\{ g_y + 1\}\)code

可是并非全部的点都能被选,因此要分类讨论一下:游戏

  • \(f_x + g_x \leq mid\),能够直接覆盖,\(f_x = -inf\)
  • \(f_x = mid\),此时选 \(x\),那么 \(f_x = -inf\)\(g_x = 0\)\(ans++\)
  • \(g_x > mid\)\(d_x = 1\),这时就要扔给 \(fa_x\) 处理,因此 \(f_x = max\{ f_x, 0\}\)

P2324 [SCOI2005]骑士精神

Description

Luogu传送门ip

Solution

\(IDA*\) 板子题,乐观估价函数就是 \(5 \times 5\) 的目标矩阵和当前 dfs 到的矩阵中不一样的点的个数。get

爆搜便可。it

P3205 [HNOI2010]合唱队

Description

Luogu传送门

Solution

经典区间 \(dp\)

\(f_{i,j}\) 表示选了区间 \([i,j]\) 且最后一我的从左边进来的方案数,\(g_{i,j}\) 表示最后一我的从右边进来的方案数。

转移就很 easy 了:

\(f_{i,j} = f_{i + 1, j} \times (a_i < a_{i + 1}) + g_{i + 1, j} \times (a_i < a_{j})\)

\(g_{i, j} = g_{i, j - 1} \times (a_{j} > a_{j - 1}) + f_{i, j - 1} \times (a_j > a_i)\)

P2513 [HAOI2009]逆序对数列

Description

Luogu传送门

Solution

看到名字,原本觉得又是树状数组维护什么东西,结果不是……

看了一眼题解发现要 \(dp\) 一会儿,\(dp\)\(dp\) 吧。

咱们设 \(f_{i,j}\) 表示 \(i\) 的全排列中,逆序对数为 \(j\) 的个数。

咱们考虑把 \(i\) 插入到 \(i - 1\) 的全排列中,枚举此次插入增长了 \(k\) 个逆序对。

那么转移方程就是:

\[f_{i, j} = \sum\limits_{k = max\{0, j - i + 1\}}^j{f_{i - 1, k}} \]

朴素的转移是 \(O(n^2)\) 的,考虑优化。

优化也很简单,发现 \(k\) 是从 0 开始枚举的,作个前缀和便可。

P2592 [ZJOI2008]生日聚会

Description

Luogu传送门

Solution

模拟赛上考了原题,仍是比较 easy 的。

发现数据范围仍是很小的,考虑四维 \(dp\)

\(dp_{i, j, c1, c2}\) 表示安排了 \(i\) 名男生,\(j\) 名女生,且后缀男生数量减去女生数量最大是 \(c1\),最大后缀女生减男生数量是 \(c2\)

转移就比较显然了,用刷表法(边界好处理一点)。

在最右边安排一名男生:

\[dp_{i + 1, j, c1 + 1, max\{ 0, c2 - 1\}} += dp_{i, j, c1, c2} \]

安排女生同理。

P4295 [SCOI2003]严格N元树

Description

Luogu传送门

Solution

高精度板子

仍是 \(dp\),设 \(f_i\) 表示深度不超过 \(i\) 的严格 \(n\) 元树的个数。

转移的过程至关于再增长一个根,且新建的根节点须要 \(n\) 个子树。

那么转移方程就是:\(f_i = f_{i - 1}\, ^ n + 1\) (+1 就是只有本身)

简单吧,可是要用高精度(

P2607 [ZJOI2008]骑士

Description

Luogu传送门

Solution

基环树上 \(dp\) 板子。

(可是为何全机房除了我其余人都作过啊啊啊,果真仍是我太菜了 \(QwQ\)

这道题给出的骑士之间的厌恶关系会造成基环树(森林),那么咱们要在上面跑 \(dp\)

如下按一棵基环树来讨论。

咱们先找到,而后选择上面的一个点为根,跑树形 \(dp\),而后再换成与它相邻的一个点为根跑一遍树形 \(dp\),取个最大值就是答案了(树形 \(dp\) 最下面再说)。

咱们再来考虑基环树森林,实际上是同样的。

主函数里枚举一遍全部的点,若是还没遍历过,就重复一次上述操做。

那么树形 \(dp\) 怎么跑?相似于 没有上司的舞会。

咱们设 \(f_{x,0/1}\) 表示以 \(x\) 为根(\(x\) 选 或 不选)的子树中最大战斗力。

转移方程:

\[f_{x, 0} += max(f_{y, 0}, f_{y, 1}) \]

\[f_{x, 1} += f_{y, 0} \]

P4035 [JSOI2008]球形空间产生器

Description

Luogu传送门

Solution

高斯消元板子

不过仍是要稍稍推一下式子的。

关于 \(n\) 维空间里两个点之间的距离题目下方的说明/提示里有。

这道题给咱们的都是表面上的点,言外之意,到球心距离相等。

假设咱们要求的球心坐标:\((x_1, x_2, x_3……x_n)\)

那么有:\(\sum\limits_{i = 1}^{n}{\sum\limits_{j = 1}^n(a_{i,j} - x_j)^2 = C}\)

可是这是个二次方程,还有个常数怎么办啊?

上下一减就完了,减的过程就不写了(懒得打字了),建议本身手推一下。

下面是化简完的式子:

\[\sum\limits_{j = 1}^n2(a_{i,j} - a_{i + 1, j})x_j = \sum\limits_{j = 1}^n(a_{i, j}^2 - a_{i + 1, j}^2) \]

看着不清新?换元一下:

\[k_j = 2(a_{i, j} - a_{i + 1, j}) \]

\[y_j = \sum\limits_{j = 1}^n(a_{i, j}^2 - a_{i + 1, j}^2) \]

\[\sum\limits_{j = 1}^n(k_j \times x_j) = y_j \]

对这个式子建个增广矩阵,跑个高斯消元就完了。

P2146 [NOI2015] 软件包管理器

Description

Luogu传送门

Solution

树链剖分板子题,很少说了。

P2375 [NOI2014] 动物园

Description

Luogu传送门

Solution

\(kmp\) 好题。可是讲一次忘一次

大概就是不能暴力调 \(next\) 数组,会被卡。

因此咱们不用重置前一次跳到的坐标,每次日后跳一格,判断一下便可。

P4133 [BJOI2012]最多的方案

Description

Luogu传送门

Solution

记忆化搜索不解释。

记录一个斐波那契数列的前缀和,每次跟当前搜索到的要分解的数\(x\) 比一下。

若是 \(x > sum_{i - 1}\) ,当前位就必须选了,不然的话选或不选两种状况都搜一遍。

P1640 [SCOI2010]连续攻击游戏

Description

Luogu传送门

Solution

二分图匹配好题。

观察到每一个物品只能用一次,即每次只用使用一个属性值。

那么咱们把武器和属性值连边,从 1 开始枚举并跑匈牙利算法。

若是没法匹配直接break(题意要求),而后输出答案便可。

P1403 [AHOI2005]约数研究

Description

Luogu传送门

Solution

不能理解为何是橙题……我怕不是连橙题都不会了……

经过打表发现,一段数的约数个数是同样的,每次让 \(i\) 等于 \(\frac{i}{n/i} + 1\) 中间的数总体算便可。

\[\_EOF\_ \]