3 DYT_B

尚未进行身份认证

我要认证

略过

等级
TA的排名 6w+

LOJ#2155. 「POI2011 R1」同谋者 Conspiracy

题目描述题解:这个题目要求的是把一张无向图变成一个团和一个独立集的方案数。这看似好像无从下手。那么我们可以换一个角度思考,我们考虑先求出一个解,然后通过调整得出所有解。假设已经求出了一个解,我们会发现,其它所有的解只可能由这个解通过三种方式得到:1.将一个原本在独立集里面的点放到团中(可行的条件下)。2.将一个原本在团中的点放到独立集中(可行的条件下)。3.将一个独立集中的点和团中的点...

2018-12-31 14:30:59

LOJ#2718. 「NOI2018」归程

题目描述题解:对于权值大于等于或者小于等于某一个值的询问我们可以考虑用kruskal重构树来解决。kruskal重构树是指在对一张无向图进行kruskal求出最小/最大生成树的同时,把当前的两颗子树合并到新的节点上,作为它的两个子节点,并且把新节点的点权赋为当前这条边的边权,最后变成一颗树。那么这样合并以后,有一些好的性质:1.两个点之间的路径经过的最大边最小/最小边最大时,只要求重构树...

2018-12-28 09:59:41

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

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

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

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

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

算法学习:快速傅里叶变换(FFT)

前置知识:1.多项式:形如:f(x)=∑0n−1ai⋅xif(x)=\sum_{0}^{n-1}ai\cdot x^if(x)=0∑n−1​ai⋅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

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

Prufer编码:51nod 1806 wangyurzee的树

题目描述:戳这里题解:

2018-10-29 18:42:21

51nod 1681 公共祖先

题目描述:戳这里题解:这个题目有一个非常好的技巧。我们要求的其实是某一个点在两颗树中的子树中同时含有的点的数量。我们发现这个东西很难求,因为这个东西在两个子树中都是散乱无序的。那么我们如果把一颗子树中的量变得有一定的关系可循,那么接下来只需要关心另一颗树就好了。那么我们不妨把第一颗树重新标一个号,编号就为原树的dfs序。那么第一颗子树中的点的编号都会变成连续的。接下来只要到第二颗子树中查询这个...

2018-10-28 19:02:58

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

BZOJ 2286消耗战

题目描述:戳这里题解:这题就是虚树的板子题啦。我们要求一些最小可以阻断给定k个点到根的路径的边权和。那么考虑没有询问的情况,可以直接用树形DP。我们先用倍增求出一个点到根的路径上的最小的边权x,然后对于一个选中的节点,肯定是求它的x作为一这个点为根的子树上的答案。而对于一个未被选中的点,就有两种可能,一种是合并它子树中的点的答案,一种是当做选中的点来处理,两个取min。但是我们考虑到有多组...

2018-10-17 18:57:42

51nod题解小集

1406:f[x]表示与x相与之后值为x的数的个数。转移就是删掉某一个二进制位上的1。但是如果先枚举当前的值,再枚举删掉那一位会产生重复(一个数删掉一个位上的1或者删掉另外一个位上的1最后都会转移到同时删掉这两个1的情况)。那么我们可以改一下循环的顺序,先枚举删掉的位,再枚举当前的数,就不会有重复啦233331407:这题是上一题的升级版本。考虑容斥。要求出相与后1的位数为x的对数只要求出相与后...

2018-10-06 14:20:28

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

凸包算法:Graham模板

感觉这个算法比衍生版的Andrew算法优秀。 算法过程大致如下: 首先找到一个y坐标最小的点(y坐标相等就x最小)作为基准点,进行极角排序。这样能保证所有点到这个点的角度都在(-180,180]之间,就不用像Andrew一样维护上下凸壳了。 然后只要维护一下凸壳就好了(如果发现是凹的就退栈)。 最后如果要算面积就分解为三角形来算。 代码如下:#include<cstdio&gt...

2018-09-01 10:19:37

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

最小费用最大流:Luogu P3381 【模板】最小费用最大流

题目描述:戳这里 题解: 最小费用最大流的套路基本上就是这样的: 1.求出当前残留网络之中s -> t的最短路 (spfa) 因为有可能会有负权边 2.答案+= dis[t] × totflow 3.在处理完了之后修正途径边的流量(正减反加) 4.循环1 2 3,直到S到T不连通代码如下:#include<cstdio>#include<stri...

2018-08-27 08:51:09

莫比乌斯容斥:Codeforces Round #251 (Div. 2)

题目描述:戳这里 题解: 这题是莫比乌斯函数的一个比较好的应用。 我们假设没有gcd为1这个限制条件,那么直接C(n-1,r-1)就行了 这样求出来的其实是大于等于gcd=1的方案总数。 而我们要求的其实是恰好gcd=1的方案数。 那么这就是容斥的典型应用。 但是我们容斥的其实是有gcd中有几个不同的素因子(同一个因子出现多次已经在在这个素因子出现一次的情况中统计过了)。 那么我们...

2018-08-10 08:22:45

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

查看更多

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