3 Top_xiao

尚未进行身份认证

暂无相关描述

等级
TA的排名 2w+

Luogu P2602 [ZJOI2010]数字计数

链接:https://www.luogu.org/problem/P2602/*首先我们要知道,从0-99,0-999,0-9999,每个数字出现的次数是一样的.我们先算在i的位置,x这个数出现了多少次,9999假设有四位数,我们现在推到第五位,那么第五位的数x出现的所有数就是,x+(0-9999),(0-9)+((0-...

2019-08-19 10:38:37

bzoj 2959: 长跑 (LCT 维护双联通分量.)

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2959三种操作,修建一条路,修改点的权值,从a走到b的权值和.我们用LCT来做.首先我们用LCT来动态加边,如果两个点不连接,那么我们直接连上就可以了,如果两个点已经连接了,那么我们有access这条路径,splay一下,然后把路径上的点的权值加...

2019-08-18 10:55:04

POJ - 2778 DNA Sequence (AC自动机,求可以构造出来多少串.不包含原串,原串有10个左右,)

链接:https://vjudge.net/problem/POJ-2778总共有101个节点,可以建一个101*101的矩阵.a[i][j]代表从节点i走到节点j的方案数.每走一步,都会形成一个后缀.就需要这个后缀不能包含给定的串,且在构造的串中,加上一个字符不能达到给定的串.如何构造矩阵呢.,就是从i节点,然后加上任意一个字符可以到达的节点j...

2019-08-17 10:16:23

2019牛客暑期多校训练营(第七场)F Energy stones (树状数组 + set)

题目:一开始有n个石头,每个石头都有一个初始的能量e[i],然后时候的能量以每秒l[i]的速度增加,每个石头的能量有一个上限c[i].现在有m个询问,t,l,r,代表在t秒,询问区间[l,r]的石头能量之和,然后询问之后区间的石头能量变成0.最后输出一个答案,所有能量之和.思路:考虑每个石头对答案的贡献,首先要算出来...

2019-08-09 20:22:24

2019牛客暑期多校训练营(第七场) E (线段树, 点代表一个区间)

给你的区间是1e9的,所以需要我们离散一下,然后每个点代表一个区间就可以了.思路:首先我们考虑到N是4e5的,所以说不同点的个数最多就是2*N的,我们就可以用线段树来做了.方法一:我们考虑离散一个区间,把右区间的端点+1,区间算是左闭右开的,这样算一个区间的值就是右端点的值减去左区间的值.我们就可以用左区间的值代表整个区间.[1,...

2019-08-09 14:29:54

Problem F Palindromadness

简单题意,找两个字符串,AB,A,B都是回文串,A是B的子串,A和B的位置任意,可以相同,f[x]为A的长度为x,的AB的对数.根据回文树的性质,如果A是B的子串,那么一定会有一条路径,B找它的父亲,然后直接fail指向A.所以我们只要考虑,A的子树,fail指针指向A的那些节点的子树....

2019-08-04 10:39:20

bzoj 4129: Haruna’s Breakfast (树上莫队 + 修改)

https://www.lydsy.com/JudgeOnline/problem.php?id=4129DescriptionHaruna每天都会给提督做早餐!这天她发现早饭的食材被调皮的Shimakaze放到了一棵树上,每个结点都有一样食材,Shimakaze要考验一下她。每个食材都有一个美味度,Shimakaze会进行两种操作:1、修改某个结点的食材的美味度。2...

2019-08-03 17:11:43

2019牛客多校第三场 A Graph Games ( 分 块 )

题意:给你一张无向图,设s(x)为与x直接相连的点的集合,题目中有两种操作:1:1lr将读入的边的序列中第l个到第r个翻转状态(有这条边->没这条边,没这条边->有这条边)2:2xy询问s(x)和s(y)是否相等。题解:首先判断 s(x)和 s(y)是不是相等,这个我们给每个点一个随机的权值,然后把每个点所连的点的权值亦或起来,判...

2019-08-02 15:01:18

分块入门 LOJ

LOJ  分块入门:1. 分块入门 1#include<bits/stdc++.h>usingnamespacestd;constintN=5e4+100;intn,blo,a[N],b[N],tag[N];voidmodify(intl,intr,intc){for(inti=l;i<=mi...

2019-07-31 13:13:50

Luogu P1501 [国家集训队]Tree II (LCT lazy 标记)

思路:和线段树2 很像.主要练习 LCT的lazy标记.我在写这个题的时候,没有看c 的取值可以是 0 ,结果就调了一上午,emmmmif(mul[x]!=1||add[x]){//这个地方写错了.mul有可能为0,emmmmm.gg一开开始写的是 mul[x]>1#include<bits/stdc++.h&g...

2019-07-31 11:25:40

Luogu P4332 [SHOI2014]三叉神经树 (LCT)

题目描述计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI的神经组织因为其和近日发现的化合物SHTSC的密切联系引起了人们的极大关注。SHOI组织由若干个SHOI细胞构成,SHOI细胞之间形成严密的树形结构。每个SHOI细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的SHOI细胞的输出作为整个组织的输出以外,其余细胞的轴突均连...

2019-07-30 22:01:45

Jittery Roads Gym - 100889J (虚树 + DP + dfs 序, + 线段树)

每次给一个点集,求每个点到其他所有点的最大距离:会修改边权;修改边权之后,我们可以用dfs序+线段树维护当前点到根节点的距离.还可以用树状数组+差分思想维护.{dfs序之后,每个点都会有一个维护的区间,然后我们在这个区间里加上这个点保存的边权.每个边修改,我们修改这个区间.区间开头+,结尾-就可以了;最后直接查询一下就会是点到...

2019-07-25 18:39:27

Gym - 100889I I - iChandu (回文自动机 + 马拉车)

题意:给你一个字符串,然后字符串中每个位置有可以换成$.每次只有一个位置换成$问当有一个位置换成$的时候,不同的回文串最多有多少个,且有多少个位置换成$形成的不同的回文串最多样例:思路:我们可以用回文自动机求出来不同的回文串的个数,然后当我们修改一个位置成为$的时候,有可能会减少回文串的个数,有可能不会.如果这样回文串有多个,且他们不交,就不...

2019-07-24 15:43:40

Luogu P4402 [Cerc2007]robotic sort 机械排序

思路:我们要知道splay区间翻转的本质是什么,本质就是每个节点编号可以随便改变,然而splay内在的数列下标是满足splay的性质,当前节点的左子树的下标小于当前节点,当前节点的右子树的下标大于当前节点.#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+100;intsz[N],...

2019-07-20 11:59:40

bzoj 4571: [Scoi2016]美味 (xor主席树)

题意:一家餐厅有n道菜,编号1…n,大家对第i道菜的评价值为ai(1≤i≤n)。有m位顾客,第i位顾客的期望值为bi,而他的偏好值为xi。因此,第i位顾客认为第j道菜的美味度为biXOR(aj+xi),XOR表示异或运算。第i位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第li道到第ri道中选择。...

2019-07-18 11:59:26

CF813E Army Creation (主席树)

题意:n个数a[i]a[i],qq次询问,n,a[i],q<=105每次问[l,r]内最多可以选多少个数,满足同一个数的出现次数不超过k?思路假设我们想找一个[l,r]区间内的数,什么时候这个区间里的数是有效的呢?那肯定是这个数x出现不超过k次,如果超过k次就无效了,也就是说,向前找和这个数x一样的数,直到向前找k个,如果这个数的位置pos小...

2019-07-18 09:19:16

CF Gym ACM Tax (主席树, LCA)

求树上两点间路径上边权的中位数.就是z=lca(x,y)xy减去两倍的z.#include<bits/stdc++.h>usingnamespacestd;constintN=5e4+100;intHead[N],Next[N*2],To[N*2],Val[N*2],cnt;intdep[N],f[N][23];intls[...

2019-07-17 20:35:09

Luogu P4559 [JSOI2018]列队 (区间问题, 主席树)

题目:https://www.luogu.org/problemnew/show/P4559一句话:教官会指定一个区间[l,r]和集合点K,所有编号在[l,r]内的学生都必须赶到集合点列队。简单来说,就是在主席树中我们要知道这个区间的学生要向什么方向移动,知道了向什么方向移动就好办了,还要知道这个区间的学生要移动到什么位置.就是一个区间的学生移动到给定的...

2019-07-17 09:11:37

HDU 6562 Lovers (线段树)

题意:有n个字符串,每个字符串一开始是空的.然后有m个操作,两种类型,一个是修改,一个是查询,修改操作:xyz区间[x,y]中的每个字符串的首尾都加上一个数字z,这个z是一个数字字符查询操作:xy,区间[x,y]中把字符串转换为数字然后全加起来是多少.这里有五个变量:val1就是每个区间的最终答案val2就是每个区间...

2019-07-16 19:15:35

Luogu P4587 [FJOI2016]神秘数 (主席树)

题目描述一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13},1=12=1+13=1+1+14=45=4+16=4+1+17=4+1+1+18无法表示为集合S的子集的和,故集合S的神秘数为8。现给定n个正整数a[1]..a[n],m个询问,每次询问给定一个区间l,r,求由a[l]...

2019-07-16 09:23:16

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。