ST表 - hzwer.com

2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)
E.Enclosure做出大小两个凸包，即所有点的凸包和前k个点的凸包按动态凸包的思路，新加入的点会把小凸包上连续的一些点弹出，这些点是一个连续的区间相当于切掉凸包的一个角，加入一个三角形若在大凸包上顺时针枚举一个加入的点，这个区间左右端点也是顺时针转的，类似旋转卡壳切掉部分的面积顺便维护由于坐标范围较大，用double精度会炸[crayon-6904d7d93444a164147113/]G.MaximumIslandsL的上下左右直接贪心为W然后剩下的就...
02017年8月11日7,211ST表,贪心,最小割,凸包,二分法,旋转卡壳

2016 ACM / ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-6904d7d935f75805725622/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
02016年9月14日4,372ST表,构造,二分法,树状数组,最短路
「小奇模拟赛2」[BZOJ3784] 小奇的树
「题目背景」小奇在研究树时，遇到了一个难题。「问题描述」给定一棵n个节点的树，求前m条最长路径的长度。「输入格式」第1行2个整数n，m。接下来n-1行，每行3个整数u，v，l，表示u，v之间有一条长度为l的边。「输出格式」m行如题，从大到小输出。「样例输入」42121132143「样例输出」54「数据范围」序号nm数据类型1103暴力223323333暴力32000300000暴力42000300000暴力5500001随机生成6779817798随机生成7779827798随机生成877983...
22016年5月22日8,430STL,ST表,点分治
PKUSC 2014 #4
A:MagicalGCD枚举每个起点gcd变化不超过log次，二分+rmq求分界点[crayon-6904d7d937513790282712/]B:DataPacking不知道是不是这样做QAQ[crayon-6904d7d937523743987742/]C:RadarInstallation得出覆盖每个点的区间贪心即可[crayon-6904d7d93752b111402361/]E:EgyptianFraction确实不好撸。。精度炸飞最后写了个分数。。。[crayon-6904d7d93753c731796018/]...
02015年5月21日3,868贪心,ST表,二分法,迭代深搜
「codechef」April Challenge 2015
BROKPHON模拟[crayon-6904d7d937daa031447756/]CHEFLCM所有约数和[crayon-6904d7d937db8291799527/]PIANO1暴力TT[crayon-6904d7d937dbf003052164/]CSEQl~r之间每个数的使用次数当作一个变量。。那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和[crayon-6904d7d937dc6198226619/]CARLOS先用并查集将能够相互转化的并在一起dpf(i,j)表示前i个末尾为j的最小改...
22015年4月12日5,385模拟,递推与动规,ST表,并查集,排列组合,乘法逆元
「POJ3693」Maximum repetition substring
DescriptionTherepetitionnumberofastringisdefinedasthemaximumnumberRsuchthatthestringcanbepartitionedintoRsameconsecutivesubstrings.Forexample,therepetitionnumberof"ababab"is3and"ababa"is1.Givenastringcontaininglowercaseletters,youaretofindasubstringofitwithmaximumrepetitionnumber.InputTheinputconsistsofmultipletestcases.Eachtestcasecontainsexactlyoneline,whichgivesanon-emptystringconsisti...
22015年1月14日6,740ST表,后缀数组
「NOIP模拟赛」数字对
「题目描述」小H是个善于思考的学生，现在她又在思考一个有关序列的问题。她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L,R](1<=L<=R<=n)。这个特殊区间满足，存在一个k(L<=k<=R)，并且对于任意的i(L<=i<=R)，ai都能被ak整除。这样的一个特殊区间[L,R]价值为R-L。小H想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些区间又分别是哪些呢？你能帮助她吧。「输...
02014年11月4日4,574ST表,二分法
「CF475D」CGCDSSQ
Givenasequenceofintegersa1, ..., anandqqueriesx1, ..., xqonit.Foreachqueryxiyouhavetocountthenumberofpairs(l, r)suchthat1 ≤ l ≤ r ≤ nandgcd(al, al + 1, ..., ar) = xi.isagreatestcommondivisorofv1, v2, ..., vn,thatisequaltoalargestpositiveintegerthatdividesallvi.InputThefirstlineoftheinputcontainsintegern,(1 ≤ n ≤ 105),denotingthelengthofthesequence.Thenextlinecont...
02014年10月6日4,878ST表,线段树,二分法
NOI2010 超级钢琴
Description小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音...
22014年9月28日8,255ST表,贪心
「BZOJ1636」[Usaco2007 Jan] Balanced Lineup
DescriptionForthedailymilking,FarmerJohn'sNcows(1<=N<=50,000)alwayslineupinthesameorder.OnedayFarmerJohndecidestoorganizeagameofUltimateFrisbeewithsomeofthecows.Tokeepthingssimple,hewilltakeacontiguousrangeofcowsfromthemilkinglineuptoplaythegame.However,forallthecowstohavefuntheyshouldnotdiffertoomuchinheight.FarmerJohnhasmadealistofQ(1<=Q<=200,000)potentialgroupsofcow...
32014年5月23日3,931ST表
「BZOJ1699」[Usaco2007 Jan] Balanced Lineup排队
Description每天,农夫John的N(1<=N<=50,000)头牛总是按同一序列排队.有一天,John决定让一些牛们玩一场飞盘比赛.他准备找一群在对列中为置连续的牛来进行比赛.但是为了避免水平悬殊,牛的身高不应该相差太大.John准备了Q(1<=Q<=180,000)个可能的牛的选择和所有牛的身高(1<=身高<=1,000,000).他想知道每一组里面最高和最低的牛的身高差别.注意:在最大数据上,输入和输出将占用大部分运行时间.Input*第一行:...
12014年3月29日4,531ST表
「vijos1514」天才的记忆
背景神仙飞啊飞描述从前有个人名叫WandNandB,他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题(专门考验记忆力的啊！)，如果谁能轻松回答出这个问题，便可以继承他的宝藏。题目是这样的：给你一大串数字（编号为1到N，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你M个询问，每次询问就给你两个数字A,B，要求你瞬间就说出属于A到B这段区间内的最大数。一天...
02014年1月7日3,881ST表