爱悠闲 > 分类 >

BZOJ 第52页

BZOJ 3998 TJOI2015 弦论 后缀自动机
题目大意:求严格/非严格K小子串 首先建立Sam 然后BFS一遍求出每个点代表状态的出现次数 此时如果是严格的那么每个点代表状态的出现次数都应该是1 然后DFS一遍求出每个节点的后继状态个数 然后就随便搞了啊= = 妈了个鸡卡常数。。。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #de
BZOJ 4010 HNOI2015 菜肴制作 拓扑排序+堆
题目大意:给定一张无向图,求一个拓扑序,使: 1的位置最靠前 在保证上面的条件下使2的位置最靠前 在保证上面的条件下使3的位置最靠前 …… 注意不是字典序最小!例如样例3 建立反图,对反图求字典序最大的拓扑序,然后反向输出即可。 我不知道为什么。真的不知道。 求个解答在线等。 #include <cstdio> #include <cstring> #include <iostream> #inc
BZOJ 4011 HNOI2015 落忆枫音 拓扑序DP
题目大意:给定一张有向无环图,现在要求加入一条边,求加入后以1为根的树形图个数 首先不考虑加入的这条边,那么这个图是一个DAG 由朱刘算法的推论可知,如果除根节点外每个点都选择一条入边,由于没有环,因此一定会形成一个树形图 因此答案就是 ∏ni=2degreei 其中 degreei 表示第 i 个点的入度 现在加入这条边之后,我们仍然可以套用这个公式,但是这样就会有一些不合法的方案被统计进来,我
BZOJ 1194 HNOI2006 潘多拉的盒子 BFS+Tarjan+拓扑序DP
题目大意:给定一些自动机,如果某个自动机 A 能产生的所有串都能在自动机 B 中产生,则称 B 是 A 的一个升级,求最长链 这题TM有毒 数据范围 50 ,暴力枚举每一对点之间的关系,然后Tarjan缩点求最长链就行了 现在对于一对自动机 A 和 B ,我想知道 A 能产生的所有串是否都能在 B 中产生,那么BFS就可以了 我们用一个二元组 (x,y) 表示走了某个串后 A 走到了节点 x ,
BZOJ 4032 HEOI2015 最短不公共子串 后缀自动机+序列自动机+BFS
题目大意:给定字符串A和B,求A最短的子串/子序列S满足S不是B的子串/子序列 这题真TM有毒*2 搞法类似http://www.aiuxian.com/article/p-2430293.html 然后子串是后缀自动机 子序列自然就是序列自动机了= = 每更新一个x节点时所有没有x的后继的节点都连向这个节点 每个节点的parent是这个字母上一次出现的位置 每个字母记录最后一次出现的位置 更新指
BZOJ 4029 HEOI2015 定价 数位贪心
题目大意:定义一个数的荒谬程度为去掉末尾所有 0 后的数字数量 ∗2 (若末尾为 5 则荒谬程度减掉 1 ),求 [l,r] 区间内荒谬程度最小的数字(若多个相同取最小) 从高位往低位贪心即可。 注意500的荒谬程度比100低 #include <assert.h> #include <cstdio> #include <cstring> #include <iostream> #include
BZOJ 4012 HNOI2015 开店 动态树分治+二分
题目大意:给定一棵树,每个点有一个颜色,多次询问颜色在 [l,r] 区间内的所有点与某个点之间的距离之和,强制在线 没记错的话这题我知道的有三种解法来着? (茴香豆的茴有四种写法泥萌知道嘛…? 1.线段树维护虚树 2.点分治+线段树 3.分块 第一种方法我不知道在线怎么搞= = (我并不知道怎么在虚树上进行点定位 第三种方法貌似内存过不去? 于是果断点分治+线段树 写完发现内存还是炸了= = O(
BZOJ 4008 HNOI2015 亚瑟王 期望DP
题目大意: n 个人, r 轮游戏,每次从左到右轮,第 i 个人有 pi 的概率被选中,选中的话本轮结束,产生 di 的贡献,否则接着轮 求期望贡献和 神思路…… 直接DP基本是死也搞不出来的 我们转化一下 我们把所有的机会一起轮 令 fi,j 表示第i个人得到j个机会的概率 然后就简单了嘛= = fi,j=fi−1,j∗(1−pi−1)j+fi−1,j+1∗(1−(1−pi−1)j+1) 然后答
BZOJ 4009 HNOI2015 接水果 树套树
题目大意:给定一棵树和 m 条路径,每条路径有一个权值,Q次询问,每次询问某条路经包含的所有路径中权值的第k小 原来精神污染那个题是这么做的啊QwQ 题解网上都有,我就直接贴代码了 没心情写题解了 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 40400 using n
BZOJ 4013 HNOI2015 实验比较 树形DP+组合数学
题目大意:给定一张图,每条边有’=’和’<’两个属性,每个点入度最多为1,求这张图可以压成多少个用’=’和’<’连接的序列 我只贴代码~~ 题解自己搜~~ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 110 #define MOD 1000000007 using n