2 RevolIA

尚未进行身份认证

RevolIA

等级
TA的排名 2w+

hdu6703 array权值线段树

题目链接、因为1操作每次加一个1e7,而k在n以内,所以1操作一下相当于把a[pos]删掉了答案一定在内,然后建一颗权值线段树,存下标的最大值每次2操作,相当于询问在中,下标大于的最小值是多少查询先看左子树中是否在,左子树中最大下标是否大于如果左子树查询完毕没有查到结果,那么看右子树是否可以查询。#include<bits/stdc++.h&...

2019-08-24 13:13:42

hdu6693 Valentine's Day

题目好难懂orz自闭题意:某人要给他女朋友买礼物,他想求他买的这些礼物让他女朋友只笑一次的概率最大是多少但是他也没给你他要买哪些,,题解:贪心从最大的开始买,假设选了前k件最大的,那么答案就是想办法优化这个一般我们的操作就是前缀和和前缀积化简、设前缀积上面式子化成了这个求和明显可以用前缀和搞定设则,化简成这样枚举i从1到...

2019-08-22 10:49:49

2019牛客多校九E.All men are brothers(统计n个数中四个不同数的相乘和)

题目链接、直接求四个不同的相乘不好求,那么维护三个的两个的和一个的,通过这三个来维护每次合并两个(删掉两个加上一个)造成的影响注意一开始的直接算的话爆掉longlong了,所以处理了一下影响:一二三四个,记为cot1+cot2+cot3+cot4,其中cot4即答案为了方便,我自己创造了俩符号,用来方便思考和叙述,表示不去重的,即选出n个中选出i个相乘(有顺序的)...

2019-08-16 11:51:41

法里数列、小结

这叫Stern-Brocot树,其中真分数(左边),叫法里数列(Farey数列)上图是一棵Stern-Brocot树,其生成规则如下:从第1行到第n行,每行相邻两数a/b和c/d,产生中间数(a+c)/(b+d),置于下一行中。将一行的分数(包括0/1,1/0),进行约分简化,则每一行(包括0/1,1/0,1/1),不会出现两个相同的分数。若分子或者分母大于n,则去掉该分数,将...

2019-08-14 11:59:26

2019牛客暑期多校(第七场)E题Find the median

题目链接、题意:给你一个空数组,n次操作,每次往里面填入里的每个数,也就是l,l+1,,,,r,然后问你中位数是谁题解:考虑树状数组维护区间、众所周知,如果差分的话,这种区间加一的操作只需要加俩点就行了,但是要求中位数的话,需要树状数组+二分才可以一般的中位数是树状数组维护原数组,然后二分前缀和,这里并不能这么用,因为不能维护原数组。所以这里考虑区间影响询问pos,...

2019-08-10 10:38:43

线段树维护区间子段和(模板题)

题目链接、题意:给定长度为N的数列A,以及M条指令,每条指令可能是以下两种之一:1、“1xy”,查询区间[x,y]中的最大连续子段和,即2、“2xy”,把A[x]改成y对于每个查询指令,输出一个整数表示答案。题解:线段树维护一、线段树的精髓——区间合并,考虑怎么合并就行了:1、合并的答案要么左区间的子段和,要么是右区间的子段和,要么是中间的一...

2019-08-09 09:42:09

2019杭电多校6,E.Snowy Smile(线段树维护子段和)

题目链接、题意:给你n个点(小于等于2e3个),每个点有个价值val,有个x,y坐标(这三个值都是1e9的)让你求一个最大的子矩阵和T组(100)题解:线段树维护子段和因为x,y,太大,所以要离散化,之后是一个n*n的矩阵,这时,原本有一个算法,即,枚举一个上下界,然后一个的dp当时我就这么写的,想了半天不造咋优化后来才知道,线段树可以维护子段和其...

2019-08-08 21:04:24

2019牛客(第七场)C.Governing sand

题目链接、题意:给你n种树,每种树有p[i]个,每个去掉花费c[i],树高h[i]让你去掉一些树,使得最高的树的个数占总数的一半以上题解:从高到底枚举树(相同高度看为一种),计算出需要去掉多少,然后二分即可一直错的原因:top=Q.top()忘记写了、#include<bits/stdc++.h>usingnamespacestd;ty...

2019-08-08 19:40:32

问题 A: Array Without Local Maximums

题目链接、我居然还打过这场的cf,还补过题,还发过博客,orz,全忘了计数dp一脸懵b第一维滚动数组用的第二维枚举当前位置是哪个数第三维0,1,2,分别表示比前面那个数小,等,大dp里面放的是方案数小:0,1,2都可以加等:只要把前面那个数的0,1,2都加上。大:加上大于这个数的数字方案数的前缀和,可以加上1,2的情况。/...

2019-08-07 11:49:56

Fhq Treap无旋Treap练习

洛谷p3369【模板】普通平衡树split采用按权/*author:revolIAsubmit:;*/#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e6+5;intl[maxn],r[maxn],val[max...

2019-08-06 11:20:51

Ac自动机练习

Ac自动机是用来解决多个小串(模式串),在一个大串(文本串)中出现次数这种类似问题的因为Trie树上直接跑dfs时间复杂度太大,所以考虑减少复杂度fail指针,相当于每次存了个扫到的当前最长后缀Trie树上用bfs建fail指针。暴力扫文本串即可洛谷p3808,简单模板给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。/*...

2019-08-02 20:03:50

字典树初步练习

字典树:一颗二十六叉树(只有小写(或大写)字母的话,数字是十叉,也有特殊的01字典树),将串插入的时候,就按着儿子走,在最后结束位置打个标记(我一般开个标记数组)感觉更像是一种思想。关于清空的小技巧:如果遇到多组输入了tot清零(动态开点),把根的二十六个儿子清空,剩下的插入的时候,如果需要申请空间了,先申请,然后清空所有儿子可以降低时间复杂度(对于...

2019-07-31 16:40:44

问题 N: 扶桑号战列舰(笛卡尔树or差分数组)

问题N:扶桑号战列舰时间限制:1Sec内存限制:128MBSpecialJudge提交:169解决:52[提交][状态][命题人:admin]题目描述众所周知,一战过后,在世界列强建造超无畏级战列舰的竞争之中,旧日本海军根据“个舰优越主义”,建造了扶桑级战列舰,完工时为当时世界上武装最为强大的舰只。同时,扶桑号战列舰也是舰岛最为科幻的战列舰。当...

2019-07-30 19:02:11

线性基

hdu3949XOR求异或第k小/***author:revolIA*submit:*/#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxbit=63;llbit[maxbit],Lbit[maxbit]...

2019-07-26 14:21:46

笛卡尔树

建树倒是会了,不知道有啥用问题N:扶桑号战列舰(笛卡尔树or差分数组)就是一个用数组下标作为另一关键字的treap因为这个下标作为关键字的性质,所以从左向右扫描数组建树的时候,新节点一定靠右,即分两种情况:为右孩子或者左孩子的父亲,所以单调栈处理一下,维护右链,每次退栈到当前元素应该插入的位置然后处理一下这两种情况就好#include...

2019-07-19 09:37:17

堆,斜堆,左偏树

二叉堆左偏树斜堆就是每次合并必定交换左右儿子,去掉dis数组(统计高度)来,这是洛谷p1177快速排序,可以去试试了小根堆141ms#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e5+7;inttree[maxn],tot,n...

2019-07-09 19:46:06

问题 A: 括号匹配2019

问题A:括号匹配2019时间限制:1Sec内存限制:128MB提交:528解决:158[提交][状态][命题人:admin]题目描述w222222s发现了一个由'('和')'组成的环,他想知道如果将环从某处断开,得到的序列有没有可能让括号能够匹配。比如环"))(("可以拆成"))((""())(""(())"")(()"四种,其中"(())"的括号...

2019-07-03 20:59:58

问题 F: 猜球球

问题F:猜球球时间限制:1Sec内存限制:128MB提交:48解决:18[提交][状态][命题人:admin]题目描述六一到了,为了庆祝这个节日,好多商家都推出了很多好玩的小游戏。Tongtong看到了一个猜球球的游戏,有n种除了颜色之外完全相同的球,商家从中拿出来一个球球放到了箱子里,已知第i种颜色的球出现在箱子里的概率为ai。Tongtong可以用下...

2019-07-03 15:23:45

12个球,有一个和其他重量不一样,一个天平三次称出是哪一个并得出轻重

如题一开始想到的一个想法,,最坏情况下是4次,后来看到的一个3次的想法4次的:考虑4个球的话,拿出其中两个,称一下如果相等,坏球就是剩下的那俩里了,再称一次就行所以4个球需要两次就可以了考虑12个球分成三堆,一堆4个拿出两堆,称一下,如果相等,说明在剩下的那一堆里,然后称两次就出来了(3次)如果不相等,把其中一堆分成两小堆(一小堆两个),称一下,相等说明不在这一...

2019-06-17 20:38:29

问题 F: Removing Coins(博弈,树的直径)

问题F:RemovingCoins时间限制:1Sec内存限制:128MB提交:35解决:15[提交][状态][命题人:admin]题目描述TakahashiandAokiwillplayagameonatree.ThetreehasNverticesnumbered1toN,andthei-thofthe...

2019-06-08 17:42:58

查看更多

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