爱悠闲 > 分类 >

BZOJ 第45页

BZOJ 3658 Jabberwocky 可持久化线段树+分治
题目大意:给定平面上n个点,一共有k种颜色,要求选定一条线段,并选取线段正上方或正下方的所有点,要求不能出现所有颜色的点,求最多选择多少点 正解是双向链表+树状数组? 让我们来点优雅的做法 由于不能出现所有颜色的点 因此一定有至少一种颜色不出现 我们可以枚举这个不出现的颜色 现在我们搞出所有极大子矩形 这个分治就好了。。。 假设我们现在求的是一条线段下方的点 那么我们考虑一条直线从下往上走 遇到禁
BZOJ 2563 阿狸和桃子的游戏 贪心
题目大意:给定一张无向图,每个点有点权,每条边有边权,两个人轮流选择点,若一条边的两端点被选择则这条边被选择,两人都想自己的得分-对手的得分最大,求最终先手得分-后手得分 考虑先手选择每个点对答案的影响 一个点如果不选,本身对答案的贡献是-w 一个点如果选,本身对答案的贡献是w 一条边如果两个端点都不选,对答案的贡献是-c 如果两个端点中只选择一个,对答案的贡献是0 如果两个端点都选,对答案的贡献
BZOJ 3620 似乎在梦中见过的样子 KMP+暴力
题目大意:给定一个字符串,求这个字符串有多少个子串满足这个子串可以拆分成ABA的形式,其中|A|>=k,|B|>=1 梦の中で逢った、ような…... n<=15000 显然是直接给你暴力用的- - 枚举子串的左端点,然后枚举右端点 对于每个子串S我们要判定是否存在一个长度在[k,|S|-1>>1]之间的前缀与后缀匹配 那我们就求出长度不超过|S|-1>>1的最长前后缀,判断是否>=k即可 这怎么和
BZOJ 1880 Sdoi2009 Elaxia的路线 SPFA+拓扑排序
题目大意:给定一张无向图,求s1到t1与s2到t2的最长公共最短路 以s1 t1 s2 t2为源做4次最短路 如果某条有向边满足s到起始点的距离+边长+终点到t的距离=s到t的最短路 那么这条边就可以在s到t的最短路上 我们把所有既在s1到t1的最短路上也在s2到t2的最短路上的有向边都拎出来 容易证明这个图一定没有环 因此拓扑排序求最长链即可 写完发现过不去样例。。。 因为这题题目描述与题意不符
BZOJ 3622 已经没有什么好害怕的了 动态规划+容斥原理
题目大意:给定两个长度为n个序列,保证这2n个数字两两不同,求有多少匹配满足a[i]>b[i]的数对数比a[i]<b[i]的数对数多k もう何も怖くない 题解:http://www.cnblogs.com/dyllalala/p/3900077.html OTZ 神思路根本就是想不到啊QAQ でも。。。もう何も怖くない。。。(大雾 此外我们可以引入一下WTY公式: C[i][j]=C[i-1][j
BZOJ 2024 SHOI2009 舞会 动态规划+容斥原理+高精度
题目大意:给定两个序列,求有多少个匹配满足a[i]<b[i]的对数不超过k对 见http://blog.csdn.net/popoqqq/article/details/44514113 高精度已废。。。 #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm>
BZOJ 3417 Poi2013 Tales of seafaring BFS
题目大意:给定一张无向图,每条边边权都是1,多次询问是否存在某个点到达另一个点的长度为d的路径 首先如果s和t是同一点且这个点没有出边 那么s到t只存在长度为0的路径 否则: 如果s到t有长度为d的路径 那么就一定有长度为d+2的路径 因此只要BFS求出s开始到每个点的奇数长度的最短路和偶数长度的最短路就行了 为了防止爆内存可以预先将询问离线化 时间复杂度O(n(n+m)) #include <c
BZOJ 1997 Hnoi2010 Planar 2-sat
题目大意:给定一个带哈密顿回路的图,判断这个图是否是平面图 这竟然是我第一次写2-sat。。。 把哈密顿回路拎出来,每条边只有两种可能:在里面或者在外面 如果两条边相交,那么必须一条在里面一条在外面 然后建2-sat就好了。。。 10000条边显然不能暴力建图,但是我们发现如果边数>3*点数,那么这个图一定不是平面图 这样就把边数缩小到了400,然后就可以做了 #include <cstdio>
BZOJ 1110 POI2007 砝码Odw 贪心
题目大意:给定n个砝码和m个背包,保证对于任意两个砝码都有一个是另一个的正整数倍,求最多拿走多少砝码 http://hzwer.com/4761.html 大概想到了进制拆分但是没想到具体怎么做。。。 我还是太弱了。。。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1
BZOJ 1111 POI2007 四进制的天平Wag 高精度+动态规划
题目大意:给定一个数n,要求将n表示成一些四进制数之和/差的形式,要求用的数最少,求方案数 光棍节快乐(巨雾 我们将n分解成4进制,从低位到高位考虑 如果这一位是0,显然不用考虑这位 如果这一位是1,显然从0开始往上加一个比较优,因为如果从0开始减掉3个还不如将高位-1然后把这一位+1 如果这一位是2,要么从0开始加两个,要么从0开始减掉两个 如果这一位是3,那么一定从0开始往下减一个比较优,因为