3 litble

尚未进行身份认证

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

等级
TA的排名 1w+

NOI2019 退役记落幕记

刚刚考完NOI,忙着打游戏,就一直咕了,本来计划着一天通一个章节,五天就能通关,结果才通了三个章节,就突然莫名其妙收到通知开学时间提前了,变成了明天。既然已经正式成为了一名高三生,我觉得我还是要清理一下还咕咕咕着的事情,比如说写这篇游记。Not all stories can end on a happy noteNOI前去广二培训,然后就是天天被广二神仙吊打,怀疑人生,怀疑自己,哦哦哦哦...

2019-07-24 16:34:17

洛谷P5210/loj2570 [ZJOI2017]线段树 处理广义线段树的一类方法

题目分析处理广义线段树的一类套路方法。首先,定义原来的线段树为原树,并且将其改造一下,使得它能够管理的区间为[0,n+1][0,n+1][0,n+1]。定义左偏树(跟一种可并堆重名了2333)为一棵将原树上,所有是左儿子的点提取出来,构成的一棵树,每个点的父亲,是代表在其左边,与其代表区间相邻的区间,且深度比它浅的节点。画出来是这样的:定义右偏树为提取右儿子们,与在它右边深度比它浅的第一...

2019-06-26 15:55:18

codeforces 917D Stranger Trees 矩阵树定理+拉格朗日插值

题目分析把原树连成完全图,在原树中的边边权为xxx,否则为111。假设一棵生成树的权值是该生成树中所有边的权值之积,若我们将所有生成树权值相加,那么xkx^kxk的系数就是含有kkk条原树边的树的个数。现在我们假设边权代表这条边有多少重边,那么总生成树个数就是原来定义的生成树权值之和。总生成树个树可以用矩阵树定理求。设x=1,2,3...nx=1,2,3...nx=1,2,3...n,代入后...

2019-06-19 18:51:38

CodeChef TREDEG Trees and Degrees NTT+生成函数

题目分析题目地址->here这是一道二合一题,对于50%的数据,有∑n≤105\sum n \leq 10^5∑n≤105,对于50%的数据有∑n≤2∗106,K=1\sum n \leq 2*10^6,K=1∑n≤2∗106,K=1。显然prufer编码,出现iii次的点度数为i+1i+1i+1。设f(i,j)f(i,j)f(i,j)表示考虑到第iii个点,此时的prufer序列长度...

2019-06-19 18:50:59

洛谷P5333/bzoj5528/loj3102 [JSOI2019]神经网络 树形DP+生成函数

题目分析链划分显然,一条欧拉路是在一棵树上走一条链,然后跳到另一棵树上走一条链,再跳……可以利用DP求出,每棵树有多少种链划分方式(注意一条链“从这头走到那头”和“从那头走到这头”算两种不同的划分方式)DP方法:设f(x,i,0/1/2)f(x,i,0/1/2)f(x,i,0/1/2)表示以xxx为根的子树,xxx所在的链往子树里伸入的有0/1/2根,一共划分为iii条链的方案数。然后用那...

2019-06-03 20:16:32

codeforces 1149E Election Promises Nim游戏

题目分析这题好喵啊。如果没有“任意修改相邻城市的税收”这个操作,就是个美滋滋的Nim游戏。接下来的思路就很巧妙了,将城市分组。所有出度为0的点为第0组,其他点为第mex(其可达节点的组编号)组。这个有两个性质:同一组不存在一对节点xxx,yyy,满足存在边(x,y)(x,y)(x,y)。对于第ttt组中的任意一个点,它可以到达第000到第ttt组,每一组中的至少一点。若每一组的...

2019-05-30 15:45:14

loj2550/洛谷P4558/bzoj5318 「JSOI2018」机器人 性质分析+DP

题目分析首先,同一根对角线上的行为决策必须一样(要么都往右要么都往下)。行走是循环的,走到最右就变成最左,走到最左就变成最右了,所以“一根对角线”的意义也是循环的,比如说下图每一种颜色的点都属于同一根对角线。假设有一根对角线,对于它上面的每一个点(x,y)(x,y)(x,y),x+y=kx+y=kx+y=k。当(x,y)(x,y)(x,y)出了边界后,为了使它拥有合法的意义,需要(x+=...

2019-05-28 10:45:39

bzoj3636 教义问答手册 分治

题目分析分块一种虽然过不了但是很喵的做法。设f[l,r]f[l,r]f[l,r]表示区间[l,r][l,r][l,r]的答案。bib_ibi​表示区间[i−L+1,i][i-L+1,i][i−L+1,i]的权值和。则有f[l,r]=max(f[l,r−1],f[l,r−L]+br)f[l,r]=max(f[l,r-1],f[l,r-L]+b_r)f[l,r]=max(f[l,r−1],...

2019-05-23 11:03:00

二次离线莫队

例题:洛谷 P5047题面图上的妹子好可爱啊(ˉ﹃ˉ)多组询问,求一个区间内的逆序对数,离线,n≤105n \leq 10^5n≤105,时限0.3s,空间限制32MB (好,不愧是lxl)二次离线莫队如果直接用莫队做这道题的话,每次移动都要来一遍树状数组,复杂度就是O(nnlog⁡n)O(n \sqrt{n} \log n)O(nn​logn)的了。记([l1,r1],[l2,r2])...

2019-05-22 08:46:59

《从Unknown谈一类支持末尾插入删除的区间信息维护方法》学习笔记+UOJ #191代码(及HACK5原理,雾)

笔记做带末尾插入删除的区间信息维护)的数据结构题的方法:分块思路:每次插删操作暴力重构最后一块。支持插删操作,支持区间查询,支持在线二进制分组思路:若每次添加一个元素进数据结构里的复杂度比较高,则每次将这个元素单独放在最后一组,若最后一组与上一组的大小相同,就将这两组合并为同一组,不难发现最后得到的每个组大小都是2的次幂,并且互不相同,复杂度会是log⁡\loglog级的。不支持删除...

2019-05-21 20:04:53

洛谷P4707 重返现世 kMAX-MIN反演+DP

题目分析kMAX-MIN反演设kMAX-MIN反演有反演系数函数f(∣S∣)f(|S|)f(∣S∣),使得kMAX(S)=∑T≠∅,T⊂Sf(∣T∣)MIN(T)kMAX(S)=\sum_{T =\not \emptyset,T \subset S} f(|T|)MIN(T)kMAX(S)=T≠​∅,T⊂S∑​f(∣T∣)MIN(T)假设SSS集合里有nnn个数,分别是a1,a2......

2019-05-20 14:42:28

UOJ #390 【UNR #3】百鸽笼 容斥+DP

题目分析算法0每个管理员选哪一列,将构成一个长度为N−1N-1N−1的序列,序列的种数可以通过经典的将aaa个相同元素插入到一个没有该元素的长度为bbb的序列里问题,轻松求出。若一列iii要求有空笼,则标号iii只出现ai−1a_i-1ai​−1次,然后算出每种序列的种数,按种数分配概率。期望得分:0算法1分析一下算法0错在哪——每种序列的出现概率并不是相等的,因为每一个管理员选择列的时...

2019-05-17 13:21:20

洛谷P3553/bzoj3414 [POI2013]Inspector 二分答案+贪心

题目分析首先二分答案,就可以只判断这几条可不可行了。根据每个人的称述,我们先可以给这些人确定一个大致的“必须存在的区间”,而那些没有称述的人,根据boshi命名法,称其为“幽灵”。假设当前检查的时刻iii,必须存在的人数为sis_isi​。nows:由于“必须存在的区间”,而导致当前时刻至少有多少人存在。people:当前已经被“使用”了的人数。ghost:当前使用了,且其所在区间还在...

2019-05-13 20:02:41

bzoj2616 SPOJ PERIODNI 笛卡尔树+DP

题目分析建立出小根堆性质的笛卡尔树,于是每个节点可以代表一个矩形,其宽度为子树大小,高度为该节点记录的那一列高度-父节点那一列高度。设f(x,i)f(x,i)f(x,i)表示以xxx为跟的子树中放了iii个棋子的方案数。初始值:f(0,0)=1f(0,0)=1f(0,0)=1首先求出不在xxx的矩形中放棋子的方案数:f(x,i)=∑j=0if(ls(x),j)f(rs(x),i−j)f(x...

2019-05-13 15:54:53

loj3042/bzoj5600/洛谷P5279 [ZJOI2019]麻将 DP+麻将自动机

题外话我这种辣鸡放到浙江分分钟暴毙啊。题目分析牌是两两不同的,相同大小的牌也是不同的假设现在有一个手头的牌的状态,则它可以表示为第iii个位置为第iii种牌取了多少张的字符串。现在我要判断我手头能不能组成一组胡牌。情况1:有七个对子,这个很好判断(设对子数为cntcntcnt,则要求cnt≥7cnt \geq 7cnt≥7)。情况2:可以拆成三面子一对子。这个有点难判断,所以在字符...

2019-05-07 21:30:53

loj3059/bzoj5494/洛谷P5294 [HNOI2019]序列 单调栈+主席树

题目分析若a单调不升,如图,b全部相等显然比b不相等要优。那么∑i=1m(ai−b)2\sum_{i=1}^m (a_i-b)^2∑i=1m​(ai​−b)2,求导得∑ai2−2b(∑ai)+mb2\sum a_i^2-2b(\sum a_i)+mb^2∑ai2​−2b(∑ai​)+mb2,当导函数等于0时取到最小值,此时b=∑aimb=\frac{\sum a_i}{m}b=m∑ai​​也...

2019-05-04 15:38:16

洛谷P5286/bzoj5489/loj3054 [HNOI2019]鱼 计算几何

题目分析不难发现需要枚举D和A,然后鱼头鱼尾分别处理。对于鱼尾,其实就是对着A的半平面内两条到D距离相等的线段组成的,枚举D后,将其他点极角排序,然后扫描线即可解决。对于鱼头,也就是BC这条线段要垂直于AD,且BC的中点在AD上。则预处理枚举每个BC,将这个点对存入它的垂直平分线的vector中,按照中点排序。然后枚举AD,找到AD所在直线的vector,二分查找vector中中点在AD上的...

2019-05-03 21:46:29

bzoj5493/洛谷P5293/loj3058 [HNOI2019]白兔之舞 单位根反演+MTT+矩阵快速幂

题目分析设AAA为给定的矩阵。余数为ttt时的答案为:∑i=0LCLiAi[i mod k=t]\sum_{i=0}^LC_L^iA^i[i \bmod{k}=t]i=0∑L​CLi​Ai[imodk=t]已知单位根反演的式子1k∑i=0k−1ωkin=[k∣n]\frac{1}{k} \sum_{i=0}^{k-1}...

2019-05-01 16:48:32

loj3057/bzoj5492/洛谷P5292 [HNOI2019]校园旅行 性质分析优化建图+bfs

题目分析30分做法:初始,所有(x,x)(x,x)(x,x)和所有满足x,yx,yx,y同色且中间有边的(x,y)(x,y)(x,y)之间都有回文路径。将所有点对放入队列中,从两个端点开始往周围各找一个同色的点,就可以扩展出新点对,满足存在回文路径。复杂度O(m2)O(m^2)O(m2)。优化建图是这样的,首先只连上那些连接同色点的边,原图构成了若干连通块。一个回文串,例如11100111,...

2019-05-01 14:29:03

洛谷P1721/bzoj4654/loj2087/uoj223 [NOI2016]国王饮水记 斜率优化

题目分析性质:所有积水高度小于等于1号点的点可以直接丢掉。所以,将留下来的水的高度都改成其原本的高度-1号点高度,最后答案再加上1号点的高度。假如被要求进行两次合并,有两杯水h1<h2h _ 1<h _ 2h1​<h2​,则一定先合并低的,再合并高的。证明:先合并低的:12(12h1+h2)=14h1+12h2\frac{1}{2}(\frac{1}{...

2019-04-30 16:30:51

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。