爱悠闲 > 分类 >

BZOJ 第36页

BZOJ 3029 守卫者的挑战 期望DP
题目大意:给定n个事件,第i个事件发生的概率为pi,收益为ai,初始收益为k,求n个事件之后发生的事件数>=l且收益>=0的概率 令f[i][j][k]表示第i个事件进行后已经发生了j个事件且当前受益为k的概率 MB破输入法打两行字错了十多遍 第三维好大- - 不会爆? 实际上第三维大于n就没有意义了 因为收益大于n时一定不会扣到负数 因此将第三维大于n的状态全都存到n上即可 时间复杂度O(n^3
BZOJ 1778 Usaco2010 Hol Dotp 驱逐猪猡 期望DP+高斯消元
题目大意:给定一个无向图,炸弹从1号节点出发,每个时刻有P/Q的概率爆炸,如果某个时刻没有爆炸,就会等概率沿着随机一条出边走到下一个城市,求最终每个城市的爆炸概率 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 330 using nam
BZOJ 3771 Triple 母函数+FFT
题目大意:给定n个物品,可以用一个/两个/三个不同的物品凑出不同的价值,求每种价值有多少种拼凑方案(顺序不同算一种) 首先搞出这n个物品的母函数a 将a的每项的平方求和得到多项式b 将a的每项的立方求和得到多项式c 那么如果不考虑顺序和重复 那么方案数就是a+b+c 现在考虑顺序和重复后 三个物品的方案数为(a^3-3*a*b+2*c)/6 两个物品的方案数为(a^2-b)/2 一个物品的方案数为
BZOJ 2836 魔法树 树链剖分
题目大意:维护一棵有根树,每个节点初始权值为0,支持下列操作: 1.链上+ 2.子树求和 。。。。。链剖裸题- - 果然链剖这种东西想要1A实在是不咋现实- - #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using namespace std; str
BZOJ 1444 JSOI2009 有趣的游戏 AC自动机+矩阵乘法
题目大意:给定n个长度为l的模式串,现在要用前m个大写字母生成一个随机串,每个字符有自己的出现几率,第一次出现的字符串获胜,求最终每个字符串的获胜几率 建出AC自动机,搞出转移矩阵 如果某个节点是模式串那么这个节点只向自己连一条概率为1的出边 然后把转移矩阵自乘50遍即可 #include <cstdio> #include <cstring> #include <iostream> #inclu
BZOJ 2322 BeiJing2011 梦想封印 高斯消元
题目大意:给定一张带权无向图,每次删去一条边并询问从点1出发走一条路径可以走出多少种不同的边权异或和 删边不好做 首先倒着做 把删边改成加边 回忆2115那题的做法 我们可以把一条路径的异或和拆成一条简单路径和一些环的异或值 2115是求最大异或和  这个题是求异或和的个数 因此我们维护两个集合 环的异或和集合和路径的异或和集合 这里说的路径包括原地不动 即从1到1的路径 如果一个环的异或和能被其
BZOJ 2839 集合计数 容斥原理
题目大意:给定n个元素,求交集大小为k的集合的集合共有多少种 考虑容斥原理 计算交集大小至少为i的集合有多少种 首先需要选出i个元素 方案为C(n,i) 其它2^(n-i)个集合每个可选可不选 一共2^[2^(n-i)]种 故答案为Σ[k<=i<=n]C(n,i)C(i,k)*2^[2^(n-i)] #include <cstdio> #include <cstring> #include <io
BZOJ 1263 SCOI2006 整数划分 高精度
题目大意:给定一个数n,要求将n划分成一些正整数的和,使这些正整数的乘积最大 结论: 如果n是3的倍数 那么将n划分成n/3个3是最优的 如果n是3的倍数+1 那么将n划分成(n-4)/3个3和两个2是最优的 如果n是3的倍数+2 那么将n划分成(n-2)/3个3和1个2是最优的 证明是有的 考虑不是划分成整数,而是划分成任意实数 设我们将n划分成了x个正实数之和 易知当这x个数相等时答案是最优的
BZOJ 3193 JLOI2013 地形生成 组合数学
题目大意:给定一些山,每座山有一个高度和一个关键值,现在要将这些山排成一个序列,要求每座山之前高度高于它的山的数量不能超过它的关键值,求合法的标号序列数和高度序列数 = = 首先我们考虑第一问 我们发现高度较小的山对高度较大的山是没有影响的 那么我们可以将山按照高度从大到小排序 每座山插入时都有一些备选位置 将备选位置数相乘即是答案 现在考虑第二问 嘲讽:谁能告诉我O(n^3)到底怎么做= = 我
BZOJ 2125 最短路 静态仙人掌
题目大意:给定一棵仙人掌,多次询问两点之间的最短路 静态仙人掌= = 在VFK讲仙人掌之前就想做= = 结果一直拖= = 好不容易写完了= = 刚过样例 BZ就开始维护- - 维护到闭营= = 交上去还WA了= = 尼玛我这傻逼到底还是把倍增LCA写挂了= = 算了回归正题 首先我们的思路是这样的 考虑给定的是一棵树 多次询问树上两点间距离  那么我们一般的做法是预处理每个点到根的距离 用两点到根