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;
}

最小树形图

Surreal Number

利用Surreal Number解决一类不平等的组合游戏(Partisan Combinatorial Games)

https://wenku.baidu.com/view/65b1a600a6c30c2259019ea8.html

http://www.matrix67.com/blog/archives/6333

待填坑

欧拉降幂

 

CF17D

直接套用公式

http://codeforces.com/contest/17/submission/33807003

 

BZOJ3884

一个数经过O(log)次求phi后变成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;
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;
}
bool u[10000010];
int T,n,f[10000010],phi[10000010],pr,p[1000010];
LL pw(LL x,LL y,LL MO){
	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;
	n=1e7;
	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]];
		}
	}
}
LL cal(int n){
	if (f[n]!=-1) return f[n];
	return f[n]=pw(2,cal(phi[n])+phi[n],n);
}
int main(){
	scanf("%d",&T);
	getp();
	memset(f,-1,sizeof(f));
	f[1]=0;
	while (T--){
		scanf("%d",&n);
		printf("%lld\n",cal(n));
	}
	return 0;
}

CF906D

因为经过O(log)次phi变成1,所以同样递归求解即可。

http://codeforces.com/contest/906/submission/33807499

三分答案

对于一个在某处x最优,其它地方离x越近越优的函数,可以三分求出x。

考虑当前三分区间[l,r]

令p=l+(r-l)/3,q=r-(r-l)/3

如果p比q优,那么[l,r]->[l,q],否则[l,r]->[p,r]

(易证)

 

CF101246J

三分距离差,求值(一定有个不动点)。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<complex>
#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 n,w,a[555];
double p,q,l,r;
double cal(double o){
	double cst=1e9;
	FOR(W,1,n){
		double t=0.0;
		FOR(i,1,n) t+=fabs(a[W]+(i-W)*o-a[i]);
		if (t<cst) cst=t,w=W;
	}
	return cst;
}
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
	scanf("%d",&n);
	FOR(i,1,n) scanf("%d",&a[i]);
	l=0.0,r=30000.0;
	FOR(rp,1,100){
		p=l+(r-l)/3;
		q=r-(r-l)/3;
		if (cal(p)<cal(q)) r=q;
		else l=p;
	}
	printf("%.10f\n",cal(r));
	FOR(i,1,n) printf("%.10f ",a[w]+(i-w)*r);
	return 0;
}

还有一种姿势叫做三分套三分。

BZOJ1857

最大权闭合子图

http://hihocoder.com/problemset/problem/1398

 

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

给你一张DAG,每个点有点权,让你找出一个拓扑序,使得最大连续子段和尽量大。n<=50,-200<=ai<=200

首先显然拓扑序的后缀一定是个闭合子图,那么拓扑序的连续子段其实是两个闭合子图的差。

把每个点拆成两个,具体自行脑补。。

#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;
typedef long double ld;
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 INF=1e9+10;
int nxt[500010],q[500010],S,T,ans,d[500010],hed[500010],cap[500010],too[500010],nedge,n,m,x,y,a[666];
void ae(int x,int y,int w){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
	cap[nedge]=w;
}
void add(int x,int y,int w){
	ae(x,y,w),ae(y,x,0);
}
bool build(){
	int he=0,ta=1;
	q[1]=S;
	FOR(i,S,T) d[i]=-1;
	d[S]=0;
	while (he!=ta){
		int x=q[++he];
		for (int i=hed[x];i;i=nxt[i]){
			int y=too[i];
			if (!cap[i] || d[y]!=-1) continue;
			d[y]=d[x]+1;
			q[++ta]=y;
			if (y==T) return 1;
		}
	}
	return 0;
}
int fnd(int x,int flo){
	if (x==T) return flo;
	int ret,w=0;
	for (int i=hed[x];i && w<flo;i=nxt[i]){
		int y=too[i];
		if (d[y]==d[x]+1 && cap[i] && (ret=fnd(y,min(flo-w,cap[i]))))
			w+=ret,cap[i]-=ret,cap[i^1]+=ret;
	}
	d[x]=-1;
	return w;
}
int dinic(){
	int ans=0;
	while (build()){
		while (1){
			int flo=fnd(S,INF);
			if (!flo) break;
			ans+=flo;
		}
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	S=0;
	T=n+n+1;
	nedge=1;
	FOR(i,1,n){
		getint(a[i]);
		ans+=abs(a[i]);
		if (a[i]>=0) add(S,i,a[i]),add(n+i,T,a[i]);
		else add(i,T,-a[i]),add(S,n+i,-a[i]);
		add(i+n,i,INF);
	}
	FOR(i,1,m){
		getint(x),getint(y);
		add(x,y,INF),add(x+n,y+n,INF);
	}
	cout<<ans-dinic()<<endl;
	return 0;
}

http://codeforces.com/contest/103/submission/33199171

先找出一个完美匹配,然后对于左边的x,匹配右边的match[x],对于右边的y,匹配左边的match'[y].

现在要证明,一个方法是合法的当且仅当:

对于任意选了的左边的x,x连出去的点y必须选了(题目条件);对于任意的选了的y,match'[y]必须也选了。

令左边选的集合为P,右边选的集合为Q。

充分性:根据hall定理,|P|<=|Q|,因为对于任意的x属于Q,match'[x]属于P,所以|P|>=|Q|,所以|P|=|Q|。

必要性:假设选了y,match'[y]没有选(即左边一个点x选了,match[x]没有选),那么一定|P|<|Q|。

假设我在左边,你在右边,因为match互不相同,所以我有一个x,你就有一个match[x],"我有的你都有了,我没有的你也有(MYC原话)“。显然不合法。

之后就是个最大权闭合子图了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<complex>
#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 INF=1e9+10;
bool c[1010][1010],v[5555];
int nxt[500010],q[500010],S,T,ans,h[500010],g[500010],d[500010],hed[500010],cap[500010],too[500010],nedge,n,m,x,y,a[666];
void ae(int x,int y,int w){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
	cap[nedge]=w;
}
void add(int x,int y,int w){
	ae(x,y,w),ae(y,x,0);
}
bool build(){
	int he=0,ta=1;
	q[1]=S;
	FOR(i,S,T) d[i]=-1;
	d[S]=0;
	while (he!=ta){
		int x=q[++he];
		for (int i=hed[x];i;i=nxt[i]){
			int y=too[i];
			if (!cap[i] || d[y]!=-1) continue;
			d[y]=d[x]+1;
			q[++ta]=y;
			if (y==T) return 1;
		}
	}
	return 0;
}
int fnd(int x,int flo){
	if (x==T) return flo;
	int ret,w=0;
	for (int i=hed[x];i && w<flo;i=nxt[i]){
		int y=too[i];
		if (d[y]==d[x]+1 && cap[i] && (ret=fnd(y,min(flo-w,cap[i]))))
			w+=ret,cap[i]-=ret,cap[i^1]+=ret;
	}
	d[x]=-1;
	return w;
}
int dinic(){
	int ans=0;
	while (build()){
		while (1){
			int flo=fnd(S,INF);
			if (!flo) break;
			ans+=flo;
		}
	}
	return ans;
}
bool ck(int x){
	FOR(y,1,n){
		if (!c[x][y] || v[y]) continue;
		v[y]=1;
		if (h[y]==-1 || ck(h[y])){
			h[y]=x;
			return 1;
		}
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	S=0;
	T=n+n+1;
	nedge=1;
	memset(h,-1,sizeof(h));
	FOR(i,1,n){
		scanf("%d",&x);
		while (x--){
			getint(y);
			c[i][y]=1;
		}
	}
	FOR(i,1,n){
		FOR(j,1,n) v[j]=0;
		ck(i);
	}
	FOR(i,1,n) g[h[i]]=i;
	FOR(i,1,n){
		FOR(j,1,n)
			if (c[i][j] && j!=g[i]){
				add(i,h[j],INF);
			}
	}
	FOR(i,1,n){
		getint(a[i]);
		a[i]=-a[i];
		if (a[i]>=0) add(S,i,a[i]),ans+=a[i];
		else add(i,T,-a[i]);
	}
	ans-=dinic();
	cout<<-ans<<endl;
	return 0;
}

另外还有一种做法用到了一个小技巧:化不合法为不优。

你让左边的权+M(M很大),那么左边的点少选一个会带来很”恶劣“的影响使得解很差,不影响你求最优解。

2-SAT

https://orbitingflea.github.io/2017/08/18/note/2-sat/

 

CF568C

显然2-sat,求出最长的lcp然后再按位确定。

用时成功垫底QAQ

http://codeforces.com/contest/568/submission/32624914

manacher

//输入,并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的

一个字符串本质不同的回文串只有O(n)个

FFT

http://picks.logdown.com/posts/177631-fast-fourier-transform

 

CF286E

让你构造尽量少的数使得这些数中选出一些数的和(可以重复选同一个数,和<=m)组成的集合与输入的集合那n个数完全相同。n,m<=1e6

首先我们可以注意到构造的数肯定在输入的集合中出现过,即构造的这些数是输入数集的子集。(否则与题意条件矛盾)

所以我们考虑一个naive的做法,按照输入集合的顺序(已经sort好了),从前往后,如果当前这个数已经出现在构造的数能组成的集合中了,就跳过此数,否则把此数加入构造的数集,考虑怎么知道这个数是否已经组出来了,直接背包,获得O(nm)算法。

我们认为一个数如果不加入构造的数集,这个数是没用的。

一个数如果是没用的,说明他可以由另外的数相加得到。

我们来证明这个数最多由2个数相加得到。

如果由3个数相加得到,比如x=a+b+c。

如果输入的集合里有y=a+b,直接用x=y+c即可不需要x=a+b+c,

如果输入的集合里没y=a+b,则组成的y与题意条件矛盾,不合法。

所以一定是由2个构造的数集中的数相加得到。

那么我们只要对于每个ai判断是否存在ai=aj+ak。

显然FFT即可。

无解的判断很简单。

http://codeforces.com/contest/286/submission/31786843