爱悠闲 > 分类 >

BZOJ 第18页

BZOJ 2467 中山市选2010 生成树 组合数学
题目大意:给定一个图,图的中心是一个n个点的多边形,每条边都外接一个五边形,求生成树个数 Matrix Tree定理?不会! 观察这个图 5n条边 4n个点 每个五边形都是一个环 必须拆掉一条边 拆掉之后发现4n个点 4n条边 是一个基环树 基环树的环上的边由中心多边形被拆掉的边所在的五边形的剩余边与中心多边形未被拆掉的边构成 容易发现这个环上任意拆掉一条边都会导致某个五边形被拆掉两条边 且一条边
BZOJ 2762 JLOI2011 不等式组 树状数组
题目大意:给定一些形如ax+b>c的不等式,支持插入和修改,以及询问当x=k时有多少不等式成立 将不等式变形 可以得到每个不等式成立时x的取值范围 在树状数组上统计即可 注意事项: 1.a可以等于0 此时若b>c x∈R 若b<=c x∈∅ 2.x的取值范围可能超过[-1000000,1000000] 3.由于有负数 所以区间修改时左右端点都要加上1000001 若加上1000000则死循环 4.
BZOJ 2594 Wc2006 水管局长数据加强版 Link-Cut-Tree
题目大意:给定一个无向图,多次删除某条边,多次查询两点之间路径上边权最大值的最小值 Link-Cut-Tree维护动态最小生成树 首先倒着做 将所有被删除的边标记(找边我用的排序+二分) 将没标记的边跑一遍Kruskal 求出最小生成树 然后每次加边和查询正常维护即可 LInk-Cut-Tree一气呵成写完,Kruskal尼玛写挂了…… 居然忘记把并查集连边 这我也是醉了 顺便吐槽一下题干上给的读
BZOJ 2111 ZJOI2010 Perm 排列计数 组合数学+Lucas定理
题目大意:求1~n的排列能组成多少种小根堆 考虑一个1~i的排列所构成的堆,l为左儿子大小,r为右儿子的大小 那么1一定是堆顶 左儿子和右儿子分别是一个堆 显然如果选出l个数给左儿子 那么左儿子的方案数显然是f[l],右儿子的方案数为f[r] 于是有f[i]=C(i-1,l)*f[l]*f[r] 于是我们线性筛处理出阶乘和阶乘的逆元 代入即可得到WA 原因是这题n可以大于p 此时要用到Lucas定
BZOJ 3551 ONTAK2010 Peaks加强版 Kruskal重构树+可持久化线段树
题目大意:同3545 强制在线 3545题解传送门:http://blog.csdn.net/popoqqq/article/details/40660953 强制在线没法排序 启发式合并也就用不了了 Kruskal重构树是个挺好玩的东西 可以拿来处理一些最小生成树的边权最值问题 这里我们Kruskal连边时并不直接连边 而是新建一个节点ext 将两个点所在子树都连到ext的儿子上 比如说样例的树
BZOJ 1224 HNOI2002 彩票 DFS
题目大意:在1~m中选n个不同的数 要求和为X/Y 求方案数 爆搜的话应该是100E左右 所以考虑加剪枝 上下界剪枝 如果当前的情况下剩余的数最大都无法到达目标或最小都无法小于目标 则剪枝 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M
BZOJ 1800 AHOI2009 fly 飞行棋 暴力
题目大意:给定圆弧上的一些点,求有多少个矩形 矩形的对角线一定是直径 所以问题转化为求直径 若直径数量为x 则答案为C(x,2) 这东西用不用啥数据结构维护一下……手贱去看了下数据范围…… 其实线性做法巨好写 为何看到那么多版本都是O(n^2)的 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm
BZOJ 1218 HNOI2003 激光炸弹 暴力
题目大意:给定平面上的n个点,求一个r*r的正方形最多覆盖多少个点 NOIP 2014 D2T1 无线网络发射器选址 直接暴力枚举正方形 加个前缀和优化就能过 n^2大法好啊 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 5010 using namespace std; in
BZOJ 2738 矩阵乘法 分块
题目大意:给定一个矩阵,多次求一个子矩阵中的第k小 正解:CDQ分治 不会  二维莫队? 不会  于是果断分块大法好(又是 我们将这n*n个数排序 分n次插入 每次插入n个 每次插入后 去链表上处理尚未出解的询问(我懒得写链表写了并查集) 如果当前询问的子矩阵内已经插入大于等于k个数 那么答案一定在当次插入的n个数中 暴力查找即可 时间复杂度O(n^3+nq) 好卡…… #include<cstd
BZOJ 1196 HNOI2006 公路修建问题 二分答案+Kruskal
题目大意:给定一个无向图,一条边可以被建为一级公路或二级公路,要求一级公路的数量不小于k条,求最小生成树 最小生成树保证的是最大边最小 直接对边排序,然后二分答案,每次用Kruskal验证 先连一级边看能不能连出k条,再连剩余的边看看能不能得到最小生成树 #include <cstdio> #include <cstring> #include <iostream> #include <algor