一些简单的想法


主要记录平时做题的时候一些trick,供自己参考。

1.一个B进制数是(B-1)的倍数,那么等价于这个数的各位数字之和是B-1的倍数。     BZOJ 4724

2.一个图的直径大于3,那么他的补图的直径一定小于3.     Codeforces 755E

3.一个引申自SPOJ IITWPC4F – Gopu and the Grid Problem的问题:让灯有三种状态0,1,2,每按一次会+1模3,操作同上,询问矩形区间三种状态各多少。

线段树每个节点有3种状态:sum0,sum1,sum2.每操作一次相当于sum0=sum2,sum1=sum0,sum2=sum1.然后还是x和y分别建立线段树。

画个图发现:,然后按照这个图就可以推公式了。感谢韩司机的想法和思路。。。

4.

5.给出n,找一个m让n*m+1不是质数。n*(n-2)+1=(n-1)*(n-1)

6.有时候点与点之间暴力连边是O(n^2)的,可以考虑根据定义(如距离之类的)每个点只和自己距离最近的点连边。    BZOJ 4153 1604

6.曼哈顿距离和切比雪夫距离的转换:把坐标(x,y)变换成(x+y,x-y)。原来的曼哈顿距离即变为现在坐标系下的切比雪夫距离。 BZOJ 1604

7.一个n*m的点阵中数有多少个不同的正方形(正着的和斜着的都算)。

证明

8.二分图的一些性质总结

(1)二分图最小点覆盖:

定义:点覆盖是图中一些点的集合,且对于图中所有的边,至少有一个端点属于点覆盖,点数最小的覆盖就是最小点覆盖。

最小点覆盖=最大匹配。证明

(2)二分图最小边覆盖:

定义:边覆盖是图中一些边的集合,且对于图中所有的点,至少有一条集合中的边与其相关联,边数最小的覆盖就是最小边覆盖。

最小边覆盖=图中点数-最大匹配。

假如把所有的最大匹配的边加入到答案里,剩余的未在最大匹配内的点任意选择一条还未加入的边加入到答案里。这样子做是一种贪心,因为最大匹配的边可以关联到两个点。最小边覆盖=最大匹配数+图中点的个数-2*最大匹配数=图中点的个数-最大匹配数。

(3)二分图最大独立集:

定义:独立集是图中一些点的集合,且图中任意两点之间都不存在边,点数最大的就是最大独立集。

最大独立集=图中点数-最小点覆盖=图中点数-最大匹配

考虑把所有的点放到集合内,现在想要删去最少的点以及他们的边来让剩余的点互不关联,那就删去最小点覆盖中的点就好了。

(4)有向无环图的最小不相交路径覆盖:

定义:在一个DAG中,用最少的不相交路径覆盖所有顶点。需要注意单独的一个点也可以视为一条路径。

方法:把每个点拆为x和y两个点,如果在原图中A->B的话,在新图中连边Ax->By。然后建完图后跑最大匹配,然后答案为原图中点数减去最大匹配数目。

假设一共有n个点,那么肯定最多只需要n条路径就可以覆盖所有的点。一开始每个点都是独立的,为一条路径,总共有n条不相交路径。而匹配的含义指的是匹配的边两两没有公共点,对应回原图中正是代表了两条边(路径)没有相交。那么每有一次匹配边就有两个路径可以被合并到一起成为一个路径,那么匹配的越多越好,自然就是最大匹配了。所以ans=n-最大匹配。

(5)有向无环图的最小相交路径覆盖

定义:在一个DAG中,用最少的可以相交的路径覆盖所有顶点。需要注意单独的一个点也可以视为一条路径。

先用floyd求原图的传递闭包,然后如果A可以到达B,那么按照最小不相交路径覆盖的做法来做就可以了。

(6)最长反链和最小链覆盖

在DAG中,链是一个点的集合,这个集合中任意两个元素v、u,要么v能走到u,要么u能走到v。反链是一个点的集合,这个集合中任意两点谁也不能走到谁。

最长反链是反链中点最多的。可以认为是一个偏序集的最大独立集。

最小链覆盖。就是用最少的链,经过所有的点至少一次,可以认为是路径可以相交的最小路径覆盖。

Dilworth定理:最大反链=最小链覆盖

它的对偶定理:最长链长度=最小反链覆盖

证明

9.欧拉函数的相关

(1)

证明:

设集合S={1,2,3,……n-1,n}。这些是所有小于等于n的数的集合。

考虑把这些数分类。我们按照每个数和n的最大公因数来分类,因为每个数和n的最大公因数都是确定的,而且按照最大公因数来分的话,每个数都会被分到有且仅有一次。

设存在一个数,那么自然有一些数是满足,那么这些中满足这个关系的数的个数和x中满足的个数是一样的。而这个个数是

那么枚举n的所有因子d,就自然把所有的数(1-n)分类了,而这个自然就是

(2)如果出现要计算这样的东西,因为欧拉函数的减少程度比log还要低,所以暴力计算到的时候就可以了。不会超过Logn项。。。 cf 776E

(3)当\(n \geq 1\),\(1\)到\(n\)的所有和\(n\)互质的数的整数和为\(\frac{n*\phi(n)}{2}\)。

因为\(gcd(n,i)=1\)可以推得\(gcd(n,n-i)=1\),所以与\(n\)互质的\(i\)是成对出现的他们的和是\(n\)。

(4)欧拉函数线性筛的理论依据:链接

10.范德蒙恒等式

有个证明,非常好懂:链接

11.

考虑组合数学的意义:等式右边相当于从a+b个中选出来b+1个东西。等式左边相当于枚举第二个选择的位置在哪里。也就是在前i个中选择第一个,i+1选择第二个,剩余的在a+b-1-i个中选择。

12.莫比乌斯反演相关

(1)简单写一下定义什么的。

(2)

对于n=1,显然成立。

当n>1时,只有由互异质因子组成的d对于答案有贡献。假设\(d=\prod _{i=1}^{k}p_i\),那么自然有\(\sum_{d|n}\mu(d)=\sum_{i=0}^{k} \binom{k}{i}(-1)^{i}\)。由二项式定理可知\((-1+1)^{k}=\sum_{i=0}^{k} \binom{k}{i}(-1)^{i}*1^{k-i}=0\)。得证。

(3)反演

形式1:

\(f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k)\),换一下主体得到:\(f(n)=\sum_{k|n}f(k)\sum_{d|\frac{n}{k}}\mu(d)=f(n)\)。

形式2:

还是像上面推,设\(k=n/d\)。

\( f(n)=\sum_{k=1}\mu(k)F(nk)=\sum_{k=1}\mu(k)\sum_{nk|t}f(t)=\sum_{n|t}f(t)\sum_{k|\frac{t}{n}}\mu(k)=f(n)\)。

就是这样QAQ。。。

13.有一个有趣的idea: \(F(x)=F(x-1)+F(x-m)   x%m!=0&&x>m\),\(F(x)=1,x<=M||x%m==0\)。求F(x)。

其实是组合数。以\(m\)为周期展开成两维即可。
14.和n!/e最接近的整数是n个元素的错排数。错排写成容斥形式,e用指数函数的麦克劳林公式展开可证(clearY语)。

一些简单的想法》上有3条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注