Mima_Reincarnation-CSDN博客

原创 BZOJ4384: [POI2015]Trzy wieże 记忆化搜索

http://www.lydsy.com/JudgeOnline/problem.php?id=4384 dp数组表示的是当前有两个数量相等，末尾字符是这两个中的一个且与它前面的字符不等，第三种的数量比这两个少1的情况。主要是基本相同的代码抄三遍所以看着比较长。。。时间复杂度o(n)。#include<cstdio>#include<algorithm>#define gm 1000005u

2017-06-28 21:16:47 1043

原创 BZOJ4381: [POI2015]Odwiedziny 分块长链剖分

http://www.lydsy.com/JudgeOnline/problem.php?id=4381 若步长小于sqrt(n)则可以预处理每个点走某种步长走到跟的权值和然后减去LCA上面的部分;若步长大于sqrt(n)则暴力走，为了避免LCA算重，可以先防止两个点走到LCA，然后再特判能否走到LCA上。第一种情况要注意不要计算走过

2017-06-09 19:03:48 875

原创 BZOJ4866: [Ynoi2017]由乃的商场之旅莫队

http://www.lydsy.com/JudgeOnline/problem.php?id=4866 询问一个字符串区间内有多少子区间重排后能形成回文串。由于字符集只有26，可以给每个字母分配一个2的幂次作为权值，则相当于询问区间异或和是否为2的幂次或0 直接很难维护，那么考虑莫队，维护一个桶记录当前区间内所有前缀的异或和，若在前端插入删除则打上全局标记，然后每次插入删除时枚举每个2的幂次

2017-06-08 20:21:37 924

原创 BZOJ4865: [Ynoi2017]由乃运椰子分块

http://www.lydsy.com/JudgeOnline/problem.php?id=4865 写题面的人语死早。。。S为空的话也是要把元素插入进去的（要不然岂不是一直为空），然后每次异或的是上一次答案的相反数。。。还有莫名其妙的标点缺失和语句重复。。。于是就是在问能拆分成最少多少个单调增的序列，显然就是众数个数，所以相当于查询区间众数。传统做法就是分块，预处理每两块之间

2017-06-08 20:06:40 806

原创 BZOJ4012: [HNOI2015]开店重链剖分可持久化线段树

http://www.lydsy.com/JudgeOnline/problem.php?id=4012 两点间距离：深度之和-2×LCA深度 http://blog.csdn.net/mima_reincarnation/article/details/54024494 ORZ16年我就会的东西现在怎么忘没了。。。那题是离线排序做，那么对于这题用可持久化线段树来维护树链剖分就可以了。#inc

2017-06-08 19:53:25 949

原创 BZOJ3672: [Noi2014]购票树分治斜率优化

http://www.lydsy.com/JudgeOnline/problem.php?id=3672 树上的CDQ分治。和常规CDQ思路相同，一个点的可行决策点是从这个点往上连续一段，那么在分治过程中先递归重心往上的一块（包括重心这个点），再将其他点按可行深度排序，然后维护上面那些点的凸包来更新底下点的答案，最后分别递归底下的块即可。#include<cstdio>#include<cs

2017-06-02 21:06:57 431

原创 BZOJ3924: [Zjoi2015]幻想乡战略游戏动态树分治

http://www.lydsy.com/JudgeOnline/problem.php?id=3924 抓紧时间补上以前忘写的博客先考虑如何求出对于一个点，其它所有点到它的带权距离和，显然用树分治结构就可以动态维护，查询复杂度logn。由于时限宽松，可以考虑每次利用分治暴力求重心，方法是从根开始判断是否存在一个方向使得移动过去更优，有的话就跳到那层分治结构上。总复杂度n*log^2(n)#i

2017-06-02 20:57:03 362

原创 BZOJ4009: [HNOI2015]接水果 kdtree

网上一堆题解这里不再赘述奈何我连扫描线都写不动只好上kdtree了#include<cstdio>#include<cmath>#include<algorithm>#define gm 40001int n,p,q;int cmp;struct pnt{ int p[2]; pnt():p(){} pnt(int x,int y){p[0]=x,p[1]=

2017-05-29 09:07:26 483

原创 BZOJ4897: [Thu Summer Camp2016]成绩单 DP

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=4897 首先每一次取的代价是相互独立的，其次考虑对于值域相同的一段，拿走它的代价是一定的，所以凡是值域相同的一段都可以同等看待。那么可以设f[i][j][k][l]表示i到j，剩下的数值域是k到l的最小代价，注意不一定要把所有k到l内的数都剩下。转移时对于一个区间，枚举一个要扩张到的端点，把中间

2017-05-26 21:04:36 800

原创 BZOJ4899: 记忆的轮廓期望DP 决策单调性

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=4899 容易发现树形结构是骗人的。。。走到错误分叉的影响是可以预处理的常数，所以就相当于一个序列从头走到尾的问题，那么可以预处理出对于每个点若在这里存档则走到其他点的期望步数很容易想到f[i][j]表示走到第i个点，已经用了j个存档机会的最优值，那么枚举i前面的k进行转移，就是o(n*n*p

2017-05-26 20:12:48 860 1

原创 BZOJ4044: [Cerc2014] Virus synthesis 回文自动机

你要用ATGC四个字母用两种操作拼出给定的串： 1.将其中一个字符放在已有串开头或者结尾 2.将已有串复制，然后reverse，再接在已有串的头部或者尾部一开始已有串为空。求最少操作次数。 len<=100000 考虑最后一次2操作，那之后的字符都是暴力拼上去的。那么可以枚举每一个回文子串，算出拼出它的最少次数，然后加上总长度减它的长度来更新答案。那么考虑怎么算出每一个回文

2017-05-02 21:54:10 1225 1

原创重聚牛顿迭代

给出n和p，求最小的正整数x使得x!>p^q 有斯特林公式n!≈√(2πn)·(n/e)^n 取个log得log(n!)≈0.5*log(2*pi)+(n+0.5)*log(n)-n 然后log(p^q)=q*log(p) 不过二分是过不去的这个函数可以牛顿迭代，就是对于一个x，在函数上做切线，与x轴的交点作为下一次的x 复杂度是loglogn eps开到1e-5才能过，太低会WA

2017-05-02 21:36:55 585

原创 BZOJ4802: 欧拉函数 pollard_rho

题意：给出n，求phi(n) 温习一下太久没用过的板子。 miller_rabin：基于费马小定理a^p-1==1 mod p 和二次探测定理 a^2==1 mod p <==> a==1 or a==p-1 mod p 单次测试的正确率约为75%。 pollard_pho：设置两个初值相同的变量，每次平方后加上一个常数，一个变量一次走一步，另一个一次走两步，若gcd(p,abs(a-b)

2017-05-02 21:23:15 626

原创 BZOJ3879: SvT 后缀树虚树

有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n]. 现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍. 怕忘记虚树怎么写于是挂个板子题。 LCP长度相当于后缀树上LCA深度，对于每个点统计有多少点对以它为LCA即可。按DFS序排

2017-05-02 21:08:14 676

原创 BZOJ4584: [Apio2016]赛艇 DP

题意：长度为N的序列，每个元素可以在[ai,bi]间取值或者不取值，求有多少种不同的上升序列（不能都不取值） N<=500，元素范围1e9 容易发现取值只会形成2*n个区间，每个元素可以在某几段区间内任意取值记F[i][j][k]表示前i个元素，最后一段落在j这个区间，这个区间一共落了k个元素的方案数考虑转移，如果一个区间之前已经有k-1个，现在要加一个，由于取值是任意的，所以相当于把（

2017-04-27 20:39:12 660

原创 BZOJ1513: [POI2006]Tet-Tetris 3D 二维线段树

题意：有一个坐标系，每次将一个矩形内所有点的值改为这个矩形内最大值+一个数，求最后所有点的最大值 N<= 20000，坐标<= 1000 首先二维线段树由于不能下推上传标记所以只能解决资磁标记永久化的问题然后观察这个问题，由于值只能改大不能改小，所以一个后来的标记肯定不会使之前的标记非法，那么就是可以标记永久化的，对于每个点记录自身的标记与子树中标记的最大值，对于一个节点，有贡献的标记

2017-04-27 20:14:22 629

原创 BZOJ4167: 永远亭的竹笋采摘分块

题意：给定一个序列，将其分成K段，每段元素不得全相同，求sigma（每段中不同元素差值的最小值）的最小值 n<=50000，k<=1000，序列中元素<=n，序列随机生成既然序列是随机的，我们可以想到一个区间可能要延伸很长一段才会改变其中的最小差值，那么不妨将所有有贡献的点对都枚举出来（即：这个区间的两个端点之差是整个区间中最小的），问题就转化成了在数轴上有一些带权值的线段，选择K条不相交的使

2017-04-24 07:21:50 913 10

原创 BZOJ4166: 月宫的符卡序列 manacher

题意：给出一个字符串，定义每个回文子串的价值为所有出现位置的中点（偶数长度向下取整）异或和，求所有价值中最大的。每个点5组串，每个串长100W 看了一下别人的码长和内存感觉我写的肯定不是正解了。。。反正能过首先学过回文自动机的都知道一个串里本质不同的回文子串最多有n个但是回文自动机是从回文串的尾端拓展节点的，fail指针连接的是一系列尾部相同的

2017-04-19 16:19:12 1232

原创 BZOJ2788: [Poi2012]Festival 差分约束

有n个正整数X1,X2,…,Xn，再给出m1+m2个限制条件，限制分为两类： 1. 给出a,b (1<=a,b<=n)，要求满足Xa + 1 = Xb 2. 给出c,d (1<=c,d<=n)，要求满足Xc <= Xd 在满足所有限制的条件下，求集合{Xi}大小的最大值。 2<=n<=600, 1<=m1+m2<=100,000 再不写博客就快忘了*4 差分约束形如给定一系列x-y<=a

2017-04-18 16:47:02 627

原创 BZOJ2882: 工艺最小表示法

题意：给一个字符串，求所有循环同构串中字典序最小的。最小表示法模板题，再不写博客就快忘了*3 记字符串下标为0~n-1，设两个指针i=0，j=1，每次暴力比较找到二者的最大相等前缀长度，记为k，若s[i+k]#include<cstdio>#include<algorithm>#define gm 600001using namespace std;int n;int s[gm];

2017-04-18 16:22:33 817

原创 BZOJ4405: [wc2016]挑战NPC 一般图最大匹配

有n个球，用整数1到n编号。还有m个筐子，用整数1到m编号。每个筐子最多能装3个球。每个球只能放进特定的筐子中。具体有e个条件，第i个条件用两个整数vi和ui描述，表示编号为vi的球可以放进编号为ui的筐子中。每个球都必须放进一个筐子中。如果一个筐子内有不超过1个球，那么我们称这样的筐子为半空的。求半空的筐子最多有多少个，以及在最优方案中，每个球分别放在哪个筐子中。注：BZ上输出

2017-04-18 15:36:04 542

原创 BZOJ3435: [Wc2014]紫荆花之恋动态树分治替罪羊树

再不写博客就快忘了这题怎么做了*1 题意：一棵树，点有点权r，边有边权c，每次增加一个叶子后询问当前有多少点对满足dis(i,j)≤ ri+rj，强制在线 N<=100000 考虑树分治，设现在要统计路径经过k的所有点对，则条件变为dis(i,k)+dis(j,k)≤ri+rj，移项得dis(i,k)-ri≤rj-dis(j,k)，则可以在每个节点中用treap记录所有的dis(i,k)-ri

2017-04-18 14:11:06 1145

原创 BZOJ4399: 魔法少女LJJ treap

题意：有⑨种操作 1.新建一个节点，权值为x。 2.连接两个节点。 3.将一个节点a所属于的联通快内权值小于x的所有节点权值变成x。 4.将一个节点a所属于的联通快内权值大于x的所有节点权值变成x。 5.询问一个节点a所属于的联通块内的第k小的权值是多少。 6.询问一个节点a所属联通快内所有节点权值之积与另一个节点b所属联通快内所有节点权值之积的大小。 7.询问a所在联通快内节点的数量

2017-04-14 16:42:26 451

原创 BZOJ4543: [POI2014]Hotel加强版长链剖分

给一个树，问有多少三元组满足两两距离相等。n<=100000 长链剖分应用之一：o(n)统计以深度为下标的可合并子树信息在当前节点，令f(i)表示相对深度为i的节点个数，g(i)表示在子树外离当前点距离为i的点可以和子树内多少对点组成答案。每次新来一个儿子，枚举长度，用当前g和儿子f以及当前f和儿子g更新一遍答案，然后用两边的f来更新g，再将儿子的f和g推入当前f和g。注意顺序问题。

2017-04-11 17:42:01 1535

原创 BZOJ2082: [Poi2010]Divine divisor 数论

Description Tz耍畸形，在寂寞的时候玩一个游戏，他随便找出一个n，然后算出n的所有因子，最后找出一个最大的k，即有一个因子d的k次方为n的因子，那个因子d就是非凡因子啦。比如48他的非凡因子d就是2，k最大为4，因为16也是48的因子。一个整数的非凡因子可能不止一个，比如6就有3个：2，3，6（k最大是1）。 Input 有两行，第一行给出一个整数m(1<=m<=600)，第二行

2017-04-11 17:20:16 487

原创 BZOJ4811: [Ynoi2017]由乃的OJ 重链剖分

题意：起床困难综合征出到树上，带单点修改和区间询问很容易想到在线段树上维护每一位遍历所有操作后会变成什么，但是第一次交TLE了。。。然后发现我以前是不是写了假的《又是nand》。。。我说怎么跑得这么慢。。。维护上面说的这个东西并不需要64*2个bool变量，而是可以压到两个unsigned long long里，分别代表每一位输入为0和每一位输入为1。将两个合并：若输入为0，经过左变

2017-04-11 16:57:34 1655

原创 BZOJ4810: [Ynoi2017]由乃的玉米田莫队 bitset

题意：一个序列（长度100000），三种询问：区间内是否存在两个数和为x、差为x、积为x 莫队，用bitset维护当前存在哪些数，还得维护一个反转的bitset。和为x用反转bitset右移后和正bitset取交判定，差为x用正bitset右移后与正bitset取交判定，积为x直接暴力分解因数检查是否存在，总复杂度n*sqrt(n)+n*n/32 这复杂度怎么过去的。。。。BZ上各种不科学复杂度

2017-04-11 16:46:22 621

原创 BZOJ3864: Hero meet devil DP套DP

题意：给出字符串S，对于每一个i,问有多少个长度为m的字符串与S的最长公共子序列长度为i |S|<=15. m<= 1000. DP的瓶颈在于如果考虑保存LCP长度或者结束位置的话，会存在状态相同的串而转移方式不同。为了消除后效性，需要将最后一位与S所有位的匹配状态都记录下来。考虑LCP的转移方程: f[i][j]=f[i-1][j-1]+1 (i==j); 或 f[i][j]=max(f

2017-04-11 16:36:53 620 2

原创 BZOJ4197: [Noi2015]寿司晚宴状压DP

题意：把2~n这些数分成两个可空集合，要求两个集合中任取一对数都必须互质，求方案数 2≤n≤500 比较显然的是可以把每个数分解质因数，相当于两个集合中不能存在同一质因数。但是质因数个数可能很多，并不好设状态。注意到每个数中最多只有一个大于等于根号n的质因子，而小于根号n的质数只有8个，那么将所有数按照大质因子分类，规定每一类最多只能被一个集合选，就可以把前八个质数状压来表示状态了。

2017-04-11 13:54:11 440

原创 BZOJ3944: Sum 杜教筛

杜教筛，用于在n的2/3次方的时间复杂度内求某些积性函数的前缀和。记目标函数为f(i)，前缀和为F(i) 令g(i)=sigma(d|i) f(d) G(i)为g(i)前缀和 G(n)=sigma(i=1~n) g(i) =sigma(i=1~n) sigma(d|i) f(d) =sigma(d=1~n) f(d)*(n/d) =sigma(i=1~n)

2017-04-11 13:30:06 386

原创 BZOJ3876: [Ahoi2014]支线剧情线性规划

题意：给一个DAG，每条边有费用，每选一次就要付出这个费用，求从1号点出发的若干条路径将所有边都覆盖的最小费用。线性规划方程：设每条边的选取次数为变量。对于每个变量：大于等于1 对于每个点：所有连向这个点的边的经过次数之和大于等于这个点连出的所有边经过次数之和。最小化：sigma（每条边经过次数*费用）可以用对偶原理获取初始解，但这样矩阵是m*m的，听说过不了。对于每个变量x，

2017-04-10 20:04:04 785

原创 BZOJ4200: [Noi2015]小园丁与老司机最小流

题意：平面上有N（N<=50000）个点，从原点出发，每次可以走上、左、右、左上45度、右上45度五种方向，只有碰到一个未走过的点才能停止，求： 1.最多走多少点 2.输出一种方案 3.对于所有最优方案，只保留上、左上、右上的边，求最少条数的路径将所有边都覆盖同一y坐标的点不超过1000个前两问DP一下即可，将所有点按y为一关键字x为二关键字排序，然后对于每一行的每个点，枚举是从这行之

2017-04-10 19:07:30 1337

原创 BZOJ2322: [BeiJing2011]梦想封印线性基

题意：给一个无向图，边上有边权，每次删一条边，询问每次删边后从1号点出发任意走一条路径可能走出多少种不同的权值异或和。 N ≤ 5000，M ≤ 20000，Q ≤20000，权值1e18 先考虑静态版本。每一条路径都可以看作由一条简单路径和若干个环组成。注意这里的环并不一定需要与路径相连，因为可以从起点绕环走一圈再走回起点，环以外的部分都被异或没了，相当于单独取了一个环。由此可以得到一个初

2017-01-07 19:35:10 776

原创 BZOJ3160: 万径人踪灭 FFT+manacher

题意：给一个字符串，求（不能是连续的一段的）回文子序列的数量。要求回文子序列的字符和位置都必须以某一对称轴对称，就是说“a空格b空格空格a”这样的是不算的。长度<=100000，只有a、b两种字符。先考虑允许连续的情况下怎么求。不妨假设原串每两个字符间已经插入了‘#’。先研究每一个对称中心，对其有贡献的字符对满足在它一左一右，距离它距离相等，且字符值相等。如果已经统计出了一个中心两边符合条件

2017-01-07 18:28:39 375

原创 BZOJ1444: [Jsoi2009]有趣的游戏矩阵求逆+AC自动机

题意：N个人，每个人有一个长度为L的字符串，字符都在前M个大写字母中，现开始连续地随机产生字符，每次产生某个字符的概率是固定的，当一个人的字符串被产生出来他就赢了，求每个人赢的概率。 N,M,L<=10 百度了一下没查着和我一样用矩阵求逆做的。。。好像精度要求不高，邻接矩阵自乘几次就能过？算了。。。首先赢不了的人可以特判掉，所有人都赢不了就直接退出（我觉得这样应该可以防止矩阵不可逆），建一下

2017-01-06 17:01:36 1156 1

原创 BZOJ3626: [LNOI2014]LCA LCT

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和） n,q<=50000 对于a和b，如果我们要求d

2017-01-04 21:29:17 848

原创 BZOJ3053: The Closest M Points kdtree

题意：k维空间n个点，t个询问，每次找m个最近点，保证答案唯一。 1 <= n <= 50000，1 <= k <= 5，1 <= t <= 10000，1 <= m <= 10，多组数据。 kdtree专属裸题。有些网站说kdtree建树时每次找方差最小的一维建树什么的，我以亲身经历表示那根本不靠谱，这题坐标值范围才10000，算个方差都快爆double了，老老实实按12345维顺序建就好

2017-01-04 21:15:56 396

原创 BZOJ4373: 算术天才⑨与等差数列线段树

题意：一个序列，两种操作：1.单点修改 2.查询[l,r]内的数由小到大排序后能否形成公差k的等差数列 1<=n,m<=300000，0<=a[i]<=10^9，强制在线正解是这么说的。。。若能形成公差为k的等差数列则：1.最大值=最小值+(r-l)*k ，2.相邻两数之差都为k的倍数，3.没有重复元素第一个好维护，第二个差分后维护，由于公共gcd从下到上是单调不增的所以均摊log，关

2017-01-04 21:10:09 517

原创 BZOJ3932: [CQOI2015]任务查询系统可持久化线段树

题意：一个长度为n时间轴，m个带权值的任务，每个任务是一段连续时间，n个询问，每次询问某时间正在进行的任务中前k大的权值之和。数据规模100000。每个时间创建一棵可持久化线段树，任务拆成一个加入和一个删除，建好一排树之后每次去里面查询就好。叶子节点需要特判，这个试了很多方法也没法避免，况且这题里可能一个叶子中有多个，只需要取一部分，也就是sum/size*k。然后好像真没什么特别的

2017-01-04 20:42:53 416

原创 BZOJ3489: A simple rmq problem kdtree

题意：给出一个长度为N的序列，M个询问，每次询问[L,R]中只出现过一次的最大数，不存在输出0，强制在线 N<=100000 M<=200000 卡时神器kdtree暴力水过。用set预处理出每个元素i前面一个和它相等的元素pre[i]和后面一个和它相等的元素nex[i]，则查询变为查询l<=pos<=r，pre < l，nex > r的元素中最大的，用三维kdtree 暴力就可以了。

2017-01-04 20:11:46 424

空空如也

空空如也