2 RevolIA

尚未进行身份认证

有事加Q吧、CSDN不常登录,QQ:2270389239

等级
TA的排名 2w+

最短路(road)配对堆优化dij

题目链接、bzoj3040、限时60s可把我吓坏了程序跑了10s点1e6,边1e7考虑配对堆优化、#说实话如果不涉及大量的改值的话,配对堆也没传说中的快/*author:revolIA*/#include<bits/stdc++.h>using namespace std;typedef long long ll;const int max...

2019-10-26 18:28:06

manacher模板

洛谷模板/*author:revolIA*/#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e7+1e6+7;char s[maxn+1<<1];int Len[maxn+1<<1];int manacher(cha...

2019-09-29 21:00:26

我才不是毒瘤出题人

题目链接、我才不是毒瘤出题人Time Limit:1000 msMemory Limit:65536 KiBSubmitStatisticDiscussProblem Description有一个长度为n的初始序列a,下标从1到n。现在你有两种操作,1:下标为k的数加12:序列中第k小的数是多少?Input第一行两个数n,m.表示序列长度和操作次数。第...

2019-09-29 20:35:25

绝地求生(珂朵莉树)

问题 B: 绝地求生时间限制:1 Sec内存限制:128 MB提交:61解决:20[提交] [状态] [命题人:admin]题目描述吃鸡开局了,你降落的森林中有一条长度为S的小路(编号从1到S),且在小路上时常会起雾,你手上的激光发射器可以让雾消散。你肯定你所在位置的视野。若位置x有浓雾,则位置x的视野为0。若从x一直到S或从x一直到1全都没有浓雾,则视野为INF...

2019-09-25 09:56:17

UVA 12657 Boxes in a Line(双向链表)

这里写的并不是uva上的那个题,而是upc上的一个题,所以,稍微有些不同You have n boxes in a line on the table numbered 1…n from left to right. Your task is tosimulate 4 kinds of commands:(i) 1 X Y: move box X to the l...

2019-09-22 19:24:19

JSOI2019招待

问题 A: 招待时间限制:1 Sec内存限制:128 MBSpecial Judge题目描述请了两位奆老来为自己种树,小X也稍稍有些不好意思了,于是他准备了一些零食和饮料来招待奆老们。然而,小X有强迫症,他希望自己和好基友们所有的零食和饮料的质量都要完全相同。由于小X是一个奆老,所以他看不起普通商店里卖的电子秤,他决定自己做一个。他的称重工具是一架由金子制成的天平,这...

2019-09-21 11:48:51

珂朵莉树练习

CF896C Willem, Chtholly and Seniorious万恶之源稍微有些复杂,因为操作比较多1lrx:将区间所有数加上x 2lrx:将区间所有数改成x 3lrx:输出将区间从小到大排序后的第xx个数是的多少(即区间第x小,数字大小相同算多次,保证) 4lrxy:输出区间每个数字的x次方的和模y的值(即(...

2019-09-14 21:58:37

计蒜客The beautiful values of the palace

题目链接、y轴压缩,维护x的树状数组矩阵查询变成两个/*author:revolIA*/#include<bits/stdc++.h>#define HEAP(...) priority_queue<__VA_ARGS__ >#define heap(...) priority_queue<__VA_ARGS__,vector<__...

2019-09-10 21:32:17

hdu6681 Rikka with Cake

题目链接、压缩y轴,维护x的树状数组/*author:revolIA*/#include<bits/stdc++.h>#define HEAP(...) priority_queue<__VA_ARGS__ >#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ &g...

2019-09-10 17:22:58

CDQ分治练习

cdq分治解决偏序与整体二分解决区间k小思路相似,都是考虑左区间对右区间的影响,但是实现略有不同偏序的重点是:理解两个有序链表的合并,即,一次归并排序整体二分的重点是:二分权值,把操作(查询与修改)划分到左右区间,然后递归处理陌上花开x排序,y分治,z树状数组/*author:revolIA*/#include<bits/stdc++.h>...

2019-09-05 16:43:04

hdu6701 Make Rounddog Happy(笛卡尔树启发式分治)

题目链接、题意:求有多少对,使得内无重复数字,且题解:预处理的管辖区间处理一颗笛卡尔树,遍历整棵树,启发式分治区间一、对于,我们先处理一个上次出现的位置+1,然后取一个前缀对于,我们先处理一个上次出现的位置-1,然后取一个后缀这想法个来自这里、二、直接暴力跑区间1、设一个r,不断往右走,一边走一边标记,当遇到标记时,记录当前位置-1,即...

2019-08-28 19:51:28

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、“1 x y”,查询区间 [x,y] 中的最大连续子段和,即2、“2 x y”,把 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>using namespace std;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

查看更多

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