- 博客(137)
- 收藏
- 关注
RSS订阅
原创 Codeforces 图论板刷总结（更新中）
图论太菜了呀，那怎么办呀，刷点题吧，写下来可以以后复习，或者造福后人？大概就从这开始刷吧：Link题目对应简略思路+题解786B 区间图最段路741C 构造题 二分图567E 最短路DAG必经边527E 欧拉回路786B 区间图最段路没啥好说的，标准的区间图最短路，建议整理板子。我的板子：Link741C 构造题 二分图很容易被搞到2-sat上去，但是猜到一定有解的情况下， 构造出二分...
2019-09-07 22:22:45
1874
4
原创 Ubuntu 18.04 常见问题（持续鸽鸽，不更了）
ubuntu18.04LTS可靠源给我校mirror站打个广告，我就是从这里下载的,校内速度无限快，校外可能稍慢一些。 http://mirrors.nju.edu.cn/ubuntu-releases/18.04/ 更新似乎很快呢，正式版也有了。双系统或三系统Win10引导失败：方案一：如果能进入ubuntu：尝试执行grub自动更新sudo update-grub...
2018-04-26 12:51:17
26309
原创 业界毒瘤仙人掌一条龙服务
本slide是为了NJU集训队准备。。。。未完待续。。。 正经定义 ： 无向图中的每条边至多位于一个简单环上，且任意两点可达。由此可知仙人掌的构造方式很“优美”，即生成一棵树，把树的某些节点，都各自变成一个简单环，就变成了仙人掌。因此仙人掌大体围绕两个重点：树边、简单环。入门篇简单环判定 : codeforces 962F题意：给出无向图，找到所有...
2018-04-17 15:59:03
1100
原创 ACM模板（个人代码集整理）（博客停止更新，内附github链接，会在github继续更新）
为方便区域赛打印pdf模板，所有代码已经搬家到了github中。目录：SAM（*）SA（*）PAM（*）树链剖分(*)01Trie(*)ACAM（*）KMP(*)LCA(*)主席树(*)点分治（*）kd-Tree（*）斜率优化DP最大流Dicnic(*)最小费用最大流（SPFA）(*)线段树(*)dfs靠谱找环靠谱找凸包(*)...
2017-09-27 15:06:02
4716
2
原创 ACM之坑&套路
写在前边：这些梗都是敝人自己做题和比赛时曾经坑过自己的地方，特别在这里记录一下，所有的链接都是本博客中的题解链接（有大致题意说明和代码），原题请到OJ上自行寻找。目的是提升自身姿势。欢迎大佬们给我提出更好的建议，十分感谢。#1：一些写法的线段树需要开四倍空间。大概是因为：在很靠近叶子的地方，他的编号就很接近2倍了。然后他的孩子（超生）就接近4倍了。 例如：Codeforces 833B...
2017-08-02 14:14:23
3303
3
原创 NEERC 2012 Moscow Subregional D Darkwing Duck : 区间最大后缀：单调栈
从叉姐姐那里学到的棒棒题~题意：给一个串，区间询问字典序最大后缀。可以离线。n,q≤5⋅105n,q \le 5\cdot 10^5n,q≤5⋅105题目链接题解:在线做法还没看懂，留坑。离线做法是这样的：首先去掉这个题的字符串背景，单纯考虑求区间最大值，有一种离线单调栈的做法：从左到右扫，维护一个单减的单调栈，然后每次处理掉所有r=ir = ir=i的询问，只需要在单调栈里二分l...
2020-01-02 12:23:06
530
原创 字符串科技：Palindrome Series
文章目录简介背景知识弱周期定理Border SeriesPalindrome SeriesPAM例题：CF 932G题意题解暴力DP使用Palindrome Series优化DP符号约定转移方法总结代码第二个题： 2019 ICPC 沈阳 MNote题意：题解：代码：简介其实不太清楚这个应该叫什么，知道的同学可以麻烦告知我。众所周知，一个串的border数量是O(n)O(n)O(n)的，但是...
2019-11-19 23:51:13
1055
原创 GP of China H Inner Product: 边分治 + 虚树dp
题意给出两棵树TTT和T′T'T′，求∑i,j∈[1,n]dis(i,j)∗dis′(i,j)\sum_{i,j \in [1,n]}{dis(i,j) * dis'(i,j)}i,j∈[1,n]∑dis(i,j)∗dis′(i,j)题解对TTT进行边分治，当前分治的边为<u,v><u,v><u,v>，边权为www时，设uuu一侧的点集为LLL，v...
2019-10-16 00:21:02
332
原创 洛谷P5115 ： SAM + 边分治 + 虚树dp
题意给出串SSS，K1,K2K1,K2K1,K2，求∑i=1n∑j=i+1nLCP(i,j)⋅LCS(i,j)⋅[LCP(i,j)≤K1]⋅[LCS(i,j)≤K2]\sum_{i = 1}^{n} \sum_{j = i + 1}^{n}{LCP(i,j) \cdot LCS(i,j) \cdot [LCP(i,j) \le K1] \cdot [LCS(i,j) \le K2]}∑i=1n...
2019-10-15 01:33:28
420
原创 洛谷 P4557 战争：凸包+闵可夫斯基和
题意：给出两个凸包AAA和BBB，有若干询问，每次给出一个向量V=(x,y)V = (x,y)V=(x,y)，将BBB按照VVV的方向平移到B′B'B′，然后回答AAA和B′B'B′是否相交。题解：题目的条件等价于 存在点a,ba,ba,b，其中a∈A,b∈Ba\in A, b \in Ba∈A,b∈B，且满足a=b+Va = b + Va=b+V。则得...
2019-05-13 21:51:49
740
原创 ICPC World Final 2019 G First of Her Name ：广义SAM / 离线ACAM / 树上SA
题意：给出n个人，他们每个人的名字都是之前某个人的名字在最前边加上一个字母得到。比如2号的名字是ACACAC，3号在2号前边加一个字母KKK，这样3号的名字是KACKACKAC。之后给出k次询问，每次给出一个字符串TTT，询问名字前缀是TTT的有几个人。题解1：把每个人名字反过来看，所有人的名字就是一个Trie。要求的是以某个T（需要把输入的T给做一次reverse）为后缀的串个数。因此考...
2019-04-05 22:59:52
1099
2
原创 莫比乌斯反演、容斥 题集
洛谷 P2257题意求x∈[1,N]x \in[1,N]x∈[1,N],y∈[1,M]y \in [1,M]y∈[1,M],且(x,y)=质数(x,y) = 质数(x,y)=质数的点对个数\begin{equation}\sum\end{equation}
2019-02-01 13:54:10
533
原创 Codeforces 653F Paper Task ： SAM
题意：给出一个括号串，求有多少个本质不同的合法括号子串。题解：首先，本质不同操作，果断SAM走一波。然后括号序列，前缀和一波，处理得到sum数组。然后map&amp;amp;amp;lt;int,vector&amp;amp;amp;lt;int&amp;amp;amp;gt;&amp;amp;amp;gt;map&amp;amp;amp;lt;int,vector&amp;amp;amp;lt;
2018-12-20 01:32:40
482
原创 2014 ACM/ICPC 牡丹江 J Jacobi Pattern
题意：给出一个串(len&lt;5000len&lt;5000len<5000),求出所有满足要求的偶数长度区间[l,r][l,r][l,r]的个数：前面一半与后面一半是循环同构。题解：稍微有点面向数据。。。因为无法构造出能卡掉这种做法的数据。。。一个串的前半与后半是循环同构，即S=UV,T=VU,ST=UVVUS = UV , T = VU,ST = UVVUS...
2018-11-01 13:42:19
327
原创 codeforces gym 100962 D Deep Purple: SAM+树剖+线段树
题意:给出一个字符串，有q次询问，每次询问一个子串S[l,r]S[l,r]S[l,r]最长的border，即最大的t&lt;r−l+1t&lt;r-l+1t<r−l+1，满足S[l,l+t−1]=S[r−t+1,r]S[l,l+t-1] = S[r-t+1,r]S[l,l+t−1]=S[r−t+1,r]。题解1：复杂度O(nlog2n)O(nlog^2n)O(nlog2...
2018-10-30 00:29:37
784
原创 Codeforces 1073G Yet Another LCP Problem:SAM+虚树DP
题意：给出一个长度为n的串s，每次询问给出两个整数集合：S，T，求∑x∈S∑y∈TLCP(S[x,n]，S[y,n])\sum_{x \in S} \sum_{y \in T}LCP(S[x,n]，S[y,n])∑x∈S∑y∈TLCP(S[x,n]，S[y,n])题解：先将S reverse一下，询问等价于 前缀的最长公共后缀，而两个串的最长公共后缀，对应于他们sam节点的fail树...
2018-10-26 23:52:31
595
原创 Codeforces 570E Pig and Palindromes : DP+滚动
题意：给出一个n*m(n,m&lt;=500)的矩形区域，每个格子上有一个小写字母，从(0,0)出发，只能向右或上走，走到(n,m)，且要求路径上的字符构成回文串，问方案数。题解：由于是回文串，要求对称，因此我们从两头一起走。dp[step][xl][xr]dp[step][xl][xr]dp[step][xl][xr]表示现在两头分别走到了(xl,step−xl)(xl,step-xl)...
2018-10-09 14:36:08
241
原创 Codeforces 246 E Blood Cousins Return: DSU on Tree
题意：给出一棵树，其中father=0的为根，会有多个根，每个点有一个name，有Q次询问，每次询问节点v的深度为h的儿子的name有多少种。题解：DSU ON Tree using mapO(nlog2n)O(nlog^2n)O(nlog2n)Code:#include &lt;bits/stdc++.h&gt;using namespace std;typedef long l...
2018-10-08 13:31:49
209
原创 ccpc-wannafly Palindrome: SAM+Manacher
题目链接题意：给出一个串串，要求选出两个子串，使他们拼接起来是一个回文串，设一种方案是[l1,r1]在前，[l2,r2]在后拼接而成，则这种方案用有序四元组(l1,r1,l2,r2)表示，求这样的四元组的个数。题解：首先，串串有2e5，如果他是2e5个a，那么答案大约是(2e5)^4，爆掉了ull。。。得开个__int_128\_\_int\_128__int_128 ，好坏怀阿。我们分...
2018-10-04 14:23:30
300
原创 Codefoces Gym 101915 G Robots : Brute Force
发一个水题。。证明我还活着。。。题意给出一棵边权互不相同且根为1的树，并给出q次询问，每次询问给出一个x，问，从根出发，只能往儿子走，每次会选择不超过x的最大的边走下去，如果不存在儿子或者不存在这样的边，则停止，问最终会停在哪个点，将所有询问的答案求和输出。题解：无脑一把梭题解 ：离线，然后LCT，没了。暴力题解：离线，从小到大把边插入树中，每次插边的时候，如果近根点已经有了一个儿子边，...
2018-10-01 22:33:05
376
1
原创 UOJ#310 【UNR #2】黎明前的巧克力:FWT
题意： 给出一个数组a，要求把a数组选出两个不相交且不同时为空的子集，满足两个集合中数字的异或和相等。题解：考虑dp[i][j]dp[i][j]dp[i][j]表示考虑前iii个数字，且现在两个集合数字的异或和为jjj时的方案数。转移方程为：dp[i][j]=dp[i−1][j]+2∗dp[i][jxora[i]]dp[i][j]=dp[i−1][j]+2∗dp[i][jxo...
2018-08-17 19:44:03
892
1
原创 2018 HDU 多校第一场 1008：RMQ Similar Sequense
题意定义运算RMQ(A,l,r)=maxi=lrA[i]RMQ(A,l,r)=maxi=lrA[i]RMQ(A,l,r) =\max_{i=l}^{r}A[i] 定义两个等长的数组A、B RMQSimilar∼∀i∈{1,n}∀j∈{i,n}RMQ(A,i,j)=RMQ(B,i,j)RMQSimilar∼∀i∈{1,n}∀j∈{i,n}RMQ(A,i,j)=RMQ(B,i,j)RMQ S...
2018-07-24 11:39:22
371
原创 2018 nowcoder 多校第二场 K题 carpet
题意找一个最小权值和 二维循环周期。题解：一般这种题，都先扔掉最优化的条件，思考如何求解，然后在考虑最优化。那么如何求解二维循环周期（注意不是循环节）呢？显然对于每一行KMP以下就可以找到每一行的循环周期，对于一个size=p行*q列的周期，意味着column[i] = column[i+q]，更具体的说就是 对于每一行r 都有s[r][i] = s[r][i+q] 。这意味着q是...
2018-07-24 10:27:27
462
原创 51Node 2012 字符串的魅力：SAM
题目传送门题解：由于k很小，显然要在这里搞一搞事情的。考虑SAM(由于要考虑所有的子串……就直接想SAM了……)，由于每个节点保存的是一些后缀，而这个k是对前缀的限制，诶……经典套路了，把输入串反过来，k就变成了对后缀的限制，那么对于每个节点保存的这些后缀，长度小于k的暴力处理，长度大于k的O(1)处理，细节巨多……写了好久。据说SA可以秒。。。Code：#include...
2018-06-26 13:50:21
396
原创 codeforces 992D:并查集
题意：给一个数列，求出子区间个数，要求满足∏rlai=K∗∑rlai∏lrai=K∗∑lrai\prod_{l}^{r}{ai} = K*\sum_{l}^{r}{ai} 数据范围: 1&lt;=n&lt;=2e5 1&lt;=K&lt;=1e5 1&lt;=ai&lt;=1e8题解：数据范围已经安排好了算法。计算等式右端的最大值：1e5*2e5*1e8=2e18。嗯LL刚好...
2018-06-19 07:31:17
653
原创 codeforces gym 101572D :BFS
题意：给出n个k维01向量，求一个k维01向量，使得给定的向量的相同位数最大值最小。题解：基本思路：最大值最小-&amp;amp;gt;最小值最大-&amp;amp;gt;bfs搜最小值-&amp;amp;gt;取最大 汉明距离：d(x,y) = x与y不同的位的个数。Min(Max(k−d(s,ai)))=Min(k+Max(−d(s,ai)))=Min(k−Min(d(s,ai)))=k+Min(−Min(d(...
2018-06-16 17:20:44
241
原创 BZOJ 3676字符串：PAM练习
题意：给出一个字符串，求 ∑S[i,j]为回文串S[i,j]出现次数∗(j−i+1)∑S[i,j]为回文串S[i,j]出现次数∗(j−i+1)\begin{equation*}\sum_{S[i,j]为回文串}S[i,j]出现次数*(j-i+1)\end{equation*}题解：构造出这个串的PAM，然后拓扑统计出每个状态的出现次数，然后扫一遍得到答案。注意long lon...
2018-05-15 19:37:46
327
原创 codeforces 487E Tourists : 圆方树+链剖+线段树+可删除堆
题意：给出一个无向联通图，每个点有一个权值，要求兹磁一种修改操作：修改某点权值；以及一种查询操作：查询某两点x，y的所有简单路径上的最小点权。题解：这东西是必然要缩点的啦，那么问题来了，缩点有三种写法：强连通，点双，边双。显然要点双啦，题目都说了要简单路径的。那么点双一缩，变成一棵树，然后考虑树上两点，他们的简单路径并={树上路径+路径上的点双里面的所有的点}。我们仿照圆方树操作：将每...
2018-05-14 20:56:16
700
原创 BZOJ 2286 [Sdoi2011]消耗战:虚树入门
题意：给出一棵带边权的树，根为1，每次询问给出一个点集，要求删掉一些树边，使得根与这些点不相连，并最小化边权之和。题解：将点集中的点拿出来建立虚树，然后对lca点和询问点讨论一下进行dp即可。（每个询问点到根的路径删除且只删除一条边）Code：#include <bits/stdc++.h>using namespace std;typedef long l...
2018-05-08 00:19:47
243
原创 Codeforces 925C BigSecret:01trie+贪心
题意：给出一个b数列，求一个b的排列，使得存在一个严格增的a数列，满足a[i]^a[i-1]=b[i]，不存在输出No，存在则输出b。题解：大致一想，最小的b肯定可以放在第一个，因为如果不放在第一个，你可以一点一点交换到第一个上去，这个交换过程不会改变a的单增性质。那么进而，a_0确定了，那么如果我们把a_0去掉，那么剩下的a相当于都亦或了a_0，于是问题变得相似了起来，再次寻找最小的b即...
2018-04-30 01:47:54
306
原创 BZOJ 2730矿场搭建：割点
题意：给出一个无向完全图，先在需要在图中选出最少的点，使得满足：删掉任意一个点之后，剩下的点都可以到达至少一个选择的点。求出最少选择的点数，以及选点的方案数。题解：显然，本题的描述本质上就是双连通性，即所有点到指定点都是点双连通的。那么考虑原图的割点，如果一个点双只包括一个割点，那么如果删掉了割点，就使得这个点双与原图断开连接，因此这个点双内一定要选出一个点(不能是割点)；如果一个点双...
2018-04-20 23:59:54
225
原创 BZOJ 2125 最短路：圆方树+LCA(倍增)
题意：给出一个仙人掌，多次询问两点间最短距离。题解：树的情况下，只需要LCA即可，树剖或者倍增都行，树剖常数比倍增小一些，而且确实好写。 仙人掌情况下，只需要建立圆方树，显然方点到圆点父亲的边权应为0。讨论两点LCA的性质： LCA为圆点：这种情况说明此圆点确为两点LCA，答案就是dis(u)+dis(v)-2*dis(lca) LCA为方点：这种情况下说明，u和v两点向上寻找LCA...
2018-04-19 21:49:32
370
原创 BZOJ 4316 小C的独立集:圆方树+DP
题意：给定一棵仙人掌图，求其最大独立集。 独立集：点集内任意两点不存在边直接相连。 点相互独立：这些点组成的点集为独立集题解：树上情况：dp[i][0/1]表示考虑i为根的子数，i不选/选最多能选几个点。设j为i的儿子，有转移方程： dp[i][0]=∑max(dp[j][0],dp[j][1])dp[i][0]=∑max(dp[j][0],dp[j][1])\begin...
2018-04-18 21:20:34
510
原创 BZOJ 1023 [SHOI2008]cactus仙人掌图：圆方树+单调队列DP
题目传送门题意：给出一个仙人掌图，边权都为1，求其直径。 仙人掌图：无向图的每条边至多存在于一个简单环中。 仙人掌图直径：Max(dis(u,v)) 1<= u < v <=n。dis(u,v)是u、v之间的最短路径。题解：先考虑退化情况：仙人掌退化为一棵树。很显然可以通过一个树形DP来解决，讨论路径的形态：1、分跨在一个点的两个子树中2、...
2018-04-18 17:32:27
582
原创 洛谷 P4129 [SHOI2006]仙人掌
题意：给出一个无向图，在判断原图是否为一个仙人掌图的基础上，求仙人掌的支撑子图个数 支撑子图：去掉一些边，但并不改变连通性，这样得到的子图为支撑子图。题解：1个仙人掌 <=> 连通性&点双均为简单环。 于是先dfs一次检验连通性，然后tarjan求点双，检验点双的点数=边数。 Ans=∏(环长+1)Ans=∏(环长+1)\begin{equatio...
2018-04-17 15:54:26
427
原创 上海高校金马五校赛 J 小y写文章
传送门题意：太懒了，去原题看吧。题解：最大值最小，明显的二分痕迹，于是果断二分最大值。check的话，可以比较明显看出是一个匹配问题，n个数字，共产生了n+1个空位，现在有m个数字要全部填进去，我们可以nm的建立数字-空位的边，然后单独再考虑一下最前最后两个空位，但是这样的匹配是n+1和m匹配，不能处理那些不填数字的空位，于是我们建立n+1-m个“空点”，某个空位如果不填数字也合法的时候，就网每个...
2018-04-15 22:50:42
285
原创 上海高校金马五校赛 D 数字游戏
传送门题意：给出两个区间[L1,R1] [L2,R2] 和一个模数mod ，两个人博弈，第一个人从区间1选出一个数字，第二个人从区间二选出一个数字，然后把第二个数字拼接到第一个数字后边，形成的新数字能被mod整除，则第二个人赢，否则第一个人赢，问第一个人是否必胜。题解：拼出来的数字形如：A*10^lb+B。(lb为B的位数),这个数字对mod取模为 (A%mod)*(10^lb%mod)+(B%m...
2018-04-15 22:31:59
284
原创 Codeforces 962F：Tarjan点双连通分量
前置技能：Tarjan三算法：强连通分量、点双连通分量、边双连通分量。资料：Tarjan三大算法之双连通分量（双连通分量）题意：给出一个无向图，求出所有只在一个简单环上出现过的边。简单环：环上每两个点都不同。题解：这个东西，稍微想一下发现，他就是个仙人掌那样的分量。。。思路基本一致。思路很清晰，就是找到简单环，那么我们可以先找环，然后判断他是不是简单的。而点双连通分量的定义就是，每一个连通分量中的...
2018-04-11 17:02:45
713
原创 Codeforces 932E:第二类斯特林数
题意：n、k为常数，模为1e9+7，求： ∑i=1N(ni)∗ik\begin{equation*}\sum_{i=1}^{N}\tbinom{n}{i}*i^k\end{equation*}题解：将i^k用斯特林数展开并化简之。 nk=∑i=1kS2(k,i)∗ni−\begin{equation*}n^k=\sum_{i=1}^{k}S_2(k,i)*n^{\underline{i}}
2018-04-09 17:29:20
513
原创 Codeforces 961G：第二类斯特林数
题意：给出一个数列wi，对于一个集合S，，对于一个w的划分R，，求w的所有划分为k部分的W之和。题解：有一个显然的事实是：每个数字是等价的，也就是说每个数字wi单独来看，他在最终答案中的贡献都是p*wi，p是计算出来的一个系数。因此 答案=p*Σwi。单独考虑每一个wx，设S是一个包含wx的集合，，那么wx对这个集合的贡献是|S|*wx，这个|S|可以分均到S中每一个元素身上，即和wx在同一个集合...
2018-04-08 20:46:05
571
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人