CRTorlonia-CSDN博客

原创 set《题》

CF 878C LOJ 6302 WerKeyTom_FTD 51Nod1614 LOJ 547 Luogu 2542 Luogu 2317 Luogu 2917

2018-04-01 09:30:18 219

原创【NOIP2017】列队 Splay

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

2018-08-01 10:16:16 380

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

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

2018-05-11 22:49:03 431 1

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

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

2018-05-09 17:08:06 266

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

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

2018-05-09 16:38:44 233

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

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

2018-05-04 12:11:04 336

原创 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 184

原题走这里由于本题中的询问是等概率选取两个收费站，因此期望花费就等于所有可能花费之和除以可能性数，即：∑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 238

原创【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 303

原创【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 324

原创【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 228

原创【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 225

原创【HAOI2012/Luogu2505】道路最短路DAG

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

2018-04-15 10:20:18 361

原创【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 268

原创【NOIP2013/Luogu1979】华容道最短路

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

2018-04-14 17:58:49 259

原创【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 324

原创【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 265

原创【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 299

原创【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 447

原创【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 212

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

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

2018-04-07 15:54:39 278

原创【NOI2007/BZOJ1494】生成树计数插头DP

原题走这里一看数据范围就知道是矩阵快速幂优化首先，设当前点为iii，接着就会发现，iii不可能与i−Ki−Ki-K之前的点相连，因此当前点的连通性只与i−Ki−Ki-K到i−1i−1i-1共K个点的连通性有关。于是我们可以用d(i,S)d(i,S)d(i,S)来表示当前点为iii，连通性为SSS的情况时的情况数。使用最小表示法，能够把连通性实质上不同的情况优化到只剩五十几种...

2018-04-01 19:33:40 339

原创【POJ3133】Manhattan Wiring 插头DP

原题走这里看起来就很难的一道题本题存在一个小陷阱，它看起来像是单回路模型（毕竟是求路径），然而它其实是多回路模型，或者说可以用多回路模型做。这道题求的是最短距离，那么这就意味着如果出现了多出来的一个回路，那么它就会因为带来了额外的距离而被舍去。于是乎，我们就可以用多回路也就是Eat the trees的思路来转移，但是路径分为2和3两种，所以轮廓线上的状态也有0,2,3三种，用四进...

2018-03-25 16:44:24 239 1

原创【HDU4285】Circuits 插头DP

原题走这里依然是经典的棋盘模型，和原题差不多。但是由于题目有限定回路数，要在状态中加一维表示已形成的回路数。此外，由于不允许回路嵌套，我们要有一个特殊规定：如果当前的一对插头要形成一个回路（也就是()到##的转移），当前这对括号前面的插头数必须为偶数，否则会出现嵌套。大致证明不太明白，不过可以感性理解一下：如果是本对括号被偶数层括号套着，比如连通性为（123321）的情况，...

2018-03-25 16:33:55 173

原创【HNOI2007/Luogu3190】神奇游乐园插头DP

原题走这里状态和模板一样，转移也几乎和模板一样。但是由于本题并不要求覆盖所有点，因此要允许“##”到“##”的转移此外由于本题是单回路，所以“()”到“##”的转移也只能发生一次，为了方便，我们可以干脆把形如“####()###”的状态，也就是只有一对相邻括号的状态作为最终解。取所有这些最终解的最大值即可。代码如下：#include <bits/stdc++.h&gt...

2018-03-25 16:06:49 248

原创【51Nod 1142】棋子遍历棋盘矩阵快速幂+插头DP

原题走这里从数据范围可以看出是矩阵快速幂优化由于这种插头DP各行之间的转移是十（yi）分（mu）相（yi）似（yang）的。我们可以用矩阵来描述d[i][m][1…S]到d[i+1][m][1…S]的转移。算出每一个d[i][m][1…S]对每一个d[i+1][m][1…S]的贡献，储存在矩阵里。做一次矩阵乘法就相当于完成了一行的转移，快速幂即可。但是最后一步由于插头dp最...

2018-03-25 15:39:43 429

原创【POJ1739】Tony's Tour 插头DP

原题走这里大概就是强制要求从左下角开始在右下角结束的哈密顿路径在图的下方加一两行： .##########. ………………… 即可。或者在dp最后返回第一和第m个插头联通的状态也可以。代码如下：#include <iostream>#include <cstring>#include <map>#define LL long long...

2018-03-25 11:38:57 198

原创【Ural1519】Formula 1 插头DP模板

原题走这里插头DP，说白了就是一类极其要命极其复杂的状压DP 通常和连通性，环，生成树之类的东西有关以轮廓线上的状态为DP的状态，逐格递推以上废话请忽略……我们先以HDU1693 Eat the Trees 作为引入，这道题是多回路，因此只需用0/1记录轮廓线上是否有回路通过。轮廓线……就是横贯方格的一条……线，由m+1段组成，如下图：图中深蓝色的就是轮廓线，此时轮廓...

2018-03-25 11:19:41 179

原创【BZOJ3992/SDOI2015】序列统计 NTT

原题走这里一道非常奇妙的题，操作十分神奇。首先原题中的式子是 a1a2a3...a|S|≡p(modm)，ai∈Sa1a2a3...a|S|≡p(modm)，ai∈Sa_1a_2a_3...a_{|S|}\equiv p (mod m) ， a_i\in S 然而乘法是没有办法直接做FFT的，所以我们要把式子中的连乘改为连加也就是说，给上面式子“取对数”求出m的原根g，将上述式子...

2018-03-11 10:25:35 191

原创【BZOJ3527/ZJOI2014】力 FFT模板题

原题走这里鉴于本机房似乎除了我以外所有人都能一眼看出来这是个卷积然而我却盯了好久才看出来所以大佬们可以直接退出 sa yo na la ~~我们把原题中的式子左右分开来看，现在只考虑左边，即 left(j)=∑i<jqi(i−j)2left(j)=\sum_{i<j}\frac{q_i}{(i-j)^2} 经观察得知： left(1)=0left(1)=0 left(2)=q112l

2018-03-11 09:37:48 185

原创【HNOI2012/BZOJ2730】矿场搭建双联通分量

原题走这里又是一道神奇的题首先我们会发现在同一个双联通分量内如果坍塌的不是割点则不会有任何影响那么我们只考虑割点坍塌的情况如果某个双连通分量有多于一个割点，则无需设置逃生出口否则要在非割点的点上设置一个每个设置了逃生出口双联通分量的大小减去1之后全部乘起来即可注意特判全图只有一个双联通分量的情况，只需2个逃生出口代码如下：#include <bi...

2018-03-01 13:56:25 205

原创【网络流24题】汽车加油行驶最短路

为什么网络流24题里会有最短路…… 原题走这里题目描述比较繁琐，重点在于如何建图题目中一个重要的点就是“加满油后可以行驶K格” 可以将其视作为让汽车油量变为K，汽车每走一格就消耗一单位油，没油时就要再加油 K<=10一看就知道是分层图最短路1~k每一种油量建一层图每走一格就会少一单位油，也就是连到下一层图加油就是又重新回到k层 SPFA即可，这里写了个LLL代...

2018-03-01 13:25:03 272

原创【AGC004D】Teleporter 贪心+DFS

原题走这里又是一道奇妙的题首先，为满足要求，首都必须指向自己，将首都指向自己后，整张图可以构成一棵树问题就转化成了，对于一颗有根树，如何将其分割成多棵树，使各棵树满足：树根是1时，深度不大于K树根不是1时，深度不大于K-1且使得切割的边数最少做法是贪心，做一个DFS，在回溯过程中，计算某子树在切割后的最大深度如果符合条件，立刻将该子树切割开最后如果首都没有指向自己就再加上1即可复杂度O(n)代码如...

2018-02-23 16:34:51 349

原创【AGC004C】AND Grid 构造

原题走这里其实我不是很喜欢这类题目构造方法十分奇妙A图涂满最左一列，以及除了最右一列以外所有的奇/偶数行格子，B图反之然后让输入图和AB两图分别取并即可还是看图吧：代码如下：#include <bits/stdc++.h>using namespace std;char a[510][510],b[510][510],c[510][510];int h,w;int main()...

2018-02-23 14:40:48 232

原创【AGC002F】Leftmost Ball 组合

原题走这里又是一道思维难度很大的题，思路很难想到首先，不妨假设颜色1~n依次出现，只要最后把答案乘上n!就可以了并且，如果排列是合法的，那么第i个无色球必然在第i个颜色之前出现那么，问题就转化为了对于所有n个0和k-1个各种颜色球的排列中，符合上述条件的有多少个。接着，我们可以发现，符合要求的排列，其实就是图一的一种拓扑序DP即可，dp[i][j]的意义如图二两种转移：删去第一行的第一个元素，则直...

2018-02-22 16:50:22 638

原创【AGC002E】Candy Pile 博弈论找规律

原题走这里又是一道十分巧妙的题重点在于找规律以及将数组转化为图形首先将各个糖果堆按降序排序就变成了类似下面图1的情况图1：排序后的糖果堆我们可以发现，操作1吃掉最大的一堆，相当于删去最左的一列，操作2从每一堆中吃掉一个，就相当于删去最下的一行再继续转化模型，将图一变成网格图则游戏就转化为了一开始全图左下角有一个棋子，操作1相...

2018-02-22 15:41:06 804 5

原创【网络流24题】骑士共存

原题走这里还是一道经典的题对棋盘黑白染色由于马只能从黑格跳到白格或者反过来，因此原图必然是二分图建图，连边，求独立集即可代码如下：#include <bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;inline int read() { int X=0,w=1;char ch=0; while(ch&...

2018-02-21 17:35:37 228

原创【网络流24题】方格取数

原题走这里似乎是非常经典的一道题说白了就是二分图带权最大独立集看到这道题的第一眼就想到了正确做法然而一直不知道如何证明黑白染色成二分图源点向黑点连边，权值为格子上的数白点向汇点连边，权值为格子上的数黑点向相邻的白点连边，权值无穷独立集与覆盖集互补，因而最大权独立集与最小权覆盖集互补又对于覆盖集中的任意一个点，按照上述方法建图时，删去其与源/汇相连的边，就相当于删去了其在二分图中覆盖的边因而最小权覆...

2018-02-21 16:49:48 289

原创 [HDU1890] Robotic Sort SPLAY

原题走这里原题有点难以描述，就不描述了，很明显的Splay（也许可以加一个离散化）思维上最大的难点就在于如何找出下一个待排序的元素的位置由于SPLAY数组中的元素下标是不变的只需预处理出一个数组，储存第n个元素在SPLAY数组中的位置即可每次把待排序元素的后继旋到根输出(根的左子树大小-i+1)将根的左子树翻转，待排序元素就到了SPALY的最左侧将其删去后重复上述即可有一个有点麻烦的地方，就是数据...

2018-02-21 15:55:02 169

原创 [HDU4292] Food 网络流

原题走这里意思大概就是有多种食品和饮料，每种个有若干个，每个人各有偏好，可能只喜欢某几种食品和饮料求如何每人分配一件食物和一件饮料，使得各人的偏好都被满足很容易就能想到网络流分层图网络流一开始我们可能会想到建三层图，食物一层，人一层，饮料一层源点向每一种食物连边，流量为该种食物的个数。类似的，饮料向汇点连边然后人和他所喜欢的食物和饮料连边，看上去是这样的然而无法限制每人只选一种食物和饮料为了限制人...

2018-02-21 15:36:49 210

空空如也

空空如也