爱悠闲 > 分类 >

BZOJ 第14页

BZOJ 1951 SDOI2010 古代猪文 数论 Lucas定理
题目大意:给定N,G,求 首先由欧拉定理易知当A与p互质时A^B %p=A^(B%φ(p) ) %p 这里p是一个质数 于是φ(p)=p-1=999911658 然后由于这个数不是质数 难以处理 我们将它分解质因数 然后对于每个质因数的解用中国剩余定理合并即可 然后就是999911658有一个很好的性质 999911658=2*3*4679*35617 每个质因数的次数都是1次 于是我们可以套用卢
BZOJ 2730 HNOI2012 矿场搭建 Tarjan
题目大意:给定一个无向图,要求将一些点设为出口 要求图中删掉任意一个点后剩余的任意一个点都与至少一个出口相连 求最少建多少个出口以及建最少出口的方案数 首先看到割点就是Tarjan搞 但是怎么搞 首先假设我们把所有的点双都缩点 那么我们一定可以得到一棵树 然后我们就会发现 叶子节点(只含有一个割点的点双)必须建 因为叶子节点如果不建 一旦割点被爆就死翘了 非叶节点(含有两个或两个以上的割点的点双)
BZOJ 1191 HNOI2006 超级英雄Hero 二分图最大匹配
题目大意:给定n个锦囊和m个问题,每个问题可以使用给定的两个锦囊之一,必须连续答题,求最多答上多少题 二分图最大匹配,每出现一个问题就向给定的两个锦囊连边,然后匈牙利算法寻找增广路,如果找不到就break 我这SB居然一开始在两个锦囊之间练了条边,然后二分答案……伤不起啊…… #include<cstdio> #include<cstring> #include<iostream> #includ
BZOJ 3714 PA2014 Kuglarz Kruskal
题目大意:有n个杯子,一些下面有小球,你可以花c[i][j]的价钱询问[i,j]区间内小球数的奇偶,求知道所有小球的最小花销 STO zrt大神…… http://www.cnblogs.com/zrts/p/bzoj3714.html 其实这道题应该写prim……不过我写了Kruskal,交上去还在想会不会TLE 还好10S过了 #include<cstdio> #include<cstring
BZOJ 1296 SCOI2009 粉刷匠 动态规划
题目大意:给定n*m的木板,每个点需要刷成1和0两种颜色之一,每次只能刷一行中连续的一段,一个点只能刷一次,求T刷子最多能刷对多少个点 首先对每行拆开处理 令f[i][j]为用i刷子刷前j个格子最多刷对多少个点 动规处理出这一行刷i刷子最多能刷对多少个点 然后分组背包即可 #include<cstdio> #include<cstring> #include<iostream> #include<
BZOJ 1458 士兵占领 Dinic最大流
题目大意:给定一个m*n的棋盘,其中k个点有障碍,要求放置最少的士兵,使第i行有至少L[i]个,第j列有至少C[j]个 首先这种问题很明显的网络流 但是正图肯定是跑不了 限制条件是至少而且要求放置的也是最少 很难解决 反向考虑 将棋盘上先放满士兵 此时若不能满足条件则无解 然后求最多能撤掉多少个士兵 其中第i行最多撤去templ[i]-l[i]个士兵 templ[i]表示第i行当前放置的士兵个数
BZOJ 1455 罗马游戏 左偏树
题目大意:给定n个点,每个点有一个权值,提供两种操作: 1.将两个点所在集合合并 2.将一个点所在集合的最小的点删除并输出权值 很裸的可并堆 n<=100W 启发式合并不用想了 左偏树就是快啊~ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 1001001 using name
BZOJ 3091 城市旅行 Link-Cut-Tree
警告:此题不可以使用cout进行输出,只能用printf,否则RE!亲测!! 题目大意:给定一棵树,每个点有一个点权,提供四种操作: 1.删除两点之间的连边 不存在边则无视 2.在两点之前连接一条边 两点已经联通则无视 3.在两点之间的路径上所有点的点权加上一个数 两点不连通则无视 4.询问两点之间路径上任选两点路径上的点权和的期望值 前三个操作都很基础 但是第四个东西……这啥玩应这是…… 首先这
BZOJ 3555 Ctsc2014 企鹅QQ Hash
题目大意:给定n个不相同的字符串,问有多少对字符串只差一个字母 枚举每个只差一个字母的位置,取除这个字符以外的哈希值判断即可 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 30300 #define BASE 149 using namespace std; typedef u
BZOJ 2038 2009国家集训队 小Z的袜子(hose) 莫队算法
题目大意:给定n个点,每个点有一个颜色,m次询问,每次询问一个区间内随机选出两个点颜色相同的概率是多少 OTZ莫队算法…… 具体做法无论是分块还是曼哈顿最小生成树网上都讲解的很详细 我就不累述了 这个题的做法是记录一个cnt数组表示当前区间内每种颜色有多少个 加入一个颜色为x的点就ans+=cnt[x] 然后cnt[x]++ 减少一个颜色为x的点就cnt[x]-- 然后ans-=cnt[x] 于是