CODE FESTIVAL 2017 qual C 题解

\(A\)

咕咕

const int N=15;

char s[N];int n;

int main(){

	scanf("%s",s+1),n=strlen(s+1);

	fp(i,1,n-1)if(s[i]=='A'&&s[i+1]=='C')return puts("Yes"),0;

	puts("No");

	return 0;

}

\(B\)

咕咕

const int N=15;

int a[N],n,res,ret;

int main(){

	scanf("%d",&n),res=ret=1;

	fp(i,1,n)scanf("%d",&a[i]),res*=3,ret*=(a[i]&1?1:2);

	printf("%d\n",res-ret);

	return 0;

}

\(C\)

首先去掉所有\(x\)之后得是一个回文，然后把不是\(x\)字母之间的\(x\)填到对称就是了

//quming

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

const int N=1e5+5;

char s[N];int st[N],n,res,top;

int main(){

	scanf("%s",s+1),n=strlen(s+1);

	fp(i,1,n)if(s[i]!='x')st[++top]=i;

	for(R int i=1,j=top;i<j;++i,--j)

		if(s[st[i]]!=s[st[j]])return puts("-1"),0;

	st[top+1]=n+1;

	for(R int i=0,j=top+1;i<j-1;++i,--j)

		res+=abs((st[i+1]-st[i]-1)-(st[j]-st[j-1]-1));

	printf("%d\n",res);

	return 0;

}

\(D\)

把前缀每个字母的奇偶性压位，记\(f_i\)表示取完前\(i\)个字母的最小步数，那么一个状态\(s\)只可能从之前某一个最多相差一个\(1\)的位置转移过来，那么记录一下每个\(s\)对应的最小步数的位置即可

//quming

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

const int N=2e5+5,L=(1<<26)+5;

char s[N];int a[N],f[N],pos[L],n;

int main(){

	scanf("%s",s+1),n=strlen(s+1);

	fp(i,1,n)a[i]=a[i-1]^(1<<(s[i]-'a'));

	memset(pos,-1,sizeof(pos));

	pos[0]=0;

	fp(i,1,n){

		f[i]=233333;

		fp(j,0,25)if(pos[a[i]^(1<<j)]!=-1)cmin(f[i],f[pos[a[i]^(1<<j)]]+1);

		if(pos[a[i]]!=-1)cmin(f[i],f[pos[a[i]]]+1);

		if(pos[a[i]]==-1||f[i]<f[pos[a[i]]])pos[a[i]]=i;

	}

	printf("%d\n",f[n]);

	return 0;

}

\(E\)

看不懂……咕了……

\(F\)

首先我们发现，如果已经确定了三个人吃的寿司的序列，那么合法的\(c\)的个数只与\(n\)有关，与它们具体吃的是什么无关，那么可以求出\(C\)吃的序列个数最后乘上这个系数

考虑\(dp\)，\(C\)吃的什么先不确定，记为\(?\)，\(f[i][j][k]\)表示\(A\)吃到第\(i\)个位置，\(B\)吃到第\(j\)个位置，\(C\)有\(k\)个\(?\)的方案数，具体过程看代码

然后再算出\(g[i][j]\)表示前\(i\)个位置放了\(j\)个不是\(C\)吃的数的方案数

//quming

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

const int P=1e9+7;

inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

int ksm(R int x,R int y){

	R int res=1;

	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;

	return res;

}

const int N=405;

int f[N][N][N],g[N][N],a[N],b[N],as[N],bs[N];

int n,m;

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d",&n),m=n/3;

	fp(i,1,n)scanf("%d",&a[i]),as[a[i]]=i;

	fp(i,1,n)scanf("%d",&b[i]),bs[b[i]]=i;

	f[1][1][0]=1;

	fp(i,1,n)fp(j,1,n)fp(k,0,m)if(f[i][j][k]){

		R int ret=f[i][j][k];

		if(bs[a[i]]<=j||as[b[j]]<=i){

			if(a[i]==b[j]){

				if(k)upd(f[i+1][j+1][k-1],mul(ret,k));

				continue;

			}

			upd((bs[a[i]]<=j?f[i+1][j][k]:f[i][j+1][k]),ret);

			continue;

		}

		upd(f[i+1][j+1][k+1],ret);

		if(k){

			upd(f[i+1][j][k-1],mul(ret,k));

			upd(f[i][j+1][k-1],mul(ret,k));

			if(k>1)upd(f[i+1][j+1][k-2],P-mul(ret,k*(k-1)));

		}

	}

	R int res=0;

	fp(i,m+1,n+1)upd(res,add(f[i][n+1][0],f[n+1][i][0]));

	upd(res,P-f[n+1][n+1][0]);

	g[0][0]=1;

	fp(i,0,n-1)fp(j,0,i)if(g[i][j]){

		if(i-j<m)upd(g[i+1][j],g[i][j]);

		if(j<m*2&&(i-j)*2>j)upd(g[i+1][j+1],mul(g[i][j],(i-j)*2-j));

	}

	res=mul(res,g[n][m<<1]);

	printf("%d\n",res);

	return 0;

}

巴特西