洛谷P3914 - 染色计数

 OI / 洛谷
被浏览

CSP-S 前要多做树上问题 (主要是因为去年 NOIP D1T3、D2T1、D2T3 全是树上问题,然后爆炸了)

这题一看就是树形DP,状态也是一眼就能想到的。

令 $f_{i,j}$ 表示 $i$ 这个点染成 $j$ 的方案数,枚举 $son_i$ 的颜色来转移。

最后答案即为 $\sum_{i=1}^{m}f_{1,i}$。

CF498B Name That Tune

 OI / CodeForces
被浏览

作为一道英文题先解释一下题意。

用 $T$ 秒时间按顺序听 $N$ 首歌,第 $i$ 首歌播放时间为 $t_i$ 秒,且每播放一秒都会有 $p_i$ 的概率被识别出来,跳到下一首。某首歌播放时间过完默认被识别,也跳到下一首。若时间有剩余而歌已全部听完则直接结束。求识别出歌数量的期望。

看见题目就想到期望DP。

第一眼想到的方程是设 $f_{i,j}$ 表示第 $i$ 秒识别到第 $j$ 首歌的期望,不难想出一个 $O(n^3)$ 的算法。

枚举一个 $k$ 表示第 $j$ 首歌已经放了几秒,注意一下边界即可。

CF643D - Bearish Fanpages

 OI / CodeForces
被浏览

作为一道英文题,我们先解释一下题意。

题面有点长就不解释了,大家自己翻译吧。

首先有一个 Simple 的想法,直接维护啊,变的节点又不多,修改不是 $O(1)$ 的吗?

然后发现错了。

洛谷P3613 - 睡觉困难综合征

 OI / 洛谷
被浏览

首先我们要知道这道题的原型是「NOI2014」起床困难综合症。

总是有出题人喜欢把序列上用线段树解决的题目出到树上,让选手强行写个树链剖分或树分治或某种动态树数据结构。

序列问题转化为树上问题,很容易想到树链剖分,直接上板子。

洛谷P4884 - 多少个1?

 OI / 洛谷
被浏览

我们通过观察可以发现 $11\cdots1$ 可以变化为 $\frac{10^{n}-1}{9}$,于是根据取模的性质,我们可以把原式两边同乘九再加一,原式变为 $10^{n} \equiv k \cdot 9 + 1 \pmod m$,发现这是个 BSGS 的标准式子,由于 $m$ 保证为质数,所以也不必用拓展 BSGS。

CF1037D - Valid BFS?

 OI / CodeForces
被浏览

作为一道英文题,我们先解释一下题意:

给你一棵树和它的一个 BFS 序,让你判断这个 BFS 序是否是一个从节点 1 开始的合法 BFS 序。

接下来我们进入正题。

第一眼看到这题时,大部分人都会想到,既然是树,那么它一定是一层一层地向下 BFS。

也就是说,BFS 序中越后出现的节点,它树上的深度肯定是大于它前面的节点的。

于是照这个思想打完后,发现 Wrong Answer 了。

洛谷P2094 - 运输

 OI / 洛谷
被浏览

这道题第一眼像是合并果子,我们考虑贪心。

我们先选择一种贪心策略:每次选当前最大的两个数合并,直到只剩最后一件物品。

接下来我们证明一下为什么这样是对的:

我们先想一想合并果子,那道题的贪心策略与这道题相反,每次选最小的两个数合并。考虑它为什么是对的——我们发现越先选的数对结果的贡献越大,为了使结果尽可能小,肯定是越小的先选越好。

洛谷P2988 - Test Taking

 OI / 洛谷
被浏览

作为一道英文题,我们先解释一下题意:

给你一个长度为 $n$ 的 01 串,其中可能至少有 $t_{i}$ 个 1,问最后你给出一个 01 串可能和其匹配的最大长度。

接下来我们进入正题。

第一眼看见觉得是水题,对于每个 $t_{i}$ 枚举应该全 0 还是全 1,但是这显然可以找出反例来。

洛谷P1351 - 联合权值

 OI / 洛谷
被浏览

由题意得一个点对的联合权值是它们的点权相乘,而 2 个点形成点对的条件是距离为 2。

于是我们可以通过枚举这 2 个节点的公共点来算出以这个点为中心的权值和。

但是先枚举中心点再枚举其相邻的节点时间复杂度达到了 $O(n^3)$,我们不能承受。

经过观察发现,对于特定的点,它都要乘上除自己以外的所有点权,再相加。然后我们就可以先处理出点权和,统计答案的时候把自己减去即可。

洛谷P1432 - 倒水问题

 OI / 洛谷
被浏览

很容易看出这是宽度优先搜索,因为要求步数最少,且每个操作代价相同。

我们可以按操作类别分 6 种情况扩展,如果搜到最终状态就跳出 BFS(搜索顺序可以随意,因为 spj 已经配置好了,不像数据修改前要有特定的顺序)。

记得标记已经出现过的情况,不然会 TLE/MLE;