2 Coco_T_

尚未进行身份认证

在校学生,oi进修中

等级
博文 946
排名 2k+

OI回忆录&&战友介绍

在没有忘记之前,我们需要一种方式记录我们的曾经——题记OI这条道路,荆棘密布,只有勇士才能踏上这条不归路而不至于无功而返曾经有勇士斩断荆棘救出沉睡的大自己100岁的公主,有骑士杀死恶龙迎娶高塔上的已经快凉了的佳人,有牧羊人打败巨人赢得万众敬仰假的。。。OIer,只是少了童话色彩的战士显然,并不是所有人都有屠龙的资质。。。博主为什么这么中二??!!好吧,不中二了...

2018-04-08 13:45:27

bzoj4539 [Hnoi2016]树(缩点+主席树+LCA【待完善)

题目链接分析:从学姐blog中扒出来的一道神题小范围数据的暴力非常的显然,然而MLE和TLE不是我们的重点一开始就想到把需要插入的子树直接视为一个点加上原树,我们得到的就是一个有m+1个结点的重构树最初的模板树缩成一点,作为大树的根结点我们考虑插入一个子树子树加入时会重新标号,但是大小顺序是不变的所以一个结点代表的子树的结点编号一定是一段连续的区间我们可以通...

2018-04-08 12:29:35

故天将降大任于斯人也,必先苦其心志,劳其筋骨,饿其体肤,行拂乱其所为,所以动心忍性,曾益其所不能心情不好的时候,感觉被人欺骗的时候,感觉孤单的时候,感觉迷茫的时候,特别是心怀嫉妒不满生气的时候,就花点时间写写书...

2018-04-08 12:29:20

SDOI2018日常

Day-1终于等到这一天,明天出发省选,OI成就梦想的第一步恍恍惚惚,就到了今天曾经也想过放弃,但是终究坚持下来了,心里还是有点小开心的几个月前,就开始制定计划,一切都是这么的潜移默化一个月之前,听到的是:没事放平心态,不行就回去学文化课但是感觉随着时间的推移,大家对我的。。。(不知道是信心还是什么)就越来越强听到的也从原来的“放平心态”变成了“等你的好...

2018-04-08 09:40:22

复习资料

早做准备(不想写题的时候就整理一下)AFO之前,也要精彩一场吧(っ*CДT)و︵☆这里提供复习的任意门dp须知斯坦纳树CDQ+dp斜率优化&&四边形不等式LIS计数数位dp极大子矩阵1,极大子矩阵2树形dp双元限制的dp1d1d优化dp关于dp的良好建议dada的总结,会让你觉得什么也没学过数论须知基础数论...

2018-04-05 17:00:37

树形结构全纪录(当然并不全)

这一部分的内容可以说是最杂的只能给出一些典型题和简单的知识讲解我们从简单的开始吧树的重心点分治的必要操作,难度:☆经典例题:树的重心voidfindroot(intnow,intfa){f[now]=0;size[now]=1;for(inti=st[now];i;i=way[i].nxt)if(way[...

2018-04-03 20:48:09

bzoj3052&&uoj58 [wc2013]糖果公园(带修改的树上莫队)

题目链接题目描述CandylandCandylandCandyland有一座糖果公园,公园里不仅有美丽的风景、好玩的游乐项目,还有许多免费糖果的发放点,这引来了许多贪吃的小朋友来糖果公园玩。糖果公园的结构十分奇特,它由nnn个游览点构成,每个游览点都有一个糖果发放处,我们可以依次将游览点编号为111至nnn。有n−1n−1n−1条双向道路连接着这些游览点,并且整个糖果公园都是连通的...

2018-04-03 15:20:24

二分+三分+莫队全纪录

二分+三分二分+三分讲解二分是一种很强的方法,不要因为ta太普遍而忽视这里指出ta的必要条件:答案具有单调性已知答案的情况下,可以判定答案的可行性也就是说,如果我们发现一个问题不好直接求解,但是我们可以想办法判定一个解得正确性,那么就可以考虑二分三分实际上就是凸函数上的“二分”一般用于凸包,二次函数等的最值求解可能有些题目的凸性不那么明显,那么我们就可以手玩一...

2018-04-03 11:09:05

BNUOJ 51279 组队活动(CDQ分治+FFT)

DescriptionBNUACM校队一共有n名队员,从1到n标号,现在n名队员要组成若干支队伍来相互学习、共同进步,为了保证学习效率,每支队伍至多有m名队员,你需要计算出一共有多少种不同的组队方案。两个组队方案被视为不同的,当且仅当存在至少一名队员在两种方案中有不同的队友。Input第一行是一个正整数T(T<=5),表示测试数据的组数,对于每组测试数据,输入只有一行,...

2018-04-03 08:51:50

点分治+CDQ分治+整体二分全纪录

点分治点分治讲解解决树上路径问题经典例题:点分治(长度小于m的路径计数)经典例题:点分治(聪聪可可)经典例题:点分治(多个定值路径计数)经典例题:点分治(采药)经典例题:点分治+ST表+优先队列经典例题:点分治+FFT+概率期望经典例题:点分治+01分数规划舒老师推荐点分治(难)注意:点分治的常数比较大每个点都会作为重心,然而每个点的遍历次数不止一次...

2018-04-02 21:03:12

R1前最后一次hu测

T1.xiz分析:题目描述不准确,不过样例很准确考虑记一个www数组,w[i]w[i]w[i]表示字符iii与上一个和ta相同的字符在字符串中的距离,如果没有则记为0这样T的w[i]w[i]w[i]可以很容易的表示出来但有个问题,在SSS中www数组是随着匹配位置变化的这题一般有两种做法,一种是用kmp匹配,一种是哈希网上dada的题解(果然是dada,看不大懂...

2018-04-02 14:55:44

平衡树+LCT全纪录

平衡树(splay)平衡数模板平衡树能干些什么呢?插入一个数删除一个数查询数xxx的排名(小于xxx的元素个数)查询排名为xxx的数查询xxx的前驱(小于xxx且最大的数)查询xxx的后继(大于xxx且最小的数)区间翻转区间加乘(像线段树一样打标记即可)但是平衡树有一个缺陷,不能在区间层面上进行上述操作所以我们可以在外面套上一层线段树(线段树套splayspl...

2018-04-01 20:53:26

图论全纪录

最短路图论最基础的想必就是最短路啦图上的文章(再谈最短路问题)最短路能解决的问题:最短路?话是这么说没错啦,不过一些题目隐藏的比较深,需要转化一下才能看出最短路的模型:经典例题差分约束系统对于差分约束我要说两句了简述给出若干形如xi<=xj+wxi<=xj+wx_ij−(w)−>ij−(w)−>ij-(w)->i上面的三角不等式...

2018-04-01 16:28:05

bzoj4453 cys就是要拿英魂!(后缀数组+单调栈+二分)

Descriptionpps又开始dota视频直播了!一群每天被pps虐的蒟蒻决定学习pps的操作技术,他们把pps在这局放的技能记录了下来,每个技能用一个字符表示。经过研究,蒟蒻们发现字典序更大的连招威力更大。于是所有蒟蒻都想学习pps最强的连招。但是他们太弱了,不能学会整个视频里的连招,只能学会陈老师一段区间间内的连招,可是这个他们求不出,于是只好向你求助。为了蒟蒻们不再被pps虐(怎么可...

2018-04-01 08:26:17

曲神的hu测 T2.Van(左偏树+dp)T3.Gay

版权属于yhzq,想要引用此题(包括题面)的朋友请联系博主T2.Van分析:这样把博弈黑出翔真的好吗。。。首先我们要明确怎么计算一个序列的最长Van序列这就和花匠那道题有异曲同工之妙了我们只需要找到序列的所有折点即可k=1这种情况下我们只能把序列中的每一个数变成一样的显然都变成中位数最优“中位数定理”的玄学证明k=2这种情况下...

2018-03-31 19:42:33

曲神的hu测 T1.FaQ(可持久化Trie)

版权属于yhzq,想要引用此题(包括题面)的朋友请联系博主分析:原创题,题面真的。。。感觉对不起博弈。。。yy了一种很科学的做法:首先,我们把这些字符串扔到一棵TrieTrieTrie上那么两个字符串的lcplcplcp就是这两个字符串ededed结点在TrieTrieTrie上的lcalcalca的深度不明白?参考一下这道题(顺便帮我刷刷访问量)我...

2018-03-31 17:09:45

反演&&杜教筛

大力鸣谢曲神的blog反演曾经naive的博主写的反演讲解反演中常见公式杜教筛从未见过如此厚颜无耻之博主,说好了要讲反演nei,为什么只给两个链接???好吧,我承认这篇文主要是想说说自己对杜教筛的崭新认识,所以下面才是正文。。。学杜教筛之前,一定要做一件事:%糖教简介杜教筛是干什么的内?求解积性函数前缀和的有力工具划重点:积性函数,前缀和...

2018-03-31 15:23:57

主席树全纪录

主席树主席树讲解感觉主席树就是一种功能强大的“前缀和”裸题当然不多了,不过主席树的题目还是有一些特征的需要支持线段树的操作,同时需要历史版本多半解决第k大(权值主席树,可以查询小于某个值的元素个数)重要的事情:可以查询小于某个值的元素个数,可以查询小于某个值的元素个数,可以查询小于某个值的元素个数主席树的形式是多种多样啦比较常见的是建立在序列上:序列下标,时间推移...

2018-03-30 20:14:37

bzoj3190 [JLOI2013]赛车(半平面交+单调栈)

题目链接分析:在任一时刻ttt,赛车iii的位置为:gi+vitgi+vitg_i+v_it我们可以得到若干形如上式的方程,对于每一辆赛车,询问是否存在一ttt使得gi+vitgi+vitg_i+v_it最大一次函数形式,如果我们把这些式子画到二维平面上,就得到若干直线青色(淡蓝色,水蓝色,管你什么蓝色)的线标出来的就是获奖赛车显然,我们只需要把这nnn条直线求一个半平...

2018-03-30 17:00:31

DP(Nietzsche)的hu测 T1(状压dp)

版权属于DP,想要引用此题(包括题面)的朋友请联系博主分析:整套题中唯一正常的题,真的没有什么可说的,甚至不想骂街。。。写了8K的代码,结果WA了,就是这么衰!!!发现是我对这道题的理解有问题:我们取完R-1个物品之后,如果要向一个方向移动,而这个方向有物品,我们就要取这个物品也就是说我们不一定取的恰好是R-1个,应该表述为至少R-1个而这种情况只会出现在R-1=0...

2018-03-30 16:43:46
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!