- 博客(96)
- 收藏
- 关注
RSS订阅原创 【cf666e Forensic Examination】（后缀自动机＋线段树合并）
这个题确实思维方向非常重要！如果用后缀数组做，就转化为区间众数，一脸不可做。（当然莫对＋堆还是可以的。。）这个题应该用后缀自动机或者后缀树来做。这样问题就是子树众数，就可以用线段树合并一个log搞定。（为什么我一个log比别人一个log+一个根号还慢啊）#include#include#include#include#include#define rep(i,a,b) for
2016-07-06 16:39:48
1163
原创 【UOJ #210】【UER #6】寻找罪犯 （2-SAT）
考试的时候死磕第一题去了，这个题没多想，其实是个裸题。。2-SAT模型显然，注意要对每个人是否是骗子，每句话是否是真话都要建点，然后暴力连边裸上就可以得40分了。瓶颈在于这种关系：若一个人说的某一句话是假话，则他说的其它话都是真话。这个暴力连边是不合适的，我们只需要增加两个信息，表示一个人的前i句话都是真话，以及后i句话都是真话，所以一个点是假话的话向他的前缀和后缀为真话连边就好了。看了下
2016-07-02 23:26:49
1025
原创 【UOJ #209】【UER #6】票数统计
做比赛的时候完全没想到怎么处理同时有前缀和后缀的限制。。智商不够啊QAQ。。其实根据数据范围就能猜出来，因为直接做的复杂度O(n)很明显n不可能给5000，所以应该枚举一下总人数，这样对后缀的限制就转化为对前缀的限制了。。然后x=y的限制取最大那一个，然后简单容斥一下即可。。这个题确实妙啊，几个转弯都很巧妙。。这个题复杂度应该写成Tmn的，然后我偷懒写了个桶，就是Tn^2的，常数大了一点。。
2016-07-02 23:19:01
535
原创 [Noi2016十连测第二场]幻想（后缀平衡树）
题意：给一个字符串，三种操作，末尾插入一个字符，弹出末尾的字符，查询区间内一个给定字符串出现了多少次。卡常神题。。500万的数据规模什么鬼。。假如没有区间限制，就是后缀平衡树的裸题。查询一个字符串s出现了多少次，就是在后缀平衡树上找出由于替罪羊的删除不是很方便，这里可以用treap，删除一个节点的时候直接重构这个节点所在的子树。以前重构操作都是直接写在rotate里面的，用起来非常方便
2016-06-17 12:19:11
1525
原创 [BZOJ3864]Hero meet devil（状压dp）
题意：给一个长度这个题让我想起了之前做过的一个数位dp，问有多少个数的数字组成的最长上升子序列长度为x。那个题中显然最长上升子序列不超过10，我们用状态压缩来模拟那个做lis时的栈即可。这个题|S|#include#include#include#include#define rep(i,a,b) for(int i=a;i<=b;++i)#define erp(i,a,b)
2016-06-14 20:16:57
1640
原创 [BZOJ3295][Cqoi2011]动态逆序对（分块重建）
题意：一个排列，每次删除一个数，求每次删除后的逆序对的数量。正确姿势请移步 http://blog.csdn.net/u011542204/article/details/50571409将操作分成根号M段，然后每段内的操作按下标排序，计算它前面的比他小的和它后面的比他大的。有一个问题就是同一个块当中的没有被减掉，由于一个块内只有根号M个操作，暴力减掉即可。如果要在线的话将那个排序变成
2016-06-02 11:13:01
737
原创 COI2016 Palinilap（manacher+后缀数组）
题意：给出一个小写字母组成的字符串，修改一个字符（或者不改），使得字符串中所有回文串的长度之和最大（本质相同的回文串算多个）。好神的题。。题意简单易懂但是做起来非常麻烦。。以后如果只是求求lcp之类的最好写二分+hash，写个后缀数组简直是自讨苦吃。。很显然回文串的长度之和就是manacher算法中半径数组之和。修改一个字符有可能破坏一些回文串，也有可能引入一些新的回文串，只要我们
2016-05-31 22:04:18
637
原创 [BZOJ2162]男生女生（二分图带权独立集+dp）
题意：懒得写了，比较麻烦。强行嵌套的题真没意思。。开始我看见数据范围n=50，第一问求什么完全子图，我以为是个搜索减枝，然后第二问那个dp我想了想，列了几个方程发现不是很对，然后又没有部分分，我就弃疗了。。其实想一想应该是想得出来的，主要是考试的时候写了第二题的很麻烦的做法，被折腾得没精力了，就没怎么想。。第一问其实很简单，二分图完全子图是P类的。我们求出这个二分图的补图，补图中的边就
2016-05-30 22:01:52
865
原创 [BZOJ2161]布娃娃（扫描线+线段树）
题意：若干个点，对每个点求能覆盖住它的线段的权值的第k大。强制在线的题做多了，作死写了个主席树套平衡树，两个log常数炸了，只得了40分暴力分。正解显然扫描线+线段树，把每个线段拆成起点和终点，代表插入和删除，线段树维护第k大权值就好了。。
2016-05-30 21:51:49
924
原创 [BZOJ2160]拉拉队排练（回文树）
题意：求一个字符串的长度前k的奇数长度回文串的长度的乘积模一个数。和APIO那个回文串的题差不多，可以先manacher搞出所有本质不同的回文串，再用后缀数组查查出现了多少次即可。这里偷懒写的回文树，注意跑完了之后那个cnt需要沿着后缀链接向上传递一下。注意那个K是10^12不是10^9。。。开的int丢了5分，还好出题人比较良心只有一个点的K超了int。#include#inclu
2016-05-30 21:44:23
621
原创 [BZOJ2629]binomial (高精度+Lucas定理+离散对数+FFT)
题意：对于给定的n和p，求对于所有的0注：p虽然要输入，但是题目标注了所以测试点的p是固定的。首先需要用正确的姿势理解lucas定理，比如求C(n,r)%p，就是将n和r分别转换为p进制，然后依次算组合数乘起来。n是一个高精度数，求C(n,r)的过程中，n不断模p得到的数（即n的p进制表示）是固定的。就是长这样：n0!/((n0-k0)!*k0!) * n1!/((n1-k1)!*k1
2016-05-29 23:11:11
803
原创 CodeChef FNCS（分块）
分成根号n块，每一块上记录每个点在这一块出现了多少次，以及这个块当中当前f函数的和。这一部分可以用n*sqrt(n)的时空复杂度求出来。修改的时候扫描每一个块，对每个块可以O(1)求出这次修改后这个块的和。回答询问的时候，对于整块中的和，直接读块中的信息，对于剩下的部分暴力即可。注意暴力求一个点的f值需要维护一个动态前缀和，即sum(r[i])-sum(l[i]-1)。这道题上面修改的数量和查
2016-05-26 20:55:54
813
原创 [BZOJ2122]工作评估（分块）
题意：给序列D和L。假设有一个初始价值x0，则经历第i天后价值变为min(x0+D[i],L[i])，记F(i,j,x0)表示以初始代价x0依次经过第i天到第j天后的价值。每次询问给出l,r,x0，求max(F(i,j,x0))，其中[i,j]是子串[l,r]的子串。这个题的最重要的性质在于：一、对于a>=b，F(i,j,a)>=F(i,j,b)；二、记G(i,j)为F(i,j,inf
2016-05-26 10:43:20
1339
原创 [BZOJ4605]崂山白花蛇草水（主席树套kd-tree）
题意：两种操作，在二维平面插入一个点及其权值，查询矩形区间第k大，强制在线。之前考试考过一个矩形区间第k大的题。。当时想了各种树套树套树，算了算复杂度都没有暴力快。。后来憋了个kd-tree套主席树，就是把若干个kd-tree上的节点上的主席树弄来一起走，时间复杂度logn*sqrt(n)，空间复杂度俩log（由于那个题是离线的，我当时写的kd-tree上自底向上的线段树合并，所以实际空间复杂
2016-05-24 22:55:18
1975
原创 [BZOJ2117][2010国家集训队]Crash的旅游计划
题意：给一棵树，求从每个点开始走向其它n-1个点的距离中第k大值。又是第k大简直cqoi既视感23333其实我一开始看到这个第k大就想起了cqoi那个k光滑数，那个题是用持久化可并堆做dp，然后这个题我就想能不能写个主席树合并然后用主席树跑树dp来表示每个点走到其它点的距离什么的，然后发现不可做。。然后再想了想，发现就是紫荆花弱化版，然后看了看时限，150秒，就觉得非常靠谱。考虑二
2016-05-21 12:39:15
1573
原创 [BZOJ2145]悄悄话
题意：给出用凯撒加密法加密后的密文，求原文。这道题让我想起了三年前做的唐教出那个提交答案题，那道题的加密是一个全排列，破解起来非常困难，当时和lzm他们一群人在机房开黑搞这题搞了一整场考试的时间，得了60分23333这个题凯撒加密的方法只有26种，可以枚举判断。其实APIO上讲课时提到过这个题的。但是我看了题目后发现他保证句子长度大于等于3，又没有保证是从哪里截取的自然英文还是出题人刻
2016-05-19 22:05:53
756
原创 [BZOJ4521][Cqoi2016]手机号码
题意：一个手机号码被定义为幸运的当且仅当其中不同时出现4和8，并且要有连续三个一样的数字（slj!!!）。求一个区间内合法的手机号码数量。CQOI考试的时候我写了个爆搜乱搞过的。。。如果这题的乱搞没写出来我就滚粗了。。。正确的姿势是数位DP，设6维状态，分别记录当前是第几位，当前位是哪个数字，当前数字连续出现了几次（超过3次视作3次），是否已经出现过三连击，是否出现过4，是否出现过8。dp
2016-05-16 19:13:17
537
原创 APIO2016游记
刚到北京时我们打了个出租车，然后就被司机坑了。本来路过了80中，我想酒店应该近了，然后就开始记路，结果连拐了十多个弯然后我就记不住了，到酒店被收了70多块钱，结果听说另一辆车只收了40多（什么玩意）。然后入住，感觉酒店环境还不错。有一个挺萌的小哥来和我们坐一个电梯，和我们说了几句话，我瞟了一眼他的胸牌——卧槽mxh大爷！！！当时吓得我嘴巴就张开了。。。 然后我们去80中，结果发现只
2016-05-09 15:40:03
953
原创 数据 (cdq分治)
题意：维护二维平面上的点集，支持插入一个点，查询点集中的点到指定点的最小、最大曼哈顿距离。不强制在线，n,m考试的时候没怎么动脑子，直接上分象限讨论+线段树套平衡树，花了2h写了7k结果常数太大只得了50分。为了降低常数，采用cdq分治。有一个特殊的技巧，就是不需要按象限分类，只讨论x,y都比当前小的情况，其他情况可以将坐标轴对称四次得到。按x坐标排序，然后按时间来划分，用树状数组来维护y
2016-03-07 16:55:56
552
原创 [BZOJ2888]资源运输 (LCT+启发式合并)
很多个连通块，每次合并两个，保证是森林。一个连通块的代价为所有节点到该块的重心距离之和。动态不停连边，询问森林中各连通块代价之和。这题确实有很多地方都很巧妙，看着claris的题解和程序才写了出来，涨了不少姿势。。首先如果已知每个树的重心，用LCT的link直接将两棵树合并的话不是很好求出新树的重心。但是如果一次只添加一个叶子，可以保证重心要么不变，要么向新加入的叶子的方向移动一下。因此我
2016-03-03 21:46:41
1207
原创 [BZOJ2908] 又是nand （树链刨分）
题意：定义位运算与非：a nand b = not(a and b)。这个运算不满足交换律，结合律。给出一棵树，支持询问0依次nand这条路径上所有点权得到的结构，或者单点修改。Claris讲题的时候我就把这题秒啦哈哈哈。。线段树上记录0/1从左往右、从右往左经过这个点的时候会变成什么。。然后线段树上的询问分为从左到右，从右到左两种。树上的询问分为从下到上，从上到下两种。树上从下到上好办，不停
2016-03-02 22:51:51
1393
原创 [BZOJ4381][POI2015]Odwiedziny （树链刨分/倍增）
题意：给定一棵树，边长为1，点带权。处理M个询问，格式为u,v,c，求从u走到v每次跳c步经过的点权之和，最后一步若不足c条边则直接走到v。N,M哈哈claris讲课的时候我直接把这题秒了。。分成c>=sqrt(N)和c=sqrt(N)，则显然步数不超过根号N步，然后模拟即可，如果是用的倍增的话一次询问就是sqrt(N)logN。不过claris上课讲了一个根号就能回答的方法，但是我忘啦。。对
2016-03-01 19:56:25
1076
原创 [BZOJ4383][POI2015]Pustynia （拓扑排序）
题意：给定一个长度为n的正整数序列a，每个数都在1到10^9范围内，告诉你其中s个数，并给出m条信息，每条信息包含三个数l,r,k以及接下来k个正整数，表示a[l]...a[r]里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大。任意构造出一组满足条件的方案，或者判断无解。n定义一条有向边(u,v,w)表示a[u]-w>=a[v]，对于每条信息，枚举属于那k个数中的某个数i向每个
2016-03-01 00:46:19
1315
原创 BNUOJ51279 组队活动（cdq分治&&NTT）
题意：N个人进行组队，每个队不超过M人，求方案数模998244353。这个递推方程我都没想到。。枚举当前这个人所在队伍剩余人数j，则f[i]=Σf[i-1-j]*C(i-1, j)，把组合数展开后发现是个卷积的形式，但是不能直接NTT，因为之前的f值没有求出来。套用cash一题的策略使用cdq分治解决，先递归左边，再用左边的更新右边，再递归右边。注意NTT需要补成2的次幂，常数有点大，但只要保
2016-02-27 22:11:05
703
原创 bzoj4361 isn（树状数组优化DP）
要点：一个不合法的状态一定是由一个长度多1的不下降子序列转移来的，直接减掉即可。然后就转化为求长度为i的不下降子序列个数。定义f[i,j]表示以i结尾的，长度为j的不下降子序列个数，则f[i,j] = sum(f[k,j-1]), k#include#include#include#include#define rep(i,a,b) for(int i=a;i<=b;++i)#d
2016-02-27 17:49:54
1075
原创 hdu5290 Bombing plan(树DP)
题意：给一棵树，边长都是1，每个点有个点权w[i]，表示这个点能覆盖与其距离多远的点。选最少的点覆盖树上所有点。N树DP好久都没练了，并且感觉以前也不是特别擅长写树DP，见的模型也不多。以前的树DP基本都是多叉转二叉，记录向上若干节点的信息，树背包等套路，这道题不一样，因为是无根树，每个点不仅会辐射他的父亲，还对他儿子有影响。我们要开两个DP数组,f[i][j]表示i节点子树全部被覆盖，且与其
2016-02-27 16:00:15
414
原创 BZOJ2310 parkii （插头DP）
题意：给一个矩阵，让找一条简单路径使路径和最小。N如果矩阵全是正数的话枚举起点终点跑跑费用流就好了，省选的话一定会给这个部分分。考虑用括号序列的插头DP，增加一个3号表示起点和终点那种插头。注意这个1表示左括号，2表示右括号，3表示其它这个是有讲究的，可以用xor来很方便地转化。分类讨论比较繁琐，参考了一下claris的才完整地写出来。但是有些细节的处理上要注意和回路的区别。还有就是要
2016-02-25 00:34:51
878
原创 ants(插头DP)
有一个N*N的矩阵，需要用若干循环将其铺满，使得每个格子都处于一个循环上，求方案数，逆时针和顺时针的循环算作不同的方案。n插头DP，用0表示空，1表示插向轮廓线下侧的插头，2表示插向轮廓线上侧的插头。一共有9种转移，分类讨论即可。实现的过程中可以用4进制来代替3进制。由于我直接用的city那道题的插头DP模板，结果N=8以上就卡了很久。注意换行的时候不能直接移位，因为会产生不合法的状态，要
2016-02-24 17:18:56
423
原创 BZOJ4310 跳蚤（后缀数组+二分答案）
题意：将一个字符串分成不超过K段，使得这K段中，所有子串中字典序最大的最小。即每一段当中取一个最大的子串，再在所有段的最大子串再取一个最大值，让这个最大值最小。长度10W。最大值最小，明显二分，但是乱二分是没前途的。要对所有本质不同的子串排名后二分，也就是你要能求出你二分出的第mid大的子串。这个可以用后缀数组来搞，先求出sum(n-sa[i]-height[i])作为不同子串的总数，求第
2016-02-24 00:41:40
2147
原创 hdu5372 Segment Game (树状数组)
题意：每次插入一条线段或删除之前一条线段，每次操作线段长度递增，求插入一段线段时有多少线段被它完全覆盖。由于保证线段长度递增，我们可以用右断点在合法区间内的减去左端点不在合法区间的，可以用树状数组分开维护。下标需要离散化。下标可以是负数，这读入优化坑了我一个小时。。#include#include#include#include#includeusing namespac
2016-02-24 00:28:01
342
原创 [BZOJ4259] 残缺的字符串 （FFT）
题意：定义*号可匹配任意字符。给出A串，B串，求A串在B中完全匹配的所有位置。将*号视作0，则两个等长的串可匹配当且仅当Σ(a[i]-b[i])^2*a[i]*b[i]==0。将A串和B串最左边对齐，每次上式都要重算一次，不科学。所以讲A串先反转过来然后补上*号，就是卷积啦。原来的万径人踪灭一题当中用FFT来求了回文串，这里又能玩字符串匹配，真是太6了。#include#includ
2016-02-21 17:42:54
2258
原创 BZOJ3125city （插头DP）
题意：就是上一道formula的基础上限定某些格子只能竖着通过，某些只能横着通过。还是括号表示。这个转移的时候特判一下就好了，具体实现基本和上一题一样。#include#include#include#include#includeusing namespace std;#define LL long long#define clr(a) memset(a,0,sizeof
2016-02-16 23:26:28
857
原创 ural1519Formula 1 （插头DP）
题意：n*m的地图，'*'代表不能走，'.'代表可以走。求哈密顿回路的数量。n,mclaris讲了插头DP，感觉都差不多听懂了，但是实现还是有一定困难，花了3个小时才写出来我的第一篇插头DP的程序。感觉就是维护一个轮廓线，每一格压位表示，然后DP过程中每一次对这个轮廓线的维护都是O(1)的。这是用括号表示的，0表示空，1表示左括号，2表示右括号。注意分类讨论就行了。实现的时候还是要ha
2016-02-16 23:24:14
576
原创 【bzoj3171】[Tjoi2013]循环格 （费用流）
题意：N*M的矩阵，每个格子有一个LRUD标记表示走到这个格子后下一个格子往哪个方向走。走出边界后自动到另一端。问至少修改几个格子使得在任意一个格子上开始都可以最后回到自身。N,M这个15真是迷一样的数据范围。。搜的话太大了，DP的话太小了。。然后我就想是不是各种状态很复杂的或者是状压DP，想了差不多15分钟没想出来。。真是太蠢啦！！以前做过一道题是要让一个有向图中每个点处于k个环内，而这道题
2016-02-14 17:08:15
530
原创 BZOJ1858 序列操作 [treap,避免双标记的特殊技巧]
题意：给一个01序列，有5种操作：0 L R 将[L,R]之间的数字都变成0；1 L R 将[L,R]之间的数字都变成1；2 L R 将[L R]之间的数字都取反；3 L R 询问[L R]之间1的个数；4 L R 询问[L,R]之间连续1的个数最大是多少.第一眼：这sb题。。第二眼：这sb题。。第三眼：哎呀卧槽这儿取反和赋值俩标记咋搞？？？大致脑补了一下，
2016-02-11 21:39:43
467
原创 [CQOI2015]任务查询系统 (可持久化treap)
题意：有n个任务。每个任务描述为(s,e,p)表示起始、结束时间、优先级。M次询问，查询i时刻优先级排前k的任务的优先级之和。如果k超过那个时刻运行任务的总量，输出那个时刻所以优先级之和。强制在线。s,e哎呀我去这么裸的主席树为什么去年省选只有一个人A了？开始看做插入一个数，结束看做删除，询问就是问第i个版本中前k个之和。先把p离散化，然后扫描一遍用主席树来维护p值。好像没什么坑点
2016-02-05 23:20:17
1543
原创 [hdu4453]looploop [treap/splay]
题意：给定一个循环序列，支持以下操作：区间增加，区间翻转，单点插入/删除，移动光标，询问光标所指的位置的值。首先一眼看出可以用线性数据结构（平衡树）来维护。然后这些操作都很基础。但是要注意光标怎么处理。可以维护一个k记录它指向第几个，但是这样在区间操作时候可能区间分别位于这个序列的两端（因为你破环为链了）。比较好的方式是每次人工使得光标指向的元素位于序列的最左端。这种题以前都是写的spla
2016-02-05 22:58:02
521
原创 WC2016酱油记
这次WC2016真有趣啊！第一课堂讲的东西普遍偏难，很难保持跟上思路，于是就当了解来学了。picks的多项式，太深奥了，接触到了一些奇葩复杂度的算法。正统的有FFT，NTT，不过不好的是取模比较麻烦。有个karatsuba算法，N^1.585的复杂度，但是是基于分治实现的，可以很方便地取模。然后有关于正规语言与自然语言处理的课。学了一下正则表达式，然后之后的都很难听懂了，大致知道自然语
2016-02-02 09:23:18
681
原创 [BZOJ3295] [Cqoi2011]动态逆序对 (树套树)or(CDQ分治)
题意：N个数的排列，M次操作，每次求当前的逆序对数量并删掉一个数。先说一下cdq分治做法。(5960kb,1.4s)网上很多题解，我都看不懂（其实很多人的程序几乎是一样的，就改了一下变量名），然后就自己硬着头皮想了这道题，基本是独立做出来的，做出来之后竟然1A，简直愉快。不过我太辣鸡了想了半天才发现这本质上是一个三维偏序，分别是时间，下标，数值，记为(t,x,y)。我们可以把删
2016-01-23 22:16:17
5020
7
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人