牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共8篇）

[NOIP2013]华容道题解

[NOIP2013]华容道首先是一种比较显然的做法。整个棋盘，除了起点，终点和空格，其他的方块是等价的。对于终点，它始终不会变化，如果搜到终点结束搜索即可，所以我们不需要考虑终点。所以需要考虑的是空格的位置和起点方块的位置。定义$f(i1,j1,i2,j2)$为空格所在坐标$...

图论搜索

2019-07-17

0 457

模拟14 题解

A. 旋转子段对于位置i上的数$a_i$，易知有且仅有一个旋转点使它旋转到$a_i$，这个旋转点是$\frac{i+a_i}{2}$ 因为旋转点分落在点上的旋转点和两点之间的旋转点，除2不易处理。不妨将位置i上的数存放在$i+a_i$处。设1~i的原本固定点为$pre_i$个，后缀同理...

模拟退火搜索图论树状数组

2019-08-08

0 474

模拟53 题解

A. u 一眼差分，在斜线上加一减一。然后发现这样的复杂度是$O(nq)$的，似乎不是很好过。然后发现打差分标记的形式也是连续的，所以差分两次就完了。 B. v 最优决策问题，一般倒着转移，$O(n*2^n)$的dp是显然的。考试时一直在想能否改成三进制状压，只压...

差分期望搜索状压 dp

2019-09-28

0 411

模拟54 题解

A. x 不妨考虑每一个质因子。那么拥有这个质因子的所有数都应当被分入一个集合中。而不拥有这个质因子的数可以有两种选择。将每个质因子的情况综合起来，用并查集维护一下联通块数量，答案就是$2^{cnt}-2$ B. y 暴力dp的设计是简单的，显然可以使用...

并查集搜索 dp 模拟

2019-09-29

0 804

模拟70 题解

A. 木板相似三角形，简单推出结论。发现要求的是$\sum \limits_{i=1}^{n-1}[n|i*i]$。那么只要把$n$质因数分解，设为$\prod_{j}^{} p_j^{c_j}$，那么设$k$为最小的合法的$i$，有$k=\prod_{j}^{} p_j^{\l...

数学 dp 构造题搜索

2019-10-13

0 301

模拟71 题解

A. 毛一琛暴搜复杂度$O(3^n)$，所以显然的优化是$meet\ in\ the\ middle$ ，可以优化为$O(\sum \limits_{i=1}^{n} \binom{n}{i}2^{\frac{i}{2}})$。只要将每个状态都分成两半，分别求出可能的方案，再枚举左侧一种...

搜索 dp 拓扑排序二分答案

2019-10-13

0 378

省选模拟12 题解

A. Colorado Potato Beetle 暴力做法是直接bfs。优化的方法是离散化。将特殊的点的横纵坐标抽出来，然后用这些横纵坐标为1e12*1e12分成一个个块，容易发现每个块内的状态是一致的。然后用与暴力类似的方法即可，注意最后统计的是每个块的实际大小。 B. D...

后缀自动机 dp 状压搜索树链剖分线段树

2020-02-01

0 359

省选模拟48 题解

A. 事情的相似度问题是区间内最大的点对 $LCS$。容易发现 $LCS$ 其实就是两个前缀的终止节点的 $lca$ 的 $len$。考虑对每个 SAM 上节点搞一个 set 维护 endpos 集合。每次的操作就是合并两个集合，然后节点 $x$ 上 endpos 集合中两两可以形成...

搜索扫描线后缀自动机 lct 线段树启发式

2020-03-17

0 383