爱悠闲 > 分类 >

BZOJ 第40页

BZOJ 3728 PA2014Final Zarowki 堆+贪心
题目大意:给定n个灯泡和n个房间,每个灯泡有一个功率,每个房间有一个照亮的最小功率,可以换k个灯泡,求照亮所有房间的最小功率 将灯泡的功率和房间的最小功率排序,从大到小扫描每个房间 对于一个房间,首先将能照亮这个房间的灯泡都加入堆 如果堆为空则花掉一次换灯泡的机会换一个功率为这个房间的最小功率的灯泡 否则取走功率最小的灯泡照亮这个房间,并将灯泡功率与房间最小功率的差值加入另一个堆 结束时如果还有换
BZOJ 2791 Poi2012 Rendezvous 倍增LCA
题目大意:给定一棵内向森林,多次给定两个点a和b,求点对(x,y)满足: 1.从a出发走x步和从b出发走y步会到达同一个点 2.在1的基础上如果有多解,那么要求max(x,y)最小 3.在1和2的基础上如果有多解,那么要求min(x,y)最小 4.如果在1、2、3的基础上仍有多解,那么要求x>=y 因此那个x>=y是用来省掉SPJ的,不是题目要求- - 容易发现: 如果a和b不在同一棵内向树上,显
BZOJ 2277 Poi2011 Strongbox 数论
题目大意:给定n和k个整数,求mod n加法下的群G的一个子群G',满足a[1]~a[k-1]都不在群中而a[k]在群中 首先易证G'一定是一个循环群 证明:显然若a在群中则a的逆元在群中 那么我们就有了减法运算 由群的封闭性可得若a和b都在群中则gcd(a,b)一定在群中 不妨设g为G'中所有元素的gcd 那么群G''={0,g,2g,...}一定是G'的一个子群 由于G'-G''中的所有元素均
BZOJ 3829 Poi2014 FarmCraft 树形DP+贪心
题目大意:给定一棵树,从1号节点出发对树进行欧拉遍历,每到达一个点这个点就开始装MC,每个点装MC的时间不同,最后回到1号节点装MC,求所有人都能联机的最少时间 令f[x]为对第x个节点进行欧拉遍历的时间,g[x]为对第x个节点进行欧拉遍历并完成所有节点的装机的最小时间 那么在每个节点以什么顺序遍历每棵子树呢? 我们发现装机多出来的时间 即g[x]-f[x]可以用来遍历其它子树 那么显然要从g[x
BZOJ 2803 Poi2012 Prefixuffix Hash
题目大意:给定一个字符串S,求一个最长的L(L*2<=n),使S长度为L的前缀和长度为L的后缀循环同构 一开始我的想法是枚举L,判断长度为L的前缀和长度为L的后缀的所有循环同构的哈希值之和是否相等 但是很快我发现这做法是扯淡- - 因为一个字符串所有循环同构的哈希值之和等于这个字符串所有字符ASCII码之和乘上(BASE^len+BASE^(len-1)+...+BASE^2+BASE+1) 然后
BZOJ 3522 Poi2014 Hotel DFS
题目大意:给定一棵树,求有多少无序三元组(x,y,z)满足x,y,z互不相等且Dis(x,y)=Dis(y,z)=Dis(x,z) 三个点在树上有两种情况 第一种是三点共链 第二种是存在且仅存在一个中心点满足三个点分别在这个点的三个不同的出边的方向 第一种情况显然无解 第二种情况一定满足三个点到中心点的距离相等 由于n<=5000因此直接枚举中心点然后枚举中心点的每一条出边DFS即可 时间复杂度O
BZOJ 2085 Poi2010 Hamsters Hash+倍增Floyd
题目大意:给定n个长度总和不超过10W的字符串,求一个最短的母串,使所有字符串的出现次数之和=m 这n个字符串保证不互相包含 TM能不能好好翻译了 令f[i][j]表示第i个字符串后面接上第j个字符串后会增加多少长度 由于j一定不是i的子串,因此这实际上就是在求i的最长的后缀,该后缀同时也是j的前缀 注意不能连出长度为0的边,因此当i=j时要保证这个长度<len[i] 怎么求呢?其实Hash一下,
BZOJ 1133 POI2009 Kon 动态规划
题目大意:给定n个站点,每个人都会在某个站点上车并在之后的某个站点下车,查票员可以在两个站点之间查票,问查票k次最多查到多少人 壮哉我大轻音部(误 令f[i][j]表示当前在第i个点和第i+1个点之间查票,已经查了j次的最大收益 枚举上一次查票的位置,统计比上一次能多查出来的人数即可 时间复杂度O(kn^2) 输出方案记录一下上一次查票的位置即可 由于没有SPJ所以要输出字典序最小的方案 注意有组
BZOJ 3887 Usaco2015 Jan Grass Cownoisseur Tarjan+拓扑排序
题目大意:给定一张图,从1开始随便走最后回到1,有一次机会可以反向沿着某条边走一次,求最多能经过多少个点 显然如果没有反向的机会的话答案就是1号节点所在强连通分量的大小 现在有了这个机会 那么将某条边反向后 缩点之后的图形成了一个包含1号节点所在强连通分量的环 这样才能使答案增加 将这个环从反向的边和1号节点所在强连通分量处断开 发现这个环被拆成了两条链 一条从1出发,一条指向1 因此缩点后利用拓
BZOJ 3357 Usaco2004 等差数列 动态规划
题目大意:给定一个长度为n的序列,求最大等差子序列 令f[i][j]表示当前等差数列最后一个数为a[i],倒数第二个数为j的最长长度 则有f[i][a[j]]=max{2,f[j][a[j]*2-a[i]]+1} 注意n=1时输出1 时间复杂度O(n^2logn) #include <map> #include <cstdio> #include <cstring> #include <iostr