思路:

本人自己写了一个傻逼的不能再傻逼的御用凸包模板,谁要是扒的话简直就是作死...

然后这道题目主要就是利用旋转卡壳寻找对踵点,然后更新答案.

然后旋转卡壳非常牛逼是\(O(n)\)的.这是为什么呢?

对于凸包上的每一条边,对踵点与这条边形成的三角形的面积必定最大.因此,这条边之外的点是成一个单峰函数分布的.

此外我们还很容易从凸包上得到单调性.

利用这两个性质,就很容易做到凸包上的线性扫描了.

#include<set>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 50010

struct Point{
	int x,y;
	Point(){}
	Point(int _x,int _y):x(_x),y(_y){}
	bool operator<(const Point&B)const{return(x<B.x)||(x==B.x&&y>B.y);}
	Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
	Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
}P[N];int cnt;
inline int Cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
inline int sqr(int x){return x*x;}
inline int dis2(const Point&a,const Point&b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
set<Point>S;

Point stk[N];int top;

#define f(x) (x>top?1:x)
int main(){
	//freopen("tt.in","r",stdin);
	int n;scanf("%d",&n);register int i,j;
	
	if(n<=1){puts("0");return 0;}
	
	int x,y;
	while(n--){scanf("%d%d",&x,&y);if(S.find(Point(x,y))==S.end())S.insert(Point(x,y)),P[++cnt]=Point(x,y);}
	
	sort(P+1,P+cnt+1);
	
	bool allline=1;
	for(i=1;i+2<=cnt;++i)if(Cross(P[i]-P[i+1],P[i+1]-P[i+2])!=0)allline=0;
	if(allline){printf("%d",dis2(P[1],P[cnt]));return 0;}
	
	int revins;for(revins=cnt;revins!=1&&P[revins].x==P[revins-1].x;--revins);
	for(i=revins;i<=(n+revins)/2;++i)swap(P[i],P[n+revins-i]);
	
	for(i=1;i<=cnt;++i){
		if(!top)stk[++top]=P[i];
		else{while(top>1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];}
	}
	int nowtop=top;
	for(i=revins-1;i>=1;--i){
		if(top==nowtop)stk[++top]=P[i];
		else{while(top>nowtop+1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];}
	}--top;
	
	int r=2,res=0;
	for(i=1;i<=top;++i){
		while(Cross(stk[i]-stk[f(i+1)],stk[i]-stk[r])<=Cross(stk[i]-stk[f(i+1)],stk[i]-stk[f(r+1)]))r=f(r+1);
		res=max(res,dis2(stk[i],stk[r]));
		res=max(res,dis2(stk[f(i+1)],stk[r]));
	}
	
	printf("%d",res);
	return 0;
}

题意:求出\(n\)个点的无向完全图的子图中有多少个是连通图.

思路:

令\(f_i\)表示\(i\)个点时的连通图个数.

考虑如果图不连通,那么必定存在某些点与\(1\)号点不在一个连通分量中.

如果我们要计算\(f_n\),那就枚举和\(1\)号点在一个连通分量中中的有几个点,那么与这个连通分量无关的点的集合内部就可以随便连边了.这种情况下我们要考虑是哪些点和\(1\)号点在一个连通分量中,另外还要乘上这个连通分量的内部连边数.这个是之前已经搞出来的.

随后利用高精度预处理一下直接输出.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

static const int mod=1e4;
struct Int{
	int d[500],l;
	Int():l(1){memset(d,0,sizeof d);}
	inline void operator=(const int&x){memset(d,0,sizeof d),l=1,d[0]=x;}
	inline void operator+=(const Int&B){
		l=l>B.l?l:B.l;for(int i=0;i<l;++i)if((d[i]+=B.d[i])>=mod)d[i]-=mod,d[i+1]++;
		if(d[l])l++;
	}
	inline void operator*=(const Int&B){
		Int C;
		for(int i=0;i<l;++i)for(int j=0;j<B.l;++j){
			C.d[i+j]+=d[i]*B.d[j];if(C.d[i+j]>=mod)C.d[i+j+1]+=C.d[i+j]/mod,C.d[i+j]%=mod;
		}
		for(C.l=l+B.l+1;!C.d[C.l-1];--C.l);
		*this=C;
	}
	inline void operator-=(const Int&B){
		for(int i=0;i<B.l;++i){if((d[i]-=B.d[i])<0){d[i]+=mod,d[i+1]--;}}
		while(l>1&&d[l-1]==0)--l;
	}
	Int operator*(const Int&B)const{Int r=*this;r*=B;return r;}
	inline void print(){
		printf("%d",d[l-1]);for(int i=l-2;i>=0;--i)printf("%04d",d[i]);
	}
};
Int pow(int y){
	Int t,r;for(t=2,r=1;y;y>>=1,t*=t)if(y&1)r*=t;return r;
}
Int C[51][51];
inline void Init(){
	C[0][0]=1,C[1][0]=1,C[1][1]=1;
	for(int i=2;i<=50;++i){
		C[i][0]=1,C[i][i]=1;
		for(int j=1;j<i;++j)C[i][j]=C[i-1][j-1],C[i][j]+=C[i-1][j];
	}
}
Int f[51];

int main(){
	f[1]=1;Init();
	for(int i=2;i<=50;++i){
		f[i]=pow(i*(i-1)>>1);
		for(int j=0;j<i-1;++j)f[i]-=C[i-1][j]*f[j+1]*pow((i-j-1)*(i-j-2)>>1);
	}
	int x;while(scanf("%d",&x)&&x)f[x].print(),puts("");
	return 0;
}

题目大意:

给定一个二分图以及一组已知的完备匹配,要求对于每个\(X\)集合中的点确定这个点与哪些个\(Y\)集合中的点匹配时,依然能够存在完备匹配.

思路:

考虑完备匹配中,\(X_i->Y_i,X_j->Y_j\),那么如果现在想要\(X_i->Y_j\),那么就要保证这样做之后从\(X_j\)出发存在增广路,否则就不能形成完备匹配.

那么这条增广路的终点显然应该是\(Y_i\),也即存在必定存在路径\(X_j->Y_i\).

我们考虑将之前给出的完备匹配的反向边连回去:即若存在匹配\(X_i->Y_i\),则连接有向边\(Y_i->X_i\).

那么我们考虑有路径\(X_j->Y_i->X_i->Y_j->X_j\),就是说形成了一个环,那么这些点必定在一个强连通分量中!

考虑与某个点\(X_i\)在一个强连通分量一些\(Y\)集合的点\(Y_k\),若存在边\(X_i->Y_k\),那么就是说\(Y_k\)要么是\(X_i\)原来的完备匹配,要么可以通过交换重新找到增广路得到完备匹配.

因此我们求一次SCC就解决了这道题目.

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>

#define N 2010

namespace Fio{
	inline int getc(){
#ifdef ONLINE_JUDGE
		static const int L=1<<15;
#else
		static const int L=1<<1;
#endif
		static char buf[L],*S=buf,*T=buf;
		if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
		return*S++;
	}
	inline bool digit(int c){return c>='0'&&c<='9';}
	template<typename T>inline void Get(T&x){
		int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
	}
	char buf[5000000],*o=buf;
	inline void putc(char c){*o++=c;}
	template<typename T>inline void print(T x){
		static int stk[100];int top=0;
		for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++='0'+stk[i];
	}
	inline void Final(){fwrite(buf,1,o-buf,stdout);}
}

int head[4010],next[2010*2010],end[2010*2010];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}

int G[2010][2010],dfn[4010],low[4010],tclock,stk[4010],bel[4010],cnt,top;bool instk[4010];

void dfs(int x){
	dfn[x]=low[x]=++tclock;stk[++top]=x,instk[x]=1;
	for(int j=head[x];j;j=next[j]){
		if(!dfn[end[j]])dfs(end[j]),low[x]=std::min(low[x],low[end[j]]);
		else if(instk[end[j]])low[x]=std::min(low[x],dfn[end[j]]);
	}
	if(dfn[x]==low[x]){
		++cnt;
		while(1){
			int i=stk[top--];instk[i]=0;
			bel[i]=cnt;
			if(i==x)break;
		}
	}
}

int seq[2010],id;

int main(){
	int n;Fio::Get(n);register int i,j;
	int t,x;for(i=1;i<=n;++i){Fio::Get(t);while(t--)Fio::Get(x),G[i][x]=1,addedge(i,n+x);}

	for(i=1;i<=n;++i)Fio::Get(x),addedge(n+x,i);

	for(i=1;i<=2*n;++i)if(!dfn[i])dfs(i);

	for(i=1;i<=n;++i){
		for(id=0,j=1;j<=n;++j)if(bel[i]==bel[n+j]&&G[i][j])seq[++id]=j;
		Fio::print(id);
		for(j=1;j<=id;++j)Fio::putc(' '),Fio::print(seq[j]);
		Fio::putc('\n');
		//printf("%d",id);
		//for(j=1;j<=id;++j)printf(" %d",seq[j]);
		//puts("");
	}

	Fio::Final();

#ifndef ONLINE_JUDGE
	system("pause");
#endif
	return 0;
}