- 博客(141)
- 收藏
- 关注
RSS订阅
原创 欢迎使用CSDN-markdown编辑器.
欢迎使用Markdown编辑器写博客（莫名其妙发出去的的第一篇blog）本Markdown编辑器使用StackEdit修改而来，用它写博客，将会带来全新的体验哦：Markdown和扩展Markdown简洁的语法代码块高亮图片链接和图片上传LaTex数学公式UML序列图和流程图离线写博客导入导出Markdown文件丰富的快捷键快捷键加粗 Ctrl +
2017-08-02 10:51:12
1166
原创 LOJ#2155. 「POI2011 R1」同谋者 Conspiracy
题目描述题解：这个题目要求的是把一张无向图变成一个团和一个独立集的方案数。这看似好像无从下手。那么我们可以换一个角度思考，我们考虑先求出一个解，然后通过调整得出所有解。假设已经求出了一个解，我们会发现，其它所有的解只可能由这个解通过三种方式得到：1.将一个原本在独立集里面的点放到团中（可行的条件下）。2.将一个原本在团中的点放到独立集中（可行的条件下）。3.将一个独立集中的点和团中的点...
2018-12-31 14:30:59
438
原创 LOJ#2718. 「NOI2018」归程
题目描述题解：对于权值大于等于或者小于等于某一个值的询问我们可以考虑用kruskal重构树来解决。kruskal重构树是指在对一张无向图进行kruskal求出最小/最大生成树的同时，把当前的两颗子树合并到新的节点上，作为它的两个子节点，并且把新节点的点权赋为当前这条边的边权，最后变成一颗树。那么这样合并以后，有一些好的性质：1.两个点之间的路径经过的最大边最小/最小边最大时，只要求重构树...
2018-12-28 09:59:41
327
原创 Codeforces 528 D. Fuzzy Search
题目描述题解：这题是字符串匹配的加强版。我们可以先预处理出S串的每一个位置能放那些字母。然后我们考虑对于每一种字母分开来处理。假设处理字母k。对于S中的每一位，有可以放这个字母k和不能放两种情况。对于T中的每一位，有是k和不是k两种情况。那么对于这个字母，如果S和T的某一位不能匹配只有一种情况：S没有k，而T有k。我们考虑用FFT来解决字符串的匹配问题。那么我们可以考虑如果S的...
2018-12-27 19:12:06
297
原创 LOJ#2127. 「HAOI2015」按位或
题目描述：戳这里题解：这题如果按照题意做看似非常不可解，但是有一个叫做Min-Max容斥的东西：Max(S)=∑U⊂S(−1)∣U∣−1Min(U)Max(S)=\sum_{U\subset S}(-1)^{\left| U \right|-1}Min(U)Max(S)=U⊂S∑(−1)∣U∣−1Min(U)对于这题，Max就是答案，也就是∣|∣到2n−12^n-12n−1的期望步数。...
2018-12-27 18:42:02
282
原创 TC srm 题解
SRM 516 div.2 T3: 题意：在一个有限制（可放或不可放）的矩阵中放入两个L型（严格，一个点或两个点都不行），求方案数。 题解： 暴力枚举，大力分类讨论。 枚举一下两个L型相交的的情况，一共4种。 代码如下：void doit(int x,int y,int x1,int y1){ if (x>x1) {swap(x,x1); sw
2018-12-24 20:00:31
490
原创 LOJ6482. LJJ 爱数数
题目描述：戳这里题解：1a+1b=1c\frac{1}{a}+\frac{1}{b}=\frac{1}{c}a1+b1=c1(a+b)c=ab(a+b)c=ab(a+b)c=ab令g=gcd(a,b),A=ag,B=bg令g=gcd(a,b),A=\frac{a}{g},B=\frac{b}{g}令g=gcd(a,b),A=ga,B=gb(A+B)c=ABg(A+B)c=ABg...
2018-12-24 19:58:20
676
原创 FFT：BZOJ4503 两个串
题目描述：戳这里题解：如果没有"?"，那么我们可以用kmp。我们可以把这道题目抽象成一个和式：假设两串S，T分别是0～n，0～m，翻转T串（变成m～0）。假设T串中"?"的位置都设为0。假设S串从第x个位置开始匹配可以匹配完T串，那么等价于要满足：∑0m(Sx+i−Tm−i)2Tm−i=0\sum_0^m(S_{x+i}-T_{m-i})^2T_{m-i}=00∑m(Sx+i−T...
2018-12-23 14:42:17
180
原创 算法学习：快速傅里叶变换（FFT）
前置知识：1.多项式:形如：f(x)=∑0n−1ai⋅xif(x)=\sum_{0}^{n-1}ai\cdot x^if(x)=0∑n−1ai⋅xi多项式表示法：系数表示法：就是上式的写法点值表示法：在f(x)上取n个点，就能唯一确定的表示出这个多项式。证明如下：∀\forall∀n点集合c定义集合A={a0,a1,a2,...,an−1a_0,a_1,a_2,...,a_...
2018-12-03 20:57:40
1312
原创 CDQ分治模板：HDU5618 Jam's problem again
题目描述:戳这里题解：这是一道CDQ分治的模板。我们想要求三维的“正序对”的数量。那么可以通过牌序第一维，然后对后两位使用一些数据结构来维护。但是这样很难维护，而CDQ分治就是解决这样的问题的一个得力工具。CDQ的思想大概就和归并排序一样。我们先以x，y，z分别为第1,2,3关键字排序。考虑分治，对于一段区间，我们把它分成l ~ mid和mid+1 ~ r两段，使其分别按y排序。那么...
2018-11-18 19:44:02
294
原创 51nod 1681 公共祖先
题目描述：戳这里题解：这个题目有一个非常好的技巧。我们要求的其实是某一个点在两颗树中的子树中同时含有的点的数量。我们发现这个东西很难求，因为这个东西在两个子树中都是散乱无序的。那么我们如果把一颗子树中的量变得有一定的关系可循，那么接下来只需要关心另一颗树就好了。那么我们不妨把第一颗树重新标一个号，编号就为原树的dfs序。那么第一颗子树中的点的编号都会变成连续的。接下来只要到第二颗子树中查询这个...
2018-10-28 19:02:58
200
原创 SPOJ 10628 /LuoguSP10628 COT - Count on a tree
题目描述：戳这里题解：这题是主席树上树（？？？）我们发现对于一个点，我们可以维护从它到根的权值线段树，那么对于一个点对x，y，我们只需要求出它们的lca z,以及z的父节点，那么就可以容斥一下，sumx+sumy−sumz−sumfazsumx+sumy-sumz-sum fazsumx+sumy−sumz−sumfaz。直接建n颗主席树是会mle的，所以我们直接用主席树，一个点的线段树建立...
2018-10-28 15:37:43
284
原创 BZOJ 2286消耗战
题目描述：戳这里题解：这题就是虚树的板子题啦。我们要求一些最小可以阻断给定k个点到根的路径的边权和。那么考虑没有询问的情况，可以直接用树形DP。我们先用倍增求出一个点到根的路径上的最小的边权x，然后对于一个选中的节点，肯定是求它的x作为一这个点为根的子树上的答案。而对于一个未被选中的点，就有两种可能，一种是合并它子树中的点的答案，一种是当做选中的点来处理，两个取min。但是我们考虑到有多组...
2018-10-17 18:57:42
205
原创 51nod题解小集
1406：f[x]表示与x相与之后值为x的数的个数。转移就是删掉某一个二进制位上的1。但是如果先枚举当前的值，再枚举删掉那一位会产生重复（一个数删掉一个位上的1或者删掉另外一个位上的1最后都会转移到同时删掉这两个1的情况）。那么我们可以改一下循环的顺序，先枚举删掉的位，再枚举当前的数，就不会有重复啦233331407：这题是上一题的升级版本。考虑容斥。要求出相与后1的位数为x的对数只要求出相与后...
2018-10-06 14:20:28
464
原创 KM算法模板
代码如下：#include<cstdio>#include<string>#include<cstring>using namespace std;const int maxn=505;int n,m,n1,t,ans,lasl[maxn],lasr[maxn],g[maxn][maxn],tagl[maxn],tagr[maxn];bool...
2018-09-05 14:33:41
316
原创 凸包算法：Graham模板
感觉这个算法比衍生版的Andrew算法优秀。 算法过程大致如下： 首先找到一个y坐标最小的点（y坐标相等就x最小）作为基准点，进行极角排序。这样能保证所有点到这个点的角度都在(-180,180]之间，就不用像Andrew一样维护上下凸壳了。 然后只要维护一下凸壳就好了（如果发现是凹的就退栈）。 最后如果要算面积就分解为三角形来算。 代码如下：#include<cstdio>...
2018-09-01 10:19:37
279
原创 HDU 5780 gcd
题目描述：戳这里题解： 首先有一个结论：gcd(xa−1,xb−1)=xgcd(a,b)−1gcd(xa−1,xb−1)=xgcd(a,b)−1gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1 推导过程可以参考一下辗转相减法。 (xa−1,xb−1)=(xa−b,xb−1)(xa−1,xb−1)=(xa−b,xb−1)(x^a-1,x^b-1)=(x^{a-b},x^b-1...
2018-08-30 18:47:27
467
原创 最小费用最大流:Luogu P3381 【模板】最小费用最大流
题目描述:戳这里 题解: 最小费用最大流的套路基本上就是这样的: 1.求出当前残留网络之中s -&gt; t的最短路 (spfa) 因为有可能会有负权边 2.答案+= dis[t] × totflow 3.在处理完了之后修正途径边的流量(正减反加) 4.循环1 2 3,直到S到T不连通代码如下:#include&lt;cstdio&gt;#include&lt;stri...
2018-08-27 08:51:09
233
原创 莫比乌斯容斥：Codeforces Round #251 (Div. 2)
题目描述：戳这里 题解： 这题是莫比乌斯函数的一个比较好的应用。 我们假设没有gcd为1这个限制条件，那么直接C(n-1,r-1)就行了 这样求出来的其实是大于等于gcd=1的方案总数。 而我们要求的其实是恰好gcd=1的方案数。 那么这就是容斥的典型应用。 但是我们容斥的其实是有gcd中有几个不同的素因子（同一个因子出现多次已经在在这个素因子出现一次的情况中统计过了）。 那么我们...
2018-08-10 08:22:45
318
原创 HDU4193 Least common multiple
题目描述：戳这里 题解： 这题中对于一个子集，它的最小公倍数一定是2max(a[i])∗3max(b[i])2max(a[i])∗3max(b[i])2^{max(a[i])}*3^{max(b[i])} 那么一个子集的LCM只取决于它之中a[i]最大的元素和b[i]最大的元素。 那么对于每一个点对（a[i],b[i]）我们可以排序一维，使它的a有序。 那么考虑排序后的第i个元素，我们只...
2018-08-07 22:33:44
243
原创 HDU4912 Paths on the tree
题目描述：戳这里 题解： 树上贪心。对于每一个路径，肯定是一个折线型的。那么我们找出两个端点的lca，然后按lca的深度排序，从深到浅，能加入就加入，否则就不加入。 证明可以口胡一下：我们会发现如果这个路径能加却不加，而是加一个深度更浅的路径，那么肯定肯定会使后面的点的限制更加紧，后面能加的路径更少，所以必然更加不优秀。那么代码如下：#include<cstdio>...
2018-08-07 22:17:06
178
原创 Codeforces 236E div.2 Strictly Positive Matrix
题目描述： CF出了点小偏差，改日再补。。简述： 给你一个矩阵，如果它的k次幂中的每一个元素都大于0，那么就输出YES，否则输出NO。题解： 这题有一个比较巧妙的小转化。如果我们把n*n的矩阵转化成描述n个点的连通性的图，那么会有什么性质？ 这样的话，矩阵的乘方不就是刷只和连通性有关的floyd吗。 那么只有图是强联通的才能输出YES。 那么我们考虑刷tarjan，如果整个图只有一...
2018-08-07 18:51:13
215
原创 HDU 4358 - Boring counting
题目描述：戳这里 题解： 这是典型的树上查询和子树有关信息并且无修改的题目。 那么就可以直接DSU on Tree 或者 启发式合并就好啦。 我写的是启发式合并，每次记录一下当前点的当前枚举过的儿子的颜色集合，那么当前枚举儿子k，我们只要两个集合合并一下即可。但是要保证把小的并到大的，这样就能保证复杂度在O(nlog(n))的范围内啦。代码如下：#include<cstd...
2018-08-07 14:44:19
300
原创 树链剖分：P3384 【模板】树链剖分
题目描述：戳这里 题解： 其实树剖的重点就在于轻重链，这篇文章写的很好 然而我线段树写得全是问题，改了半天2333代码如下：#include<cstdio>#include<string>#include<cstring>using namespace std;const int maxn=100005;int n,m,root,tt,t...
2018-08-06 09:33:41
207
原创 Codeforces Round #379 (Div. 2) E. Anton and Tree
题目描述：戳这里 题解： 这题还是比较妙的。 我们发现有这么多的同色块，块的大小又不一样，好像无从下手。 但是我们发现一个块最多只要改一次，那么我们可以把每一个块缩成一个点（dfs一下）就省去了很多麻烦。 缩完点之后，题目就变得简单了很多，一个黑点边上只有白点，白点边上只有黑点。这就可以贪心解决，答案肯定是树的直径的一半。代码如下：#include<cstdio>...
2018-08-05 18:10:31
143
原创 主席树：LuoguP3834 【模板】可持久化线段树 1（主席树）
题目描述：戳这里 题解： 话说我去年好像学过主席树。。。 然后我就不会了，然后我就害怕的又学了一次。 主席树其实就是线段树的优化。 我们考虑这道模板题。 如果用暴力的方法做，肯定会Tle。 那么我们想一想能不能用线段树来优化一下。 先简单化一下题目，如果求的是1~m（m&lt;=n）的第k大值，怎么用线段树做？ 那么我们就可以建立一颗权值（权值是点权离散化之后的位置）线段树，每一...
2018-08-05 16:52:31
200
原创 割边：ZOJ2588:Burning Bridges
题目描述:戳这里题解： ZOJ绝对有毒。。。格式要求令人害怕。 这题是割边的裸题。 因为在无向图中，刷出DFS序后只有返祖边（yy一下应该就知道为什么了）。那么一条边是割边一定要满足它的子树中所有点的返祖边都不会跨过它。 那么这个条件很容易用树上差分来实现。但是考虑到要和割点以及强连通分量联系起来，我们也用dfn和low来实现。 那么对于一条边，我们只要看它的son的low是不是大于...
2018-08-03 08:14:28
180
原创 平面最近点对：HDU1007：Quoit Design
题目描述：戳这里 题解： 这题是平面最近点对的裸题。 感觉平面最近点对还是比较玄妙的。 这个算法用到的是分治的思想，先分为左右两边 ，然后合并其。 那么就具体来讲讲吧。 首先我们先按照x坐标来排序n个点。 然后就是求解过程，根据我前面说的，对于一段区间[L…R]，我们求出它的中点mid，然后分治[l…mid],[mid+1…R]。 我们假设d=两段中较小的最短长度。 那么我们当前...
2018-08-02 19:03:11
220
原创 ZOJ:3649 Social Net
题目描述：戳这里 题解: 这题绝对有毒。。。 第一眼看到这题的题面感觉应该比较简单，只要倍增维护一下最大值和最小值就好了？？？ 然而码了70+行之后发现题目读错了。有一个限制条件，两个点x，y是“有向”的，x到y的路径序列中，最大值的位置编号一定要大于最小值的位置编号。。。 这样就比较麻烦了[汗]。 但是也不是不可做，我们“只需要”维护五个倍增数组就可以了。 f[i][j]f[i][...
2018-08-02 08:28:01
236
原创 BZOJ1977: [BeiJing2010组队]次小生成树 Tree
题目描述：戳这里 题解： 求非严格次小生成树是比较简单的，但是严格的就有点（超级）麻烦了。 我们可以考虑一下用克鲁斯卡尔做最小生成树的过程，一定是找了一些最小的边来构造。 我们假设造好了最小生成树，那么任意一条没有被选择过的边加入树都会在树上形成一个环。 则我们只需要考虑取出当前环上权值最大的一条边，换成当前这条，看看是不是最小次大的就可以了。 但是题目中说了是严格次小生成树，所以有可...
2018-07-29 14:07:28
169
原创 BZOJ3124: [Sdoi2013]直径
题目描述：戳这里 题解：： 这题是一道比较经典的和直径有关的题目。我们首先肯定要刷出直径。 有一个关于直径的结论，如果有多条直径，那么它们相交的部分肯定是连续的一段（yy一下应该能想出来）。 那么在我们刷出来的直径中，为什么会出现一条边没有被所有直径经过呢，那么肯定是从直径上的某一个在它之前的点有至少两条最长路径，那么这个点在某一条中，那么肯定就不满足题目条件了。 我们思考一下，是不是只...
2018-07-29 08:59:24
205
原创 Manacher算法：Luogu P3805 【模板】manacher算法
题目描述：戳这里题解：： 以前听说过，但是没有学过manacher算法，现在发现其实还挺简单的。。。 manacher算法可以用来解决最长回文串的长度这一类的问题。 讲这个算法之前，我们首先要解决一个重要的问题：回文串分为奇数长度和偶数长度。 那么我们可以用一个巧妙（暴力）的方法，每两个字符之间加一个#（或者随便什么符号），这样不管是偶数长度还是奇数长度的回文字符串都会变成奇数长度的。...
2018-07-28 10:06:49
199
原创 排列组合初步
数学基础：公式大全: C0n+C1n+C2n...+Cnn=2nCn0+Cn1+Cn2...+Cnn=2nC_{n}^{0}+C_{n}^{1}+C_{n}^{2}...+C_{n}^{n}=2^{n} 1C1n+2C2n+3C3n...+nCnn=n2n−11Cn1+2Cn2+3Cn3...+nCnn=n2n−11C_{n}^{1}+2C_{n}^{2}+3C_{n}^{3}...+nC_{...
2018-07-26 16:21:45
635
原创 Topcoder SRM 672 Div.2 题解
T1：判断两个集合A、B的关系，包括A包含B，B包含A，A和B完全相同或者A和B不满足以上所有的关系。那么模拟一下。可以开一个hsh数组标记一下，对于一个A[i]，将hsh[a[i]]–；对于一个B[i]，将hsh[B[i]]++。这样有一个好处，就是如果这个数即存在于a数组，也存在于b数组，可以相互抵消。最后分四种情况特判一下就可以啦。代码如下：我是代码T2这题给定一...
2018-07-24 21:31:00
314
原创 Codeforces#253 D - Andrey and Problem
题目描述：戳这里 题解： 这题是口胡DP题？？？ 然后我发现我两个月以前做过，并且现在不会做了 ？？？ 好吧，还是正经点吧。。。 我们只需要一道题，那么我们就可以考虑一个比较sb的DP。f[i][j][0/1]f[i][j][0/1]f[i][j][0/1]表示前i个人，选了j个(i必选)，第i个人有（1）或者没有（0）一个人给了题的概率。 那么就可以写出转移方程（表示不知道是否有正确...
2018-07-22 10:35:05
204
原创 Light Oj 1316 - A Wedding Party
题目描述：戳这里题解：这题一看就可以用状压来解决，复杂度可行。 但是代码改了好久。。。 看来我还是太菜了。。。 代码如下：#include<cstdio>#include<string>#include<cstring>using namespace std;const int maxn=20,maxm=177250;int n,...
2018-07-20 20:03:47
191
原创 HDU 3001 Travelling
题目描述：戳这里 题解：SB状压题啊。。。 这题注意到题目中有一个条件，每一个点最多可以经过两次。这样就不能愉快地直接状压了。但是我们可以考虑一下三进制的状压DP，每个点可以经过1次或者两次。 那么直接两点之间有边就转移就可以了。 然而这题卡内存，开大一点就MLE。。。 我改了半天，又WA了。。。 最后才发现原来是-1的情况的判断没有注意到ans的大小。。。 无语。。。#in...
2018-07-19 20:52:46
137
原创 AC自动机模板：P3796 【模板】AC自动机（加强版）
题目描述：戳这里 题解：AC自动机简单版的题解 这题相较于那一题只是改变了一下求的东西，我们只要稍加改动，就能AC。代码如下：#include<cstdio>#include<string>#include<cstring>using namespace std;const int maxn=10505,maxm=1e6+5;int n...
2018-07-18 07:59:16
297
原创 AC自动机模板：Luogu P3808 【模板】AC自动机（简单版）
题目描述：戳这里题解：这题是AC自动机的模板题。 AC自动机可以看作是Trie和kmp的结合体（我连kmp都不会写了。。。） 它可以看作是kmp的延伸。kmp求的是某一字符串在给定字符串中出现的次数，而AC自动机求的是某一些字符串在给定字符串中出现的次数之和或者这一类的问题。 AC自动机是用Trie来实现的，只是多了一个fail（指针）。 那么我们就重点来介绍fail的作用。 ...
2018-07-17 21:30:38
240
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人