爱悠闲 > 分类 >

BZOJ 第21页

BZOJ 3787 Gty的文艺妹子序列 分块+树状数组
题目大意:带修改、强制在线的区间逆序对 将之前3744TLE了的某个做法重写了一发 把其中一些预处理改成了树状数组 不得不说树状数组常数还是小啊 令g[i][j](i<=j)表示第i块中的元素与第i~j块中的元素之间的逆序对数 第一维暴力第二维树状数组维护前缀和 equals[i][j]表示前i块之内j的数量 这个直接暴力即可 smaller[i][j]表示前i块之内小于等于j的数的数量 第一维暴
BZOJ 2419 电阻 高斯消元
题目大意:给定n个点,一些点之间有电阻相连,求1~n的等效电阻 首先我们设电流为1A 终点电势为零 点i的电势为Ui 由于电流是流 显然对于每个点(点1和点n除外) 有总流入等于总流出 即 Σ(Ui-Uj)/Rij=0 (i!=1,i!=n) Σ(U1-Uj)/R1j=1 Σ(Un-Uj)/Rnj=-1 Un=0 联立方程组高斯消元即可 最后输出点1的电势就是答案 注意自环要无视 重边要用倒数和缩
BZOJ 3040 最短路(road) Pairing-Heap优化Dijkstra
题目大意:给定n个点m条边的图,求1~n的最短路 n<=100W m<=1000W 题目上说要用高效的堆来优化Dijkstra 于是我们自然而然就会想到斐波那契堆 但是那东西真的不是很好写 于是我们有很高效的替代品——Pairing-Heap(配对堆) 这东西真的很好写(除了手写栈以外,一个节点有多个儿子所以手写了栈) 首先Pairing-Heap有几个基本操作: Merge(x,y) 将两堆合并
BZOJ 1030 JSOI2007 文本生成器 AC自动机+DP
题目大意:给定n个模式串,求长度为m的至少含有一个模式串的字符串共有多少种 照例,令f[i][j]表示长度为i的字符串与AC自动机上的第j个点匹配的方案数 直接DP很难,我们考虑补集法,即用26^m减去不含任何模式串的字符串的数量 后者就是经典的AC自动机DP模型啦~~ #include <cstdio> #include <cstring> #include <iostream> #includ
BZOJ 2393 Cirno的完美算数教室 容斥原理+DFS
警告:网上的题解都是误人子弟,看此篇题解之前请将脑海中对其它写于本题解之前的网上常见题解的印象全部消除之后方可阅读 此题的数据范围是10^9 但是10^10一样可以做 不影响 首先我们可以预处理出1~r以内所有只由2和9构成的⑨数 容易发现最多有1022个 但是其中有一些⑨数是另一些的倍数 比如说a是b的倍数 那么一个数如果是a的倍数那么就一定是b的倍数 我们只需要计算b即可 无需计算a 这里可以
BZOJ 3172 Tjoi2013 单词 fail树
题目大意及后缀数组做法见 http://blog.csdn.net/popoqqq/article/details/41042473 原来正解是fail树……难怪后缀数组被卡成这样 首先我们将给出的n个串构建AC自动机 朴素的做法是对于每个串将这个串每个节点沿着fail指针扫一遍,将路径上的所有点的cnt++ 但是这样做会TLE 我们不妨反向思考 fail指针反向后是一棵树 沿着fail指针扫一遍
BZOJ 2754 SCOI2012 喵星球上的点名 fail树+set启发式合并
题目大意:给定n个目标串和m个模式串,问这m个模式串每个在多少个目标串中出现过,以及n个目标串每个以最多多少个模式串为子串 我错了……就算用fail树+set启发式合并也优化不到O(nlog^2n)……这题的数据范围相当无解啊 首先将所有名字和点名的字符串全都插进AC自动机 将每个点上开一个set记录这个点是哪些喵星人的名字的前缀 然后建立fail树 沿着fail树从下到上启发式合并 每合并完一个
BZOJ 2657 ZJOI2012 旅游(journey) 树形DP
题目大意:给定一个三角剖分之后的凸多边形,求连接凸多边形的两个顶点的线段能经过的最多的三角形数 首先结论1:将相邻的三角形连边 得到的一定是一棵树 证明:如果此图出现环 那么一定有一群三角形围成一圈 那么就会在这些三角形的中间出现一些顶点 这显然是不可能的 结论2:连接两个三角形的线段经过的三角形等同于树上两个三角形路径上的所有点 证明:不会 自己画个图YY吧 总之就是相邻的三角形连边 然后O(n
BZOJ 1060 ZJOI2007 时态同步 树形DP
题目大意:给定一棵有根树,每次操作可以使某条边边权+1,求最少的操作次数,使根节点到每一个叶节点的距离都相等 树形DP 容易发现操作对于越靠近根节点的边进行越有利 首先对于每个节点扫一遍记录这个节点到子树中所有叶节点的最大距离 然后枚举每一个儿子 将该节点和该儿子之间的边权补至最大距离相等 对于每个节点都如此做 最后就能保证根节点到每个叶节点的距离都相等 数据有误坑死人…… #include <c
BZOJ 2929 Poi1999 洞穴攀行 最大流
题目大意:给定一个有向图,与起点和终点相连的边只能走一次,剩下的边可以走无数次,问起点到终点可以走多少个人 把这题的翻译给我揪出来我要打死他…… #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 210 #define INF 0x3f3f3f3f #define S 1