爱悠闲 > 分类 >

BZOJ 第47页

Ural 2040 Palindromes and Super Abilities 2 回文自动机
题目大意:给定一个字符串,从左到右依次加入每个字符,问每加入一个字符之后本质不同的回文串的数量增加多少 http://blog.csdn.net/huyuncong/article/details/41181953 回文自动机OTZ 注意: 1.这道题必须把奇串和偶串分开建 如果通过插入分隔符的方式建在一起会MLE 2.把长度为500W的01串一个一个输出会T掉 存在一个char数组里一起输出就行
BZOJ 3676 Apio2014 回文串 回文自动机
题目大意:定义一个回文串的出现值为出现次数*长度,求最大出现值 我并不知道这道题曾经的解法是什么,但是自从回文自动机出现之后它成为了一道裸题。。。裸题。。。裸题。。。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 300300 using namespace std;
BZOJ 3695 滑行 迭代+二分
题目大意:给定一个n层的区域,从左下角走到右上角,每个区域的高度和速度都不同,问怎么走最快 由于我并不知道光路最速原理所以我写了迭代+二分23333 首先易知每一层的路线都一定是一条直线 我们考虑只有两层的情况 由于左下角和右上角固定 因此我们可以三分确定中间的转折点的位置 或者可以写出时间关于转折点坐标的函数关系 求导之后二分 这个更快一些 那么现在是多层 我们这样搞: 每次迭代,枚举1~n-1
BZOJ 1283 序列 费用流
题目大意:给定一个长度为n的序列,要求选一些数,使得任意一个长度为m个区间中最多选k个数,求最大的和 费用流直接跑就是了 把这个序列用流量为k费用为0的边连成一条直线 然后第i个点向第i+m个点连一条费用为a[i]流量为1的边 跑最大费用最大流即可 卡单纯型差评。。。。 #include <cstdio> #include <cstring> #include <iostream> #includ
BZOJ 2666 cqoi2012 组装 贪心
题目大意:给定数轴上的m个点,共有n种颜色,要求在数轴上选定一个点,使这个点到每种颜色最近的点的平方和最小 初始将所有颜色最左侧的点作为最近点,然后不断选择【当前点与同种颜色下一个点的中点最靠左的点】进行替换,并更新ans 理性证明见http://www.cnblogs.com/jianglangcaijin/p/4204478.html 下面来个感性证明: 这不是显然么- - 考虑将组装车间从-
BZOJ 3270 博物馆 期望DP+高斯消元
题目大意:给定一张无向连通图,两个人初始各在某个点上,每个时刻每个人会不动或任选出边走,求两人最终期望在哪里相遇 把点数平方,原图上的两个点(x,y)变成新图上的一个点 然后令A为这个图的邻接矩阵(若两人在同一点上则没有出边,否则按概率转移),S为初始行向量(S[(a,b)]=1),ans为答案行向量 那么有ans=S+SA+SA^2+SA^3+... =S(I-A^+∞)/(I-A) =S/(I
BZOJ 3614 Heoi2014 逻辑翻译 分治 = =HEOI2014全AC达成?
题目大意:给定一个含有n个变量的2^n项的多项式,将每个变量分别选-1和1代入求值,求多项式的各项系数 《论一道题究竟如何出才能同时卡时间卡内存卡精度卡输入卡输出卡评测》 很久之前盯着这道题看了很长时间……直到今天我才发现这题原来是道傻逼题。。。 我们用三个变量举例 假设f(x)=a0x1x2x3+a1x1x2+a2x1x3+a3x2x3+a4x1+a5x2+a6x3+a7 那么我们把含有x1的项
BZOJ 1135 POI2009 Lyz 线段树+Hall定理
题目大意:有1~n型号的滑冰鞋,每种有k双,一个x号脚的人只能适应[x,x+d]号滑冰鞋,每次增加一些x号脚的人或减少一些x号脚的人,问能否匹配 http://m.blog.csdn.net/blog/u012732945/40707885 OTZ 这题我居然还能贡献一个WA真是醉了 #include <cstdio> #include <cstring> #include <iostream>
BZOJ 1142 POI2009 Tab Hash
题目大意:给定两个矩阵,保证矩阵内所有元素都不相同,求第一个矩阵通过交换行和列是否可以得到第二个矩阵 令每一行的哈希值为这一行的元素排序后的RK哈希值,将行按照哈希值排序 然后把每一列按顺序哈希一下,排个序取RK哈希作为整个矩阵的哈希值 判断两个矩阵的哈希值是否相等即可 由于矩阵中元素不重复所以可以保证第一步的哈希值不会出现重复 然后。。。我都写完了它告诉我是2B题???? 算了反正POI官网上能
BZOJ 1141 POI2009 Slw
题目大意:给定一个01串,定义h(s)为将s中所有的"0"变成"1",所有的"1"变成"10",求Σh^ai("0")是否是h^m("0")的子串 其中m∈[0,﹢∞) 跪VFK。。。 令Si=h^i("0") 打表会发现Sn=S(n-1)+S(n-2) 但是这个性质对于这题帮助不大 我们暂且忽略这个性质。。。(后面某个地方会用到) 首先我们定义h^-1(s)为h(s)的逆变换 即对于每个"1"