爱悠闲 > 分类 >

BZOJ 第34页

BZOJ 2119 股市的预测 后缀数组
题目大意:给定一个序列,求差分后有多少个子串满足形式为ABA,其中B部分长度为m,A部分长度大于0 首先枚举A的长度j,将序列上每隔j个点插入一个关键点 对于第i个位置上的关键点,我们找到第i+j+m个位置 利用后缀数组找出两个位置向左拓展多少个位置都是相同的,以及向右拓展都少个位置都是相同的 为了保证不重复向左和向右最多拓展j-1个位置 设拓展之后长度为len,那么如果len>=j,ans+=(
BZOJ 2229 ZJOI2011 最小割 最小割+分治 400AC达成&&2000Submission达成
题目大意:给定一个图,多次询问有多少个点对之间的最小割小于等于某个值 最小割分治- - 首先朴素的想法是做O(n^2)遍网络流 但是这样显然是过不去的 根据一些结论,最小割最多有n-1个,这n-1个最小割构成一个最小割树 别问我为什么- - 因此我们分治寻找这n-1个最小割 每层分治,先任选两个点作为源汇做一遍最小割 然后找出S集和T集,对所有S集的点和T集的点构成的点对用本次得到的最小割更新一遍
BZOJ 2132 圈地计划 最小割
题目大意:给定一个m*n的矩阵,每个位置如果作为商业区或者工业区各有一个收益,如果相邻两块是不同的也会有一个收益,求最大收益 吐槽:住宅区呢- - 地理老师骗我们- - 普通的最小割建图会遇到一个问题: 割断两块之间的边收益为正,即代价为负 因此我们如果正常建最小割,那么两块之间的边权就会是负的 那么我们将这个矩阵黑白染色,将白格ST反向 这样割断两块之间的连边相当于两块选择了同一用途,代价为正
BZOJ 3162 独钓寒江雪 树同构+树形DP
题目大意:给定一棵树,求本质不同的独立集个数对1000000007取模后的值 首先独立集个数应该都会求吧- - 令f[x][0]为x这个点不选的独立集个数 f[x][1]为x这个点选的独立集个数 那么有f[x][0]=Σf[son[x]][0]+f[son[x]][1] f[x][1]=Σf[son[x]][0] 但是现在要求本质不同 说到本质不同我们很容易想到群论 但是群论显然写不了- - 于是
BZOJ 3197 Sdoi2013 assassin 动态规划+树同构+费用流
题目大意:给定一棵树和两组权值,求第一组权值最少改变多少个之后这棵树经过重标号之后与第二组权值相同 这个题做法很神- - 首先和3162一样的处理方式 我们先找到这棵树的重心作为根 如果重心有两个就新建一个根连向这两个重心 令f[x][y]表示x所在子树的第一组权值和y所在子树的第二组权值匹配的最小花销 转移的必要条件是x所在的子树与y所在的子树同构且x与y深度相同 为了保证无后效性,x的所有子节
BZOJ 1143 CTSC2008 祭祀river 二分图最大匹配
题目大意:给定一个拓扑图,求一个最大的点集,点集中的点两两不可达 这实际上就是让你求传递闭包后图的最大点独立集- - 利用二分图最大匹配就能搞- - #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 110 using namespace std; int n,m,ans;
BZOJ 3198 Sdoi2013 spring Hash+容斥原理
题目大意:给定n个元素,每个元素是一个六元组,求有多少对元素满足相同的位置恰好有k个 首先对于恰好有K个这种东西果断考虑容斥原理 我们2^6枚举相同的位置 恰好有k个元素相同的对数=至少有k个位置相同的对数-至少有k+1个位置相同的对数+至少有k+2个位置相同的对数…… 但是我们计数时会发现一些问题 比如下面这组样例显然是0: 2 3 1 2 3 4 5 5 1 2 3 4 6 6 但是这一对元素
BZOJ 2339 HNOI2011 卡农 组合数学
题目大意:求由1~n构成的m个集合有多少种 其中1~n中每个数都出现了偶数次 围观题解: http://blog.csdn.net/orpinex/article/details/7405538 吾等蒟蒻到底也只会看题解了- - #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define
BZOJ 3173 Tjoi2013 最长上升子序列 Treap+树状数组
题目大意:给定一个序列,依次将1~n插入,问每次插入之后序列的LIS长度是多少 由于是从小到大插入,因此插入一个数之后显然是不影响之前的答案的 因此我们不妨先用平衡树搞出插入之后的序列,再求一遍LIS即可 注意最后每个点还要对前面的取一下max 因为插入后LIS可能还是之前的序列 蒟蒻的我到底还是把平衡树写挂了。。。 #include <cstdio> #include <cstring> #in
BZOJ 2965 保护古迹 平面图转对偶图+最小割
题目大意:给定一个平面图以及一些点,求将1个、2个、3个……点围起来所需要的最小代价 首先平面图转对偶图 枚举每个点的每条没有走过的出边进行DFS,每到达一个点之后向来时的边逆/顺时针转到的第一条边继续深搜,这样可以搜出所有的区域(包括最外层的无限区域) 我们可以用面积的符号来判断出最外层的无限区域 接下来我们需要判断一个点在哪个区域,由于点只有10个,因此暴力枚举即可 判断一个点是否在某个简单多