2 CRTorlonia

尚未进行身份认证

暂无相关简介

等级
TA的排名 17w+

【NOIP2017】列队 Splay

原题走这里鉴于蒟蒻的脑细胞不足,看不懂大佬们的树状数组离线解法,于是就只能用Splay了。暂时先不考虑最右一列,只考虑n行的左m-1个元素。 给每一行都建一个大小为m-1的Splay明显是不现实的。这里存在一个小小的心理陷阱,心理素质差的人比如我一看到300000*300000的方阵就被吓到了,就会下意识地认为修改规模和元素的个数相等,可能会到达300000*300000级别,然后就...

2018-08-01 10:16:16

【HAOI2016/BZOJ4566】找相同字符 后缀数组+单调栈

原题走这里鉴于我实在不是很懂单调栈和单调队列这一系列东西,所以我决定稍微具体讲一下单调栈。恩,本题实质上就是求两个字符串的公共子串数,其中只要出现位置不同,就算是不同的子串。 处理多个字符串的经典套路:把两个字符串连在一起,中间用分割符分割。 于是问题就转化为了:求分隔符前后都出现过的子串个数。 子串就是后缀的前缀,于是问题又转化成了:求整个串中,任意两个后缀的LCP之和,这两个子串...

2018-05-11 22:49:03

【USACO06DEC/Luogu2852】牛奶模式 后缀数组 半模板题

原题走这里本题实质上,就是求序列中最长的出现了至少kkk次的子串 而子串实质上就是后缀的前缀,于是我们可以使用后缀数组 鉴于后缀数组中,拥有相同前缀的的一系列后缀会表现为一段连续的区间 而相邻后缀的公共前缀长度又储存在heightheightheight,因此我们只需要求height数组中所有长度为k−1k−1k-1的区间的区间最小值的最大值即可。虽然求区间最小值可以RMQ,然而偷懒...

2018-05-09 17:08:06

【HEOI2016&TJOI2016/BZOJ4552】排序 二分+线段树

原题走这里这题的操作是真的神奇。鉴于我们只有一组询问,我们可以二分第qqq位的数 于是我们的任务就变成了判断第qqq位是否大于midmidmid 由于序列中的数本身不会变,我们就只需要关心序列中的数是大于midmidmid还是小于等于midmidmid就行了。 于是我们可以把整个整个序列变成一个01序列,大于midmidmid就是1,反之就是0我们明显可以通过线段树实现对01序列...

2018-05-09 16:38:44

【SHOI2014/Luogu4332】三叉神经树 树链剖分

原题走这里首先我们定义节点的状态0,1,2,3分别代表该节点分别接收到0,1,2,3个信号。 那么我们会发现,叶子节点的状态改变,会导致叶子节点到根的路径上一连串节点的状态改变。 比如当某叶子节点到根的路径上, 由叶子节点开始的若干个连续的节点均处于状态2,且该叶子节点处于激活状态, 那么此时,如果我们改变这一叶子节点的状态, 则从叶子节点开始,一路向根走,遇到的这些连续的2节点全部...

2018-05-04 12:11:04

set 易错点

LCT: 如果LCT要维护区间信息,则access,cut,rotate这种直接修改父子关系的操作,一定要随时update,cut操作完就update,access每循环一次都要update,rotate先update(y)再update(x)AC自动机: 建AC自动机时,要事先把root的所有孩子先塞进队列里面,我也不知道为什么 必须死记硬背的那一部分int v=ch[u][i],...

2018-04-28 10:18:44

【HAOI2012/BZOJ2752】高速公路 线段树

原题走这里由于本题中的询问是等概率选取两个收费站,因此期望花费就等于所有可能花费之和除以可能性数,即:∑l≤i≤j≤r−1s(i,j)(r−l)(r−l+1)2∑l≤i≤j≤r−1s(i,j)(r−l)(r−l+1)2\frac{\sum_{l\le i\le j\le r-1}s(i,j) }{\frac{(r-l)(r-l+1)}{2}} 其中s[i][j]是第iii到jjj个区间的长度...

2018-04-23 22:06:47

【NOI2010/BZOJ2005】能量采集 莫比乌斯反演

原题走这里这其实是我的第一道认真做的莫比乌斯反演题经过观察发现,位于(x,y)(x,y)(x,y)的植物的能量损失为gcd(x,y)−1gcd(x,y)−1gcd(x,y)-1 于是我们发现,原题实际上就是在让我们求∑i=1n∑j=1m(2∗gcd(i,j)−1)=2∗∑i=1n∑j=1mgcd(i,j)−n∗m∑i=1n∑j=1m(2∗gcd(i,j)−1)=2∗∑i=1n∑j=1mg...

2018-04-19 20:32:48

【51Nod1766】树上的最远点对 线段树+LCA

原题走这里正解:对于每个询问以a~b,c~d之间的点为关键点建虚树,然后枚举a到b中的每一个点,bfs求最长路即可原题中存在区间询问,因此八成会扯到数据结构,尤其是线段树。 然而……线段树维护区间最长路?首先我们有这样一个结论: 对于两棵树,设它们的直径/最长路分别为(a,b)(a,b)(a,b)和(c,d)(c,d)(c,d), 则两棵树合并成新树后,最长路的端点也必然在a,b...

2018-04-15 21:45:56

【SDOI2014/BZOJ3530】数数 AC自动机+数位DP

原题走这里数位DP+AC自动机似乎是常见套路? 首先题目一看就能想到数位DP。同时题目还涉及到多模式串匹配,于是又要用到AC自动机。 于是,我们可以初步得到状态d[i][j]d[i][j]d[i][j],表示当前在第i位,在AC自动机中匹配到第j个节点时的方案数。 然而有以下几个问题: 第一,题目要求的是比n小的满足条件的数的个数,按照经典做法,我们应该加一维表示第i位之前是否与n相同...

2018-04-15 12:11:37

【HNOI2017/BZOJ4827】礼物 FFT

原题走这里原题相当于求∑(a[i]−b[i]+C)2∑(a[i]−b[i]+C)2\sum(a[i]-b[i]+C)^2,其中b可以任意旋转,C为整数,由于原题中有a,b小于m的限制条件,所以C范围最大也大不过(−m,m)(−m,m)(-m,m)。 那么我们可以把式子拆开: ∑i=0n−1(a[i]2+b[i]2−2∗a[i]∗b[i]+2∗C(a[i]−b[i])+C2)∑i=0n−1(...

2018-04-15 11:12:02

【HAOI2012/Luogu2505】道路 最短路DAG

原题走这里本题的整个思想十分暴力。 首先,既然最多只有1500个点,那么就可以枚举最短路的起点,然后把最短路的条数累加到各条边上就可以了。 然而,枚举出每一条最短路再累加明显是不现实的,于是我们还需要另一个东西:最短路DAG最短路DAG,说白了就是由一张图上所有的以某个节点为起始点的最短路构成的图。 或者更加抽象一点就是所有满足dis[v]=dis[u]+a[u][v]dis[v]=...

2018-04-15 10:20:18

【POI2010/Luogu3502】CHO-Hamsters AC自动机+矩阵乘法

原题走这里原来矩阵乘法还能这么用的嘛??!!——看完题解后的我首先,题目中很重要的一句话是字符串之间不相互覆盖。 这意味着在最终解里面字符串一定是依次出现的。 那么我们可以预处理出dis[i][j]dis[i][j]dis[i][j],表示将j放在i后面会增加的字符数。 这里可以用AC自动机进行预处理,建好AC自动机之后,从每个字符串结尾,按照fail指针向后找就可以了。接着怎么...

2018-04-15 09:34:06

【NOIP2013/Luogu1979】华容道 最短路

原题走这里一看到这道题, 首先可以用脚指头想到, 既然目标是让指定棋子移到目标位置上, 那么决定棋盘状态的就只有指定棋子的位置和空格的位置两个因素。接着,可以用手指头想到, 既然,指定格子只有在周围有空格时才能动, 那么实际上状态就只有棋子的位置,以及空格在棋子的哪个方向。 共4nm4nm4nm个,对每个状态建点。接着我们会发现,对于一个棋盘状态,有两种转移: 1.让棋子...

2018-04-14 17:58:49

【SHOI2009/luogu2159】舞会 DP+容斥+高精度

原题走这里应该是本人做过的第一道DP+容斥了,容斥原理博大精深啊……原题问的是至多k对女比男高的情况,我们可以先考虑 至少 k对女比男高的情况,然后用容斥来转化。首先,让男生女生按身高排序。 设d[i][j]d[i][j]d[i][j]为前iii个女生中已经确定有jjj个女生比对应的男生高的情况下,这jjj个女生的配对情况数,其它女生暂时不考虑。 则得出d[i][j]的转移方程: ...

2018-04-09 07:50:41

【HDU3480】Division 斜率优化/四边形不等式优化

原题走这里首先很容易想到给原数组排序,于是最大值和最小值就变成最左和最右。明显是选取连续的区间最优,于是原问题就转化为了区间DP,设前iii个中选取jjj个区间的最优解为d[i][j]d[i][j]d[i][j],转移方程: d[i][j]=min(d[i−1][k]+(s[j]−s[k])2)d[i][j]=min(d[i−1][k]+(s[j]−s[k])2)d[i][j]=min(d[...

2018-04-08 13:49:02

【FJOI2007/BZOJ1002】轮状病毒 找规律+高精度

原题走这里一看题……矩阵树定理秒杀…… 等等……我连行列式都不会求用什么矩阵树定理…… 于是就只能推式子了。让我们暂时先把环剖成链,于是问题就变成了一个类似整数剖分的形式: d[i]=∑j=1i−1d[j]∗(i−j)d[i]=∑j=1i−1d[j]∗(i−j)d[i]=\sum_{j=1}^{i-1}d[j]*(i-j) 要乘上i−ji−ji-j的原因在于每划分出一个大小为i−j...

2018-04-07 22:11:26

【SHOI2007/BZOJ1933】书柜的尺寸 dp

原题走这里 目前见过的DP中算是思维难度比较大的了,其主要原因在于我太菜了本题问的是书柜总高度*书柜长度的最小值,这种情况下,我们应当将其中一个作为状态,另外一个作为代价,然后统计得到最小值。 于是,我们就可以把状态设为d[i][j][k]d[i][j][k]d[i][j][k],表示前iii本书,三层书架长度分别为j,k,sum[i]−j−kj,k,sum[i]−j−kj,k,sum[i...

2018-04-07 18:26:56

【SDOI2009/BZOJ1879】Bill的挑战 状压DP

原题走这里 一看数据范围就知道是状压 首先预处理出s[i][j]即n个字符串的第i位与字母j的匹配状态 设d[i][S]为前i个字母匹配状态为S的情况下的方案 然后对于每个状态枚举下一位是多少就可以了 最后统计一波~~~AC代码如下:#include <bits/stdc++.h>#define MOD 1000003using namespace std;...

2018-04-07 17:34:19

【NOIP2015/luogu2680】运输计划 二分+树上差分

原题走这里本题求的是改造后,使得所有路线的最大值最小。 一看到最大值最小,立刻想到二分答案,我们可以二分所有路线中最长的一条,设为x,判断是否可能通过改造,使得所有路线都小于等于x。问题就被转化为了判定性问题。接着就是是判断可行性:为了判断可行性,我们要找到这样一条边,使得 1)它被所有大于x的路径包含, 2)原最长路线-本边长度<=x,即改造本边可以可以是所有路径长度都减到x...

2018-04-07 15:54:39

查看更多

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