邝斌的ACM模板

更新时间：2024-03-14 04:07:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

1 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

字符串处理 ........................................... 3

1、KMP 算法 ..................................... 3 2、扩展KMP ..................................... 4 3、Manacher 最长回文子串 ........................ 5 4、AC 自动机 .................................... 5 5、后缀数组 ..................................... 7 6、后缀自动机 ................................... 9 7、字符串HASH ................................. 10 数学 ................................................ 10

1、素数 ........................................ 10 2、素数筛选和合数分解 .......................... 12 3、扩展欧几里得算法（求ax+by=gcd 的解以及逆元素） ............................................... 12 4、求逆元 ...................................... 12 5、模线性方程组 ................................ 12 6、随机素数测试和大数分解(POJ 1811) ............ 13 7、欧拉函数 .................................... 14 8、高斯消元（浮点数） .......................... 15 9、FFT ......................................... 16 10、高斯消元法求方程组的解 ..................... 17 11、整数拆分 ................................... 20 12、求A^B 的约数之和对MOD 取模 ................ 21 13、莫比乌斯反演 ............................... 22 14、Baby-Step Giant-Step ....................... 23 15、自适应simpson 积分 ......................... 23 相关公式 ....................................... 23 数据结构 ............................................ 24

1、划分树 ...................................... 24 2、RMQ ......................................... 25 3、树链剖分 .................................... 26 4、伸展树（splay tree） ........................ 29 5、动态树 ...................................... 31 6、主席树 ...................................... 34 7、Treap ....................................... 40 图论 ................................................ 41

1、最短路 ...................................... 42 2、最小生成树 .................................. 44 3、次小生成树 .................................. 44 4、有向图的强连通分量 .......................... 45 5、图的割点、桥和双连通分支的基本概念 .......... 46

6、割点与桥 ..................................... 47 7、边双连通分支 ................................. 48 8、点双连通分支 ................................. 50 9、最小树形图 ................................... 51 10、二分图匹配 .................................. 52 11、生成树计数 .................................. 54 11、二分图多重匹配 .............................. 56 12、KM 算法（二分图最大权匹配） ................. 56 13、最大流 ...................................... 57 14、最小费用最大流 .............................. 60 15、2-SAT ....................................... 61 16、曼哈顿最小生成树 ............................ 64 17、一般图匹配带花树 ............................ 65 18、LCA ......................................... 67 19、欧拉路 ...................................... 70 计算几何 ............................................. 73

1、基本函数 ..................................... 73

2、凸包138

3、平面最近点对（HDU1007）139 4、旋转卡壳140 5、半平面交146

6、三点求圆心坐标（三角形外心）149 7、求两圆相交的面积150 8、Pick公式150 动态规划150

1、最长上升子序列O(nlogn)150 搜索151

1、DancingLinks151 其他156

1、高精度156 2、完全高精度158

3、strtok 和sscanf结合输入163 4、解决爆栈，手动加栈163 5、STL163

6、输入输出外挂165 7、莫队算法166 8、VIM配置172

改版者言：

此版本是由2013-11-8月上传的pdf文档改版的。非2013-9-27版本的改版。做了写简单处理内部代码没动过但是：

本文的格式发生改动部分文字的格式出现问题一些表达式已无法辨认代码中少量大括号错位目录无法正常使用，

2 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

字符串处理 1、KMP 算法

* next[]的含义：x[i-next[i]...i-1]=x[0...next[i]-1]

* next[i]为满足x[i-z...i-1]=x[0...z-1]的最大z值（就是x的自身匹配） */

void kmp_pre(char x[],int m,int next[]) {

int i,j; j=next[0]=-1; i=0; while(i

while(-1!=j && x[i]!=x[j])j=next[j]; next[++i]=++j;

}

} /*

* kmpNext[]的意思：next'[i]=next[next[...[next[i]]]] (直到next'[i]<0或者 x[next'[i]]!=x[i]) * 这样的预处理可以快一些 */

void preKMP(char x[],int m,int kmpNext[]) {

int i,j; j=kmpNext[0]=-1; i=0; while(i

while(-1!=j && x[i]!=x[j])j=kmpNext[j]; if(x[++i]==x[++j])kmpNext[i]=kmpNext[j]; else kmpNext[i]=j;

}

} /*

* 返回x在y中出现的次数，可以重叠 */

int next[10010];

int KMP_Count(char x[],int m,char y[],int n) {//x是模式串，y是主串

int i,j; int ans=0;

//preKMP(x,m,next); kmp_pre(x,m,next); i=j=0; while(i

while(-1!=j && y[i]!=x[j])j=next[j]; i++;j++; if(j>=m) {

ans++; j=next[j];

}

return ans;

}

经典题目：POJ 3167

* POJ 3167 Cow Patterns * 模式串可以浮动的模式匹配问题

* 给出模式串的相对大小，需要找出模式串匹配次数和位置

* 比如说模式串：1，4，4，2，3，1 而主串：5,6,2,10,10,7,3,2,9 * 那么2,10,10,7,3,2就是匹配的 *

* 统计比当前数小，和于当前数相等的，然后进行kmp */

#include #include #include #include

#include using namespace std; const int MAXN=100010; const int MAXM=25010; inta[MAXN]; int b[MAXN]; int n,m,s;

int as[MAXN][30]; int bs[MAXM][30]; void init() {

for(int i=0;i

if(i==0) {

for(int j=1;j<=25;j++)as[i][j]=0;

} else {

for(int j=1;j<=25;j++)as[i][j]=as[i-1][j];

}

as[i][a[i]]++;

}

for(int i=0;i

if(i==0) {

for(int j=1;j<=25;j++)bs[i][j]=0;

3 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

} else {

for(int j=1;j<=25;j++)bs[i][j]=bs[i-1][j];

}

bs[i][b[i]]++;

}

int next[MAXM]; void kmp_pre() {

int i,j; j=next[0]=-1; i=0; while(i

int t11=0,t12=0,t21=0,t22=0; for(int k=1;k

if(i-j>0)t11+=bs[i][k]-bs[i-j-1][k]; else t11+=bs[i][k];

}

if(i-j>0)t12=bs[i][b[i]]-bs[i-j-1][b[i]]; else t12=bs[i][b[i]]; for(int k=1;k

t21+=bs[j][k];

}

t22=bs[j][b[j]];

if(j==-1 || (t11==t21&&t12==t22)) {

next[++i]=++j;

}

else j=next[j];

}

vectorans; void kmp() {

ans.clear(); int i,j; kmp_pre(); i=j=0;

while(i

int t11=0,t12=0,t21=0,t22=0; for(int k=1;k

if(i-j>0)t11+=as[i][k]-as[i-j-1][k]; else t11+=as[i][k];

}

if(i-j>0)t12=as[i][a[i]]-as[i-j-1][a[i]]; else t12=as[i][a[i]]; for(int k=1;k

t21+=bs[j][k];

}

t22=bs[j][b[j]];

if(j==-1 || (t11==t21&&t12==t22)) {

i++;j++; if(j>=m) {

ans.push_back(i-m+1); j=next[j];

}

else j=next[j];

}

int main() {

while(scanf(\,&n,&m,&s)==3) {

for(int i=0;i

scanf(\,&a[i]);

}

for(int i=0;i

scanf(\,&b[i]);

}

init();

kmp(); printf(\,ans.size()); for(int i=0;i

printf(\,ans[i]);

}

return 0;

}

2、扩展KMP

* 扩展KMP算法 */

//next[i]:x[i...m-1]与x[0...m-1]的最长公共前缀 //extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀

4 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

void pre_EKMP(char x[],int m,int next[]) {

next[0]=m; int j=0;

while(j+1

for(int i=2;i

int p=next[k]+k-1; int L=next[i-k]; if(i+L

j=max(0,p-i+1);

while(i+j

}

void EKMP(char x[],int m,char y[],int n,int next[],int extend[]) {

pre_EKMP(x,m,next); int j=0;

while(j

for(int i=1;i

int p=extend[k]+k-1; int L=next[i-k]; if(i+L

j=max(0,p-i+1);

while(i+j

}

3、Manacher 最长回文子串

* 求最长回文子串 */

const int MAXN=110010; char Ma[MAXN*2]; int Mp[MAXN*2];

void Manacher(char s[],int len) {

int l=0; Ma[l++]='$'; Ma[l++]='#';

for(int i=0;i

Ma[l++]=s[i]; Ma[l++]='#';

}

Ma[l]=0;

int mx=0,id=0;

for(int i=0;i

Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;

while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++; if(i+Mp[i]>mx) {

mx=i+Mp[i]; id=i;

}

} /*

* abaaba

*i:0 1 2 3 4 5 6 7 8 9 10 11 1213

* Ma[i]: $ # a # b # a # a $ b # a # * Mp[i]: 1 1 2 1 4 1 2 7 2 1 4 1 2 1 */

char s[MAXN]; int main() {

while(scanf(\,s)==1) {

int len=strlen(s); Manacher(s,len); int ans=0; for(int i=0;i<2*len+2;i++) ans=max(ans,Mp[i]-1); printf(\,ans);

}

return 0;

}

4、AC 自动机

//====================== // HDU 2222

// 求目标串中出现了几个模式串 //==================== #include #include

5 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

#include #include #include

using namespace std; struct Trie {

int next[500010][26],fail[500010],end[500010]; int root,L; int newnode() {

for(int i = 0;i < 26;i++) next[L][i] = -1; end[L++] = 0; return L-1;

}

void init() {

L = 0;

root = newnode();

}

void insert(char buf[]) {

int len = strlen(buf); int now = root; for(int i = 0;i < len;i++) {

if(next[now][buf[i]-'a'] == -1)

next[now][buf[i]-'a'] = newnode();

now = next[now][buf[i]-'a'];

}

end[now]++;

}

void build() {

queueQ; fail[root] = root; for(int i = 0;i < 26;i++)

if(next[root][i] == -1) next[root][i] = root; else {

fail[next[root][i]] = root; Q.push(next[root][i]);

}

while( !Q.empty() ) {

int now = Q.front(); Q.pop(); for(int i = 0;i < 26;i++)

if(next[now][i] == -1)

next[now][i] = next[fail[now]][i];

else {

fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]);

}

int query(char buf[]) {

int len = strlen(buf); int now = root; int res = 0;

for(int i = 0;i < len;i++) {

now = next[now][buf[i]-'a']; int temp = now;

while( temp != root ) {

res += end[temp]; end[temp] = 0; temp =fail[temp];

}

return res;

}

void debug() {

for(int i = 0;i

printf(\,i,fail[i],end[i]); for(int j = 0;j < 26;j++)

printf(\,next[i][j]); printf(\);

}

};

char buf[1000010]; Trie ac; int main() {

int T;

int n; scanf(\,&T); while( T-- ) {

scanf(\,&n); ac.init(); for(int i = 0;i

6 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

scanf(\,buf); ac.insert(buf);

}

ac.build();

scanf(\,buf); printf(\,ac.query(buf));

}

return 0;

}

5、后缀数组

5.1 DA 算法

*suffix array

*倍增算法O(n*logn)

*待排序数组长度为n,放在0~n-1中，在最后面补一个0 *da(str,n+1,sa,rank,height,,);//注意是n+1; *例如： *n=8;

*num[]= { 1, 1, 2, 1, 1, 1, 1, 2, $};注意num最后一位为0，其他大于0

*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值 *sa[]= { 8, 3, 4, 5, 0, 6, 1, 7, 2};sa[1~n]为有效值，sa[0]必定为n是无效值 *height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值 * */

const int MAXN=20010;

int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值 //待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m, //除s[n-1]外的所有s[i]都大于0，r[n-1]=0 //函数结束以后结果放在sa数组中

bool cmp(int *r,int a,int b,int l) {

return r[a] == r[b] && r[a+l] == r[b+l];

}

void da(int str[],int sa[],int rank[],int height[],int n,int m) {

n++;

int i, j, p, *x = t1, *y = t2;

//第一轮基数排序，如果s的最大值很大，可改为快速排序 for(i = 0;i < m;i++)c[i] = 0;

for(i = 0;i < n;i++)c[x[i] = str[i]]++; for(i = 1;i < m;i++)c[i] += c[i-1];

for(i = n-1;i >= 0;i--)sa[--c[x[i]]] = i; for(j = 1;j <= n; j <<= 1) {

p = 0;

//直接利用sa数组排序第二关键字

for(i = n-j; i < n; i++)y[p++] = i;//后面的j个数第二关键字为空的最小 for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j; //这样数组y保存的就是按照第二关键字排序的结果 //基数排序第一关键字

for(i = 0; i < m; i++)c[i] = 0;

for(i = 0; i < n; i++)c[x[y[i]]]++; for(i = 1; i < m;i++)c[i] += c[i-1];

for(i = n-1; i >= 0;i--)sa[--c[x[y[i]]]] = y[i]; //根据sa和x数组计算新的x数组 swap(x,y); p = 1; x[sa[0]] = 0; for(i = 1;i < n;i++)

x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;

if(p >= n)break;

m = p;//下次基数排序的最大值 }

int k = 0; n--;

for(i = 0;i <= n;i++)rank[sa[i]] = i; for(i = 0;i < n;i++) {

if(k)k--;

j = sa[rank[i]-1]; while(str[i+k] == str[j+k])k++; height[rank[i]] = k; } }

int rank[MAXN],height[MAXN]; int RMQ[MAXN]; int mm[MAXN];

int best[20][MAXN]; void initRMQ(int n) {

mm[0]=-1;

for(int i=1;i<=n;i++)

mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; for(int i=1;i<=n;i++)best[0][i]=i; for(int i=1;i<=mm[n];i++)

for(int j=1;j+(1<

int a=best[i-1][j];

int b=best[i-1][j+(1<<(i-1))];

if(RMQ[a]

7 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

int askRMQ(int a,int b) {

int t; t=mm[b-a+1]; b-=(1<

a=best[t][a];b=best[t][b]; return RMQ[a]

int lcp(int a,int b) {

a=rank[a];b=rank[b]; if(a>b)swap(a,b);

return height[askRMQ(a+1,b)]; }

char str[MAXN]; int r[MAXN]; int sa[MAXN]; intmain() {

while(scanf(\,str) == 1) {

int len = strlen(str); int n = 2*len + 1; for(int i = 0;i < len;i++)r[i] = str[i];

for(int i = 0;i < len;i++)r[len + 1 + i] = str[len - 1 - i]; r[len] = 1; r[n] = 0;

da(r,sa,rank,height,n,128);

for(int i=1;i<=n;i++)RMQ[i]=height[i]; initRMQ(n); int ans=0,st; int tmp;

for(int i=0;i

tmp=lcp(i,n-i);//偶对称 if(2*tmp>ans) {

ans=2*tmp; st=i-tmp; }

tmp=lcp(i,n-i-1);//奇数对称 if(2*tmp-1>ans) {

ans=2*tmp-1; st=i-tmp+1; } }

str[st+ans]=0;

printf(\,str+st); }

return 0; }

5.2 DC3 算法

da[]和str[]数组要开大三倍，相关数组也是三倍

* 后缀数组

* DC3算法，复杂度O(n) * 所有的相关数组都要开三倍 */

const int MAXN = 2010;

#define F(x) ((x)/3+((x)%3==1?0:tb))

#define G(x) ((x)

int wa[MAXN*3],wb[MAXN*3],wv[MAXN*3],wss[MAXN*3]; int c0(int *r,int a,int b) {

return r[a] == r[b] && r[a+1] == r[b+1] && r[a+2] == r[b+2];

}

int c12(int k,int *r,int a,int b) {

if(k == 2)

return r[a] < r[b] || ( r[a] == r[b] && c12(1,r,a+1,b+1) );

else return r[a] < r[b] || ( r[a] == r[b] && wv[a+1] < wv[b+1] );

}

void sort(int *r,int *a,int *b,int n,int m) {

int i;

for(i = 0;i < n;i++)wv[i] = r[a[i]]; for(i = 0;i < m;i++)wss[i] = 0; for(i = 0;i

for(i = 1;i < m;i++)wss[i] += wss[i-1]; for(i = n-1;i >= 0;i--)

b[--wss[wv[i]]] = a[i];

}

void dc3(int *r,int *sa,int n,int m) {

int i, j, *rn = r + n;

int *san = sa + n, ta = 0, tb = (n+1)/3, tbc = 0, p; r[n] = r[n+1] = 0;

for(i = 0;i < n;i++)if(i %3 != 0)wa[tbc++] = i; sort(r + 2, wa, wb, tbc, m); sort(r + 1, wb, wa, tbc, m); sort(r, wa, wb, tbc, m);

for(p = 1, rn[F(wb[0])] = 0, i = 1;i < tbc;i++) rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p - 1 : p++; if(p < tbc)dc3(rn,san,tbc,p);

else for(i = 0;i < tbc;i++)san[rn[i]] = i;

8 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

for(i = 0;i < tbc;i++) if(san[i] < tb)wb[ta++] = san[i] * 3; if(n % 3 == 1)wb[ta++] = n - 1; sort(r, wb, wa, ta, m); for(i = 0;i < tbc;i++)wv[wb[i] = G(san[i])] = i; for(i = 0, j = 0, p = 0;i < ta && j < tbc;p++)

sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];

for(;i < ta;p++)sa[p] = wa[i++]; for(;j < tbc;p++)sa[p] = wb[j++];

}

//str和sa也要三倍

void da(int str[],int sa[],int rank[],int height[],int n,int m) {

for(int i = n;i < n*3;i++) str[i] = 0; dc3(str, sa, n+1, m); int i,j,k = 0;

for(i = 0;i <= n;i++)rank[sa[i]] = i; for(i = 0;i < n; i++) {

if(k) k--;

j = sa[rank[i]-1]; while(str[i+k] == str[j+k]) k++; height[rank[i]] =k;

}

6、后缀自动机

const int CHAR = 26; const int MAXN = 250010; struct SAM_Node {

SAM_Node *fa,*next[CHAR];

int len; int id,pos; SAM_Node(){} SAM_Node(int _len) {

fa = 0;

len = _len;

memset(next,0,sizeof(next)); } };

SAM_Node SAM_node[MAXN*2], *SAM_root, *SAM_last; int SAM_size;

SAM_Node *newSAM_Node(int len) {

SAM_node[SAM_size] = SAM_Node(len); SAM_node[SAM_size].id = SAM_size; return &SAM_node[SAM_size++]; }

SAM_Node *newSAM_Node(SAM_Node *p) {

SAM_node[SAM_size] = *p; SAM_node[SAM_size].id = SAM_size; return &SAM_node[SAM_size++]; }

void SAM_init() {

SAM_size = 0;

SAM_root = SAM_last = newSAM_Node(0); SAM_node[0].pos = 0; }

void SAM_add(int x,int len) {

SAM_Node *p = SAM_last, *np = newSAM_Node(p->len+1); np->pos = len; SAM_last = np;

for(;p && !p->next[x];p = p->fa) p->next[x] = np; if(!p) {

np->fa = SAM_root; return; }

SAM_Node *q = p->next[x]; if(q->len == p->len + 1) {

np->fa = q; return; }

SAM_Node *nq = newSAM_Node(q); nq->len = p->len + 1; q->fa = nq; np->fa = nq;

for(;p && p->next[x] == q;p = p->fa) p->next[x] = nq; }

void SAM_build(char *s) {

SAM_init();

int len = strlen(s); for(int i = 0;i < len;i++)

SAM_add(s[i] - 'a',i+1);

}

//加入串后进行拓扑排序。 char str[MAXN];

int topocnt[MAXN]; SAM_Node *topsam[MAXN*2];

int n = strlen(str); SAM_build(str); memset(topocnt,0,sizeof(topocnt)); for(int i = 0;i < SAM_size;i++)

topocnt[SAM_node[i].len]++;

for(int i = 1;i <= n;i++) topocnt[i] += topocnt[i-1];

9 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

for(int i = 0;i < SAM_size;i++)

topsam[--topocnt[SAM_node[i].len]] = &SAM_node[i];

多串的建立：

//多串的建立,注意SAM_init()的调用 void SAM_build(char *s) {

int len = strlen(s); SAM_last = SAM_root; for(int i = 0;i < len;i++) { i+1) )

}

if(!SAM_last->next[s[i]-'0']||!(SAM_last->next[s[i]-'0']->len== SAM_add(s[i] -'0',i+1); else SAM_last = SAM_last->next[s[i] - '0']; }

7、字符串HASH

HDU4622 求区间不相同子串个数 const int HASH = 10007; const int MAXN = 2010; struct HASHMAP {

int head[HASH],next[MAXN],size; unsigned long long state[MAXN]; int f[MAXN]; void init() {

size = 0;

memset(head,-1,sizeof(head));

}

int insert(unsigned long long val,int _id) {

int h = val%HASH;

for(int i = head[h]; i != -1;i = next[i])

if(val == state[i]) {

int tmp = f[i]; f[i] = _id; return tmp;

}

} } H;

f[size] = _id; state[size] = val; next[size] = head[h]; head[h] = size++; return 0;

const int SEED = 13331; unsigned long long P[MAXN]; unsigned long long S[MAXN]; char str[MAXN]; int ans[MAXN][MAXN]; int main() {

//freopen(\

//freopen(\P[0] = 1;

for(int i = 1;i < MAXN;i++) P[i] = P[i-1] * SEED; int T; scanf(\,&T); while(T--) {

scanf(\,str);

int n = strlen(str); S[0] = 0; for(int i = 1;i <= n;i++)

S[i] = S[i-1]*SEED + str[i-1];

memset(ans,0,sizeof(ans)); for(int L = 1; L <= n;L++) {

H.init();

for(int i = 1;i + L - 1 <= n;i++) {

int l = H.insert(S[i+L-1] - S[i-1]*P[L],i); ans[i][i+L-1] ++; ans[l][i+L-1]--;

}

for(int i = n;i >= 0;i--)

for(int j = i;j <= n;j++)

ans[i][j] += ans[i+1][j] + ans[i][j-1] - ans[i+1][j-1];

int m,u,v; scanf(\,&m); while(m--) {

scanf(\,&u,&v); printf(\,ans[u][v]);

}

return 0; }

数学 1、素数

1.1 素数筛选（判断

* 素数筛选，判断小于MAXN的数是不是素数。

* notprime是一张表，为false表示是素数，true表示不是素数 */

const int MAXN=1000010;

bool notprime[MAXN];//值为false表示素数，值为true表示非素数 void init() {

memset(notprime,false,sizeof(notprime)); notprime[0]=notprime[1]=true; for(int i=2;i

if(!notprime[i]) {

if(i>MAXN/i)continue;//防止后面i*i溢出(或者i,j用long long)

10 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

//直接从i*i开始就可以，小于i倍的已经筛选过了,注意是j+=i for(int j=i*i;j

}

1.2 素数筛选（筛选出小于等于 MAXN 的素数）

* 素数筛选，存在小于等于MAXN的素数 * prime[0] 存的是素数的个数 */

const int MAXN=10000; int prime[MAXN+1]; void getPrime() {

memset(prime,0,sizeof(prime)); for(int i=2;i<=MAXN;i++) {

if(!prime[i])prime[++prime[0]]=i;

for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++) {

prime[prime[j]*i]=1;

if(i%prime[j]==0) break; } } }

1.3 大区间素数筛选（POJ 2689）

* POJ 2689 Prime Distance

* 给出一个区间[L,U]，找出区间内容、相邻的距离最近的两个素数和 * 距离最远的两个素数。

* 1<=L

#include #include #include #include using namespace std;

const int MAXN=100010; int prime[MAXN+1]; voidgetPrime() {

memset(prime,0,sizeof(prime)); for(int i=2;i<=MAXN;i++) {

if(!prime[i])prime[++prime[0]]=i;

for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++) {

prime[prime[j]*i]=1; if(i%prime[j]==0)break;

}

bool notprime[1000010]; int prime2[1000010];

void getPrime2(int L,int R) {

memset(notprime,false,sizeof(notprime)); if(L<2)L=2;

for(int i=1;i<=prime[0]&&(long long)prime[i]*prime[i]<=R;i++) {

int s=L/prime[i]+(L%prime[i]>0); if(s==1)s=2;

for(int j=s;(long long)j*prime[i]<=R;j++) if((long long)j*prime[i]>=L)

notprime[j*prime[i]-L]=true;

}

prime2[0]=0;

for(int i=0;i<=R-L;i++)

if(!notprime[i]) prime2[++prime2[0]]=i+L;

}

int main() {

getPrime(); int L,U;

while(scanf(\,&L,&U)==2) {

getPrime2(L,U);

if(prime2[0]<2)printf(\); else {

int x1=0,x2=100000000,y1=0,y2=0; for(int i=1;i

if(prime2[i+1]-prime2[i]

x1=prime2[i]; x2=prime2[i+1];

}

if(prime2[i+1]-prime2[i]>y2-y1) {

y1=prime2[i]; y2=prime2[i+1];

}

11 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

printf(\,x1,x2,y1,y2);

}

2、素数筛选和合数分解

//****************************************** //素数筛选和合数分解 const int MAXN=10000; int prime[MAXN+1]; void getPrime() {

memset(prime,0,sizeof(prime)); for(int i=2;i<=MAXN;i++) {

if(!prime[i])prime[++prime[0]]=i;

for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++) {

prime[prime[j]*i]=1;

if(i%prime[j]==0) break; } } }

long long factor[100][2]; int fatCnt;

int getFactors(long long x) {

fatCnt=0;

long long tmp=x;

for(int i=1;prime[i]<=tmp/prime[i];i++) {

factor[fatCnt][1]=0; if(tmp%prime[i]==0) {

factor[fatCnt][0]=prime[i]; while(tmp%prime[i]==0) {

factor[fatCnt][1]++; tmp/=prime[i]; }

fatCnt++; } }

if(tmp!=1) {

factor[fatCnt][0]=tmp; factor[fatCnt++][1]=1; }

return fatCnt; }

//******************************************

3、扩展欧几里得算法（求ax+by=gcd 的解以及逆元素）

//******************************

//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y

long long extend_gcd(long long a,long long b,long long &x,long long &y) {

if(a==0&&b==0) return -1;//无最大公约数 if(b==0){x=1;y=0;return a;}

long long d=extend_gcd(b,a%b,y,x); y-=a/b*x; return d; }

//*********求逆元素******************* //ax = 1(mod n)

long long mod_reverse(long long a,long long n) {

long long x,y;

long long d=extend_gcd(a,n,x,y); if(d==1) return (x%n+n)%n; else return -1; }

4、求逆元

4.1 扩展欧几里德法（见上面） 4.2 简洁写法

注意：这个只能求a < m的情况，而且必须保证a和m互质 //求ax = 1( mod m) 的x值，就是逆元(0

if(a == 1)return 1;

return inv(m%a,m)*(m-m/a)%m; }

4.3 利用欧拉函数

mod为素数,而且a和m互质

long long inv(long long a,long long mod)//mod为素数 {

return pow_m(a,mod-2,mod); }

5、模线性方程组

long long extend_gcd(long long a,long long b,long long &x,long long&y) {

12 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

if(a == 0 && b == 0)return -1;

if(b ==0 ){x = 1; y = 0;return a;} long long d = extend_gcd(b,a%b,y,x); y -= a/b*x; return d;

}

int m[10],a[10];//模数为m,余数为a, X % m = a bool solve(int &m0,int &a0,int m,int a) {

long long y,x;

int g = extend_gcd(m0,m,x,y); if( abs(a - a0)%g )return false; x *= (a -a0)/g; x %= m/g;

a0 = (x*m0 + a0); m0 *= m/g; a0 %= m0;

if( a0 < 0 )a0 += m0; return true; } /*

* 无解返回false,有解返回true;

* 解的形式最后为 a0 + m0 * t (0<=a0

bool MLES(int &m0 ,int &a0,int n)//解为 X = a0 + m0 * k {

bool flag = true; m0 = 1; a0 = 0;

for(int i = 0;i < n;i++)

if( !solve(m0,a0,m[i],a[i]) ) {

flag = false; break; }

return flag; }

6、随机素数测试和大数分解(POJ 1811)

/* ************************************************* * Miller_Rabin 算法进行素数测试

* 速度快，可以判断一个 < 2^63 的数是不是素数 *

**************************************************/ const int S = 8; //随机算法判定次数，一般8~10就够了 // 计算ret=(a*b)ê,b,c <2^63

long long mult_mod(long long a,long long b,long long c) {

a %= c; b %= c; long long ret = 0; long long tmp = a; while(b) {

if(b & 1) {

ret += tmp;

if(ret > c)ret -= c;//直接取模慢很多 }

tmp <<= 1;

if(tmp > c)tmp -= c; b >>= 1; }

return ret; }

// 计算 ret = (a^n)%mod

long long pow_mod(long long a,long long n,long long mod) {

long long ret = 1;

long long temp = a%mod; while(n) {

if(n & 1)ret = mult_mod(ret,temp,mod); temp = mult_mod(temp,temp,mod); n >>= 1; }

return ret;

}

// 通过 a^(n-1)=1(mod n)来判断n是不是素数 // n-1 = x*2^t 中间使用二次判断

// 是合数返回true, 不一定是合数返回false

bool check(long long a,long long n,long long x,long long t) {

long long ret = pow_mod(a,x,n); long long last = ret;

for(int i = 1;i <= t;i++) {

ret = mult_mod(ret,ret,n);

if(ret == 1 && last != 1 && last != n-1)return true;//合数 last = ret; }

if(ret != 1)return true; else return false;

}

//**************************************************

13 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

// Miller_Rabin算法

// 是素数返回true,(可能是伪素数) // 不是素数返回false

//************************************************** bool Miller_Rabin(long long n) {

if( n < 2)return false; if( n == 2)return true; if( (n&1) == 0)return false;//偶数 long long x = n - 1; long long t = 0;

while( (x&1)==0 ){x >>= 1; t++;}

srand(time(NULL));/* *************** */ for(int i = 0;i < S;i++) {

long long a = rand()%(n-1) + 1; if( check(a,n,x,t) )

return false;

}

return true;

}

//********************************************** // pollard_rho 算法进行质因素分解 // //

//*********************************************

long long factor[100];//质因素分解结果（刚返回时时无序的） int tol;//质因素的个数，编号0~tol-1

long long gcd(long long a,long long b) {

long long t; while(b) {

t = a; a = b; b = t%b; }

if(a >= 0)return a; else return -a;

}

//找出一个因子

long long pollard_rho(long long x,long long c) {

long long i = 1, k = 2; srand(time(NULL));

long long x0 = rand()%(x-1) + 1; long long y = x0; while(1) {

i ++;

x0 = (mult_mod(x0,x0,x) + c)%x; long long d = gcd(y - x0,x); if( d != 1 && d != x)return d; if(y == x0)return x; if(i == k){y = x0; k += k;} }

}

//对 n进行素因子分解，存入factor. k设置为107左右即可 void findfac(long long n,int k) {

if(n == 1)return; if(Miller_Rabin(n)) {

factor[tol++] = n; return; }

long long p = n; int c = k; while( p >=n)

p = pollard_rho(p,c--);//值变化，防止死循环k findfac(p,k); findfac(n/p,k);

}

//POJ 1811

//给出一个N(2 <= N < 2^54),如果是素数，输出\否则输出最小的素因子 int main() {

int T;

long long n; scanf(\,&T); while(T--) {

scanf(\,&n); if(Miller_Rabin(n))printf(\); else {

tol = 0; findfac(n,107); long long ans = factor[0];

for(int i = 1;i < tol;i++) ans = min(ans,factor[i]); printf(\,ans); } }

return 0;

}

7、欧拉函数

6.1 分解质因素求欧拉函数

14 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

getFactors(n); int ret = n;

for(int i = 0;i < fatCnt;i++) {

ret = ret/factor[i][0]*(factor[i][0]-1); }

6.2 筛法欧拉函数

int euler[3000001]; void getEuler() {

memset(euler,0,sizeof(euler)); euler[1] = 1; for(int i = 2;i <= 3000000;i++)

if(!euler[i])

for(int j = i;j <= 3000000; j += i) {

if(!euler[j]) euler[j] = j; euler[j] = euler[j]/i*(i-1); }

}

6.2 求单个数的欧拉函数

long long eular(long long n) {

long long ans = n;

for(int i = 2;i*i <= n;i++) {

if(n % i == 0) {

ans -= ans/i;

while(n % i == 0) n /= i; } }

if(n > 1)ans -= ans/n; return ans; }

6.3 线性筛（同时得到欧拉函数和素数表）

const int MAXN = 10000000;

bool check[MAXN+10]; int phi[MAXN+10]; intprime[MAXN+10]; int tot;//素数的个数

void phi_and_prime_table(int N) {

memset(check,false,sizeof(check)); phi[1] = 1; tot = 0;

for(int i = 2; i <= N; i++) {

if( !check[i] ) {

prime[tot++] = i; phi[i] = i-1;

}

for(int j = 0; j < tot; j++) {

if(i * prime[j] > N)break; check[i * prime[j]] = true; if( i % prime[j] == 0) {

phi[i * prime[j]] = phi[i] * prime[j]; break;

} else {

phi[i * prime[j]] = phi[i] * (prime[j] - 1);

}

8、高斯消元（浮点数）

#define eps 1e-9 const int MAXN=220;

double a[MAXN][MAXN],x[MAXN];//方程的左边的矩阵和等式右边的值，求解之后x存的就是结果 int equ,var;//方程数和未知数个数 /*

*返回0表示无解，1表示有解 */

int Gauss() {

int i,j,k,col,max_r;

for(k=0,col=0;k

max_r=k;

for(i=k+1;ifabs(a[max_r][col]))

max_r=i; if(fabs(a[max_r][col])

for(j=col;j

x[k]/=a[k][col]; for(j=col+1;j

15 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

for(i=0;i

x[i]-=x[k]*a[i][k]; for(j=col+1;j

return 1; }

9、FFT

//HDU 1402 求高精度乘法

#include #include #include #include #include using namespace std;

const double PI = acos(-1.0); //复数结构体

struct Complex {

double x,y;//实部和虚部x+yi

Complex(double _x = 0.0,double _y = 0.0) {

x = _x; y = _y; }

Complex operator -(const Complex &b)const {

return Complex(x-b.x,y-b.y); }

Complex operator +(const Complex &b)const {

return Complex(x+b.x,y+b.y); }

Complex operator *(const Complex &b)const {

return Complex(x*b.x-y*b.y,x*b.y+y*b.x); } }; /*

* 进行FFT和IFFT前的反转变换。

* 位置i和（i二进制反转后位置）互换 * len必须去2的幂 */

void change(Complex y[],int len) {

int i,j,k;

for(i = 1, j = len/2;i

if(i < j)swap(y[i],y[j]);

//交换互为小标反转的元素，i

//i做正常的+1，j左反转类型的+1,始终保持i和j是反转的 k = len/2; while(j >= k) {

j -= k; k /= 2; }

if(j < k)j += k; } } /*

* 做FFT

* len必须为2^k形式，

* on==1时是DFT，on==-1时是IDFT */

void fft(Complex y[],int len,int on) {

change(y,len);

for(int h = 2; h <= len; h <<= 1) {

Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); for(int j = 0;j < len;j+=h) {

Complex w(1,0);

for(int k = j;k < j+h/2;k++) {

Complex u = y[k]; Complex t = w*y[k+h/2]; y[k] = u+t; y[k+h/2] = u-t; w = w*wn; } } }

if(on == -1)

for(int i = 0;i < len;i++) y[i].x /= len;

}

const int MAXN = 200010; Complex x1[MAXN],x2[MAXN]; char str1[MAXN/2],str2[MAXN/2]; int sum[MAXN]; int main()

16 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

{

while(scanf(\,str1,str2)==2) {

int len1 = strlen(str1); int len2 = strlen(str2); int len = 1;

while(len < len1*2 || len < len2*2)len<<=1; for(int i = 0;i < len1;i++)

x1[i] = Complex(str1[len1-1-i]-'0',0);

for(int i = len1;i < len;i++) x1[i] = Complex(0,0); for(int i = 0;i < len2;i++)

x2[i] = Complex(str2[len2-1-i]-'0',0);

for(int i = len2;i < len;i++) x2[i] = Complex(0,0); //求DFT

fft(x1,len,1); fft(x2,len,1);

for(int i = 0;i < len;i++) x1[i] = x1[i]*x2[i]; fft(x1,len,-1);

for(int i = 0;i < len;i++) sum[i] = (int)(x1[i].x+0.5); for(int i = 0;i < len;i++) {

sum[i+1]+=sum[i]/10; sum[i]%=10; }

len = len1+len2-1;

while(sum[len] <= 0 && len > 0)len--; for(int i = len;i >= 0;i--)

printf(\,sum[i]+'0'); printf(\);

}

return 0; }

//HDU 4609

//给出n 条线段长度，问任取3 根，组成三角形的概率。 //n<=10^5用FFT 求可以组成三角形的取法有几种

const int MAXN = 400040; Complex x1[MAXN]; int a[MAXN/4];

long long num[MAXN];//100000*100000会超int long long sum[MAXN]; int main() {

int T;

int n; scanf(\,&T); while(T--) {

scanf(\,&n); memset(num,0,sizeof(num)); for(int i = 0;i < n;i++) {

scanf(\,&a[i]); num[a[i]]++; }

sort(a,a+n);

int len1 = a[n-1]+1; int len = 1;

while( len < 2*len1 )len <<= 1;

for(int i = 0;i < len1;i++) x1[i] = Complex(num[i],0); for(int i = len1;i < len;i++) x1[i] = Complex(0,0); fft(x1,len,1);

for(int i = 0;i < len;i++) x1[i] = x1[i]*x1[i]; fft(x1,len,-1);

for(int i = 0;i < len;i++)

num[i] = (long long)(x1[i].x+0.5); len = 2*a[n-1]; //减掉取两个相同的组合

for(int i = 0;i < n;i++) num[a[i]+a[i]]--;

for(int i = 1;i <= len;i++)num[i]/=2; sum[0] = 0;

for(int i = 1;i <= len;i++) sum[i] = sum[i-1]+num[i]; long long cnt = 0;

for(int i = 0;i < n;i++) {

cnt += sum[len]-sum[a[i]]; //减掉一个取大，一个取小的

cnt -= (long long)(n-1-i)*i;

//减掉一个取本身，另外一个取其它 cnt -= (n-1); cnt -= (long long)(n-1-i)*(n-i-2)/2; }

long long tot = (long long)n*(n-1)*(n-2)/6; printf(\,(double)cnt/tot); }

return 0; }

10.1 一类开关问题，对2 取模的01 方程组

POJ 1681 需要枚举自由变元，找解中 1 个数最少的

//对2取模的01方程组 const int MAXN = 300;

//有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var int equ,var;

int a[MAXN][MAXN]; //增广矩阵 int x[MAXN]; //解集

int free_x[MAXN];//用来存储自由变元（多解枚举自由变元可以使用） int free_num;//自由变元的个数

10、高斯消元法求方程组的解

17 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

//返回值为-1表示无解，为0是唯一解，否则返回自由变元个数 int Gauss() {

int max_r,col,k; free_num = 0;

for(k = 0, col = 0 ; k < equ && col < var ; k++, col++) {

max_r = k;

for(int i = k+1;i < equ;i++) {

if(abs(a[i][col]) >abs(a[max_r][col])) max_r = i;

}

if(a[max_r][col] == 0) {

k--;

free_x[free_num++] = col;//这个是自由变元 continue;

}

if(max_r != k) {

for(int j = col; j < var+1; j++) swap(a[k][j],a[max_r][j]);

}

for(int i = k+1;i < equ;i++) {

if(a[i][col] != 0) {

for(int j = col;j < var+1;j++) a[i][j] ^= a[k][j];

}

for(int i = k;i < equ;i++)

if(a[i][col] != 0) return -1;//无解

if(k < var) return var-k;//自由变元个数 //唯一解，回代

for(int i = var-1; i >= 0;i--) {

x[i] = a[i][var];

for(int j = i+1;j < var;j++) x[i] ^= (a[i][j] && x[j]);

}

return 0;

}

int n;

void init() {

memset(a,0,sizeof(a));

memset(x,0,sizeof(x)); equ = n*n; var = n*n;

for(int i = 0;i < n;i++)

for(int j = 0;j < n;j++) {

int t = i*n+j; a[t][t] = 1; if(i > 0)a[(i-1)*n+j][t] = 1; if(i < n-1)a[(i+1)*n+j][t] = 1; if(j > 0)a[i*n+j-1][t] = 1; if(j < n-1)a[i*n+j+1][t] = 1;

}

void solve() {

int t = Gauss(); if(t == -1) {

printf(\); return;

}

else if(t == 0) {

int ans = 0;

for(int i = 0;i < n*n;i++) ans += x[i]; printf(\,ans); return;

} else {

//枚举自由变元

int ans = 0x3f3f3f3f; int tot = (1<

for(int i = 0;i < tot;i++) {

int cnt = 0;

for(int j = 0;j < t;j++) {

if(i&(1<

x[free_x[j]] = 1; cnt++;

}

else x[free_x[j]] = 0;

18 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

for(int j = var-t-1;j >= 0;j--) {

int idx;

for(idx = j;idx < var;idx++)

if(a[j][idx]) break;

x[idx] = a[j][var];

for(int l = idx+1;l < var;l++)

if(a[j][l])

x[idx] ^= x[l];

cnt += x[idx];

}

ans = min(ans,cnt);

}

printf(\,ans);

}

char str[30][30]; int main() {

int T; scanf(\,&T); while(T--) {

scanf(\,&n); init(); for(int i = 0;i < n;i++) {

scanf(\,str[i]); for(int j = 0;j < n;j++) {

if(str[i][j] == 'y') a[i*n+j][n*n] = 0; else a[i*n+j][n*n] = 1;

}

solve();

}

return 0; }

10.2 解同余方程组 POJ 2947 Widget Factory

//求解对MOD取模的方程组 const int MOD = 7; const int MAXN = 400;

int a[MAXN][MAXN];//增广矩阵 int x[MAXN];//最后得到的解集 inline int gcd(int a,int b) {

while(b != 0) {

int t = b; b = a%b; a = t;

}

return a;

}

inline int lcm(int a,int b) {

return a/gcd(a,b)*b;

}

long long inv(long long a,long long m) {

if(a == 1)return 1;

return inv(m%a,m)*(m-m/a)%m; }

int Gauss(int equ,int var) {

int max_r,col,k;

for(k = 0, col = 0; k < equ && col < var; k++,col++) {

max_r = k;

for(int i = k+1; i < equ;i++)

if(abs(a[i][col]) >abs(a[max_r][col])) max_r = i;

if(a[max_r][col] == 0) {

k--;

continue;

}

if(max_r != k)

for(int j = col; j < var+1;j++) swap(a[k][j],a[max_r][j]);

for(int i = k+1;i < equ;i++) {

if(a[i][col] != 0) {

int LCM = lcm(abs(a[i][col]),abs(a[k][col])); int ta = LCM/abs(a[i][col]);

int tb = LCM/abs(a[k][col]); if(a[i][col]*a[k][col] < 0)tb = -tb; for(int j = col;j < var+1;j++)

a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%MOD + MOD)%MOD;

}

19 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

for(int i = k;i < equ;i++)

if(a[i][col] != 0) return -1;//无解

if(k < var) return var-k;//多解 for(int i = var-1;i >= 0;i--) {

int temp = a[i][var];

for(int j = i+1; j < var;j++) {

if(a[i][j] != 0) {

temp -= a[i][j]*x[j];

temp = (temp%MOD + MOD)%MOD;

}

x[i] = (temp*inv(a[i][i],MOD))%MOD;

}

return 0;

}

int change(char s[]) {

if(strcmp(s,\) == 0) return 1; else if(strcmp(s,\)==0) return 2; else if(strcmp(s,\)==0) return 3; else if(strcmp(s,\)==0) return 4; else if(strcmp(s,\)==0) return 5; else if(strcmp(s,\)==0) return 6; else return 7; }

int main() {

int n,m;

while(scanf(\,&n,&m) == 2) {

if(n == 0 && m == 0)break; memset(a,0,sizeof(a)); char str1[10],str2[10]; intk; for(int i = 0;i < m;i++) {

scanf(\,&k,str1,str2);

a[i][n] = ((change(str2) - change(str1) + 1)%MOD + MOD)%MOD; int t;

while(k--) {

scanf(\,&t); t--; a[i][t] ++; a[i][t]%=MOD;

}

int ans = Gauss(m,n); if(ans == 0) {

for(int i = 0;i < n;i++)

if(x[i] <= 2) x[i] += 7;

for(int i = 0;i < n-1;i++)printf(\,x[i]); printf(\,x[n-1]);

}

else if(ans == -1)printf(\); else printf(\);

}

return 0; }

11、整数拆分

HDU 4651

const int MOD = 1e9+7; int dp[100010]; void init() {

memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i = 1;i <= 100000;i++) {

for(int j = 1, r = 1; i - (3 * j * j - j) / 2 >= 0; j++, r *= -1) {

dp[i] += dp[i -(3 * j * j - j) / 2] * r; dp[i] %= MOD; dp[i] = (dp[i]+MOD)%MOD;

if( i - (3 * j * j + j) / 2 >= 0 ) {

dp[i] += dp[i - (3 * j * j + j) / 2] * r; dp[i] %= MOD; dp[i] = (dp[i]+MOD)%MOD; } } } }

int main() {

int T; int n; init();

scanf(\,&T); while(T--)

20 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

{

scanf(\,&n);

printf(\,dp[n]); }

return 0; }

HDU 4658

数n(<=10^5)的划分，相同的数重复不能超过k 个。

const int MOD = 1e9+7; int dp[100010]; void init() {

memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i = 1;i <= 100000;i++) {

for(int j = 1, r = 1; i - (3 * j * j - j) / 2 >= 0; j++, r *= -1) {

dp[i] += dp[i -(3 * j * j - j) / 2] * r; dp[i] %= MOD; dp[i] = (dp[i]+MOD)%MOD;

if( i - (3 * j * j + j) / 2 >= 0 ) {

dp[i] += dp[i - (3 * j * j + j) / 2] * r; dp[i] %= MOD; dp[i] = (dp[i]+MOD)%MOD; } } } }

int solve(int n,int k) {

int ans = dp[n];

for(int j = 1, r = -1; n - k*(3 * j * j - j) / 2 >= 0; j++, r *= -1) {

ans += dp[n -k*(3 * j * j - j) / 2] * r; ans %= MOD; ans = (ans+MOD)%MOD;

if( n - k*(3 * j * j + j) / 2 >= 0 ) {

ans += dp[n - k*(3 * j * j + j) / 2] * r; ans %= MOD;

ans = (ans+MOD)%MOD; } }

return ans; }

int main() {

init(); int T; int n,k; scanf(\,&T); while(T--) {

scanf(\,&n,&k);

printf(\,solve(n,k)); }

return 0; }

12、求A^B 的约数之和对MOD 取模

参考POJ 1845

里面有一种求 1+p+p^2+p^3+…p^n 的方法。需要素数筛选和合数分解的程序，需要先调用getPrime();

long long pow_m(long long a,long long n) {

long long ret = 1; long long tmp = a%MOD; while(n) {

if(n&1)ret = (ret*tmp)%MOD; tmp = tmp*tmp%MOD; n >>= 1;

}

return ret;

}

//计算1+p+p^2+...+p^n

long long sum(long long p,long long n) {

if(p == 0)return 0; if(n == 0)return 1; if(n & 1) {

return ((1+pow_m(p,n/2+1))%MOD*sum(p,n/2)%MOD)%MOD;

}

else return ((1+pow_m(p,n/2+1))%MOD*sum(p,n/2-1)+pow_m(p,n/2)%MOD)%MOD;

}

//返回A^B的约数之和 % MOD

long long solve(long long A,long long B) {

getFactors(A);

long long ans = 1;

for(int i = 0;i < fatCnt;i++) {

ans *= sum(factor[i][0],B*factor[i][1])%MOD; ans %= MOD;

}

return ans;

}

21 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

13、莫比乌斯反演

莫比乌斯反演公式：

???

?n ??

F(n)??d|nf(d) 则f(n)????d?F?????d|n莫比乌斯函数

??dn ?1 ??nk???1

????

n ?p1p2 ?pk

?0其余情况

?????n|df(d)

???

另外一种更常用的形式：在某一范围内：F(n)??则f(n)??

?d ????Fn|d?? n

? ? ?d??

线性筛法求解积性函数（莫比乌斯函数）

const int MAXN = 1000000;

bool check[MAXN+10]; int prime[MAXN+10]; int mu[MAXN+10]; voidMoblus() {

memset(check,false,sizeof(check)); mu[1] = 1; int tot = 0;

for(int i = 2; i <= MAXN; i++) {

if( !check[i] ) {

prime[tot++] = i; mu[i] = -1;

}

for(int j = 0; j < tot; j++) {

if(i * prime[j] > MAXN) break; check[i * prime[j]] = true; if( i % prime[j] ==0) {

mu[i * prime[j]] = 0; break;

} else {

mu[i * prime[j]] = -mu[i];

}

例题： BZOJ 2301

对于给出的n 个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y)=k， gcd(x,y)函数为 x 和 y 的最大公约数。 1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

const int MAXN = 100000;

bool check[MAXN+10]; int prime[MAXN+10]; int mu[MAXN+10]; voidMoblus() {

memset(check,false,sizeof(check)); mu[1] = 1; int tot = 0;

for(int i = 2; i <= MAXN; i++) {

if( !check[i] ) {

prime[tot++] = i; mu[i] = -1;

}

for(int j = 0; j < tot; j ++) {

if( i * prime[j] > MAXN) break; check[i * prime[j]] = true; if( i % prime[j] ==0) {

mu[i * prime[j]] = 0; break;

} else {

mu[i * prime[j]] = -mu[i];

}

int sum[MAXN+10];

//找[1,n],[1,m]内互质的数的对数 long long solve(int n,int m) {

long long ans = 0;

22 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

if(n > m)swap(n,m);

for(int i = 1, la = 0; i <= n; i = la+1) {

la = min(n/(n/i),m/(m/i));

ans += (long long)(sum[la] - sum[i-1])*(n/i)*(m/i);

}

return ans;

}

int main() {

Moblus(); sum[0] = 0;

for(int i = 1;i <= MAXN;i++) sum[i] = sum[i-1] + mu[i]; int a,b,c,d,k; int T; scanf(\,&T); while(T--) {

scanf(\,&a,&b,&c,&d,&k);

longlongans=solve(b/k,d/k)-solve((a-1)/k,d/k)-solve(b/k,(c-1)/k)

+ solve((a-1)/k,(c-1)/k);

printf(\,ans);

}

return 0; }

14、Baby-Step Giant-Step

(POJ 2417,3243)

//baby_step giant_step

// a^x = b (mod n) n是素数和不是素数都可以 // 求解上式 0<=x < n的解 #define MOD 76543

int hs[MOD],head[MOD],next[MOD],id[MOD],top; void insert(int x,int y) {

int k = x%MOD;

hs[top] = x, id[top] = y, next[top] = head[k], head[k] = top++;

}

int find(int x) {

int k = x%MOD;

for(int i = head[k]; i != -1; i = next[i])

if(hs[i] == x)

return id[i];

return -1;

}

int BSGS(int a,int b,int n) {

memset(head,-1,sizeof(head)); top = 1;

if(b == 1)return 0; int m = sqrt(n*1.0), j; long long x = 1, p =1;

for(int i = 0; i < m; ++i, p = p*a%n)insert(p*b%n,i); for(long long i = m; ;i += m) {

if( (j = find(x = x*p%n)) != -1 )return i-j; if(i > n)break;

}

return -1;

}

15、自适应simpson 积分

double simpson(double a,double b) {

double c = a + (b-a)/2;

return (F(a) + 4*F(c) + F(b))*(b-a)/6;

}

double asr(double a,double b,double eps,double A) {

double c = a + (b-a)/2;

double L = simpson(a,c), R = simpson(c,b);

if(fabs(L + R - A) <= 15*eps)return L + R + (L + R - A)/15.0; return asr(a,c,eps/2,L) + asr(c,b,eps/2,R);

}

double asr(double a,double b,double eps) {

return asr(a,b,eps,simpson(a,b));

}

相关公式

?（1

modn）

1、欧拉定理

对于互质的整数a和n，有

?(n)

费马定理：a是不能被质数p 整除的正整数，有

p?1

?1(modp )

2、Polya 定理

L ?C( f)

??k,f?G

设 G 是 p 个对象的一个置换群，用 k 种颜色去染这p 个对象，若一种染色方案在群G 的作用下变为一种方案，则这两个方案当作是同一种方案，这样的不同染色方案数为： 1

G 23 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

C(fi)??

gcd(n,i),i表示旋转i颗宝石以后。i=0时gcd(n,0)=n nn

对于翻转置换：

如果n为偶数：则有n/2个置换,有n/2个置换

C(f)为循环节，G表示群的置换方法数。

对于n 个位置的手镯，有n 种旋转置换和n 种翻转置换对于旋转置换：

C(f)??

C(f)??1

如果n为奇数：则有n个置换

nC(f)??1

3、欧拉函数??n ??

??n??

积性函数，对于一个质数p和正整数k，有 kk

??p??p

k ?1 ? p?(p

k?1

?1)p 1k

?p (1 ?)

?d|n

??d ??n

n??n ?当n ?1时，1?n 中与n 互质的整数和为

?数据结构 1、划分树

* 划分树（查询区间第k大） */

const int MAXN = 100010;

int tree[20][MAXN];//表示每层每个位置的值 int sorted[MAXN];//已经排序好的数

int toleft[20][MAXN];//toleft[p][i]表示第i层从1到i有数分入左边 void build(int l,int r,int dep) {

if(l == r)return; int mid = (l+r)>>1;

int same = mid - l + 1;//表示等于中间值而且被分入左边的个数 for(int i = l; i <= r; i++) //注意是l,不是one

if(tree[dep][i] < sorted[mid]) same--; int lpos = l;

int rpos = mid+1;

for(int i = l;i <= r;i++) {

if(tree[dep][i] < sorted[mid]) tree[dep+1][lpos++] = tree[dep][i]; else if(tree[dep][i] == sorted[mid] && same > 0) {

tree[dep+1][lpos++] = tree[dep][i]; same--; } else

tree[dep+1][rpos++] = tree[dep][i]; toleft[dep][i] = toleft[dep][l-1] + lpos - l;

}

build(l,mid,dep+1); build(mid+1,r,dep+1); }

//查询区间第k大的数,[L,R]是大区间，[l,r]是要查询的小区间 int query(int L,int R,int l,int r,int dep,int k) {

if(l == r)return tree[dep][l]; int mid = (L+R)>>1;

int cnt = toleft[dep][r] - toleft[dep][l-1]; if(cnt >= k) {

int newl = L + toleft[dep][l-1] - toleft[dep][L-1]; int newr = newl + cnt - 1;

return query(L,mid,newl,newr,dep+1,k); } else {

int newr = r + toleft[dep][R] - toleft[dep][r]; int newl = newr - (r-l-cnt);

return query(mid+1,R,newl,newr,dep+1,k-cnt); } }

int main() {

int n,m;

while(scanf(\,&n,&m)==2) {

memset(tree,0,sizeof(tree)); for(int i = 1;i <= n;i++) {

scanf(\,&tree[0][i]); sorted[i] = tree[0][i]; }

sort(sorted+1,sorted+n+1); build(1,n,0); int s,t,k; while(m--)

24 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

{

scanf(\,&s,&t,&k); printf(\,query(1,n,s,t,0,k)); } }

return 0; }

2.1 一维

求最大值，数组下标从 1 开始。

求最小值，或者最大最小值下标，或者数组从0 开始对应修改即可。

const int MAXN = 50010; int dp[MAXN][20]; int mm[MAXN];

//初始化RMQ,b数组下标从1开始，从0开始简单修改 void initRMQ(int n,int b[]) {

mm[0] = -1;

for(int i = 1; i <= n;i++) {

mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1]; dp[i][0] = b[i]; }

for(int j = 1; j <= mm[n];j++)

for(int i = 1;i + (1<

dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);

}

//查询最大值

int rmq(int x,int y) {

int k = mm[y-x+1];

return max(dp[x][k],dp[y-(1<

2、RMQ

2.2 二维

* 二维RMQ，预处理复杂度 n*m*log*(n)*log(m) * 数组下标从1开始 */

int val[310][310];

int dp[310][310][9][9];//最大值

int mm[310];//二进制位数减一，使用前初始化 void initRMQ(int n,int m) {

for(int i = 1;i <= n;i++)

for(int j = 1;j <= m;j++) dp[i][j][0][0] = val[i][j]; for(int ii = 0; ii <= mm[n]; ii++)

for(int jj = 0; jj <= mm[m]; jj++)

if(ii+jj)

for(int i = 1; i + (1<

for(int j = 1; j + (1<

if(ii)dp[i][j][ii][jj] = max(dp[i][j][ii-1][jj],dp[i+(1<<(ii-1))][j][ii-1][jj]);

else dp[i][j][ii][jj] = max(dp[i][j][ii][jj-1],dp[i][j+(1<<(jj-1))][ii][jj-1]);

}

//查询矩形内的最大值(x1<=x2,y1<=y2)

int rmq(int x1,int y1,int x2,int y2) {

int k1 = mm[x2-x1+1]; int k2 = mm[y2-y1+1]; x2 = x2 - (1<

return max(max(dp[x1][y1][k1][k2],dp[x1][y2][k1][k2]),max(dp[x2][y1][k1][k2],dp[x2] [y2][k1][k2])); }

int main() {

//在外面对mm数组进行初始化 mm[0] = -1;

for(int i = 1;i <= 305;i++)

mm[i] = ((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; int n,m; int Q;

int r1,c1,r2,c2;

while(scanf(\,&n,&m) == 2) {

for(int i = 1;i <= n;i++)

for(int j = 1;j <= m;j++)

scanf(\,&val[i][j]); initRMQ(n,m);

scanf(\,&Q); while(Q--) {

scanf(\,&r1,&c1,&r2,&c2); if(r1 > r2)swap(r1,r2); if(c1 > c2)swap(c1,c2);

int tmp = rmq(r1,c1,r2,c2); printf(\,tmp);

if(tmp==val[r1][c1]||tmp==val[r1][c2]||tmp==val[r2][c1]|| tmp ==val[r2][c2])

printf(\); else printf(\);

25 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

} }

return 0; }

3.1 点权

基于点权，查询单点值，修改路径的上的点权（HDU 3966 树链剖分+树状数组）

const int MAXN = 50010; struct Edge {

int to,next; }edge[MAXN*2];

int head[MAXN],tot;

int top[MAXN];//top[v] 表示v所在的重链的顶端节点 int fa[MAXN];//父亲节点 int deep[MAXN];//深度

int num[MAXN];//num[v] 表示以v为根的子树的节点数 int p[MAXN];//p[v]表示v对应的位置 int fp[MAXN];//fp和p数组相反 int son[MAXN];//重儿子 int pos; void init() {

tot = 0;

memset(head,-1,sizeof(head)); pos =1;//使用树状数组，编号从头1开始 memset(son,-1,sizeof(son));

}

void addedge(int u,int v) {

edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;

}

void dfs1(int u,int pre,int d) {

deep[u] = d; fa[u] = pre; num[u] = 1;

for(int i = head[u];i != -1; i = edge[i].next) {

int v = edge[i].to; if(v != pre) {

dfs1(v,u,d+1); num[u] += num[v];

if(son[u] == -1 || num[v] > num[son[u]])

son[u] = v;

}

void getpos(int u,int sp) {

top[u] = sp; p[u] = pos++; fp[p[u]] = u; if(son[u] == -1) return; getpos(son[u],sp); for(int i = head[u];i != -1;i = edge[i].next) {

int v = edge[i].to;

if( v != son[u] && v != fa[u]) getpos(v,v);

}

//树状数组

int lowbit(int x) {

return x&(-x);

}

int c[MAXN]; int n;

int sum(int i) {

int s = 0; while(i > 0) {

s += c[i];

i -= lowbit(i);

}

return s;

}

void add(int i,int val) {

while(i <= n) {

c[i] += val; i += lowbit(i);

}

void Change(int u,int v,int val)//u->v的路径上点的值改变val {

int f1 = top[u], f2 = top[v]; int tmp = 0;

3、树链剖分

26 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

while(f1 != f2) {

if(deep[f1] < deep[f2]) {

swap(f1,f2); swap(u,v);

}

add(p[f1],val);

add(p[u]+1,-val); u = fa[f1]; f1 = top[u];

}

if(deep[u] > deep[v]) swap(u,v); add(p[u],val); add(p[v]+1,-val);

}

int a[MAXN]; int main() {

int M,P;

while(scanf(\,&n,&M,&P) == 3) {

int u,v;

int C1,C2,K;

char op[10]; init();

for(int i = 1;i <= n;i++) {

scanf(\,&a[i]);

}

while(M--) {

scanf(\,&u,&v); addedge(u,v); addedge(v,u);

}

dfs1(1,0,0);

getpos(1,1); memset(c,0,sizeof(c)); for(int i = 1;i <= n;i++) {

add(p[i],a[i]); add(p[i]+1,-a[i]);

}

while(P--) {

scanf(\,op); if(op[0] == 'Q') {

scanf(\,&u); printf(\,sum(p[u]));

} else {

scanf(\,&C1,&C2,&K); if(op[0] == 'D')

K = -K;

Change(C1,C2,K);

}

return 0; }

3.2 边权

基于边权，修改单条边权，查询路径边权最大值（SPOJQTREE树链剖分+线段树）

const int MAXN = 10010; struct Edge {

int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

int top[MAXN];//top[v]表示v所在的重链的顶端节点 int fa[MAXN]; //父亲节点 int deep[MAXN];//深度

int num[MAXN];//num[v]表示以v为根的子树的节点数

int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置

int fp[MAXN];//和p数组相反 int son[MAXN];//重儿子 intpos; void init() {

tot = 0;

memset(head,-1,sizeof(head)); pos = 0; memset(son,-1,sizeof(son));

}

void addedge(int u,int v) {

edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;

}

void dfs1(int u,int pre,int d) //第一遍dfs求出fa,deep,num,son {

deep[u] = d; fa[u] = pre; num[u] = 1;

for(int i = head[u];i != -1; i = edge[i].next) {

27 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

int v = edge[i].to; if(v != pre) {

dfs1(v,u,d+1); num[u] += num[v];

if(son[u] == -1 || num[v] > num[son[u]]) son[u] = v;

}

void getpos(int u,int sp) //第二遍dfs求出top和p {

top[u] = sp; p[u] = pos++; fp[p[u]] = u; if(son[u] == -1) return; getpos(son[u],sp);

for(int i = head[u] ; i != -1; i = edge[i].next) {

int v = edge[i].to;

if(v != son[u] && v != fa[u]) getpos(v,v);

}

//线段树

struct Node {

int l,r; int Max;

}segTree[MAXN*3];

void build(int i,int l,int r) {

segTree[i].l = l; segTree[i].r = r; segTree[i].Max = 0; if(l == r)return; int mid = (l+r)/2; build(i<<1,l,mid);

build((i<<1)|1,mid+1,r);

}

void push_up(int i) {

segTree[i].Max = max(segTree[i<<1].Max,segTree[(i<<1)|1].Max);

}

void update(int i,int k,int val) // 更新线段树的第k个值为val {

if(segTree[i].l == k && segTree[i].r == k) {

segTree[i].Max = val; return;

}

int mid = (segTree[i].l + segTree[i].r)/2;

if(k <= mid)update(i<<1,k,val); else update((i<<1)|1,k,val); push_up(i);

}

int query(int i,int l,int r) //查询线段树中[l,r]的最大值 {

if(segTree[i].l == l && segTree[i].r == r)

return segTree[i].Max;

int mid = (segTree[i].l + segTree[i].r)/2; if(r <= mid)return query(i<<1,l,r);

else if(l > mid)return query((i<<1)|1,l,r);

else return max(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));

}

int find(int u,int v)//查询u->v边的最大值 {

int f1 = top[u], f2 = top[v]; int tmp = 0; while(f1 != f2) {

if(deep[f1] < deep[f2]) {

swap(f1,f2); swap(u,v);

}

tmp = max(tmp,query(1,p[f1],p[u])); u = fa[f1]; f1 = top[u];

}

if(u == v)return tmp;

if(deep[u] > deep[v]) swap(u,v);

return max(tmp,query(1,p[son[u]],p[v]));

}

int e[MAXN][3]; int main() {

//freopen(\ //freopen(\ int T;

int n; scanf(\,&T); while(T--) {

init();

scanf(\,&n);

for(int i = 0;i < n-1;i++) {

28 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

scanf(\,&e[i][0],&e[i][1],&e[i][2]); addedge(e[i][0],e[i][1]); addedge(e[i][1],e[i][0]);

}

dfs1(1,0,0);

getpos(1,1); build(1,0,pos-1); for(int i = 0;i < n-1; i++) {

if(deep[e[i][0]] > deep[e[i][1]])

swap(e[i][0],e[i][1]);

update(1,p[e[i][1]],e[i][2]);

}

char op[10]; int u,v;

while(scanf(\,op) == 1) {

if(op[0] == 'D')break; scanf(\,&u,&v); if(op[0] == 'Q')

printf(\,find(u,v));//查询u->v路径上边权的最大值 else update(1,p[e[u-1][1]],v);//修改第u条

边的长度为v

}

return 0; }

4、伸展树（splay tree）

题目：维修数列。经典题，插入、删除、修改、翻转、求和、求和最大的子序列

#define Key_value ch[ch[root][1]][0] const int MAXN = 500010; const int INF = 0x3f3f3f3f;

int pre[MAXN],ch[MAXN][2],key[MAXN],size[MAXN]; int root,tot1;

int sum[MAXN],rev[MAXN],same[MAXN]; int lx[MAXN],rx[MAXN],mx[MAXN]; int s[MAXN],tot2;//内存池和容量 int a[MAXN]; int n,q;

//debug部分********************************** void Treavel(int x) {

if(x) {

Treavel(ch[x][0]);

printf(\结点：-: 左儿子 - 右儿子 - 父结点 -size

= -\\n\,x,ch[x][0],ch[x][1],pre[x],size[x]); Treavel(ch[x][1]);

}

void debug() {

printf(\,root); Treavel(root);

}

//以上是debug部分************************************** void NewNode(int &r,int father,int k) {

if(tot2) r = s[tot2--];//取的时候是tot2--,存的时候就是++tot2 else r = ++tot1; pre[r] = father; ch[r][0] = ch[r][1] = 0; key[r] = k; sum[r] = k;

rev[r] = same[r] = 0; lx[r] = rx[r] = mx[r] = k; size[r] =1;

}

void Update_Rev(int r) {

if(!r)return; swap(ch[r][0],ch[r][1]); swap(lx[r],rx[r]); rev[r] ^=1;

}

void Update_Same(int r,int v) {

if(!r)return; key[r] = v;

sum[r] = v*size[r];

lx[r] = rx[r] = mx[r] = max(v,v*size[r]); same[r] = 1;

}

void push_up(int r) {

int lson = ch[r][0], rson = ch[r][1]; size[r] = size[lson] + size[rson] + 1; sum[r] = sum[lson] + sum[rson] + key[r];

lx[r] = max(lx[lson],sum[lson] + key[r] + max(0,lx[rson])); rx[r] = max(rx[rson],sum[rson] + key[r] + max(0,rx[lson])); mx[r] = max(0,rx[lson]) + key[r] + max(0,lx[rson]); mx[r] = max(mx[r],max(mx[lson],mx[rson]));

}

void push_down(int r) {

if(same[r]) {

Update_Same(ch[r][0],key[r]);

29 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

Update_Same(ch[r][1],key[r]); same[r] = 0;

}

if(rev[r]) {

Update_Rev(ch[r][0]);

Update_Rev(ch[r][1]); rev[r] = 0;

}

void Build(int &x,int l,int r,int father) {

if(l > r)return;

int mid = (l+r)/2; NewNode(x,father,a[mid]); Build(ch[x][0],l,mid-1,x);

Build(ch[x][1],mid+1,r,x); push_up(x);

}

void Init() {

root = tot1 = tot2 = 0;

ch[root][0] = ch[root][1] = size[root] = pre[root] = 0; same[root] = rev[root] = sum[root] = key[root] = 0; lx[root] = rx[root] = mx[root] = -INF;

NewNode(root,0,-1); NewNode(ch[root][1],root,-1); for(int i = 0;i < n;i++)

scanf(\,&a[i]);

Build(Key_value,0,n-1,ch[root][1]); push_up(ch[root][1]); push_up(root);

}

//旋转,0为左旋，1为右旋

void Rotate(int x,int kind) {

int y = pre[x]; push_down(y); push_down(x);

ch[y][!kind] = ch[x][kind]; pre[ch[x][kind]] = y; if(pre[y])

ch[pre[y]][ch[pre[y]][1]==y] = x; pre[x] = pre[y];

ch[x][kind] = y; pre[y] = x; push_up(y);

}

//Splay调整，将r结点调整到goal下面 void Splay(int r,int goal) {

push_down(r);

while(pre[r] != goal) {

if(pre[pre[r]] == goal) {

push_down(pre[r]); push_down(r); Rotate(r,ch[pre[r]][0] == r);

} else {

push_down(pre[pre[r]]); push_down(pre[r]); push_down(r); int y = pre[r];

int kind = ch[pre[y]][0]==y; if(ch[y][kind] == r) {

Rotate(r,!kind); Rotate(r,kind);

} else {

Rotate(y,kind); Rotate(r,kind);

}

push_up(r);

if(goal == 0) root = r;

}

int Get_kth(int r,int k) {

push_down(r);

int t = size[ch[r][0]] + 1; if(t == k)return r;

if(t > k)return Get_kth(ch[r][0],k); else return Get_kth(ch[r][1],k-t);

}

//在第pos个数后面插入tot个数 void Insert(int pos,int tot) {

for(int i = 0;i < tot;i++)scanf(\,&a[i]); Splay(Get_kth(root,pos+1),0); Splay(Get_kth(root,pos+2),root); Build(Key_value,0,tot-1,ch[root][1]); push_up(ch[root][1]); push_up(root);

}

//删除子树

void erase(int r) {

if(!r)return; s[++tot2] = r; erase(ch[r][0]); erase(ch[r][1]);

}

//从第pos个数开始连续删除tot个数 void Delete(int pos,int tot)

30 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

if(c[lson[left_root]]-c[lson[right_root]] >= k ) {

r = mid;

left_root = lson[left_root]; right_root = lson[right_root];

} else {

l = mid + 1;

k -= c[lson[left_root]] - c[lson[right_root]]; left_root = rson[left_root]; right_root = rson[right_root];

}

return l;

}

int main() {

//freopen(\ //freopen(\ while(scanf(\,&n,&q) == 2) {

tot = 0;

for(int i = 1;i <= n;i++)

scanf(\,&a[i]); Init_hash();

T[n+1] = build(1,m); for(int i = n;i ;i--) {

int pos = hash(a[i]);

T[i] = update(T[i+1],pos,1);

}

while(q--) {

int l,r,k;

scanf(\,&l,&r,&k); printf(\,t[query(T[l],T[r+1],k)]);

}

return 0;

}

6.3 树上路径点权第 k 大（SPOJ COT） LCA + 主席树

//主席树部分 *****************8 const int MAXN = 200010; const int M = MAXN *40; int n,q,m,TOT;

int a[MAXN], t[MAXN];

int T[MAXN], lson[M], rson[M], c[M]; void Init_hash() {

for(int i = 1; i <= n;i++) t[i] = a[i]; sort(t+1,t+1+n);

m = unique(t+1,t+n+1)-t-1;

}

int build(int l,int r) {

int root = TOT++; c[root] = 0; if(l != r) {

int mid = (l+r)>>1; lson[root] = build(l,mid); rson[root] = build(mid+1,r);

}

return root;

}

int hash(int x) {

return lower_bound(t+1,t+1+m,x) - t;

}

int update(int root,int pos,int val) {

int newroot = TOT++, tmp = newroot; c[newroot] = c[root] + val; int l = 1, r = m; while( l < r) {

int mid = (l+r)>>1; if(pos <= mid) {

lson[newroot] = TOT++; rson[newroot] = rson[root]; newroot = lson[newroot]; root = lson[root]; r = mid;

} else {

rson[newroot] = TOT++; lson[newroot] = lson[root]; newroot = rson[newroot]; root = rson[root]; l = mid+1;

}

c[newroot] = c[root] + val;

}

return tmp;

}

36 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

int query(int left_root,int right_root,int LCA,int k) {

int lca_root = T[LCA]; int pos = hash(a[LCA]); int l = 1, r = m; while(l < r) {

int mid = (l+r)>>1;

inttmp=c[lson[left_root]]+c[lson[right_root]]-2*c[lson[lca_root]]

+ (pos >= l && pos <= mid);

if(tmp >= k) {

left_root = lson[left_root]; right_root = lson[right_root]; lca_root = lson[lca_root]; r = mid;

} else {

k -= tmp;

left_root = rson[left_root]; right_root = rson[right_root]; lca_root = rson[lca_root]; l = mid + 1;

}

return l;

}

//LCA部分

int rmq[2*MAXN];//rmq数组，就是欧拉序列对应的深度序列 struct ST {

int mm[2*MAXN];

int dp[2*MAXN][20];//最小值对应的下标 void init(int n) {

mm[0] = -1;

for(int i = 1;i <= n;i++) {

mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1]; dp[i][0] = i;

}

for(int j = 1; j <= mm[n];j++)

for(int i = 1; i + (1<

rmq[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];

}

int query(int a,int b)//查询[a,b]之间最小值的下标 {

if(a > b)swap(a,b); int k = mm[b-a+1];

return rmq[dp[a][k]] <=

rmq[dp[b-(1<

}

};

//边的结构体定义 struct Edge {

int to,next;

};

Edge edge[MAXN*2]; int tot,head[MAXN];

int F[MAXN*2];//欧拉序列，就是dfs遍历的顺序，长度为2*n-1,下标从1开始 int P[MAXN];//P[i]表示点i在F中第一次出现的位置 int cnt; ST st;

void init() {

tot = 0;

memset(head,-1,sizeof(head));

}

void addedge(int u,int v)//加边，无向边需要加两次 {

edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;

}

void dfs(int u,int pre,int dep) {

F[++cnt] = u; rmq[cnt] = dep; P[u] = cnt;

for(int i = head[u];i != -1;i = edge[i].next) {

int v = edge[i].to; if(v == pre)continue; dfs(v,u,dep+1); F[++cnt] = u; rmq[cnt] =dep;

}

void LCA_init(int root,int node_num)//查询LCA前的初始化 {

cnt = 0; dfs(root,root,0); st.init(2*node_num-1);

}

int query_lca(int u,int v)//查询u,v的lca编号 {

37 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

return F[st.query(P[u],P[v])];

}

void dfs_build(int u,int pre) {

int pos = hash(a[u]);

T[u] = update(T[pre],pos,1);

for(int i = head[u]; i != -1;i = edge[i].next) {

int v = edge[i].to; if(v == pre)continue; dfs_build(v,u);

}

int main() {

//freopen(\ //freopen(\ while(scanf(\,&n,&q) == 2) {

for(int i = 1;i <= n;i++)

scanf(\,&a[i]); Init_hash();

init(); TOT = 0; int u,v;

for(int i = 1;i < n;i++) {

scanf(\,&u,&v); addedge(u,v); addedge(v,u);

}

LCA_init(1,n); T[n+1] = build(1,m); dfs_build(1,n+1); intk; while(q--) {

scanf(\,&u,&v,&k); printf(\,t[query(T[u],T[v],query_lca(u,v),k)]);

}

return 0;

}

return 0; }

6.4 动态第k 大（ZOJ 2112）树状数组套主席树

const int MAXN = 60010; const int M = 2500010; int n,q,m,tot;

int a[MAXN], t[MAXN];

int T[MAXN], lson[M], rson[M],c[M]; int S[MAXN]; struct Query {

int kind; int l,r,k;

}query[10010];

void Init_hash(int k) {

sort(t,t+k);

m = unique(t,t+k) - t;

}

int hash(int x) {

return lower_bound(t,t+m,x)-t;

}

int build(int l,int r) {

int root = tot++; c[root] = 0; if(l != r) {

int mid = (l+r)/2; lson[root] = build(l,mid); rson[root] =build(mid+1,r);

}

return root;

}

int Insert(int root,int pos,int val) {

int newroot = tot++, tmp = newroot;

int l = 0, r = m-1; c[newroot] = c[root] + val; while(l < r) {

int mid = (l+r)>>1; if(pos <= mid) {

lson[newroot] = tot++; rson[newroot] = rson[root]; newroot = lson[newroot]; root = lson[root]; r = mid;

} else {

rson[newroot] = tot++; lson[newroot] = lson[root]; newroot = rson[newroot]; root = rson[root]; l = mid+1;

}

c[newroot] = c[root] + val;

38 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

return tmp;

}

int lowbit(int x) {

return x&(-x);

}

int use[MAXN];

void add(int x,int pos,int val) {

while(x <= n) {

S[x] = Insert(S[x],pos,val); x += lowbit(x);

}

int sum(int x) {

int ret = 0; while(x > 0) {

ret += c[lson[use[x]]]; x -= lowbit(x);

}

return ret;

}

int Query(int left,int right,int k) {

int left_root = T[left-1]; int right_root = T[right]; int l = 0, r = m-1;

for(int i = left-1;i;i -= lowbit(i)) use[i] = S[i]; for(int i = right;i ;i -= lowbit(i)) use[i] = S[i]; while(l < r) {

int mid = (l+r)/2;

int tmp = sum(right) - sum(left-1) + c[lson[right_root]] - c[lson[left_root]]; if(tmp >= k) {

r = mid;

for(int i = left-1; i ;i -= lowbit(i))

use[i] = lson[use[i]];

for(int i = right; i; i -= lowbit(i)) use[i] = lson[use[i]]; left_root = lson[left_root]; right_root = lson[right_root];

} else {

l = mid+1; k -= tmp;

for(int i = left-1; i;i -= lowbit(i)) use[i] = rson[use[i]]; for(int i = right;i ;i -= lowbit(i)) use[i] = rson[use[i]]; left_root = rson[left_root]; right_root = rson[right_root];

}

return l;

}

void Modify(int x,int p,int d) {

while(x <= n) {

S[x] = Insert(S[x],p,d); x += lowbit(x);

}

int main() {

//freopen(\ //freopen(\

int Tcase; scanf(\,&Tcase); while(Tcase--) {

scanf(\,&n,&q); tot = 0; m = 0;

for(int i = 1;i <= n;i++) {

scanf(\,&a[i]); t[m++] = a[i];

}

char op[10];

for(int i = 0;i < q;i++) {

scanf(\,op); if(op[0] == 'Q') {

query[i].kind = 0;

scanf(\,&query[i].l,&query[i].r,&query[i].k);

} else {

query[i].kind = 1;

scanf(\,&query[i].l,&query[i].r); t[m++] = query[i].r;

}

39 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

Init_hash(m);

T[0] = build(0,m-1);

for(int i = 1;i <= n;i++)

T[i] = Insert(T[i-1],hash(a[i]),1);

for(int i = 1;i <= n;i++) S[i] = T[0]; for(int i = 0;i < q;i++) {

if(query[i].kind == 0)

printf(\,t[Query(query[i].l,query[i].r,query[i].k)]); else

{

Modify(query[i].l,hash(a[query[i].l]),-1);

Modify(query[i].l,hash(query[i].r),1); a[query[i].l] = query[i].r;

}

return 0; }

7、Treap

ZOJ3765

long long gcd(long long a,long long b) {

if(b == 0)return a;

else return gcd(b,a%b);

}

const int MAXN = 300010; int num[MAXN],st[MAXN]; struct Treap {

int tot1;

int s[MAXN],tot2;//内存池和容量 int ch[MAXN][2];

int key[MAXN],size[MAXN]; int sum0[MAXN],sum1[MAXN]; int status[MAXN]; void Init() {

tot1 = tot2 = 0; size[0] = 0; ch[0][0] = ch[0][1] = 0; sum0[0] = sum1[0] = 0;

}

bool random(double p) {

return (double)rand() / RAND_MAX < p;

}

int newnode(int val,int _status) {

int r;

if(tot2)r = s[tot2--]; else r = ++tot1; size[r] = 1; key[r] = val; status[r] = _status; ch[r][0] = ch[r][1] = 0;

sum0[r] = sum1[r] = 0;//需要push_up return r;

}

void del(int r) {

if(!r)return; s[++tot2] = r; del(ch[r][0]); del(ch[r][1]);

}

void push_up(int r) {

int lson = ch[r][0], rson = ch[r][1]; size[r] = size[lson] + size[rson] + 1; sum0[r] = gcd(sum0[lson],sum0[rson]); sum1[r] = gcd(sum1[lson],sum1[rson]); if(status[r] == 0)

sum0[r] = gcd(sum0[r],key[r]);

else sum1[r] = gcd(sum1[r],key[r]);

}

void merge(int &p,int x,int y) {

if(!x || !y)

p = x|y;

else if(random((double)size[x]/(size[x]+size[y]))) {

merge(ch[x][1],ch[x][1],y); push_up(p=x);

} else {

merge(ch[y][0],x,ch[y][0]); push_up(p=y);

}

void split(int p,int &x,int &y,int k) {

if(!k) {

x = 0; y = p; return;

40 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

if(size[ch[p][0]] >= k) {

y = p; split(ch[p][0],x,ch[y][0],k); push_up(y);

} else {

x = p;

split(ch[p][1],ch[x][1],y,k - size[ch[p][0]] - 1); push_up(x);

}

void build(int &p,int l,int r) {

if(l > r)return;

int mid = (l + r)/2;

p = newnode(num[mid],st[mid]); build(ch[p][0],l,mid-1); build(ch[p][1],mid+1,r); push_up(p);

}

void debug(int root) {

if(root == 0)return;

printf(\左儿子：%d 右儿子: %d size = %dkey

= %d\\n\,root,ch[root][0],ch[root][1],size[root],key[root]); debug(ch[root][0]);

debug(ch[root][1]);

}

};

Treap T;

char op[10]; int main() {

//freopen(\

//freopen(\int n,q; while(scanf(\,&n,&q) == 2) {

int root = 0; T.Init(); for(int i = 1;i <= n;i++)

scanf(\,&num[i],&st[i]); T.build(root,1,n);

while(q--) {

scanf(\,op); if(op[0] == 'Q') {

int l,r,s; scanf(\,&l,&r,&s); int x,y,z; T.split(root,x,z,r); T.split(x,x,y,l-1); if(s == 0)

printf(\,T.sum0[y] == 0? -1:T.sum0[y]);

else

printf(\,T.sum1[y] == 0?-1:T.sum1[y]); T.merge(x,x,y);

T.merge(root,x,z);

}

else if(op[0] == 'I') {

int v,s,loc; scanf(\,&loc,&v,&s); int x,y; T.split(root,x,y,loc); T.merge(x,x,T.newnode(v,s)); T.merge(root,x,y);

}

else if(op[0] == 'D') {

int loc;

scanf(\,&loc); int x,y,z; T.split(root,x,z,loc);

T.split(x,x,y,loc-1); T.del(y); T.merge(root,x,z);

}

else if(op[0] == 'R') {

int loc; scanf(\,&loc); int x,y,z; T.split(root,x,z,loc); T.split(x,x,y,loc-1);

T.status[y] = 1-T.status[y]; T.push_up(y); T.merge(x,x,y); T.merge(root,x,z);

} else {

int loc,v; scanf(\,&loc,&v); int x,y,z; T.split(root,x,z,loc);

T.split(x,x,y,loc-1); T.key[y] = v; T.push_up(y); T.merge(x,x,y); T.merge(root,x,z);

}

return 0; }

图论

41 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

1、最短路

1.1 Dijkstra 单源最短路，邻接矩阵形式权值必须是非负

* 单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(n^2)

* 求出源beg到所有点的最短路径，传入图的顶点数，和邻接矩阵cost[][]

* 返回各点的最短路径lowcost[],路径pre[].pre[i]记录beg到i路径上的父结点，pre[beg]=-1 * 可更改路径权类型，但是权值必须为非负 * */

const int MAXN=1010; #define typec int

const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大 bool vis[MAXN]; int pre[MAXN];

void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg) {

for(int i=0;i

lowcost[i]=INF;vis[i]=false;pre[i]=-1;

}

lowcost[beg]=0;

for(int j=0;j

int k=-1; int Min=INF;

for(int i=0;i

if(!vis[i]&&lowcost[i]

Min=lowcost[i]; k=i;

}

if(k==-1)break; vis[k]=true; for(int i=0;i

if(!vis[i]&&lowcost[k]+cost[k][i]

lowcost[i]=lowcost[k]+cost[k][i]; pre[i]=k;

}

1.2 Dijkstar 算法+堆优化使用优先队列优化，复杂度O (E log E)

* 使用优先队列优化Dijkstra算法 * 复杂度O(ElogE)

* 注意对vectorE[MAXN]进行初始化后加边 */

const int INF=0x3f3f3f3f; const int MAXN=1000010; struct qnode {

int v; int c;

qnode(int _v=0,int _c=0):v(_v),c(_c){} bool operator <(const qnode &r)const {

return c>r.c;

}

};

struct Edge {

int v,cost;

Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}

};

vectorE[MAXN]; bool vis[MAXN]; int dist[MAXN];

void Dijkstra(int n,int start)//点的编号从1开始 {

memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++)dist[i]=INF;

priority_queueque; while(!que.empty())que.pop(); dist[start]=0; que.push(qnode(start,0)); qnode tmp;

while(!que.empty()) {

tmp=que.top(); que.pop();

int u=tmp.v; if(vis[u])continue; vis[u]=true; for(int i=0;i

int v=E[tmp.v][i].v; int cost=E[u][i].cost;

if(!vis[v]&&dist[v]>dist[u]+cost) {

dist[v]=dist[u]+cost; que.push(qnode(v,dist[v]));

}

42 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

void addedge(int u,int v,int w) {

E[u].push_back(Edge(v,w));

} /*

1.3 单源最短路 bellman_ford算法

* 单源最短路bellman_ford算法，复杂度O(VE)

* 可以处理负边权图。

* 可以判断是否存在负环回路。返回true,当且仅当图中不包含从源点可达的负权回路 * vectorE;先E.clear()初始化，然后加入所有边 * 点的编号从1开始(从0开始简单修改就可以了) */

const int INF=0x3f3f3f3f;

const int MAXN=550; int dist[MAXN]; struct Edge {

int u,v; int cost;

Edge(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost){}

};

vectorE;

bool bellman_ford(int start,int n)//点的编号从1开始 {

for(int i=1;i<=n;i++)dist[i]=INF; dist[start]=0; for(int i=1;i

bool flag=false;

for(int j=0;j

int u=E[j].u; int v=E[j].v;

int cost=E[j].cost;

if(dist[v]>dist[u]+cost) {

dist[v]=dist[u]+cost; flag=true;

}

if(!flag)return true;//没有负环回路

}

for(int j=0;j

if(dist[E[j].v]>dist[E[j].u]+E[j].cost) return false;//有负环回路

return true;//没有负环回路

}

1.4 单源最短路SPFA

* 单源最短路SPFA * 时间复杂度 0(kE)

* 这个是队列实现，有时候改成栈实现会更加快，很容易修改 * 这个复杂度是不定的 */

const int MAXN=1010; const int INF=0x3f3f3f3f; structEdge {

int v; int cost;

Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}

};

vectorE[MAXN];

void addedge(int u,int v,int w) {

E[u].push_back(Edge(v,w));

}

bool vis[MAXN];//在队列标志

int cnt[MAXN];//每个点的入队列次数 int dist[MAXN];

bool SPFA(int start,int n) {

memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++)dist[i]=INF; vis[start]=true;

dist[start]=0; queueque;

while(!que.empty())que.pop(); que.push(start);

memset(cnt,0,sizeof(cnt)); cnt[start]=1; while(!que.empty()) {

int u=que.front(); que.pop(); vis[u]=false; for(int i=0;i

int v=E[u][i].v;

if(dist[v]>dist[u]+E[u][i].cost) {

dist[v]=dist[u]+E[u][i].cost; if(!vis[v]) {

vis[v]=true; que.push(v); if(++cnt[v]>n)return false;

//cnt[i]为入队列次数，用来判定是否存在负环回路

}

43 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

return true;

}

2、最小生成树

2.1 Prim算法

Prim求MST

* 耗费矩阵cost[][]，标号从0开始，0~n-1 * 返回最小生成树的权值，返回-1表示原图不连通 */

const int INF=0x3f3f3f3f; const int MAXN=110; bool vis[MAXN]; int lowc[MAXN];

int Prim(int cost[][MAXN],int n)//点是0~n-1 {

int ans=0; memset(vis,false,sizeof(vis)); vis[0]=true; for(int i=1;i

int minc=INF; int p=-1;

for(int j=0;j

if(!vis[j]&&minc>lowc[j]) {

minc=lowc[j]; p=j;

}

if(minc==INF)return -1;//原图不连通

ans+=minc; vis[p]=true; for(intj=0;j

if(!vis[j]&&lowc[j]>cost[p][j]) lowc[j]=cost[p][j];

}

return ans;

}

2.2 Kruskal算法

Kruskal算法求MST */

const int MAXN=110;//最大点数 const int MAXM=10000;//最大边数 int F[MAXN];//并查集使用 struct Edge {

int u,v,w;

}edge[MAXM];//存储边的信息，包括起点/终点/权值 int tol;//边数，加边前赋值为0

void addedge(int u,int v,int w) {

edge[tol].u=u; edge[tol].v=v; edge[tol++].w=w;

}

bool cmp(Edge a,Edge b)

{//排序函数，讲边按照权值从小到大排序 return a.w

int find(int x) {

if(F[x]==-1)return x;

else return F[x]=find(F[x]);

}

int Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1 {

memset(F,-1,sizeof(F)); sort(edge,edge+tol,cmp); int cnt=0;//计算加入的边数 int ans=0;

for(int i=0;i

int u=edge[i].u; int v=edge[i].v; int

w=edge[i].w; int t1=find(u); int t2=find(v); if(t1!=t2) {

ans+=w; F[t1]=t2; cnt++;

}

if(cnt==n-1)break;

}

if(cnt

}

3、次小生成树

* 次小生成树

* 求最小生成树时，用数组Max[i][j]来表示MST中i到j最大边权

* 求完后，直接枚举所有不在MST中的边，替换掉最大边权的边，更新答案 * 点的编号从0开始 */

const int MAXN=110;

44 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

const int INF=0x3f3f3f3f;

bool vis[MAXN]; int lowc[MAXN]; int pre[MAXN];

int Max[MAXN][MAXN];//Max[i][j]表示在最小生成树中从i到j的路径中的最大边权 bool used[MAXN][MAXN];

int Prim(int cost[][MAXN],int n) {

int ans=0; memset(vis,false,sizeof(vis)); memset(Max,0,sizeof(Max)); memset(used,false,sizeof(used)); vis[0]=true; pre[0]=-1;

for(int i=1;i

lowc[i]=cost[0][i]; pre[i]=0;

}

lowc[0]=0;

for(int i=1;i

int minc=INF; int p=-1;

for(int j=0;j

if(!vis[j]&&minc>lowc[j]) {

minc=lowc[j]; p=j;

}

if(minc==INF)return -1; ans+=minc;

vis[p]=true; used[p][pre[p]]=used[pre[p]][p]=true; for(int j=0;j

if(vis[j])Max[j][p]=Max[p][j]=max(Max[j][pre[p]],lowc[p]); if(!vis[j]&&lowc[j]>cost[p][j]) {

lowc[j]=cost[p][j]; pre[j]=p;

}

return ans;

}

4、有向图的强连通分量

4.1 Tarjan

Tarjan算法 * 复杂度O(N+M) */

const int MAXN = 20010;//点数 const int MAXM = 50010;//边数 struct Edge {

int to,next; }edge[MAXM];

int head[MAXN],tot;

int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc int Index,top;

int scc;//强连通分量的个数 bool Instack[MAXN];

int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc //num数组不一定需要，结合实际情况 void addedge(int u,int v) {

edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;

}

void Tarjan(int u) {

int v;

Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true;

for(int i = head[u];i != -1;i = edge[i].next) {

v = edge[i].to; if( !DFN[v] ) {

Tarjan(v);

if( Low[u] > Low[v] )Low[u] = Low[v];

}

else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v];

}

if(Low[u] == DFN[u]) {

scc++; do {

v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++;

}

while( v != u);

}

void solve(int N)

45 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

{

memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(num,0,sizeof(num)); Index = scc = top = 0; for(int i = 1;i <= N;i++)

if(!DFN[i])

Tarjan(i); }

void init() {

tot = 0;

memset(head,-1,sizeof(head));

}

4.2 Kosaraju

Kosaraju算法，复杂度O(N+M) */

const int MAXN = 20010; const int MAXM = 50010; struct Edge {

int to,next;

}edge1[MAXM],edge2[MAXM];

//edge1是原图G，edge2是逆图GT int head1[MAXN],head2[MAXN]; bool mark1[MAXN],mark2[MAXN]; int tot1,tot2; int cnt1,cnt2;

int st[MAXN];//对原图进行dfs，点的结束时间从小到大排序 int Belong[MAXN];//每个点属于哪个连通分量(0~cnt2-1) int num;//中间变量，用来数某个连通分量中点的个数 int setNum[MAXN];//强连通分量中点的个数，编号0~cnt2-1 void addedge(int u,int v) {

edge1[tot1].to = v;edge1[tot1].next = head1[u];head1[u] = tot1++; edge2[tot2].to = u;edge2[tot2].next = head2[v];head2[v] = tot2++;

}

void DFS1(int u) {

mark1[u] = true;

for(int i = head1[u];i != -1;i = edge1[i].next)

if(!mark1[edge1[i].to])

DFS1(edge1[i].to); st[cnt1++] = u;

}

void DFS2(int u) {

mark2[u] = true; num++; Belong[u] = cnt2;

for(int i = head2[u];i != -1;i = edge2[i].next)

if(!mark2[edge2[i].to])

DFS2(edge2[i].to);

}

void solve(int n)//点的编号从1开始 {

memset(mark1,false,sizeof(mark1)); memset(mark2,false,sizeof(mark2)); cnt1 = cnt2 = 0;

for(int i = 1;i <= n;i++)

if(!mark1[i]) DFS1(i);

for(int i = cnt1-1;i >= 0; i--)

if(!mark2[st[i]]) {

num = 0; DFS2(st[i]); setNum[cnt2++] = num;

}

5、图的割点、桥和双连通分支的基本概念

[点连通度与边连通度]

在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点集合中的顶点数。类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。一个图的边连通度的定义为，最小割边集合中的边数。

[双连通图、割点与桥]

如果一个无向连通图的点连通度大于1，则称该图是点双连通的(point biconnected)，简称双连通或重连通。一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点(cut point)，又叫关节点(articulationpoint)。

如果一个无向连通图的边连通度大于 1，则称该图是边双连通的(edge biconnected)，简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为 1，则割边集合的唯一元素被称为桥(bridge)，又叫关节边 (articulation edge)。

可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，均既可指点双连通，又可指边双连通。

[双连通分支]

在图G的所有子图G'中，如果G'是双连通的，则称G'为双连通子图。如果一个双连通子图G'它不是任何一个双连通子图的真子集，则 G'为极大双连通子图。双连通分支(biconnectedcomponent)，或重连通分支，就是图的极大双连通子图。特殊的，点双连通分支又叫做块。

[求割点与桥]

该算法是R.Tarjan发明的。对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。根据定义，则有：

Low(u)=Min { DFS(u) DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)

一个顶点u是割点，当且仅当满足(1)或(2)(1)u为树根，且u有多于一个子树。(2)u不为树根，且满足存在(u,v)为树枝边(或称父子边，即 u 为 v 在搜索树中的父亲)，使得 DFS(u)<=Low(v)。一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)

[求双连通分支]

下面要分开讨论点双连通分支与边双连通分支的求法。对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v)，说明u 是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取

46 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。对于边双连通分支，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。

[构造双连通图] 一个有桥的连通图，如何把它通过加边变成边双连通图？方法为首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为 1。

统计出树中度为 1 的节点的个数，即为叶节点的个数，记为 leaf。则至少在树上添加(leaf+1)/2 条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两

个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2 次，把所有点收缩到了一起。

6、割点与桥

模板： /*

* 求无向图的割点和桥

*可以找出割点和桥，求删掉每个点后增加的连通块。

*需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重 */

const int MAXN = 10010; const int MAXM = 100010; struct Edge {

int to,next;

bool cut;//是否为桥的标记 }edge[MAXM];

int head[MAXN],tot;

int Low[MAXN],DFN[MAXN],Stack[MAXN]; int Index,top;

bool Instack[MAXN]; bool cut[MAXN];

int add_block[MAXN];//删除一个点后增加的连通块 int bridge;

void addedge(int u,int v) {

edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false; head[u] = tot++; }

void Tarjan(int u,int pre) {

int v;

Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true;

int son = 0;

for(int i = head[u];i != -1;i = edge[i].next) {

v = edge[i].to;

if(v == pre)continue; if( !DFN[v] ) {

son++; Tarjan(v,u);

if(Low[u] > Low[v])Low[u] = Low[v]; //桥

//一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u) DFN[u]) {

bridge++; edge[i].cut = true; edge[i^1].cut = true; }

//割点

//一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 //(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边， //即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v) if(u != pre && Low[v] >= DFN[u])//不是树根 {

cut[u] = true; add_block[u]++; } }

else if( Low[u] > DFN[v]) Low[u] = DFN[v]; }

//树根，分支数大于1

if(u == pre && son > 1)cut[u] = true; if(u == pre)add_block[u] = son - 1; Instack[u] = false; top--; }

调用：

1）UVA 796 Critical Links 给出一个无向图，按顺序输出桥 void solve(int N) {

memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack));

memset(add_block,0,sizeof(add_block)); memset(cut,false,sizeof(cut)); Index = top = 0; bridge = 0; for(int i = 1;i <= N;i++)

if( !DFN[i] )

Tarjan(i,i);

printf(\,bridge); vector>ans; for(int u = 1;u <= N;u++)

for(int i = head[u];i != -1;i = edge[i].next)

if(edge[i].cut && edge[i].to > u) {

ans.push_back(make_pair(u,edge[i].to));

47 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

}

sort(ans.begin(),ans.end()); //按顺序输出桥

for(int i = 0;i < ans.size();i++)

printf(\,ans[i].first-1,ans[i].second-1); printf(\);

}

void init() {

tot = 0;

memset(head,-1,sizeof(head)); }

//处理重边

mapmapit;

inline bool isHash(int u,int v) {

if(mapit[u*MAXN+v])return true; if(mapit[v*MAXN+u])return true; mapit[u*MAXN+v] = mapit[v*MAXN+u] = 1; return false; }

int main() {

int n;

while(scanf(\,&n) == 1) {

init(); int u; int k; int v; //mapit.clear();

for(int i = 1;i <= n;i++) {

scanf(\,&u,&k); u++;

//这样加边，要保证正边和反边是相邻的，建无向图 while(k--) {

scanf(\,&v); v++; if(v <= u)continue;

//if(isHash(u,v))continue; addedge(u,v); addedge(v,u); } }

solve(n); }

return 0; }

2）POJ 2117 求删除一个点后，图中最多有多少个连通块 void solve(int N) {

memset(DFN,0,sizeof(DFN)); memset(Instack,0,sizeof(Instack));

memset(add_block,0,sizeof(add_block)); memset(cut,false,sizeof(cut)); Index = top = 0;

int cnt = 0;//原来的连通块数 for(int i = 1;i <= N;i++)

if( !DFN[i] ) {

Tarjan(i,i);//找割点调用必须是Tarjan(i,i) cnt++; }

int ans = 0;

for(int i = 1;i <= N;i++)

ans = max(ans,cnt+add_block[i]); printf(\,ans); }

void init() {

tot = 0;

memset(head,-1,sizeof(head)); }

int main() {

int n,m; int u,v;

while(scanf(\,&n,&m)==2) {

if(n==0 && m == 0)break; init(); while(m--) {

scanf(\,&u,&v); u++;v++; addedge(u,v); addedge(v,u); }

solve(n); }

return 0; }

7、边双连通分支

去掉桥，其余的连通分支就是边双连通分支了。一个有桥的连通图要变成边双连通图的话，把双连通子图收缩为一个点，形成一颗树。需要加的边为(leaf+1)/2(leaf为叶子结点个数)

48 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

POJ 3177 给定一个连通的无向图 G，至少要添加几条边，才能使其变为双连通图。 #include #include #include #include #include

using namespace std;

const int MAXN = 5010;//点数

const int MAXM = 20010;//边数，因为是无向图，所以这个值要*2 struct Edge {

int to,next;

bool cut;//是否是桥标记 }edge[MAXM];

int head[MAXN],tot;

int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block int Index,top;

int block;//边双连通块数 bool Instack[MAXN]; intbridge;//桥的数目

void addedge(int u,int v) {

edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false; head[u] = tot++; }

void Tarjan(int u,int pre) {

int v;

Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true;

for(int i = head[u];i != -1;i = edge[i].next) {

v = edge[i].to;

if(v == pre)continue; if( !DFN[v] ) {

Tarjan(v,u);

if( Low[u] > Low[v] )Low[u] = Low[v]; if(Low[v] > DFN[u]) {

bridge++; edge[i].cut = true; edge[i^1].cut = true; } }

else if( Instack[v] && Low[u] > DFN[v] ) Low[u] = DFN[v]; }

if(Low[u] == DFN[u]) {

block++; do {

v = Stack[--top]; Instack[v] = false; Belong[v] = block; }

while( v!=u ); } }

void init() {

tot = 0;

memset(head,-1,sizeof(head)); }

int du[MAXN];//缩点后形成树，每个点的度数 void solve(int n) {

memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); Index = top = block = 0; Tarjan(1,0);

int ans = 0; memset(du,0,sizeof(du)); for(int i = 1;i <= n;i++)

for(int j = head[i];j != -1;j = edge[j].next)

if(edge[j].cut)

du[Belong[i]]++;

for(int i = 1;i <= block;i++)

if(du[i]==1) ans++;

//找叶子结点的个数ans,构造边双连通图需要加边(ans+1)/2 printf(\,(ans+1)/2); }

int main() {

int n,m; int u,v;

while(scanf(\,&n,&m)==2) {

init(); while(m--) {

49 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

scanf(\,&u,&v); addedge(u,v); addedge(v,u); }

solve(n); }

return 0; }

8、点双连通分支

对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足 DFS(u)<=Low(v)，说明 u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。 POJ 2942

奇圈，二分图判断的染色法，求点双连通分支 /*

POJ 2942 Knights of the Round Table 亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求： 1、相互憎恨的两个骑士不能坐在直接相邻的2个位置； 2、出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。

注意：1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。 2、由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。即每个骑士的座位两边都必定各有一个骑士。 3、一个骑士无法开会，就是说至少有3个骑士才可能开会。首先根据给出的互相憎恨的图中得到补图。然后就相当于找出不能形成奇圈的点。利用下面两个定理：

（1）如果一个双连通分量内的某些顶点在一个奇圈中（即双连通分量含有奇圈），那么这个双连通分量的其他顶点也在某个奇圈中；（2）如果一个双连通分量含有奇圈，则他必定不是一个二分图。反过来也成立，这是一个充要条件。

所以本题的做法，就是对补图求点双连通分量。然后对于求得的点双连通分量，使用染色法判断是不是二分图，不是二分图，这个双连通分量的点是可以存在的 */

const int MAXN = 1010; const int MAXM = 2000010; struct Edge {

int to,next; }edge[MAXM];

int head[MAXN],tot;

int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN]; int Index,top;

int block;//点双连通分量的个数 bool Instack[MAXN]; bool can[MAXN];

bool ok[MAXN];//标记

int tmp[MAXN];//暂时存储双连通分量中的点 int cc;//tmp的计数

int color[MAXN];//染色

void addedge(int u,int v) {

edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; }