AC自动机

板子

http://192.168.45.99/problem.php?id=1623

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int cnt[500010],q[500010],fail[500010],n,m,x,son[500010][26],tot;
char s[500010];
LL ans;
void ins(){
    x=0;
    FOR(i,0,m-1){
        if (!son[x][s[i]-'a']) son[x][s[i]-'a']=++tot;
        x=son[x][s[i]-'a'];
    }
    cnt[x]=1;
}
void build(){
    int he=0,ta=1;
    q[1]=0;
    while (he!=ta){
        int x=q[++he];
        cnt[x]+=cnt[fail[x]];
        FOR(i,0,25){
            int y=son[x][i];
            if (!y) continue;
            if (x){
                int tmp=fail[x];
                while (tmp && !son[tmp][i]) tmp=fail[tmp];
                fail[y]=son[tmp][i];
            }
            q[++ta]=y;
        }
    }
}
void fnd(){
    x=0;
    FOR(i,0,m-1){
        while (x && !son[x][s[i]-'a']) x=fail[x];
        if (son[x][s[i]-'a']) x=son[x][s[i]-'a'];
        ans+=cnt[x];
    }
}
int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        scanf("%s",s);
        m=strlen(s);
        ins();
    }
    build();
    scanf("%s",s);
    m=strlen(s);
    fnd();
    cout<<ans<<endl;
    return 0;
}

基础练习题

http://codeforces.com/contest/86/submission/33919169

http://codeforces.com/contest/163/submission/33955397

http://codeforces.com/contest/696/submission/33960564

 

http://codeforces.com/contest/547/submission/34041438

每个串可以看成是它的所有的前缀,fail树上能走到k的是合法的,转化为静态二维数点。

CF710F强在AC自动机(留坑

splay

复习splay

http://codeforces.com/contest/38/submission/33897822

http://www.lydsy.com/JudgeOnline/problem.php?id=3786

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
struct node{
	int tp,d,fa;
	int ch[2],siz;
	LL s,v,tag;
}t[200010];
char s[55];
int rt,stk[500010],top,x,y,X,Y,nxt[500010],hed[500010],too[500010],nedge,n,m,a[100010],L[100010],R[100010],dfn,tot;
void ae(int x,int y){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
}
bool isroot(int x){
	return (t[x].fa==0);
}
void dfs(int x,int l){
	L[x]=++dfn;
	t[L[x]].v=a[x];
	t[L[x]].tp=1;
	for (int i=hed[x];i;i=nxt[i]){
		int y=too[i];
		if (y==l) continue;
		dfs(y,x);
	}
	R[x]=++dfn;
	t[R[x]].v=-a[x];
	t[R[x]].tp=-1;
}
void TAG(int x,LL y){
	t[x].v+=t[x].tp*y;
	t[x].s+=t[x].d*y;
	t[x].tag+=y;
}
void pushup(int x){
	t[x].s=t[x].v+t[t[x].ch[0]].s+t[t[x].ch[1]].s;
	t[x].d=t[x].tp+t[t[x].ch[0]].d+t[t[x].ch[1]].d;
	t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
}
void pushdown(int x){
	if (t[x].tag){
		if (t[x].ch[0]) TAG(t[x].ch[0],t[x].tag);
		if (t[x].ch[1]) TAG(t[x].ch[1],t[x].tag);
		t[x].tag=0;
	}
}
void debug(int x){
	pushdown(x);
	if (t[x].ch[0]) debug(t[x].ch[0]);
	printf("%lld ",t[x].v);
	if (t[x].ch[1]) debug(t[x].ch[1]);
}
int build(int l,int r,int fa){
	int m=l+r>>1;
	t[m].s=t[m].v;
	t[m].fa=fa;
	if (l<=m-1) t[m].ch[0]=build(l,m-1,m);
	if (m+1<=r) t[m].ch[1]=build(m+1,r,m);
	pushup(m);
	return m;
}
void rot(int x){
	int fa=t[x].fa;
	int gfa=t[fa].fa;
	int t1=(x!=t[fa].ch[0]);
	int t2=(fa!=t[gfa].ch[0]);
	int ch=t[x].ch[t1^1];
	if (!isroot(fa)) t[gfa].ch[t2]=x;
	t[ch].fa=fa;
	t[x].fa=gfa;
	t[x].ch[t1^1]=fa;
	t[fa].fa=x;
	t[fa].ch[t1]=ch;
	pushup(fa);
	pushup(x);
}
void splay(int x,int too){
	if (too==0) rt=x;
	if (too==-1) too=rt;
	stk[top=1]=x;
	int y=x;
	while (!isroot(y)) stk[++top]=t[y].fa,y=t[y].fa;
	FORD(rp,top,1) pushdown(stk[rp]);
	while (t[x].fa!=too){
		int fa=t[x].fa;
		int gfa=t[fa].fa;
		if (gfa!=too)
			x==t[fa].ch[0]^fa==t[gfa].ch[0]?rot(x):rot(fa);
		rot(x);
	}
}
int rnk(int x){
	splay(x,0);
//	debug(rt),puts("");
	return t[t[x].ch[0]].siz+1;
}
int fnd(int x,int k){
	if (x==-1) x=rt;
//	debug(rt),puts("");
	if (t[t[x].ch[0]].siz>=k) return fnd(t[x].ch[0],k);
	else if (k==t[t[x].ch[0]].siz+1) return x;
	else return fnd(t[x].ch[1],k-t[t[x].ch[0]].siz-1);
}
int main(){
//	freopen("t.in","r",stdin);
//	freopen("t.out","w",stdout);
	scanf("%d",&n);
	FOR(i,2,n){
		int t;
		getint(t);
		ae(t,i);
	}
	FOR(i,1,n) getint(a[i]);
	dfs(1,0);
	tot=dfn;
	rt=build(1,tot,0);
	t[tot+1].ch[1]=tot+2;
	t[tot+2].fa=tot+1;
	t[tot+2].ch[0]=rt;
	t[rt].fa=tot+2;
	rt=tot+1;
	scanf("%d",&m);
//	debug(rt),puts("");
	while (m--){
		scanf("%s",s);
	//	debug(rt),puts("");
		if (s[0]=='Q'){
			getint(x);
		//	debug(rt),puts("");
			int h=fnd(-1,rnk(L[x])+1);
		//	debug(rt),puts("");
			splay(h,0);
			pushdown(rt);
			printf("%lld\n",t[t[h].ch[0]].s);
		}
		else if (s[0]=='F'){
			getint(x),getint(y);
			X=fnd(-1,rnk(L[x])-1);
			Y=fnd(-1,rnk(R[x])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			TAG(t[t[rt].ch[1]].ch[0],y);
			pushdown(rt);
			pushdown(t[rt].ch[1]);
			pushup(t[rt].ch[1]);
			pushup(rt);
		}
		else{
			getint(x),getint(y);
			X=fnd(-1,rnk(L[x])-1);
			Y=fnd(-1,rnk(R[x])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			int w=t[t[rt].ch[1]].ch[0];
			t[t[w].fa].ch[0]=0;
			pushup(t[w].fa);
			pushup(rt);
		//	debug(rt),puts("");
			X=fnd(-1,rnk(L[y]));
			Y=fnd(-1,rnk(L[y])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			t[Y].ch[0]=w;
			t[w].fa=Y;
			pushup(Y);
			pushup(X);
		}
	}
	return 0;
}

化不合法为不优

O(time)->O(ans)

http://www.lydsy.com/JudgeOnline/problem.php?id=4716

正解是用个堆,然而有个非常高明的”暴力“。

#pragma GCC optimize("O2")
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for (register int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
typedef long long ll;
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> vec;
inline void read(int &x) {
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
const int N = 1050;
int n,m,xmn,ymn,k;
int a[N][N];
ll s[N][N];
inline ll getsum(int x0, int y0, int x1, int y1) {
    x0--; y0--;
    return s[x1][y1]-s[x0][y1]-s[x1][y0]+s[x0][y0];
}
inline int getans(int val) { //"<=val"
    int res=0; //if (res>=k) return res;
    rep(i,1,n-xmn+1) rep(j,1,m-ymn+1) {
        register int x=i+xmn-1,y=j+ymn-1;
        for (;x<=n;x++) {
            if (getsum(i,j,x,y)>val) break;
            rep(Y,y,m) {
                if (getsum(i,j,x,Y)>val) break;
                res++; if (res>=k) return res;
            }
        }
    }
    return res;
}
int main() {
    read(n); read(m); read(xmn); read(ymn); read(k);
    rep(i,1,n) rep(j,1,m) read(a[i][j]);
    rep(i,1,n) rep(j,1,m) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    int l=0,r=n*m*2000;
    while (l<r) {
        register int mid=(1LL*l+r)>>1;
        if (getans(mid)<k) l=mid+1; else r=mid;
    }
    printf("%d",l+1);
    return 0;
}

可以证明,每次getans函数,里面有用的解只有O(k)个,没用的解(多余的复杂度)也只有O(k+nm)个,所以复杂度是O(nm+k)。

生成树计数-基尔霍夫定理

http://vfleaking.blog.163.com/blog/static/1748076342013112523651955/

https://www.cnblogs.com/GerynOhenz/p/4450417.html

http://blog.csdn.net/werkeytom_ftd/article/details/60766200

 

找规律

BZOJ1228

这个SG规律真难找,找了半天也找不出最后看了题解。

这个规律不是O(1)的,是O(log)的。

SG[i/2][j/2]->SG[i][j]

int GetSG(int n,int m){
    if((n&1)&&(m&1)) return 0;
    if(!(n&1)&&!(m&1)) return GetSG(n/2,m/2)+1;
    return (n&1)?GetSG((n+1)/2,m/2)+1:GetSG(n/2,(m+1)/2)+1;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int tmp[500010],ts,mex,sg[555][555];
int main(){
	FOR(t,2,60)
		FOR(j,1,t-1){
			int i=t-j;
			ts=0;
			FOR(k,1,i-1) tmp[++ts]=sg[k][i-k];
			FOR(k,1,j-1) tmp[++ts]=sg[k][j-k];
			sort(tmp+1,tmp+ts+1);
			ts=unique(tmp+1,tmp+ts+1)-tmp-1;
			mex=-1;
			FOR(k,1,ts)
				if (tmp[k]==mex+1) ++mex;
			sg[i][j]=mex+1;
		}
	FOR(i,1,30){
		FOR(j,1,30) printf("%d ",sg[i][j]);
		puts("");
	}
	return 0;
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3288

欧拉函数前缀积。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
int n,phi[1000010],p[1000010],pr;
LL ans;
bool u[1000010];
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
void getp(){
	phi[1]=1;
	FOR(i,2,n){
		if (!u[i]){p[++pr]=i;phi[i]=i-1;}
		FOR(j,1,pr){
			if (i*p[j]>n) break;
			u[i*p[j]]=1;
			if (i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
			else phi[i*p[j]]=phi[i]*phi[p[j]];
		}
	}
}
int main(){
	cin>>n;
	getp();
	ans=1;
	FOR(i,1,n) ans=ans*phi[i]%MO;
	cout<<ans<<endl;
	return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
int a[1010][1010],n,k;
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
LL det(){
	LL ans=1;
	FOR(i,1,n){
		k=0;
		FOR(j,i,n)
			if (a[j][i]!=0){k=j;break;}
		if (!k) return 0ll;
		if (i!=k){
			FOR(j,1,n) swap(a[i][j],a[k][j]);
			ans=-ans;
		}
		LL t=pw(a[i][i],MO-2);
		FOR(j,i+1,n)
			if (a[j][i]!=0){
				LL w=-t*a[k][i]%MO;
				FOR(k,i,n) (a[j][k]+=a[i][k]*w)%=MO;
			}
	}
	FOR(i,1,n) ans=ans*a[i][i]%MO;
	return ans;
}
int main(){
	cin>>n;
	FOR(i,1,n)
		FOR(j,1,n)
			a[i][j]=__gcd(i,j);
	cout<<det()<<endl;
	return 0;
}

生成树计数-prufer

https://www.cnblogs.com/dirge/p/5503289.html

BZOJ1005

确定每个点度数后容易求出有多少种不同的无根树。

https://loj.ac/problem/6044

硬点一些点作为奇层点,一些点作为偶层层,方案数为C(n-1,k-1)。

令S(x,y)表示左边x个点右边y个点的二分图的生成树计数。

ans=C(n-1,k-1)*S(k,n-k)

考虑用prufer推S(x,y):

最后剩下的两个点肯定一个是左边的,一个是右边的。

因为我们已经确定了左边x个点的标号和右边y个点的标号,所以我们进行求prufer序列这个操作的时候,每次删掉的点是哪一个是确定的,只要考虑写入prufer的数是哪个,如果是删除左边,那么prufer中新增的数有y-1种可能,如果是删除右边,那么prufer中新增的数有x-1种可能,所以S(x,y)=x^(y-1)*y^(x-1)。

https://loj.ac/submission/52865

KMP

http://codeforces.com/contest/631/submission/33833481

最小圆覆盖

http://blog.csdn.net/commonc/article/details/52291822

BZOJ2823

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const double eps=1e-6;
struct Point{
	double x,y;
	Point(){}
	Point(double X,double Y){x=X;y=Y;}
	Point operator - (const Point & A) const{
		return Point(x-A.x,y-A.y);
	}
}P[1000010];
int n;
struct Circle{
	Point o;
	double r;
}C;
int sgn(double x){
	if (fabs(x)<eps) return 0;
	else if (x>0) return 1;
	else return -1;
}
double dis(Point A,Point B){
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
bool IN(Point P,Circle C){
	return (sgn(dis(P,C.o)-C.r)<=0);
}
Circle get1(Point A,Point B){
	Circle t;
	t.o.x=(A.x+B.x)/2,t.o.y=(A.y+B.y)/2;
	t.r=dis(A,B)/2;
	return t;
}
Point rev(Point P){
	return Point(P.y,-P.x);
}
Circle get2(Point A,Point B,Point C){
	Circle O;
	Point P1=Point((A.x+B.x)/2,(A.y+B.y)/2);
	Point Q1=rev(B-A);
	Point P2=Point((A.x+C.x)/2,(A.y+C.y)/2);
	Point Q2=rev(C-A);
	double b=(Q1.x*P1.y-Q1.x*P2.y+P2.x*Q1.y-P1.x*Q1.y)/(Q2.y*Q1.x-Q2.x*Q1.y);
	double a;
	if (sgn(Q1.x)!=0) a=(P2.x+Q2.x*b-P1.x)/Q1.x;
	else a=(P2.y+Q2.y*b-P1.y)/Q1.y;
	O.o.x=P1.x+Q1.x*a;
	O.o.y=P1.y+Q1.y*a;
	O.r=dis(O.o,A);
	return O;
}
int main(){
	scanf("%d",&n);
	FOR(i,1,n) scanf("%lf%lf",&P[i].x,&P[i].y);
	random_shuffle(P+1,P+n+1);
	C.o.x=P[1].x,C.o.y=P[1].y,C.r=0.0;
	FOR(i,2,n)
		if (!IN(P[i],C)){
			C.o=P[i],C.r=0.0;
			FOR(j,1,i-1)
				if (!IN(P[j],C)){
					C=get1(P[i],P[j]);
					FOR(k,1,j-1)
						if (!IN(P[k],C))
							C=get2(P[i],P[j],P[k]);
				}
		}
	printf("%.2f %.2f %.2f\n",C.o.x,C.o.y,C.r);
	return 0;
}

最小树形图