Welcome to My Blog!

CF555E Case of Computer Network

idea

边双缩点，LCA，树上差分。

解

步骤很多但代码很短的一道题。

首先，可以发现边双连通分量里面一定存在一种定向方式使得所有点可以互相到达。

P4819 [中山市选]杀人游戏

idea

缩点，逻辑推理。

解决

首先，一个强连通分量里面问一个就知道所有人身份，故可缩点。

P3244 [HNOI2015]落忆枫音

idea

$dp$ ，数学

solution

设 $ind[i]$ 表示 $i$ 节点的入度。如果图是一个 $DAG$ ，答案为 $\prod_{i=2}^n ind[i]$ 。

CF1681F Unique Occurrences

idea

栈，深搜，dp

解决

首先容易想到转化为求每条边的贡献。

一条颜色为 $c$ 的边的贡献就是，从它左端点开始的不经过颜色为 $c$ 的边的连通块的节点数乘上右端点…的节点数。

我们在学习选择排序的时候，每次选择最小的一个数，将其放到最前面，就可以在 $O(n^2)$ 内完成排序。

我们不满足于这样的复杂度，我们想要更快地找到最小的数。

P4514 上帝造题的七分钟

idea:

二维树状数组，数学

解决：

如果是单点查询或者是单点询问那就是二维树状数组的裸题。

P3332 [ZJOI2013]K大数查询

idea:

参考 $zhoukangyang$ 题解。

树状数组套动态加点权值线段树。

CF527D Clique Problem

idea:

思维

解决方案：

参考第一篇题解。

P6075 [JSOI2015]子集选取

idea:

数学

解决方案：

这道题是真的不简单，不知道为什么只是一个黄题。

P1447 [NOI2010] 能量采集

idea:

数论