- 博客(330)
- 收藏
- 关注
RSS订阅
原创 [最小割] BZOJ3144: [Hnoi2013]切糕
经典的最小割建图，用 ∞∞\infty 边体现限制条件。inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int getint(){ ...
2018-02-21 22:26:54
521
原创 [最小割+Tarjan] BZOJ1797: [Ahoi2009]Mincut 最小割
关于最小割唯一性：在残余网络上跑 TarjanTarjanTarjan 。记 idxidxid_x为点 xxx 所在 SCCSCCSCC 的编号。将每个 SCCSCCSCC 缩成一个点，得到的新图就只含有满流边了。那么新图的任一 S−TS−TS-T 割都对应原图的某个最小割。对于任意一条满流边 (u,v)(u,v)(u,v)，若能够出现在某个最小割集中，当且仅当 idu≠idvidu≠...
2018-02-21 21:47:30
570
原创 《最小割模型在信息学竞赛中的应用》——学习笔记
《最小割模型在信息学竞赛中的应用》学习笔记基础流网络的定义，容量限制，反对称性，流守恒性…我们约定对于点集X,YX,YX,Y ,令 f(X,Y)=∑u∈X∑v∈Yf(u,v)f(X,Y)=∑u∈X∑v∈Yf(u,v)f(X,Y)=\sum_{u \in X}\sum_{v \in Y} f(u,v) ∀X,f(X,X)=0∀X,Y,f(X,Y)=−f(Y,X)∀X,Y,Z,&nb...
2018-02-16 00:44:50
993
原创 [最小割] BZOJ2400: Optimal Marks
论文题。 二进制每位独立算，每个编号就只有 010101 两种。可以看作分成两个集合，用最小割模型解。 题目要求在边权和最小的前提下，还要保证编号和最小。这个只需要每次从 TTT 出发倒着走，能到的点一定是在 TTT 集合内，其他的都看作是 000，这样就是最小的。#include<cstdio>#include<cctype>#include<cst...
2018-02-14 23:39:21
407
原创 [Matrix-Tree 定理] SPOJ HIGH - Highways
模板题。Matrix−TreeMatrix−TreeMatrix-Tree 定理用于求生成树个数。给出一个无向图 GGG ,GGG 的度数矩阵 DDD 是一个 n∗nn∗nn∗n 的矩阵，当 i≠ji≠ji \neq j 时, di,j=0di,j=0d_{i,j}=0 ,di,idi,id_{i,i} 等于 iii 的度数。GGG 的邻接矩阵为 AAA 。我们定义 GGG 的 Kir...
2018-02-13 21:34:38
428
原创 [二进制分组 + 凸包] BZOJ4140: 共点圆加强版
对于给出的一个圆心 (xi,yi)(xi,yi)(x_i,y_i) ，在它内部点 (x,y)(x,y)(x,y) 需满足 (x−xi)2+(y−yi)2≤x2i+y2i⇔x2+y2≤2xxi+2yyi⇔yi≥−xyxi+x2+y22y(x−xi)2+(y−yi)2≤xi2+yi2⇔x2+y2≤2xxi+2yyi⇔yi≥−xyxi+x2+y22y(x-x_i)^2+(y-y_i)^2 \le x...
2018-02-11 23:47:36
461
原创 斯特林数(Stirling)——学习笔记
第一类斯特林数s(n,m)s(n,m)s(n,m) 表示 nnn 个元素组成 mmm 个圆排列 有 s(n,m)=s(n−1,m−1)+s(n−1,m)∗(n−1)s(n,m)=s(n−1,m−1)+s(n−1,m)∗(n−1)s(n,m)=s(n−1,m−1)+s(n−1,m)∗(n−1)s(n,m)=∑i=1ns(n−i,m−1)(n−1i−1)(i−1)!s(n,m)=...
2018-02-11 20:30:25
1088
原创 伯努利数(Bernoulli)——学习笔记
http://www.bernoulli.org/ http://blog.csdn.net/whai362/article/details/43148939 https://baike.baidu.com/item/%E4%BC%AF%E5%8A%AA%E5%88%A9%E6%95%B0/1304247?fr=aladdin https://www.cnblogs.com...
2018-02-10 22:21:54
6235
原创 [分治FFT] HDU5730 Shell Necklace
分治 FFTFFTFFT，就是 CDQCDQCDQ 分治加 FFTFFTFFT。 用来解决这样的问题：已知 g(x)g(x)g(x)，且 f(i)=∑i=0n−1f(i)g(n−i)f(i)=∑i=0n−1f(i)g(n−i)f(i)=\sum_{i=0}^{n-1} f(i)g(n-i) 求 f(x)f(x)f(x)。 就是直接 CDQCDQCDQ 分治，算 [L,mid][L,mi...
2018-02-09 23:25:52
467
原创 [原根 + NTT] LOJ#2183 BZOJ3992:「SDOI2015」序列统计
做法比较显然，应该就是这样的 DPDPDP : f(i)=∑j∗k≡i(modm)f′(j)g(k)f(i)=∑j∗k≡i(modm)f′(j)g(k) f(i)=\sum_{j*k \equiv i \pmod m} f'(j)g(k) 可以用原根转化为加法，就变成 f(i)=∑j+k≡i(modm)f′(j)g(k)f(i)=∑j+k≡i(modm)f′(j)g(k)f(i)=\...
2018-02-09 15:42:33
464
原创 快速数论变换(NTT)——学习笔记
NTT嗷， 很简单。FFTFFTFFT 之所以能加速，是由于有主n次单位根 wn=e2πinwn=e2πinw_n=e^{\frac{2\pi i}{n}} ，的那些很好的性质。而在自然数域，模 PPP 意义下，可以把 wnwnw_n 换成 gP−1ngP−1ng^{\frac{P-1}{n}} ，ggg 是 PPP 的原根，可以发现那些性质是类似的。逆变换也是把 gP−1ngP−1ng...
2018-02-08 21:30:20
4145
原创 多项式求逆——学习笔记
基本概念多项式的度：对于一个多项式 A(x)A(x)A(x) ,称其最高项次数为多项式的度，记作 degAdegAdeg A 多项式的逆元：对于 A(x)A(x)A(x) 若存在 B(x)B(x)B(x) 满足 degB≤degAdegB≤degAdegB \le degA 且 A(x)B(x)≡1(modxn)A(x)B(x)≡1(modxn) A(x)B(x) \equiv 1...
2018-02-08 18:56:03
1512
原创 【施工ing】生成函数与多项式——学习笔记
生成函数大概是一个无穷幂级数形式的函数，我们只关心它的形式，而不会去带入 xx 求值。可以看做是多项式，只是带入没有意义。它的一些运算可以对应组合意义，所以能通过它解决一些组合问题。一般生成函数(OGF)：f(x)=a0+a1x1+a2x2+a3x3+a4x4...f(x)=a_0+a_1x^1+a_2x^2+a_3x^3+a_4x^4...指数型生成函数（EGF），之后会看到为什么要
2018-01-18 21:16:11
892
原创 Emacs 配置
记一下…(custom-set-variables ;; custom-set-variables was added by Custom. ;; If you edit it by hand, you could mess it up, so be careful. ;; Your init file should contain only one such instance.
2017-12-29 10:32:56
396
原创 [线性基] BZOJ2844: albus就是要第一个出场
有个结论：一个可异或得到的数，用原来 nn 个数异或得到它都有 2n−cnt2^{n-cnt} 种组合方法。想想发现是很有道理的，就是不要把消出的 n−cntn-cnt 扔掉，00 怎么异或都不变的，所以是 2n−cnt2^{n-cnt}。 知道这个就做完了。#include<cstdio>#include<algorithm>using namespace std;const int MO
2017-12-24 21:20:10
432
原创 [DFS树 + 线性基] BZOJ2115: [Wc2011] Xor
线性基裸题。需要知道一个东西：对于随意一条 11 到 nn 的路径的异或和，都可以通过任意一条 11 到 nn 路径的异或和与图中的一些环的异或和来组合得到。 然后就 DFSDFS 树找简单环，瞎搞搞…#include<cstdio>#include<algorithm>using namespace std;const int maxn=50005,maxe=200005;typedef
2017-12-24 19:30:12
396
原创 [线性基] HDU3949: XOR
裸题。线性基消成对角后， 最高位为 i 的数是唯一的。这个性质很好，使得选的数集中最大数的最高位，在异或后一定是 11。设 bib_i 为线性基第 ii 小的数，kik_i 为二进制下第 ii 位。 答案就是 Xor b[i]ki \text{Xor } b[i]k_i。#include<cstdio>#include<cstring>#include<algorithm>using nam
2017-12-24 18:53:18
337
原创 线性基——学习笔记
http://blog.csdn.net/qaq__qaq/article/details/53812883 https://blog.sengxian.com/algorithms/linear-basis https://www.cnblogs.com/vb4896/p/6149022.html 一些线代前置知识： 向量空间 \quad 定义 (F,V,+,⋅)(F, V, +, \c
2017-12-19 21:20:21
537
原创 [WQS二分套WQS二分] Codeforces #739E. Gosha is hunting
O(n3)O(n^3) DPDP 很显然。要优化就只能 WQSWQS 二分了。每种食物肯定是都用完的，所以相当于强制选若干个 AA 物品，若干个 BB 物品。发现物品选越多，收益是会增加的越来越慢的，所以这两维都可以 WQSWQS 二分。就能做到 O(nlog2n)O(nlog^2 n) ,很优美。 http://codeforces.com/blog/entry/49691 #include<c
2017-12-19 19:12:39
895
原创 [WQS二分] BZOJ2654：tree
以前做这题的时候以为只是个神奇的二分，没有完全懂原理，现在发现实际上就是 WQSWQS 二分。 考虑 g(x)g(x) 表示选共 xx 条白边的最优解，可以感觉到这个 g(x)g(x) 应是上凸的，满足斜率不降。所以就 WQSWQS 二分就好了。#include<cstdio>#include<algorithm>using namespace std;const int maxn=1000
2017-12-19 18:25:29
621
原创 WQS二分——学习笔记
http://www.doc88.com/p-949564862405.html http://codeforces.com/blog/entry/49691 我的理解 (不一定很对)： 大概就是某个东西越多总贡献越大，要求刚好取n个时的最优解。可以把 DPDP 状态里记的取的个数这一维去掉，而设一个 costcost，取 kk 个物品，总贡献要多减去cost*k，然后 DPDP 。costc
2017-12-17 20:24:44
3619
原创 [错排] BZOJ2034:「SDOI2016」排列计数
大水题。 主要是记一下错排的公式。顺便水一水 递推公式：fi=(i−1)(fi+fi−1)f_i=(i-1)(f_i+f_{i-1}) 推导过程大概是，考虑数字ii, 它有 i−1i-1 种可能的位置，设 ii 在位置 kk ,则数字 kk 可能放在 位置 ii 或不放在位置 ii。放在位置 ii , 则其他方案数等价于 fi−2f_{i-2}，否则等价于 fi−1f_{i-1}。 还有一个
2017-12-14 20:33:18
440
原创 [树上依赖背包] BZOJ4910 LOJ2268: [SDOI2017] 苹果树
首先考虑 t−hmax≤kt-h_{max} \le k 的限制。可以看做除去最长到根链上的点各一个，剩下的最多取 kk 。 可以想到枚举叶子，求必选这个叶到根路径上各一个之后，其他取 kk 个的最大值。 普通的树上依赖背包一般是： 按后序遍历顺序 DPDP , fi,jf_{i,j} 表示后序遍历前 ii 个中选了 jj 个的最优解，后序遍历的好处是 ii 的子树内的点是 ii 前面的连续一
2017-12-14 19:52:17
757
原创 [Johnson + 桶维护DIJ ] Codeforces #843D. Dynamic Shortest Path
这题用到了 JohnsonJohnson 算法的思想，就是先一趟最短路刷出 dis(i)dis(i) 然后把图改造。边 (x,y)(x,y) 的权改为 w(x,y)+dis(x)−dis(y)w(x,y)+dis(x)-dis(y)。 这样搞之后，边权都非负，再新图上做最短路的事情与原图是完全等价的，新图上从 11 到 vv 的某条路径的长度就是原图的对应长度与 dis(v)dis(v) 的差值。
2017-12-10 20:33:35
703
原创 [dsu on tree] Codeforces #741D. Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths
考虑一个字符集，若能排成回文串，则出现个数是奇数的字符种数是0或1。字符有22种，就想到异或。 合法的链 (x,y)(x,y) 满足 s(x) xor s(y)=0或2is(x)\text{ xor }s(y)=0或2^{i}。 直接 dsu on tree 瞎搞。 #include<cstdio>#include<vector>#include<algorithm>using names
2017-12-07 21:18:56
550
原创 [dsu on tree] Codeforces #600E. Lomsat gelral
所谓dsu on tree，就是树上的启发式合并，处理出重儿子然后搞就行了。树的特殊性会使写起来比数据结构启发式合并方便一点。只需维护一个数据结构，支持插入删除单个元素。 这题就是模板题啦…#include<cstdio>#include<vector>#include<algorithm>using namespace std;typedef long long LL;const in
2017-12-05 20:26:41
317
原创 [矩阵乘法] LOJ#2002. 「SDOI2017」序列计数
注意到 pp 很小，容易想到矩乘。fi→f(i+j)%Pf_i \to f_{(i+j)\text{%}P}。 关于那个质数的限制，只需要 11 到 mm的方案 减去 11 到 mm 扣去所有质数的方案即可。 构造 11 到 mm 转移矩阵 P2P^2 搞。扣去质数直接暴力 O(m/lnm∗P)O(m/\ln m*P)。#include<cstdio>#include<cstring>#in
2017-12-02 11:02:36
485
原创 [树链剖分+李超线段树] BZOJ4515: [Sdoi2016]游戏
先进行转化，把路径分成两条链，a(deps−depi)+b=(−a)∗depi+a∗deps+ba(dep_s-dep_i)+b=(-a)*dep_i+a*dep_s+b…类似这样变形一下，就转化成和 k∗depi+bk*dep_i+b 的形式。depidep_i 是递增的，所以可以看做是一次函数 y=kx+by=kx+b 在某些离散的点上有定义。 现在需要实现区间插入线段，求区间最小值。这个问题
2017-12-02 06:19:04
433
原创 [数论杂题] BZOJ1951: [Sdoi2010]古代猪文
为了数论而数论的题…..没什么技术含量… 就是求： G∑i|n(ni)%P=G(∑i|n(ni)%ϕ(P))%PG^{\sum_{i|n} {n\choose i}} \text{%} P=G^{(\sum_{i|n} {n\choose i}\text{%} \phi(P))} \text{%} P 现在需要求 (∑i|n(ni))%M(\sum_{i|n} {n\choose i})\
2017-11-28 20:36:04
516
原创 [SG函数 + 分块] BZOJ4035: [HAOI2015]数组游戏
博弈好题。这种博弈的01取反的模型可以把白色看做有奇数个石子，黑色看做偶数个，因为同一位置偶数个石子SG值异或会抵消….. 这么理解的话，可以把一个石子，即一个白块看做一个独立的游戏。 现在只需求SG值。 SG(i)=mex{0,SG(2i),SG(2i) ^ SG(3i),SG(2i) ^ SG(3i) ^ SG(4i),...} SG(i)=\text{mex}\{0,SG(2i),SG
2017-11-28 19:36:29
485
原创 [虚树 + DP] BZOJ2286: [Sdoi2011]消耗战
虚树入门题。 所谓虚树就是只保留需要的关键节点及互相的lca进行重建树，在虚树上跑DP之类的，是的复杂度之和关键点个数相关。 建虚树代码：void buildVT(){ inT.clear(); sort(S.begin(),S.end(),_cmp); stk[top=1]=1; inT.push_back(1); for(int i=0;i<S.size();i++)
2017-11-26 20:11:09
387
原创 [DP+AC自动机] BZOJ1212: [HNOI2004]L语言
直接 DPDP，fif_{i} 表示前 ii 个是否合法。fi|=fi−len(aj)(s[i−len(aj)+1]=aj)f_{i}|=f_{i-len(a_j)}(s[i-len(a_j)+1]=a_j) 用ACAC自动机加速转移的匹配过程。#include<cstdio>#include<queue>#include<algorithm>#include<cstring>using
2017-11-26 16:33:05
371
原创 [矩阵乘法] BZOJ2326: [HNOI2011]数学作业
我们一个一个接上，应该是 res=res∗10t(i)+ires=res*10^{t(i)}+i 这样的形式，其中t(i)t(i) 表示 ii 的位数。 怎么样快速算呢，看成递推式：f(i)=f(i−1)∗10t(i)+if(i)=f(i-1)*10^{t(i)}+i 。显然可以用矩乘加速。位数相同的一起搞就行了。#include<cstdio>#include<cstring>#includ
2017-11-26 16:27:17
427
原创 [SG函数] BZOJ1188: [HNOI2007]分裂游戏
可以发现，一颗石子可以看作是一个独立的游戏。 nn 很小，瞎暴力求 SGSG 函数就好啦。#include<cstdio>#include<algorithm>using namespace std;const int maxn=105;int _test,n,allsg,a[maxn],sg[maxn],vis[maxn],clk,ans,ans1,ans2,ans3;int main
2017-11-26 16:20:07
381
原创 [DP] BZOJ4321. queue2
套路DP…这种和相邻数有关的一般考虑从小到大插入。 fi,j,0/1f_{i,j,0/1} 表示放了前 ii 个数，有 jj 个间隙两数相邻，0/10/1 表示 ii 和 i−1i-1 是否相邻。就好了。#include<cstdio>#include<algorithm>using namespace std;const int maxn=1005,MOD=7777777;typedef
2017-11-10 14:28:07
312
原创 [二分图最大独立集] BZOJ4808：马
棋盘01染色，然后把互相能打到的点连边，发现是个二分图。 二分图最大独立集 == 点数 −- 最大匹配数 Dinic练手…#include<cstdio>#include<queue>#include<cstring>#include<algorithm>using namespace std;const int maxn=40005,maxe=400005,flag[8][2]={{
2017-11-10 11:53:34
393
原创 [DP] Codeforces #714E. Sonya and Problem Wihtout a Legend
不严格的比较简单，其实严格的可以转化成不严格的： i<j,aj−ai≥j−i⇔ai−i≤aj−ji<j,\quad a_j-a_i \ge j-i \Leftrightarrow a_i-i \le a_j-j 就是满足 ai−ia_i-i 不严格递增就好了。 不严格的做法就是直接 DPDP，改变的值肯定是原本就有的数，数的值范围是 O(n)O(n)。直接 fi,jf_{i,j} 表示前 ii
2017-11-09 11:26:14
423
原创 [杂题] Codeforces #598B. Queries on a String
简单题。直接考虑原来的某个位置的元素最后到了哪里….O(nm)O(nm)#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=10005,maxm=305;int n,m,L[maxm],R[maxm],rd[maxm];char s[maxn],res[maxn];
2017-11-08 20:36:36
380
原创 [杂题 计数 图论] Codeforces 51E. Pentagon
挺烦的题…..很容易wa… 总之就是求出 Bi,jB_{i,j} 表示 ii 到 jj ,走两步的方案，Ci,jC_{i,j} 表示走三步。 然后 ∑Bi,j∗Ci,j\sum B_{i,j}*C_{i,j}。然后会有不合法的和重复的… 不合法的大概是 一个三角形多出一个脚…或者就是一个三角形… 在纸上大力分类讨论一下，把它们都扣去就好了。 参考了网上dalao的实现。#include<cs
2017-11-08 20:12:50
475
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人