爱悠闲 > 分类 >

BZOJ 第12页

BZOJ 1044 HAOI2008 木棍分割 二分答案+动态规划
题目大意:给定n个连在一起的木棍,分成m+1段,使每段最大值最小,求最大值的最小值及最大值最小时分割的方案数 第一问水爆了……二分答案妥妥秒过 第二问就有些难度了 首先我们令f[i][j]表示用前j个棒♂子得到i段的方案数 诶我没打什么奇怪的符号吧 于是我们有动规方程 f[i][j]=Σf[i-1][k] (sum[j]-sum[k]<=ans,k<j) 这个最坏情况下是O(m*n^2)的,肯定挂
BZOJ 1029 JSOI2007 建筑抢修 贪心+堆
题目大意:n个建筑需要抢修,第i个建筑需要T1时间抢修,必须在T2时间之前抢修完毕,求最多能抢修多少建筑 首先我们对T2排序 然后依次修理 但是这样贪心显然是不正确的 比如说这组数据: 5 10 10 10 20 2 21 2 21 2 21 贪心只能修理前两个,而实际上最多可以修理4个 于是我们考虑修正贪心算法 比如说这组数据,当我们枚举到3的时候,虽然已经无法修理更多了,但是我们可以取消修理建
BZOJ 1295 SCOI2009 最长距离 SPFA+暴力
题目大意:给定一个棋盘,一些格子上有障碍物,可以移除T个障碍物,求移除后所有能互相到达的点对中的最大欧几里得距离 m,n<=30,900个点,我们可以枚举起始点,跑一遍SPFA,求出所有经过不超过T个障碍物可达的点,统计ans即可 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algor
BZOJ 1022 SHOI2008 小约翰的游戏John 博弈论
题目大意:反Nim游戏,即取走最后一个的人输 首先状态1:如果所有的堆都是1,那么堆数为偶先手必胜,否则先手必败 然后状态2:如果有两个堆数量相同且不为1,那么后手拥有控场能力,即: 若先手拿走一堆,那么后手可以选择将另一堆留下1个或者全拿走,使这两堆最终只剩1个或0个; 若先手将一堆拿剩一个,那么后手可以选择将另一堆留下一个让先手拿或全拿走,使这两堆最终只剩1个或0个; 若先手将一堆拿走一部分,
BZOJ 2744 HEOI2012 朋友圈 二分图最大匹配
题目大意:求一个图的最大团 图长啥样自己看题 最大团是NP难度问题 但由于这个图的特殊性 我们可以通过一些技♂巧♂搞定它 这破输入法又打了一些多余的符号…… 首先我们建立反图 易知最大团=反图的最大点独立集 然后我们观察 A国奇数是一个完全图 偶数是一个完全图 于是A国顶多选出2个人 B国奇数之间没有边 偶数之间没有边 奇偶之间构成二分图 于是我们枚举A国的两个人(可以是1个人或者不选,全部枚举一
BZOJ 1043 HAOI2008 下落的圆盘 计算几何
题目大意:n个圆盘依次下落,求最终能看到的轮廓线面积 円盘反对!让我们一起团结起来!赶走円盘! 咳咳。很神的一道题 今天去看了题解和白书才搞出来…… 首先我们倒着做 对于每个圆盘处理出在它之后落下的圆盘和它的覆盖区间 然后求一个区间并就能算出这个圆盘的可见弧长 然后就是相交部分怎么求的问题了 首先两个圆必须相交 然后作圆心1到圆心2的向量 用atan2求出极角 然后利用余弦定理求出两个交点和圆心连
BZOJ 1032 JSOI2007 祖码Zuma 动态规划
题目大意:给定一个祖玛序列,任选颜色射♂出珠子,问最少射♂出多少珠子 输入法最近越来越奇怪了0.0 首先我们把连续相同的珠子都缩在一起 令f[i][j]表示从i开始的j个珠子的最小消除次数 初值 f[i][1]=cnt[i]==1?2:1 然后对于每个区间,我们枚举中间点,拆成两半求和 如果这个区间两端点颜色相同,我们还可以把中间消掉,然后两边再补射1或0个 尼玛珠子的颜色可以是0……因为这个WA
POJ 2494 Acid Text 模拟
题目大意:给定CSS语言的图片合成器,要求编译运行并输出结果 首先过样例 这个应该问题不大 然后交上去WA 那么请注意以下问题 1.读入用char 然后构造成string 2.由于White Space的肆虐横行,我们可以写一个Kill_Char(int x)函数,该函数的作用是干掉x个' ''\t''\n''\r'以外的字符,可以方便快捷地把题目中的无用信息清理掉 3.位置坐标的x和y是反的 过
BZOJ 1050 HAOI2006 旅行comf 动点SPFA
题目大意:给定一个无向图,每条边上有权值,求起点到终点的路径中最长边和最短边的最小比值 随手点开一道居然是动点SPFA的裸题…… 魔法森林都切了这个问题就不大了 我们把边权排序,从大到小加进这个图中,每加进一条边就把边的两个端点加进队列,直接跑SPFA,维护起点到每个点路径上的最长边的最小值,然后用当前边权作为分母更新ans 这样可以保证每次跑出来的都是当前边为最短边时起点到终点的最长边的最小值,
BZOJ 1211 HNOI2004 树的计数 Prufer序列
题目大意:给定一棵树中所有点的度数,求有多少种可能的树 Prufer序列,具体参考[HNOI2008]明明的烦恼 直接乘会爆long long,所以先把每个数分解质因数,把质因数的次数相加相减,然后再乘起来 注意此题无解需要输出0 当n!=1&&d[i]==0时 输出0 当Σ(d[i]-1)!=n-2时输出0 写代码各种脑残……居然直接算了n-2没用阶乘…… #include<cstdio> #i