爱悠闲 > 分类 >

BZOJ 第11页

BZOJ 1483 HNOI2009 梦幻布丁 链表+启发式合并
题目大意:给定n个布丁,每个布丁有一个颜色,多次将某种颜色的所有布丁变为另一种颜色,多次询问颜色段数 数据范围:n<=10W 颜色数<=100W 链表的启发式合并0.0 一直没写明白 其实就是开个链表记录每种颜色的位置,合并时撸一遍短的链看看两边是不是长链的颜色就行 不过交换比较麻烦0.0 要开个数组记录每个数字代表的真实颜色 交换时把数组的这两个位置也交换下就可以了 注意用过的垃圾不要留在原位
BZOJ 1038 ZJOI2008 瞭望塔 半平面交
题目大意及模拟退火题解:见 http://blog.csdn.net/popoqqq/article/details/39340759  这次用半平面交写了一遍……求出半平面交之后,枚举原图和半平面交的每个点,求出答案即可 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm
BZOJ 1047 HAOI2007 理想的正方形 单调队列
题目大意:给定一个a*b的矩阵,求一个n*n的子矩阵,使矩阵中的最大值与最小值之差最小 对于每行维护一个单调递减的队列,再弄一个竖着的队列,维护n个格子之内的最大值即可 两遍统计出最大值和最小值 然后得到ans即可 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 1010 usi
BZOJ 2759 一个动态树好题 Link-Cut-Tree+扩展欧几里得
题目大意:给定n个形如xi=ki*x_pi+bi mod p的同余方程组 支持修改操作和求解操作 确实好题 感谢此题作者 顺便吐槽一下作者的Splay不加空节点太蛋疼了0.0 将每个点i的父亲设为pi 我们将会得到一座基环树林 将环上的一条边拆掉,在边的起始节点新开个域special_father记录这条边(P.S:好浪费 但是没办法) 于是我们得到了一座森林 显然可以用LCT来维护 每个节点的权
BZOJ 2152 聪聪可可 树的点分治/树形DP
题目大意:给定一棵树,每条边上有边权,求距离为3的倍数的有序点对 树的点分治,对于每个重心统计出每棵子树距离重心长度为0/1/2的点的数量,计算出ans即可 最后ans*2+1 和n^2进行一下约分即可 其实我上当了……这题根本就没必要写树的点分治,直接树形DP就出来了 开一个三元组记录某棵子树中距离子树的根节点距离为某值的点的个数 然后直接统计+转移就行了 树的点分治: #include<cst
BZOJ 1096 ZJOI2007 仓库建设 斜率优化
题目大意:给定n个厂房,在其中一些建仓库,一个点如果没有仓库就要把仓库运到右侧的仓库中,求最小花销 很简单的斜率优化……之前刷斜率优化的时候怎么居然把这道题漏了 令f[i]为在i点建厂使i之前的货物全部安置的最小花销 则有 公式编辑器就是爽啊~ 令sump[i]为p[i]的前缀和 令sumxp[i]为p[i]*x[i]的前缀和 化简有 f[j] + sumxp[j] = x[i]*sump[j]
BZOJ 2982 combination Lucas定理
题目大意:发上来就过不了审核了……总之大意就是求C(n,m) mod 10007 m,n∈[1,2*10^8] 卢卡斯定理:C(n,m)=C(n%p,m%p)*C(n/p,m/p) mod p 要求p是质数 其中n%p可能会小于m%p 这种情况下直接返回0即可 证明去问卢卡斯 我不知道 #include<cstdio> #include<cstring> #include<iostream> #i
BZOJ 1024 SCOI2009 生日快乐 DFS
题目大意:给定一块x*y的蛋糕,切n-1刀分成n块大小相同的块,只能平行于边界切,求长宽比最大值最小 虽然求最大值最小但是这题没必要二分答案……直接深搜就可以了 枚举切成的两块的面积比,横竖各切一次即可 本大爷读入读错了TLE半天……尼玛死的心都有啊 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #inc
BZOJ 1025 SCOI2009 游戏 动态规划
题目大意:给定n,定义一个置换的排数为1~n的循环经过这个置换最少T次(T>0)可以回到原来的序列 求所有可能的排数的数量 将一个置换分解为一些循环,那么这个置换的排数就是这些循环的长度的最小公倍数 于是对于一个数,我们验证这个数是否是排数的方式就是将这个数分解质因数,令x=p1^a1*p2^a2*...*pk^ak,若p1^a1+p2^a2+...+pk^ak<=n,则x就是可能的排数 分组背包
BZOJ 1027 JSOI2007 合金 计算几何+Floyd
题目大意:给定一些合金,选择最少的合金,使这些合金可以按比例合成要求的合金 首先这题的想法特别奇妙 看这题干怎么会想到计算几何 而且计算几何又怎么会跟Floyd挂边 好强大 首先由于a+b+c=1 所以我们只要得到a和b即可 c=1-a-b 所以c可以不读入了 然后我们把每种原料抽象成一个点 可知两个点能合成的合金一定在两点连线的线段上 证明:设两个点为(x1,y1)和(x2,y2),新合成的合金