「模拟测试」颜色-分块/莫队

给出一个序列,每个位置有同一个颜色,每个颜色有一个价值,要求支持单点修改,查询区间 $[l, r]$ 的权值和,相同颜色只算一次。

查看更多

分享到

「模拟测试」管道-倍增

给出一个无向图,对于每条边,求必须选择这条边的情况下,使得原图连通的最小代价。

查看更多

分享到

「模拟测试」20171030

T2 Game

甲乙两个人轮流那一些物品,甲先手,他可以拿走 $1$ 或 $2$ 个物品。对于后面,若前一个人拿走 $k$ 个物品,当前的人可以拿走 $k$ 或 $k + 1$ 个物品,甲乙的策略都是让自己尽量比别人拿的物品的价值高,求最优策略下,甲最多比乙多拿多少?

查看更多

分享到

「模拟测试」大逃杀

一棵树,经过一条边花费 $c_i$ 的时间,某些点上有障碍,经过额外花费 $t_i$ 时间,每个节点有 $w_i$ 的价值,求 $T$ 秒后获得的最大价值。

查看更多

分享到

「BZOJ 4001」概率论-生成函数

求随机生成的一棵有根二叉树的叶子节点数的期望。

查看更多

分享到

「模拟测试」20171024

T1 建设图

给出一个无向图,求最少添加多少条边使得,无论删掉哪条边任意两点都可以互相到达。

查看更多

分享到

「SuperOJ 2004」姓名匹配-后缀数组+线段树+链表+set

给出 $n$ 个字符串,再给出 $n$ 个字符串,求一一匹配情况下 LCP 的最大长度和。

查看更多

分享到

「UVA 10453」Make Palindrome-区间 DP

给定一个长度为 $n$ 的字符串,你需要在任意位置添加尽量少的字符,使新串是回文串。输出最少添加的字符个数以及新串。

查看更多

分享到

「模拟测试」20171023

T1 Fibonacci

询问一个数能否被分成两个 Fibonacci 数的乘积。

查看更多

分享到

「UVA 10163」Storage Keepers-DP

有 $n$ 个仓库,让 $m$ 个人来看管。一个仓库只能由一个人来看管,一个人可以看管多个仓库。
每个人有一个能力值 $p_i$,如果他看管 $k$ 个仓库,那么所看管的每个仓库的安全值为 $\lfloor \frac {p_i} {k}\rfloor$
如果某个仓库没有人看管,那么它的安全值为 $0$。所有仓库的安全值 $L$ 为所有仓库安全值的最小值
如果雇佣一个人的工资等于他的能力值 $p_i$。
从 $m$ 个人中选择一些人雇佣,问所有仓库的安全值最高是多少,在安全值最高的情况下,求雇佣的最少价钱。

查看更多

分享到

「SuperOJ 1998」「模拟测试」矩阵-DP

有一个 $n \times m$ 的矩阵,请你选出其中 $k$ 个子矩阵,使得这个 $k$ 个子矩阵分值之和最大。注意:选出的 $k$ 个子矩阵不能相互重叠。

查看更多

分享到

「模拟测试」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$ 。保证所有边只在端点相交,也就是这是一个平面图,也没有重边和自环。

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

查看更多

分享到