爱悠闲 > 分类 >

BZOJ 第46页

BZOJ 1112 POI2008 砖块Klo Treap
题目大意:给定一个长度为n的序列,求一个长度为k的子区间,将这个长度为k的区间变成一样的,代价总和最小,求最小花销 显然选取的是这k个数的中位数时代价总和最小 于是我们从左往右扫一遍 用一个Treap来维护这个长度为k的区间即可 时间复杂度O(nlogn) 这水题居然还贡献了一个WA真是。。。 #include <cstdio> #include <cstring> #include <iostr
BZOJ 1107 POI2007 驾驶考试egz LIS
题目大意:。。。不是很好叙述自己看吧。注意要剪掉初始就能到达所有终点的点的数量 http://blog.163.com/c_sunshine/blog/static/2439650542015028013488/ OTZ 这做法实在是太优雅了! #include <cstdio> #include <cstring> #include <iostream> #include <algorithm>
BZOJ 1116 POI2008 CLO 并查集
题目大意:给定一个无向图,求能否找到一个点和边的匹配,使匹配数为点数。 我又一次被并查集虐傻了。。。。 http://blog.csdn.net/popoqqq/article/details/41544997 很好奇自信Dinic的话O(40W*√10W)的复杂度会不会T 估计会。。。 #include <cstdio> #include <cstring> #include <iostream
BZOJ 1131 POI2008 Sta 树形DP
题目大意:给定一棵树,求一个点,使以这个点为根时深度之和最大,在此基础上要求编号最小 裸TreeDP。。。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1001001 using namespace std; struct abcd{ int to,next; }t
BZOJ 1130 POI2008 POD Subdivision of Kingdom DFS
题目大意:给定一个n个点的无向图,要求将点集分成大小相等的两个子集,使两个子集之间的边数最少 n<=26,直接C(26,13)枚举也只有1000W(其实去掉重复的只有500W,我写代码时脑残忘去掉了) 但是常规的枚举方法每次需要O(n)统计答案,显然会T 这里我们考虑搜索 初始令S集为空,T集包含全部的点,然后依次枚举T的某个点加入S集 这个点加入S集时,与S集的连边需要从答案中扣除,与T集的连边
BZOJ 1121 POI2008 激光发射器SZK
题目大意:给定一个边与坐标轴垂直的多边形,从一个角的角分线射出,经过反射射向另一个角,求最多射出几条 答:因为光路可逆,因此两条射线一定不会射到同一个点上,故一定能射出n/2条 main(){int n;scanf("%d",&n);printf("%d",n/2);}
BZOJ 1123 POI2008 BLO Tarjan+树形DP
题目大意:给定一张无向图,求每个点被封锁之后有多少个有序点对(x,y)(x!=y,1<=x,y<=n)满足x无法到达y 还是看原题面爽。。。 Tarjan求点双,然后TreeDP即可 时间复杂度O(n+m) #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm>
BZOJ 3632 外太空旅行 DFS
题目大意:给定一张无向图,求最大团 从小到大依次枚举每个点加或者不加 如果加必须满足加入后是一个团 这样状态数很大显然会T 因此可以考虑加入剪枝 统计还未加入的所有点中有多少点可以加入当前的团 如果这样的点的数量加上当前团中点的数量仍然比ans小 就剪枝 这样就可以过了- - 其实根据这个估价函数还可以写个A*。。。 我懒得写了。。。 #include <cstdio> #include <cst
BZOJ 1125 POI2008 Poc Hash+Treap
题目大意:给定n个长度为l的字符串,m次交换两个字符,问每个字符串任意时刻最多与多少个相同 把字符串Hash一下 然后就是千山鸟飞绝了。。。 http://blog.csdn.net/popoqqq/article/details/44353883 BZ挂了交不了题真闹心QAQ #include <queue> #include <cstdio> #include <cstring> #inclu
BZOJ 1127 POI2008 KUP 单调队列
题目大意:给定一个矩形,求一个子矩形满足权值和在[k,2k]之间 跪漆子超= = 首先考虑1*n的情况 如果存在[k,2k]之间的点,直接输出 否则如果存在一个区间满足和>=k且任意元素<k 则有解 否则无解 这个很显然 因为区间内所有元素都<k 因此前缀和不会跨越[k,2k]直接到达(2k,+∞) 那么我们把这个结论扩展到二维 也是对的 证明:如果存在一个子矩形满足和>=k且所有元素<k,那么: