SOJ 4484 静态规划(dp)

题意: $N\le 10^5个沙堆,|A_i|\le10^9,可以任意加减每个沙堆的高度$$现要使得修改后的沙堆高度A_i’\le A_{i+1}’,i\in [1, N)$$求最小修改的高度和$     Read more
TaoSama's avatar
TaoSama Apr 11, 2016

HDU 4647 Another Graph Game(贪心、边权映射到点权)

题意: $N,M\le 10^5,N个点M条边,点权W_i、边权C_i \le 10^9 $$2个人玩游戏轮流选点得到权值,选过的不能再选$$规定如果一条边的2个端点都被同一个人选到,那么它获得边权$$假设2个人采取最优策略,输出先手得分-后手得分$     Read more
TaoSama's avatar
TaoSama Apr 11, 2016

SOJ 4482 忽悠大神(MST、点权映射到边权)

题意: $N,M\le 10^5,N个点M条边无向图,点权W_i,边权C_i\le 1000$$现要保证图联通的情况下删除最多的边$$在此基础上,使得从某一起点出发,经过所有的点回到原点的权和最小$$输出这个权和$     Read more
TaoSama's avatar
TaoSama Apr 11, 2016

SOJ 4481 学院杯辩论赛(概率dp)

题意: $N\le 7,给定2^N个队伍进行N轮比赛$$每轮比赛将所遇剩余队伍编号排序,第一小的队伍和第二小的比,第三小的和第四小的比,以此类推$$N轮比赛后剩余一支队伍,问哪只队伍获胜概率最大,输出编号$     Read more
TaoSama's avatar
TaoSama Apr 11, 2016

SOJ 4479 Easy Problem III(区间贪心)

题意: $给定一条无限长的直线,给定N\le 10^5条线段[s, t]覆盖这条直线$$问覆盖的长度(重复覆盖只算一次)$     Read more
TaoSama's avatar
TaoSama Apr 11, 2016

SOJ 4478 Easy Problem II(栈)

题意: $N\le 10^5,1-N的数按顺序入栈,现给定出栈序列,问是否合法$     Read more
TaoSama's avatar
TaoSama Apr 11, 2016

ZOJ 3933 Team Formation(KM)

题意: $N\le 500个人,分为X组和Y组,每个人可能是男或者女$$X和Y要匹配,现要每个人都有厌恶的list,不和list上的人匹配$$求最大匹配数,以及满足条件下的女生总和最多的方案,输出任意方案$     Read more
TaoSama's avatar
TaoSama Apr 10, 2016

ZOJ 3932 Handshakes(逆向思维)

题意: $有一间教室,N\le 10^5依次来到这间教室,每个人来的时候要跟里面的所有人握手$$现在给定每个人进来那一次握了多少次手$$求每个人最多握多少次手,输出那个最大值$     Read more
TaoSama's avatar
TaoSama Apr 10, 2016

ZOJ 3930 Dice Notation(模拟)

题意: $给定规则让你展开式子,就读3个小圆点就可以了$$1.ndX\Rightarrow(\underbrace{[dX] + \cdots + [dX])}_n,dX\Rightarrow [dX],+号左右各1个空格$$2.给+-*/的左右各添加1个空格$$3.最后添加,$”$ = [Result]$”     Read more
TaoSama's avatar
TaoSama Apr 10, 2016

ZOJ 3929 Deque and Balls(数学、BIT)

题意: $N\le 10^5的序列,A_i\le N,将这个序列按顺序装入一个deque$$每次装在deque的首尾概率均等,问所有序列相邻逆序个数的期望$$相邻逆序个数:=\sum_{i=1}^{N-1} A_i > A_{i+1}$     Read more
TaoSama's avatar
TaoSama Apr 10, 2016