爱悠闲 > 分类 >

BZOJ 第60页

BZOJ 4245 ONTAK2015 OR-XOR
题目大意:给定一个长度为 n 的序列,要求分成 m 段,使得每段异或和的或值最小 求出前缀异或和后从大到小按位确定,如果某一位上有至少 m 个数是0且第 n 个数是0,那么这一位就可以是0,同时将所有是1的数字标记为不可选 时间复杂度O (nlogai) #include <cstdio> #include <cstring> #include <iostream> #include <algor
BZOJ 4236~4247 题解
BZOJ 4236 JOIOJI f[i][0..2] 表示前i个字符中 ′J′/′O′/′I′ 的个数 将二元组 <f[i][0]−f[i][1],f[i][1]−f[i][2]> 扔进map,记录一下最早出现的时间 对于每个位置去map里面查一下即可 时间复杂度 O(nlogn) #include <map> #include <cstdio> #include <cstring> #incl
BZOJ 2725 Violet 6 故乡的梦 堆优化Dijkstra+线段树
题目大意:给定一张带权无向图和起点 S 、终点 T ,每次询问如果某条边被删掉那么从 S 到 T 的最短路是多少 数据范围 2∗105 注意样例错了 第二个输出应该是 6 不是 5 首先搞出从 S 到 T 的任意一条最短路 然后对于一条边 (x,y) ,如果不在最短路径上,预处理出 S 到 x 的最短路以及何时离开选定的最短路径 S′ ,以及 y 到 T 的最短路以及何时进入选定的最短路径 T′
BZOJ 2654 tree 二分答案+Kruskal
题目大意:给定一张带权无向图,每条边有一个颜色(黑色/白色),求一棵生成树满足有 need 条白色边且权值和最小 二分一个 x ,然后将所有白边权值加上 x ,跑两遍Kruskal,第一遍白边排在前面,第二遍黑边排在前面,这样可以求出当前白边数量的最大最小值 如果 need 在最大最小值之间那么直接输出结果,否则如果小于最小值就增大 x ,大于最大值就减小 x 然而我并不会证明正确性。。。 #in
BZOJ 3107 CQOI2013 二进制a+b 构造
题目大意:给定 n 位二进制数 a,b,c ,要求重组三个数的各个位,使得 a′+b′=c′ 且最小化 c′ 一个构造题咋这么多人写DP…… 不考虑位数限制,显然答案只与三个数中 1 的个数有关 令 x=cnta,y=cntb,z=cntc ,其中 cntx 代表 x 中 1 的个数 不妨令 x≥y 以下用 x=10,y=5 来举例 若 z=1 ,构造方式如下: 000001111111111 0
BZOJ 2302 HAOI2011 Problem c 动态规划
题目大意:给定 n 个人和 n 个位置,要求生成一个序列 ai ,然后第 1...n 个人依次走到第 a1...n 个位置,如果那个位置已经有人了就走到下一个位置,直到找到一个空位,坐下。如果找完第 n 个座位还是没有找到就称这个序列不合法 现在已经确定了一些 ai ,求合法序列的数量 一个序列合法等价于编号 ≤i 的人至少有 i 个 然后就可以DP辣。。。 令 fi,j 表示编号 ≤i 的人有
BZOJ 2669 cqoi2012 局部极小值 状压DP+容斥原理
题目大意:给定一个 n∗m 的矩阵,标记出其中的局部极小值,要求填入 1...n∗m ,求方案数 《多年的心头大恨终于切掉了系列》 考虑将数字从小到大一个一个填进去 由于局部极小值最多 8 个,我们可以状压DP 令 fi,j 表示已经填完了前 i 个数,局部极小值的填充状态为 j 的方案数 预处理出 cntj 表示填充状态为 j 时共有多少位置是可以填充的(包括已填充的局部极小值位置) 那么有DP
BZOJ 2503 相框 并查集
题目大意:给定一张无向图,每次可以进行以下两种操作: 1.将一个点分裂成一些点,原先这个点连接的每条边任选一个新点进行连接 2.将两个度数为1的点合并为1个点 求将这个图变成一个环的最小操作次数 首先我们考虑拆 由于终态每个点度数最多为2,因此我们将每个度数大于2的点都拆成一些度数为2的点,如果有零头,留下一个度数为1的点 由欧拉通路的相关结论可知,按照这种拆法,一个有 k(k>=2) 个奇度数点
BZOJ 2908 又是nand Link-Cut-Tree
题目大意:给定一棵树,每个点有一个权值,多次修改某个点的权值或询问从某个点 x 到另一个点 y 的路径上的 0 nand ax nand...nand ay nand操作不支持交换律和结合律,不过由于每一位独立,我们可以记录 ai,j 表示第 i 位初始为 j 的时候一路nand过来的结果 然后用LCT维护一下即可 时间复杂度 O(nlog2n) #include <cstdio> #includ