爱悠闲 > 分类 >

BZOJ 第38页

BZOJ 3884 上帝与集合的正确用法 欧拉定理
题目大意:求2^(2^(2^(2^(2^...)))) mod p的值 SB出题人被各种乱艹系列…… 其实是某天脑洞比较大突然想算算这东西= = 然后就发现了这个好玩的性质= = 其实+∞个2看着吓人其实没啥可怕的= = #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1
BZOJ 1190 HNOI2007 梦幻岛宝珠 动态规划
题目大意:01背包,其中weight<=2^30,但是每个weight都能写成a*2^b的形式,其中a<=10,b<=30 直接背包肯定TLE+MLE 考虑到每个weight都能写成a*2^b的形式,显然我们要按照b分层来进行背包 令f[i][j]表示有j*2^i+(w&(1<<i)-1)的空间时的最大价值 首先每层内部先做一个01背包 然后层与层之间再转移 从大到小枚举j 转移方程为f[i][j
BZOJ 2500 幸福的道路 树形DP+单调队列
题目大意:给定一棵树,令a[i]为从第i个节点出发的最长链,求a[i]中最长的区间,满足区间内最大值与最小值之差不超过m 读错题害死人,脑残害死人 求a[i]显然是树形DP 考虑从一个点出发的链可以从子节点走,也可以从父节点走 因此我们DP两次,第一次求出从子节点走的最长链,第二次求出从父节点走的最长链,两次取max就是答案 但是直接DP会有问题,因为从父节点走的最长链可能是从自己的子树出发的,这
BZOJ 3454 家族 并查集
题目大意:给定一张无向图,每个点有边权,给每个联通块大小一个喜爱度,求一个最小的区间,使保留这个区间内的所有边权的边时喜爱度之和最大 n<=1000,m<=5000 脑残没法治系列…… 如果暴力枚举区间并每次计算喜爱度,时间复杂度为O(nm^2),超时 固定一个左端点,将右端点右移,每次用并查集加边并维护喜爱度之和,时间复杂度O(m^2) 然后这题就做完了= = #include <cstdio>
BZOJ 3875 Ahoi2014 骑士游戏 SPFA
题目大意:给定n个怪物,每个怪物可以用魔法直接干掉,或者用物理攻击使其分裂为一些其他怪物,求杀掉1号怪物的最小花销 令f[i]为杀死i号怪物的最小花销,则f[i]=min(k[i],s[i]+Σf[j]) 其中j为i用物理攻击后可以分裂为的怪物 但是直接DP有后效性,因此我们用SPFA来跑这个DP即可 注意如果每次更新一个点之后都重新计算花销会T掉 改成减掉花销的差值就好了 具体写法去看代码吧-
BZOJ 3894 文理分科 最小割
题目大意:给定一个m*n的矩阵,每个格子的人可以学文或者学理,学文和学理各有一个满意度,如果以某人为中心的十字内所有人都学文或者学理还会得到一个额外满意度,求最大满意度之和 令S集为学文,T集为学理 每个人学文或者学理的满意度很好连边 如果某个集合内的人都学理会获得一个满意度,那么就新加一个点,将集合内的所有人向这个点连流量为正无穷的边,再从这个点向T连一条流量为满意度的边,表示集合内任意一个人学
BZOJ 3892 [Usaco2014 Dec]Marathon 动态规划
题目大意:给定n个点,定义从一个点到另一个点的距离为曼哈顿距离,要求从点1依次走到点n,中途可以跳过k个点不走,求最小距离和 令f[i][j]表示从第一个点走到第i个点中途跳过j次的最小距离和 则有f[i][j]=min{f[i-k-1][j-k]+dis[i-k-1][i]} 时间复杂度O(n^3) #include <cstdio> #include <cstring> #include <i
BZOJ 3891 [Usaco2014 Dec]Piggy Back BFS
题目大意:给定一张无向图,第一个人从点1出发每走一条边消耗A,第二个人从点2出发每走一条边消耗B,两个人相遇后一起走每走一条边消耗C,两个人到达点n的最小花销 分别从点1、点2、点n出发BFS一遍,预处理出每个点到点1、点2、点n的最短路 然后枚举两人相遇的点,计算消耗之和即可 #include <cstdio> #include <cstring> #include <iostream> #in
BZOJ 3893 [Usaco2014 Dec]Cow Jog
题目大意:给定一些牛,每头牛有一个初始位置和速度,如果某头牛能追上后面的那头速度就会和后面那头一样,求T分钟后会形成多少小团体 《论排序算法的低效性和如何避免使用排序算法以及认真读题的重要性》 一头牛的速度不会被后面的牛所影响 因此我们从后往前扫,如果当前的牛追不上后面那个小团体中最慢的那头牛,这头牛就成为新的小团体 时间复杂度O(n) 注意数据有点问题,虽然说初始位置和速度都小于等于100W但是
BZOJ 2962 序列操作 线段树
题目大意:给定一个序列,给定一个长度为n的序列,维护三种操作: 区间加 区间变为相反数 求某个区间内任取c个不同的数乘积的所有方案之和对P的模 比如说a b c三个数中取两个 就是ab+ac+bc 这题显然是用线段树来维护下- - 我们用一个0~20的数组a来记录某个区间的信息,其中a[i]表示区间内取i个数的乘积之和 区间合并就是a[i]=Σb[j]*c[i-j] 这个很好理解 区间变为相反数就