爱悠闲 > 分类 >

BZOJ 第39页

BZOJ 3895 取石子 博弈论+记忆化搜索
题目大意:给定n堆石子,两人轮流操作,每个人可以合并两堆石子或拿走一个石子,不能操作者输,问是否先手必胜 直接想很难搞,我们不妨来考虑一个特殊情况 假设每堆石子的数量都>1 那么我们定义操作数b为当前石子总数+当前堆数-1 若b为奇数,则先手必胜,否则后手必胜 证明: 若当前只有一堆,则正确性显然 否则: 若b为奇数,那么先手只需进行一次合成操作,此时操作数会-1,且仍不存在大小为1的堆 因此只需
BZOJ 2055 80人环游世界 有上下界的费用流
题目大意:给定n个点,每个点有固定的经过次数,m个人从任意节点出发任意节点结束,只能向右走,要求总边权和最小 有源汇、有上下界的费用流 其实上下界费用流有两种写法- - 一种是按照上下界网络流那么转化- - 一种是把必经边的费用减掉一个INF 跑完再加回去 我比较倾向于第一种写法- - 第二种写法在INF的取值上有点麻烦- - #include <cstdio> #include <cstring
BZOJ 3562 SHOI2014 神奇化合物 暴力
题目大意:维护一张弦图,支持加边、删边和询问图中有多少个联通块 暴力题233 直接做O(qn+qm)会挂 因此我们预先将m条边中自始至终不会被删除的边用并查集缩点 这样图中的边就只有O(q)条 暴力即可 时间复杂度O(nq+q^2) 很疑惑为什么要给一张弦图- - 去找了下没看到类似于动态弦图的东西- - #include <map> #include <vector> #include <cst
BZOJ 3878 Ahoi2014 奇怪的计算器 线段树
题目大意:给定n个操作,每个操作有四种形式,操作之后若<L就变成L,>R就变成R,现在给定q个输入,求他们的输出 n,q<=10W 将这q个数建立线段树,四个操作都可以在线段树上完成 但是溢出怎么办呢? 容易发现若x<=y,那么操作过后x一定<=y 因为四个操作都是线性的,溢出也不会反转两个数的大小关系 那么我们可以预先将q个数排序 那么溢出的数一定是连续的两段 区间修改就行了 至于怎么找两端溢出
BZOJ 2095 Poi2010 Bridges 二分答案+网络流
题目大意:给定一张图,每条边的两个方向有两个不同的权值,现在要求从1号节点出发遍历每条边一次且仅一次,最后回到1号节点,求最大边权的最小值 谁TM翻译的这道题给我滚出来看我不打死你 二分最大边的权值,然后就是经典的判断混合图欧拉回路存在性的问题了 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm
BZOJ 1199 HNOI2005 汤姆的游戏 计算几何+暴力
题目大意:给定n个图形,每个图形可以是矩形或圆,m次询问某个点在多少个图形内部 将点按横坐标排序 对于每个图形,二分找到x值满足要求的区间,对于区间内每个点暴力 时间复杂度O(n^2) 数据范围25W 果然像hwd说的一样计算几何题数据范围出的这么大就是作死么= = #include <cmath> #include <cstdio> #include <cstring> #include <io
BZOJ 1531 POI2005 Bank notes 多重背包
题目大意:多重背包 一大早就水了个题233 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 20200 using namespace std; int n,k,b[220],c[220]; int f[M]; int main() { int i,j,k; cin>
BZOJ 3610 Heoi2014 林中路径 矩阵乘法
题目大意:给定一张有向图,多次询问从S到T经过不超过K条边的所有路径的长度的平方和 首先这题一点也不麻烦 现有一带权整数集合S 我们令一个矩阵F_S表示从第i个点到第j个点,经过k条边(k∈S)的所有路径长度的平方和 令矩阵G_S表示从第i个点到第j个点,经过k条边(k∈S)的所有路径长度之和 令矩阵H_S表示从第i个点到第j个点,经过k条边(k∈S)的路径条数 定义T_S为(F_S,G_S,H_
BZOJ 2333 SCOI2011 棘手的操作 可并堆套可并堆
题目大意:给定n个节点,每个节点有一个初始权值,维护以下操作: 1.合并两个联通块 2.某个点权值+x 3.某个点所在联通块权值+x 4.所有点权值+x 5.询问某个点的权值 6.询问某个点所在联通块的最大权值 7.询问所有点之间的最大权值 2333333333333333333333333333333333333333333333333333333333333 23333333333333333
BZOJ 2084 Poi2010 Antisymmetry Manacher算法
题目大意:给定一个长度为n的01串,问有多少个子串满足翻转并取反后和原来一样 定义0=1,0≠0,1≠1,跑Manacher即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 500500 using namespace std; int n; char s[M]; l