「模拟测试」20171019

T1 打牌

给出一些数字,求最多能组成多少个对子 $(x, x)$ 或顺子 $(x, x + 1, x + 2)$。

查看更多

分享到

「UVA 11404」Palindromic Subsequence-DP

给出一个字符串,输出其字典序最小的最长回文子序列。

查看更多

分享到

「UVA 11552」Fewest Flops-DP

给出一个字符串,把它分成 $k$ 块,块内可以任意排序,连续的相同字母算作一段,求最终字符串中的最小段数。

查看更多

分享到

「模拟测试」20171017

T1 购买板凳

有 $n$ 条信息,每条信息包含 $x$ 个人,这 $x$ 个人会在 $A$ 时间到达,$B$ 时间离开,每个人到达后会占用一个板凳,求至少要准备多少个板凳。

查看更多

分享到

「SuperOJ 1979」「模拟测试」拆墙-最小生成树+平面图转对偶图

地主的傻儿子豆豆家很大很大,由很多个区域组成。其中有不少封闭的区域,豆豆觉得很不爽于是决定拆墙,把家打通使得他可以访问到每一个区域(包括家外面无限大的区域)。我们用 $N$ 个端点和 $M$ 条边来描述豆豆的家。第 $i$ 个端点的坐标为($x_i, y_i$),第 $i$ 条边连接端点 $A_i$ 和 $B_i$,拆除所需要花费的力气为 $C_i$ 。保证所有边只在端点相交,也就是这是一个平面图,也没有重边和自环。

现在豆豆想知道他最少一共需要花费多少力气?

查看更多

分享到

「BZOJ 4105」平方运算-线段树

现有一个长度为 $n$ 的序列 ${x_1, x_2, \cdots, x_n}$,要求支持两种操作:

  1. 0 l r 表示将 $i \in [l, r], x_i \leftarrow x_i^2 \bmod p$
  2. 1 l r 询问 $\sum\limits_{i = l} ^ r x_i$

查看更多

分享到

「BZOJ 3578」GTY的人类基因组计划2-Hash

$n$ 个人来做实验,有 $m$ 个房间,一开始所有人都在 $1$ 号房间里,有两个操作:

  1. 让第 $i$ 个人去房间 $j$
  2. 让区间 $[l,r]$ 的房间做实验

实验会获得一些实验信息点数,点数为房间里的人数(不会重复增加点数),求每次操作获得的点数。

查看更多

分享到

「BZOJ 2064」分裂-状压 DP

给定一个初始集合和目标集合,有两种操作:

  1. 合并集合中的两个元素,新元素为两个元素之和
  2. 分裂集合中的一个元素,得到的两个新元素之和等于原先的元素

要求用最小步数使初始集合变为目标集合,求最小步数。

查看更多

分享到

「BZOJ 4154」Generating Synergy-k-d 树

给定一棵以 $1$ 为根的有根树,初始所有节点颜色为 $1$,每次将距离节点 $a$ 不超过 $l$ 的 $a$ 的子节点染成 $c$,或询问点 $a$ 的颜色。

查看更多

分享到

「BZOJ 3337」ORZJRY I-块状链表

题意很清晰,直接给链接。

链接

BZOJ 3337

查看更多

分享到

「BZOJ 4518」征途-dp + 斜率优化

Pine 开始了从 $ S $ 地到 $ T $ 地的征途。
从 $ S $ 地到 $ T $ 地的路可以划分成 $ n $ 段,相邻两段路的分界点设有休息站。
Pine 计划用 $ m $ 天到达 $ T $ 地。除第 $ m $ 天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。

设方差是 $ v $,可以证明,$ v \times m ^ 2 $ 是一个整数。为了避免精度误差,输出结果时输出 $ v \times m ^ 2 $。

查看更多

分享到

「CC FAVNUM」Favourite Numbers-AC 自动机 + 数位 dp

给出一些数字串作为模式串,求 $[l, r]$ 中第 $k$ 个包含至少一个模式串的串。

查看更多

分享到

「HDU 3709」Balanced Number-数位 dp

求 $[l, r]$ 中平衡数的个数,平衡数就是一某一位为支点,两侧的力矩相等。

查看更多

分享到

「BZOJ 4552」排序-平衡树 + fingerSearch/线段树分裂合并

给出一个 $n$ 的排列,进行 $m$ 次操作,每次操作是将一个区间升序或降序排序。
请你输出 $m$ 次操作后第 $p$ 个位置的值。

查看更多

分享到

「HDU 4773」Problem of Apollonius-圆的反演

给定相离的两个圆(圆心坐标以及半径)以及圆外的一个定点 $P$,求出过点 $P$ 的且与已知的两个圆外切的所有圆。

查看更多

分享到

「BZOJ 3453」XLkxc-拉格朗日插值


$$\sum_{i=0}^{n} \sum_{j=1}^{a+i \times d} \sum_{l=1}^{j}l^k$$

查看更多

分享到