9.26 2017-2018 ACM-ICPC, Asia Daejeon Regional Contest

E.How Many to Be Happy?(最小割)

正解是网络流，因为范围很小...
对每条边，要使加入所有边权小于它的边后图仍不能连通，而加入这条边后可以连通。
可以以这条边的两个端点作为源汇点，将所有边权小于它的边加入图中，跑最小割即为它的答案。
没写代码

G.Rectilinear Regions(模拟)

模拟。。就是判断一下直线相交的时候的情况。
直接判断加入一个点之前与之后两条直线的点的位置关系，再用一个变量临时存面积，区域结束时加入答案即可，但我写麻烦了。。（可以看这个）
结果是不仅要判的多，遇到递减序列需要将序列反过来变成递增（注意y会变化！！）。

//31ms	500KB
#include <cstdio>
#include <cctype>
#include <cassert>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=25005,INF=1<<28;

LL Ans[N];
bool vis[50005];
struct Node
{
	int x,y;
}down[N],up[N];

inline int read()
{
	int now=0,f=1;register char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}

int main()
{
	int m=read(),n=read(),yd=read();
	for(int i=1; i<=m; ++i) down[i].x=read(),down[i].y=read(),assert(!vis[down[i].x]),vis[down[i].x]=1;
	int yu=read();
	for(int i=1; i<=n; ++i) up[i].x=read(),up[i].y=read(),assert(!vis[up[i].x]),vis[up[i].x]=1;
	if((yd>down[1].y)^(yu>up[1].y)) return puts("0 0"),0;

	int tag=0;
	if(yd>down[1].y)//zbl
	{
		std::reverse(up+1,up+1+n), std::reverse(down+1,down+1+m);
		tag=1, up[n+1].y=yu, yu=up[1].y, down[m+1].y=yd, yd=down[1].y;
		for(int i=1; i<=n; ++i) up[i].x*=-1;
		for(int i=1; i<=m; ++i) down[i].x*=-1;
	}

	int cnt=0,las=INF; up[n+1].x=INF, down[m+1].x=INF;
	for(int i=1,j=1; i<=n||j<=m; )//i:up j:down
	{
		if(up[i].x<down[j].x)
		{
			int x=up[i].x,y=up[(i++)+tag].y;
			if(yu>yd)
				if(las<INF) Ans[cnt]+=1ll*(x-las)*(yu-yd), las=x;
				else ;
			else if(y>yd) las=x, ++cnt;
			yu=y;
		}
		else
		{
			int x=down[j].x,y=down[(j++)+tag].y;
			if(yu>yd)
				if(y<yu)
					if(las<INF) Ans[cnt]+=1ll*(x-las)*(yu-yd), las=x;
					else ;
				else Ans[cnt]+=1ll*(x-las)*(yu-yd), las=INF;
			yd=y;
		}
	}
	if(las<INF) --cnt;
	LL ans=0;
	for(int i=1; i<=cnt; ans+=Ans[i++]);
	printf("%d %lld
",cnt,ans);

	return 0;
}

H.Rock Paper Scissors(FFT) √

就是求字符串匹配的最大长度。
FFT，类似这道题，不过更简单。
分别枚举三个字符，每次将该字符在S和T中的位置设为1，两个多项式相乘即可得到这个字符在任意位置的匹配个数。

//202ms	10600KB
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=(1<<18)+5;
const double PI=acos(-1);

int rev[N],ans[N];
char S[N],T[N];
struct Complex
{
	double x,y;
	Complex(double x=0,double y=0):x(x),y(y) {}
	Complex operator +(const Complex &a) {return Complex(x+a.x, y+a.y);}
	Complex operator -(const Complex &a) {return Complex(x-a.x, y-a.y);}
	Complex operator *(const Complex &a) {return Complex(x*a.x-y*a.y, x*a.y+y*a.x);}
}A[N],B[N];

inline int read()
{
	int now=0,f=1; char c=gc();
	for(; !isdigit(c); c=='-'&&(f=-1),c=gc());
	for(; isdigit(c); now=now*10+c-48,c=gc());
	return now*f;
}
void FFT(Complex *a,int lim,int opt)
{
	for(int i=1; i<lim; ++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
	for(int i=2; i<=lim; i<<=1)
	{
		int mid=i>>1; Complex Wn(cos(PI/mid),opt*sin(PI/mid));
		for(int j=0; j<lim; j+=i)
		{
			Complex w(1,0),t;
			for(int k=j; k<j+mid; ++k,w=w*Wn)
				a[k+mid]=a[k]-(t=a[k+mid]*w), a[k]=a[k]+t;
		}
	}
	if(opt==-1) for(int i=0; i<lim; ++i) a[i].x/=lim;
}

int main()
{
	int n=read(),m=read();
	scanf("%s",S), scanf("%s",T);
	for(int i=0; i<m; ++i) T[i]=(T[i]=='R')?'S':T[i]=='P'?'R':'P';
	std::reverse(T,T+m);
	for(int i=m; i<n; ++i) T[i]='A';

	int lim=1,l=-1;
	while(lim<=n+m-2) lim<<=1,++l;
	for(int i=1; i<lim; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l);

	for(int i=0; i<n; ++i) A[i]=Complex(S[i]=='P'?1:0,0),B[i]=Complex(T[i]=='P'?1:0,0);
	for(int i=n; i<lim; ++i) A[i]=Complex(0,0),B[i]=Complex(0,0);
	FFT(A,lim,1), FFT(B,lim,1);
	for(int i=0; i<lim; ++i) A[i]=A[i]*B[i];
	FFT(A,lim,-1);
	for(int i=0; i<n; ++i) ans[i]+=int(A[m+i-1].x+0.5);

	for(int i=0; i<n; ++i) A[i]=Complex(S[i]=='R'?1:0,0),B[i]=Complex(T[i]=='R'?1:0,0);
	for(int i=n; i<lim; ++i) A[i]=Complex(0,0),B[i]=Complex(0,0);
	FFT(A,lim,1), FFT(B,lim,1);
	for(int i=0; i<lim; ++i) A[i]=A[i]*B[i];
	FFT(A,lim,-1);
	for(int i=0; i<n; ++i) ans[i]+=int(A[m+i-1].x+0.5);

	for(int i=0; i<n; ++i) A[i]=Complex(S[i]=='S'?1:0,0),B[i]=Complex(T[i]=='S'?1:0,0);
	for(int i=n; i<lim; ++i) A[i]=Complex(0,0),B[i]=Complex(0,0);
	FFT(A,lim,1), FFT(B,lim,1);
	for(int i=0; i<lim; ++i) A[i]=A[i]*B[i];
	FFT(A,lim,-1);
	for(int i=0; i<n; ++i) ans[i]+=int(A[m+i-1].x+0.5);

	int res=0;
	for(int i=0; i<n; ++i) res=std::max(res,ans[i]);
	printf("%d
",res);

	return 0;
}

I.Slot Machines(KMP) √

将串反过来，然后如果一个位置是一个循环节（前缀是该循环节）的结尾，就可以作为答案，暴力枚举该循环节长度更新答案即可。
复杂度应该是2n叭。

//62ms	7800KB
#include <bits/stdc++.h>
#define gc() getchar()
typedef long long LL;
const int N=1e6+5;

int f[N],A[N];

inline int read()
{
	int now=0,f=1; char c=gc();
	for(; !isdigit(c); c=='-'&&(f=-1),c=gc());
	for(; isdigit(c); now=now*10+c-48,c=gc());
	return now*f;
}

int main()
{
	int n=read();
	for(int i=1; i<=n; ++i) A[i]=read();
	std::reverse(A+1,A+1+n);
	for(int i=2,j=0; i<=n; ++i)
	{
		while(j&&A[i]!=A[j+1]) j=f[j];
		f[i]=A[i]==A[j+1]?++j:0;
	}
	int k=1e9,p=1e9;
	for(int i=1; i<=n; ++i)
		if(!(i%(i-f[i])))
		{
			int kk=n-i,pp=i-f[i];
			for(int j=i+1; j<i+i-f[i]; ++j)
				if(A[j]==A[j-i]) --kk;
				else break;
			if(kk+pp<k+p) k=kk, p=pp;
		}
	printf("%d %d
",k,p);

	return 0;
}

K.Untangling Chain(模拟) √

可以发现绕着起点不断转圈即可。
转圈的话需要记当前走过的，最左上、左下、右上、右下位置，下次走时越过极限位置即可。
边长最长（最差）的情况下是走一条直线，恰好需要走n步。

//30ms	100KB
#include <bits/stdc++.h>
#define gc() getchar()
typedef long long LL;
const int N=10005;

struct Opt
{
	int len,way;
}opt[N];
struct Point
{
	int x,y;
};

inline int read()
{
	int now=0,f=1; char c=gc();
	for(; !isdigit(c); c=='-'&&(f=-1),c=gc());
	for(; isdigit(c); now=now*10+c-48,c=gc());
	return now*f;
}

int main()
{
	int n=read();
	for(int i=1; i<=n; ++i) opt[i]=(Opt){read(),read()};
	int x=0,y=0,now=2;//now:朝向 0123:左上右下 
	Point ul=(Point){0,0},ur=ul,dl=ul,dr=ul;
	for(int i=1; i<=n; ++i)
	{
		switch(now)
		{
			case 0:
			{
				int d=std::abs(x-std::min(ul.x,dl.x))+1;
				x-=d, printf("%d ",d);
				break;
			}
			case 1:
			{
				int d=std::abs(std::max(ul.y,ur.y)-y)+1;
				y+=d, printf("%d ",d);
				break;
			}
			case 2:
			{
				int d=std::abs(std::max(ur.x,dr.x)-x)+1;
				x+=d, printf("%d ",d);
				break;
			}
			case 3:
			{
				int d=std::abs(y-std::min(dl.y,dr.y))+1;
				y-=d, printf("%d ",d);
				break;
			}
		}
		if(x<=ul.x && y>=ul.y) ul=(Point){x,y};
		if(x>=ur.x && y>=ur.y) ur=(Point){x,y};
		if(x<=dl.x && y<=dl.y) dl=(Point){x,y};
		if(x>=dr.x && y<=dr.y) dr=(Point){x,y};
		now=((now-opt[i].way)%4+4)%4;
	}
	

	return 0;
}