2 syh0313

尚未进行身份认证

noip rp++

等级
TA的排名 6w+

bzoj4025

时间线段树+启发式合并并查集启发式合并并查集只需要记录下合并前的转态,合并的时候按秩合并,然后根据之前记录的状态回退就好了我的代码常数有点大(早上交T了,晚上就卡着过了)/**************************************************************Problem:4025User:syh0313La...

2019-08-14 20:37:08

bzoj1861

splay1操作:从平衡树中取出这个数,把rank改成最小,再insert进去2操作:从平衡树中取出这个数,把rank改成最大,再insert进去3操作:取出x和它相邻的数(1是右相邻,-1是左相邻,0直接continue)4操作:查询x的rank5操作:查询rank=x的数/*************************************************...

2019-07-28 17:31:32

bzoj2286

虚树如何构建虚树:step1:将询问点按dfs序排好,root节点作为非关键点先入栈step2:判断当前要加的点a[i]和sta[top]的关系我们令lc=lca(a[i],sta[top]);(1).如果lc在栈sta中并且就是栈顶的话,直接将a[i]加入栈(2).如果lc在栈sta中但是不是栈顶的话,一直弹...

2019-07-17 23:27:00

bzoj2152

点分治按重心分治,每次暴力统计x下所有子树和的答案,分治进子树的时候减去该子树中的贡献即可复杂度:nlogn/**************************************************************Problem:2152User:syh0313Language:C++Result:Accept...

2019-07-15 22:04:01

bzoj1935

树状数组将询问差分成四个矩阵之后就变成一个二维偏序问题,用树状数组搞一搞就好了 /************************************************************** Problem:1935 User:syh0313 Language:C++ Result:Accepte...

2019-07-02 17:39:48

bzoj1176

CDQ分治裸题单点加询问子矩阵和因为矩阵过大,所以树套树肯定是要跪的那么我们考虑将子矩阵差分了,那么就是变成每次询问(0,0)到(x,y)这个矩阵的和了那么直接cdq分治就好了 /************************************************************** Problem:1176 Use...

2019-07-02 15:58:07

bzoj2733

启发式合并权值线段树说实话我写的是一个自己yy的东西首先我对于初始每个联通块开了一个权值线段树然后对于每个联通块维护了一个vector表示里面有哪些点对于B操作每次启发式合并vector+权值线段树对于Q操作在该联通块所属的权值线段树上二分即可最后注意bzoj不能用auto /********************************************...

2019-07-02 13:09:35

Codeforces Round #566 (Div. 2)

A.FillingShapes数学题#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<algorithm>...

2019-06-12 22:44:27

Codeforces Round #565 (Div. 3)

A.模拟即可,最多不会超过3logn次#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<algorithm>usin...

2019-06-10 20:54:55

Codeforces Round #563 (Div. 2)

A.排序即可#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>usingnamespacestd;constintmaxn=10010;intn;longlonga[maxn],sum[maxn];intmain()...

2019-06-07 14:26:44

cf678F(时间线段树+凸包+三分)

解法:时间线段树+凸包+三分一开始本来想的是:cdq分治+李超线段树(因为之前学长在湘潭ccpc的时候给我嘴过一个类似的)后来发现我的做法要对于每个分治区间开一棵李超线段树肯定mle以时间为轴建立线段树,表示某个点(x,y)存在的时间对于线段树的每个节点上的若干(x,y)维护一个上凸壳;对于每个询问,从根一路访问到所在的叶子节点,对于途中每经过的一个节点,在其上的凸壳上三分一个...

2019-05-30 14:47:12

cf1111D

dp好题!首先我们可以求出所有字母都在一侧的方案数dp[n/2];假设左半部分为集合S,右半部分为T,那么假设选出的a,b已经同属一个集合时S中可以乱放,T中也可以乱放那么S中乱放的方案数有:(n/2)!/(num[i]!*num[j]!*.....)(i...j属于S);1同样T中乱放的方案数有:(n/2)!/(num[i]!*num[j]!*.....)(i...j...

2019-05-28 16:26:39

2011 WorldFinal Machine Works

CDQ分治+斜率优化dp首先考虑dp,有dp[i]表示到第i天所获得的价值最大是多少(机器卖出),所以最后的答案就是dp[n+1]然后推一推式子:dp[i]=max(dp[j]+(d[i]-d[j]-1)*g[j]+r[j]-p[j])设当j>k时从dp[j]转移会比从dp[k]转移更优,那么有:dp[j]+d[i]*g[j]-(d[j]+1)*g[j]+r[j]-p[j]&...

2019-05-19 21:21:23

bzoj1568

李超线段树李超线段树的每个节点维护一个区间,并且用标记记录当前区间上的最优线段的标号对于add一条新的线段:1.该区间无标记,则打上这条线段的标号2.若新线段在该区间上的左右端点的y值都>=原标记线段在该区间上的左右端点的y值,则新线段更优,直接覆盖3.若新线段在该区间上的左右端点的y值都<=原标记线段在该区间上的左右端点的y值,则原线段更优,直接return4...

2019-05-06 22:23:09

bzoj3211

势能线段树对于一个数非零n一直执行开根号,那么log(logn)次就会变成1所以每个数最多被修改log(logn)次对于n个数最多只会修改nlog(logn)次,所以直接暴力改到之间全为1或0就好了 /************************************************************** Problem:3211 ...

2019-05-06 14:44:46

bzoj3262

树套树/CDQ分治太弱了以至于不会写CDQ分治这道题其实树套树还是很好写的首先离线排序一维之后就变成二维偏序,就可以转换成平面单点+,询问矩阵和/**************************************************************Problem:3262User:syh0313Language:C++...

2019-05-06 11:24:02

bzoj5334

线段树因为模数不一定是质数,所以不能用逆元做那么就用线段树维护一下每个位置要乘的数(2操作或已经除掉的位置就是1)另外注意下线段树加数时记得先模一下模数,不然会爆longlong/**************************************************************Problem:5334User:syh0313...

2019-05-05 19:13:59

bzoj1798

线段树基础题看到有大佬写了splay.....orz%%二维标记下传,注意下传的顺序就好了/**************************************************************Problem:1798User:syh0313Language:C++Result:AcceptedT...

2019-05-05 16:14:06

bzoj1208

权值线段树这题应该是平衡树,然而可以用权值线段树代替开2棵权值线段树分别表示有哪些权值的人和有哪些权值的宠物然后查下前驱和后继就好了/**************************************************************Problem:1208User:syh0313Language:C++...

2019-05-05 14:28:26

bzoj2653

二分+主席树个人感觉这道题非常好,思维难度高,代码好写(然而自己写的时候神志不清,转态全无qwq)首先要知道一个关于中位数的基本套路,将大于等于它的赋值成1,小于它的赋值成-1然后通过区间和就能找出中位数了对于本题来说:首先显然答案满足单调性,因为二分的是第k大的数,所以1,-1这个序列和肯定是单调变化的其次我们考虐将[a,b],[c,d]区间转化成[a,b],(b,c),...

2019-05-05 00:12:48

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。