4 Mima_Reincarnation

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 8w+

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

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

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

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

2017-06-08 20:21:37

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

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

2017-06-08 20:06:40

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

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

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

2017-06-02 21:06:57

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

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

2017-06-02 20:57:03

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

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

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

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

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

2017-05-02 21:54:10

重聚 牛顿迭代

给出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

BZOJ4802: 欧拉函数 pollard_rho

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

2017-05-02 21:23:15

BZOJ3879: SvT 后缀树 虚树

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

2017-05-02 21:08:14

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

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

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

2017-04-27 20:14:22

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

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

2017-04-24 07:21:50

BZOJ4166: 月宫的符卡序列 manacher

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

2017-04-19 16:19:12

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

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

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!