- 博客(187)
- 收藏
- 关注
RSS订阅原创 bzoj4259: 残缺的字符串
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4259思路：FFT是一种高效的字符串匹配算法只要想到FFT就好办了令为‘*’的位置值为0那么两个字符串匹配当且仅当Σ(a[i]-b[i])^2*a[i]*b[i]=0式子的含义很好理解，前面就是字符相同，后面就是该位是否为通配符为了FFT能做，我们要把A串反过来才有
2016-07-01 11:56:04
639
原创 bzoj1417: Pku3156 Interconnect
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1417思路：注意到每个点没有什么区别，我们关心的只是联通情况我们可以用每个连通块的大小来表示状态30的整数拆分数是5604,也就是说最多有5604种状态这些状态之间的转移关系显然是DAG转移方程：设当前状态S={C1,C2...C[m]}的合并两个连通块的后继状态为
2016-06-25 21:50:53
631
原创 bzoj2720: [Violet 5]列队春游
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2720思路：利用期望的线性性，可以转为求每个人的期望设每个人能看到的距离为diE[Σdi]=ΣE[di]考虑怎么求每个人的期望设sum[i]表示身高小于i的身高的人数枚举位置，再枚举长度即可 但其实我们可以不用枚举位置，每个位置(如果足够长)其实是一样的
2016-06-25 21:49:32
819
原创 bzoj2698: 染色
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2698思路：令xi=1,col=white =0,col=blackE[X]=E[Σxi]=ΣE[xi]因为只要覆盖一次就算覆盖，所以直接算不太方便考虑每个点m次不被覆盖的概率就是一次不被覆盖的概率的m次方#include#include#include
2016-06-25 21:47:10
658
原创 后缀自动机总结
后缀自动机总结后缀自动机的构造和相关性质及复杂度证明可以看陈老师的ppt时间复杂度据说可以用均摊分析证明是O(n)的一开始看直接看陈老师的ppt确实有点难以理解，但是陈老师的ppt确实是讲的最正规的一个一些定义：right集合：后缀自动机中节点代表的子串的右端点位置构成的集合 mins/maxs：节点代表的串的最短长度和最长长度现在开始进入正题：
2016-06-02 21:53:41
8385
原创 bzoj3667: Rabin-Miller算法
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3667思路：首先我们说说Miller_Rabin算法我们发现了费马小定理那它倒过来对不对呢如果a^(p-1)=1(mod p),那么p一定是素数吗？很不幸，是错的虽然出错概率很低，但是可以被卡于是我们就给它打补丁我们又找到了一个二次探测的方法如果p是质数，那
2016-05-08 22:39:04
2445
1
原创 bzoj3205: [Apio2013]机器人
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3205思路：类似斯坦纳树的想法但是因为这里的合并必须连号所以子集枚举就变成了区间合并说说做法好了首先记搜搜出每个点向四个方向走一步会到哪里注意：转向器可能导致机器人一直在里面转出不来，要特判掉然后设f[l][r][x][y]表示当前合并的机器人是[l,r]，
2016-05-08 20:08:18
2585
原创 bzoj4006: [JLOI2015]管道连接
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4006思路：一眼看上去很像斯坦纳树但是限制稍有不同，只要每种颜色的点联通即可也就是说最后可能是森林我听说裸写斯坦纳树有90所以我们要在外面再套一层DPf[i][j]还是斯坦纳树的状态，i是以i为根，j是状态为j先用斯坦纳树求出每种联通状况的最小费用再
2016-05-08 19:56:07
1185
原创 bzoj2595: [Wc2008]游览计划
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2595思路：斯坦纳树斯坦纳树问题就是给你n个点的图，点或边上有权值，有k个点是关键点求使k个关键点联通且权值和最小的方案我们知道最后的结果一定是一棵树DP状态就是f[i][j]表示以i为根，关键点联通性为j(一个二进制数，1为以联通，0为未联通)那么转移有两种枚举子
2016-05-08 19:47:25
536
原创 bzoj4262: Sum
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4262思路：写这题之前推荐先写uoj164也是维护一个函数性质标记题解见：http://www.cnblogs.com/clrs97/p/4824806.html#include#include#include#includetypedef long long ll
2016-04-26 10:41:54
607
原创 uoj#164. 【清华集训2015】V
传送门：http://uoj.ac/problem/164思路：科学的题面：请你写一个数据结构支持以下功能：1：区间[l,r]加x2：区间[l,r]减x并和0取max3：区间覆盖4：单点询问5：单点历史最大值询问线段树维护分段函数标记就是一个二元组(a,b)表示标记生效后x=max(x+a,b)1操作就是打(x,0)的标记2就是(-x,0)3
2016-04-26 10:37:17
759
原创 bzoj2653: middle
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2653思路：陈老师的题可持久化线段树的又一种应用对于每次询问，二分答案我们怎么知道它是大于中位数还是小于中位数呢？我们把每个小于它的赋成-1，大于等于赋为1查询左端点在[a,b]右端点在[c,d]的区间的最大子段和若小于0，则偏大，大于等于0，偏小或者正好我们建
2016-04-26 10:14:43
356
原创 APIO2015&2014题解
传送门：似乎uoj都有思路：APIO2015：巴厘岛的雕塑：看到位运算，又要求结果最小，最外层肯定是个从高位到低位的按位贪心这里有两个部分分，task1:Ntask2:N先考虑task1令sum[i]表示雕塑权值的前缀和假设我们考虑到了第bit位那么我们怎么知道在前面位数满足要求的前提下，当前位能否是0DP即可设f[i][j]表示前i
2016-04-26 10:03:20
1490
原创 bzoj1975: [Sdoi2010]魔法猪学院
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1975思路：可以用A*做，但是要手写堆或者用pb_ds的堆，不然会被卡空间（原题256M，bzoj64M...）设出发点为S，结束点为T，边权为val(e)，边的出发点为head(e)，到达点为tai(e)也可以用论文方法，参见俞鼎力的《堆的可持久化和k短路》论文首先我
2016-04-22 16:30:18
938
原创 bzoj1598: [Usaco2008 Mar]牛跑步
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1598思路：裸的k短路，直接用A*+堆即可A*就是引入一个估价函数h(x)=f(x)+g(x)优先选择估价小的去搜索f(x)就是当前到的x已花费代价g(x)就是估计x到终点还要多少代价这里f(x)就是出发点S到x的距离g(x)就是x到终止点T的距离g(x)可
2016-04-22 15:51:48
809
原创 bzoj2809: [Apio2012]dispatching
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2809思路：很明显忍者之间的关系是一个树形结构先自底向上枚举管理者x，那么根据题意，我们就要从x的子树中选择尽量多的忍者，且工资总和不超过m用一个可并堆到一个点x，就把它的儿子节点的可并堆并起来显然优先选工资低的，那么维护大根堆，不停地删堆顶，直到工资满足预算即可#
2016-04-22 15:32:30
411
原创 bzoj1455: 罗马游戏
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1455思路：左偏树练习题用并查集维护连通，然后开个数组记录每个人是否已被杀死，用可并堆支持合并和求最小值左偏树是一种支持合并的堆，写起来比手写堆还要短...只有一个操作，merge(a,b)，就是把a，b合并...具体构建参见论文：http://wenku.baidu.
2016-04-22 15:13:35
354
原创 bzoj4540: [Hnoi2016]序列
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4540思路：又是莫队....我们发现左右端点移动时，只会增加或删除某个点开头或结尾的区间先考虑右端点从r移动到r+1令p为[l,r]中最小值的位置那么它会对新加的区间中的p-l+1个区间产生a[p]的贡献另一些左端点在[p+1,r]，右端点是r+1的区间怎么统计呢？
2016-04-20 20:17:33
1233
原创 bzoj4538: [Hnoi2016]网络
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4538思路：首先二分答案K那么对于每个询问我们只要判断权值大于K的路径的交是否都过x即可路径的交还是路径，路径交满足结合律拿个线段树维护一下即可，以权值为关键字，每个点记录该段区间的路径交二分时在线段树上二分即可。如果lca用倍增求，复杂度是O(nlog^2n)链交
2016-04-20 19:42:07
1076
原创 bzoj4537: [Hnoi2016]最小公倍数
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4537思路：把边按a排序，每sqrt(m)分一组然后把询问按b排序，把在这组及以前的边按b排序把这些边用并查集一条一条插入并维护零散的部分暴力插入并记录，做完后暴力撤销注意：并查集不能路径压缩，否则无法撤销回去#include#include#include#in
2016-04-20 19:35:27
1534
原创 bzoj4539: [Hnoi2016]树
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4539思路：首先把大树缩点，一个点代表一次操作复制的子树两个点之间的边权值就是两个子树的根在大树中的距离，这个可以在原树中用倍增求出至于从大树标号转成原树标号，就相当于求子树内编号第k大的点的编号，用可持久化线段树即可。询问的话，就先把两个点移到对应复制操作的子树的根，计算距离
2016-04-20 19:25:06
1053
原创 bzoj4542: [Hnoi2016]大数
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4542思路：当P！=2或5时，显然10^x%P!=0把后缀模P的值搞出来于是问题就便成询问区间内%P为x的分别有多少个这个再套一个莫队就可以了。#include#include#include#include#includeconst int maxn=100
2016-04-19 12:05:13
691
原创 codechef CBAL
传送门：https://www.codechef.com/problems/CBAL思路：先求一遍出现次数前缀和，我们只管每个字母出现次数奇偶性，所以可以把状态压缩一下，离散化之后就只有最多n个状态对于子串[l,r]如果s[l-1]==s[r]，那么[l,r]合法f 前i块，状态j，出现下标k次方之和，ans 块i到j的答案完整的块直接得答案，外面剩余的一个一个加进来假设现
2016-03-16 08:36:24
554
原创 bzoj3680: 吊打XXX
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3680思路：puts("nan nan");得AC爬山就够了，膜你退火也可以。膜你退火就是在膜你一个退火的过程，他和爬山的区别就在于，它多了一个温度参数
2016-03-11 09:18:28
1256
原创 jsoi2015R2D2和R3D1测试总结
传送门：然而并没有...这两天测试状态比较奇怪，前面1.5h-2h完全不知所措，一脸茫然，感觉自己吃枣药丸后面才发现有很多题可捉的，并没有想象的那么难，但是时间已经不充裕了...R2D2T1：不知所措数学题一开始总想着有什么DP可以拿一些部分分然而连30分DP都不会....咦，好像有大样例那就找一发规律妈呀真是2^(nk)快速幂完事....
2016-03-06 20:48:01
769
原创 bzoj3779: 重组病毒
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3779思路：RELEASE操作怎么给人一种access的感觉呢？“如果新变种在感染过程中尚未销毁过这类旧变种，需要先花费1单位时间分析旧变种，才能销毁”这不就是到根统计虚边条数+1吗继续看下去RECENTER好像就是换根，换完了正好要access一下REQUEST询问子
2016-02-28 17:36:28
1352
原创 bzoj3159: 决战
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3159思路：题解与标程在此：http://tieba.baidu.com/p/2307619154首先链翻转显然不能直接在lct上打翻转标记，那样是在翻转链的深度，不是翻转链上的值于是就有了一种做法，写两个splay，一个维护权值，一个维护形态每棵形态splay和对应值spla
2016-02-28 10:30:31
967
原创 bzoj1311: 最优压缩
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1311思路：很明显的二元组建图还是这个图，设与S相连表示设为V0，与T相连表示设为v1列方程，设有两个相邻的点ij，注意一组ij只能算一次，所以两个1/2就并成1了a+b=|A[i]-v0|+|A[j]-v0|c+d=|A[i]-v1|+|A[j]-v1|a+f+d
2016-01-21 16:06:42
367
原创 bzoj3894: 文理分科
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3894思路：令S为学文，T为学理对于额外的收入，新加一个点也可以用二元组建图来解决还是这个图，x表示一个学生，与S连通表示学文，与T连通表示学理y表示新加的点，用来计算同时学理的额外收益，与S连通表示不要额外收益，与T连通表示要额外收益先算出总收益，在用最小割减去即
2016-01-21 14:21:57
686
原创 bzoj2039: [2009国家集训队]employ人员雇佣
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2039思路：还是二元组建图先求出总收益，再解方程建图求最小割题意有些坑c+d=w[i]+w[j]a+b=2*E[i][j]a+d+f=A[j]+3*E[i][j]b+c+e=A[i]+3*E[i][j]然后就没有然后了#inclu
2016-01-21 11:02:54
797
原创 bzoj2127: happiness
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2127思路：二元组建图要求的就是i选A就有A[i]收益，选B就有B[i]收益，j相同，两两之间如果同时选A就有A[i,j]的额外收入，同时选B就有B[i,j]的额外收入先把收益加起来，在减掉最小损失即可最小损失就可以用上面的构图，解出方程赋相应的边权求最小割即可
2016-01-21 10:57:18
629
原创 bzoj3661: Hungry Rabbit
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3661思路：网络流，但这不是标算，bzoj为了大概是为了让网络流过才把时限开到100s建两个源点,S向S‘连容量为K的边，这个是为了限制总流量的每天的每只兔子拆成两个点，之间连1的边进行点容量限制，表示这只兔子今天只算一只（不限制后面会出问题）每只兔子向下一天的自己连1的边
2016-01-21 10:45:37
524
原创 bzoj1449: [JSOI2009]球队收益&&bzoj2597: [Wc2007]剪刀石头布
剪刀石头布就难想一些首先是补集转化总共有C(n,3)个三元组
2016-01-21 10:23:21
693
原创 bzoj1927: [Sdoi2010]星际竞速
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1927思路：拆点拆成x和x'S向x'连边，容量为1，费用为定位时间S向x连边，容量为1，费用为0对于原图的边u->vu向v‘连边，容量为1，费用为时间x’向T连边，容量为1，费用为0；跑一遍费用流即可#include#include#include
2016-01-21 09:33:29
920
原创 bzoj3504: [Cqoi2014]危桥
传送门：http://http://www.lydsy.com/JudgeOnline/problem.php?id=3504思路：证明见此http://blog.csdn.net/wzq_QwQ/article/details/46546977#include#include#include#includeconst int maxn=110,maxm=10010,inf=1
2016-01-19 09:32:13
702
原创 bzoj1066: [SCOI2007]蜥蜴
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1066思路：很显然的点容量限制，那就拆点，从一个点向另一个点连点容量限制的边S向有蜥蜴的点连1的边，两两可达的点连边，可以出去的就向会连边#include#include#include#include#includeconst int dx[]={0,0,1,-1};
2016-01-19 09:30:02
288
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人