补档计划

补档计划

明日は明日の风が吹く,调整状态,进入新的征程,好好补一些东西…

查看更多

分享到

「模拟测试」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$$

查看更多

分享到

「BZOJ 4559」成绩比较-拉格朗日插值

$G$ 系共有 $n$ 位同学,$M$ 门必修课。这 $N$ 位同学的编号为 $0$ 到 $N - 1$ 的整数,其中 $B$ 神的编号为 $0$号。这 $M$ 门必修课编号为 $0$ 到 $M - 1$ 的整数。一位同学在必修课上可以获得的分数是 $1$ 到 $U_i$ 中的一个整数。如果在每门课上 $A$ 获得的成绩均小于等于 $B$ 获得的成绩,则称 $A$ 被 $B$ 碾压。在 $B$ 神的说法中,$G$ 系共有 $K$ 位同学被他碾压(不包括他自己),而其他 $N-K-1$ 位同学则没有被他碾压。$D$ 神查到了 $B$ 神每门必修课的排名。这里的排名是指:如果 $B$ 神某门课的排名为 $R$,则表示有且仅有 $R-1$ 位同学这门课的分数大于 $B$ 神的分数,有且仅有 $N-R$ 位同学这门课的分数小于等于 $B$ 神(不包括他自己)。我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足B神的说法,也能符合 $D$ 神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。你不需要像 $D$ 神那么厉害,你只需要计算出情况数模 $10 ^ 9 + 7$ 的余数就可以了。

查看更多

分享到