AtCoder Regular Contest 081 题解

成功AK啦

D - Coloring Dominoes：

显然牌只能这么放：
$aa \ \ \ \ \ c$aa     c

$bb \ \ \ \ \ c$bb     c
直接dp，讨论转移。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const LL mod=1e9+7;
LL n,s,p,ans;
char s1[55],s2[55];
int main()
{
	scanf("%lld",&n);getchar();
	scanf("%s%s",s1+1,s2+1);
	if(n==1) return puts("3"),0;
	if(s1[1]==s2[1]) p=2,ans=3,s=1;
	else p=3,ans=6,s=2;
	while(p<=n)
	{
		LL t;
		if(s1[p]==s2[p]) p++,t=1;
		else p+=2,t=2;
		if(s==1) (ans*=2)%=mod;
		else if(t!=1) (ans*=3)%=mod;
		s=t;
	}
	printf("%lld",ans);
}

E - Don’t Be a Subsequence：

听说可以dp，然而直接序列自动机就无脑过了
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
struct Xam{
	int a[26],par;
}xam[200010];int last[26];
char s[200010];
void addxam()
{
	int len=strlen(s+1);
	for(int i=0;i<26;i++) last[i]=1;
	for(int i=1;i<=len;i++)
	{
		int p=i+1,c=s[i]-'a';
		for(int j=0;j<26;j++)
			for(int k=last[j];k&&!xam[k].a[c];k=xam[k].par) xam[k].a[c]=p;
		xam[p].par=last[c];last[c]=p;
	}
}
int son[200010],len[200010];
void dfs(int x)
{
	if(son[x]!=-1) return;
	if(!x) {son[x]=0,len[x]=0;return;}
	for(int i=0;i<26;i++)
	{
		int y=xam[x].a[i];
		dfs(y);
		if(son[x]==-1||len[y]<len[xam[x].a[son[x]]]) son[x]=i,len[x]=len[y]+1;
	}
}
void print(int x)
{
	if(!x) return;
	printf("%c",son[x]+'a');
	print(xam[x].a[son[x]]);
}
int main()
{
	scanf("%s",s+1);
	addxam();
	memset(son,-1,sizeof(son));
	dfs(1);print(1);
}

F - Flip and Rectangles：

观察下什么矩阵可以经过一番操作变为全黑，可以发现它们满足：
即你可以通过画若干条线将矩形分成若*分，且子矩形内部颜色相同，相邻矩形颜色不同。
那么大致上按bzoj 1057那样，悬线法即可。
具体细节见代码
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,h[2010][2010],l[2010][2010],r[2010][2010],ans;
char s[2010][2010];
int main()
{
	scanf("%d %d",&n,&m);getchar();
	ans=max(n,m);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(j==1||i==1) h[i][j]=1;
			else h[i][j]=((s[i][j]==s[i][j-1])==(s[i-1][j]==s[i-1][j-1]))?h[i-1][j]:i;
		}
	for(int i=1;i<=n;i++)
	{
		if(i==1) for(int j=1;j<=m;j++) l[i][j]=1,r[i][j]=m;
		else
		{
			l[i][1]=1;for(int j=2  ;j<=m;j++) l[i][j]=(s[i][j]==s[i-1][j])==(s[i][j-1]==s[i-1][j-1])?l[i][j-1]:j;
			r[i][m]=m;for(int j=m-1;j>=1;j--) r[i][j]=(s[i][j]==s[i-1][j])==(s[i][j+1]==s[i-1][j+1])?r[i][j+1]:j;
		}
		for(int j=1;j<=m;j++)
		{
			if(h[i][j]==i) l[i][j]=1,r[i][j]=m;
			else l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]);
			int N=i-h[i][j]+1,M=r[i][j]-l[i][j]+1;
			ans=max(ans,N*M);
		}
	}
	printf("%d",ans);
}