CODE FESTIVAL 2017 Final题解

\(A\)

咕咕

const int N=55;

const char to[]={"AKIHABARA"};

char s[N];int n;

int main(){

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

	R int i=0,j=0;

	for(;i<n;){

		while(j<9&&s[i]!=to[j]&&to[j]=='A')++j;

		if(j>=9||s[i]!=to[j])return puts("NO"),0;

		++i,++j;

	}

	while(j<9&&to[j]=='A')++j;

	puts(j==9?"YES":"NO");

	return 0;

}

\(B\)

为了不回文，必须得\(ABCABC...\)这样放，那么三个字母出现次数之差不能超过\(1\)

const int N=1e5+5;

char s[N];int cnt[3],n,mx;

int main(){

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

	fp(i,1,n)++cnt[s[i]-'a'];

	mx=max(cnt[0],max(cnt[1],cnt[2]));

	if(!cnt[0]||!cnt[1]||!cnt[2])return puts(mx<=1?"YES":"NO"),0;

	fp(i,0,2)if(cnt[i]<mx-1)return puts("NO"),0;

	puts("YES");

	return 0;

}

\(C\)

首先每个\(d\)的出现次数不能超过\(2\)否则答案必定为\(0\)，那么接下来记录一下每个\(d\)的出现次数然后爆搜每个\(d\)是位于\(d\)还是\(24-d\)就行了

//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=35,inf=0x3f3f3f3f;

int cnt[N],n,res;

inline int min(R int x,R int y){return x<y?x:y;}

inline int abs(R int x){return x<0?-x:x;}

void dfs(int pos,int s,int ret){

	if(ret<=res)return;

	if(pos==12){

		if(cnt[12]){

			fp(i,1,23)if(s>>i&1)cmin(ret,abs(12-i));

			cmin(ret,12);

		}

		cmax(res,ret);

		return;

	}

	if(!cnt[pos])return dfs(pos+1,s,ret),void();

	cmin(ret,pos);

	if(cnt[pos]==2){

		fp(i,1,23)if(s>>i&1)cmin(ret,abs(pos-i)),cmin(ret,abs(24-pos-i));

		cmin(ret,abs(pos-(24-pos)));

		dfs(pos+1,s|(1<<pos)|(1<<(24-pos)),ret);

		return;

	}

	R int tmp=ret;

	fp(i,1,23)if(s>>i&1)cmin(tmp,abs(pos-i));

	dfs(pos+1,s|(1<<pos),tmp);

	tmp=ret;

	fp(i,1,23)if(s>>i&1)cmin(tmp,abs(24-pos-i));

	dfs(pos+1,s|(1<<(24-pos)),tmp);

}

int main(){

	scanf("%d",&n);

	for(R int i=1,x;i<=n;++i)scanf("%d",&x),++cnt[x];

	if(cnt[0]||cnt[12]>1)return puts("0"),0;

	fp(i,1,11)if(cnt[i]>2)return puts("0"),0;

	dfs(1,0,inf);

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

	return 0;

}

\(D\)

首先选的顺序肯定是按\(h_i+p_i\)排序之后再选最优的（证明的话，可以考虑一个合法的选的序列，对于每一个\(i\)必须满足\(\sum_{j\leq i} h\leq h_i+p_i\)，因为前缀和递增所以\(h_i+p_i\)也必须非降才是），然后直接\(dp\)就是了

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

typedef long long ll;

const int N=5005;const ll inf=0x3f3f3f3f3f3f3f3f;

int a[N],b[N],c[N],id[N],n;ll mn[N];

inline bool cmp(const int &x,const int &y){return c[x]==c[y]?b[x]<b[y]:c[x]<c[y];}

int main(){

	scanf("%d",&n);

	fp(i,1,n)scanf("%d%d",&a[i],&b[i]),c[i]=a[i]+b[i],id[i]=i;

	sort(id+1,id+1+n,cmp);

	memset(mn,0x3f,sizeof(mn));

	mn[0]=0;

	fp(i,1,n){

		R int t=n-1;

		while(mn[t]==inf)--t;

		fd(j,t,0)if(mn[j]<=a[id[i]])cmin(mn[j+1],mn[j]+b[id[i]]);

	}

	fd(i,n,0)if(mn[i]!=inf)return printf("%d\n",i),0;

	return 0;

}

\(E\)

差分之后等价于每次\(l_i\)位置\(+1\)，\(r_i+1\)位置\(-1\)，而此时回文的条件就是对于每个\(i\)有\(a_i+a_{n-2-i}\)是\(26\)的倍数（最中间位置除外），因为每个连通块的权值之和不变，所以要满足每个连通块权值之和为\(26\)的倍数（包含最中间位置那个连通块除外）

//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 fa[N],b[N],sum[N],vis[N],n,m;

inline int val(R int x){return x<0?x+26:x;}

inline int find(R int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int main(){

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

	fp(i,1,n+1)s[i]-='a',fa[i]=i;

	s[n+1]=0;

	scanf("%d",&m);

	for(R int i=1,l,r;i<=m;++i)scanf("%d%d",&l,&r),fa[find(r+1)]=find(l);

	fp(i,1,n+1)b[i]=val(s[i]-s[i-1]);

	fp(i,1,(n+1)>>1)fa[find(n+2-i)]=find(i);

	fp(i,1,n+1)sum[find(i)]+=b[i];

	if((n+1)&1)vis[find((n+2)>>1)]=1;

	fp(i,1,n+1)if(i==find(i)&&sum[i]%26)

		if(!vis[i])return puts("NO"),0;

	puts("YES");

	return 0;

}

\(F\)

手玩了一下\(k\)较小的情况去考虑对应的\(n\)……

首先对于前\(k\)行，每行都令\(1\)开头，剩下的数依次从\(2\)取到\(n\)，这样的话总共需要\(n=k(k-1)+1\)个数，且第\(i\)行的第\(2\)到\(k\)个数依次是\((i-1)(k-1)+2\)到\(i(k-1)+1\)，后面为了方便起见用\(st[i][j]\)表示第\(i\)行第\(j\)列的数

对于接下来的每\(k\)行，依次令\(st[1][j]\)开头，然后在\(2\)到\(k\)行中各取一个数，共取\(k-1\)组，要保证选出的\(k-1\)组中任意两组没有重复的数，那么只要以\(j-1\)为步长，以第\(2\)行中的第\(2\)到第\(k\)个数开头，就能保证取完下面所有数了

然而对于两组开头不一样的行，直接这样取可能会有大于一个重复的情况，注意到一种步长会导致这种情况当且仅当步长为\(k-1\)的因子，那么只要保证\(k-1\)是个质数就行了，取\(k=38\)即可

具体细节可以看代码理解

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

vector<int>st[N];int n,k,tot;

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

int main(){

	k=38,n=k*(k-1)+1,tot=1;

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

	fp(i,1,k){

		printf("%d ",1);

		st[i].resize(k-1);

		fp(j,0,k-2)st[i][j]=++tot;

		fp(j,0,k-2)printf("%d ",st[i][j]);

		puts("");

	}

	fp(i,0,k-2){

		fp(s,0,k-2){

			R int p=s;

			printf("%d ",st[1][i]);

			fp(j,2,k)printf("%d ",st[j][p]),p=add(p,i);

			puts("");

		}

	}

	return 0;

}

\(G\)

发现要让剩下的石子最少，每次一定是取从左往右第一个可以操作的操作

记\(f_i\)表示\(i\)到\(n\)的数中总的操作次数，如果\(a_i\leq i\)，那么\(f_i=f_{i+1}+(f_{i+1}+a_i)/i\)（下取整），最终的分数就是\(\sum a_i-f_1\)

前面总和很好求，所以我们转化为来求\(\sum f_1\)

注意到上面的转移之和\(f_{i+1}\)的值有关，且\(f_{i}\)是\(O(n^2)\)级别的，那么我们记\(s_{i,j}\)表示对于\(i\)，\(f_i=j\)的方案数，然后枚举当前数是什么，转移即可

复杂度\(O(n^4)\)

//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=105,M=N*N;

int f[N][M],dv[N][M],n,p,s,res,sum;

int main(){

	scanf("%d%d",&n,&p);

	f[n][0]=1;

	fp(i,1,n)fp(j,1,n*n/i)dv[i][i*j]=j;

	fp(i,1,n)fp(j,1,n*n)if(!dv[i][j])dv[i][j]=dv[i][j-1];

	fd(i,n,1){

		if(p>i)fp(j,0,s)f[i-1][j]=mul(f[i][j],p-i);

		R int t=s;

		fp(j,0,s)if(f[i][j])fp(k,0,min(p,i)){

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

			cmax(t,j+dv[i][j+k]);

		}

		s=t;

	}

	fp(i,0,s)upd(res,mul(i,f[0][i]));

	sum=mul(n*p*(p+1)>>1,ksm(p+1,n-1));

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

	return 0;

}

\(H\)

首先发现一格如果左上，右上，左下，右下四个方位中的一个没有冰山，那么他最终肯定会消失

还有另一种方法是把一个大矩形分成四块，并把左上和右下或右上和左下的冰山全部消掉，然后剩下的两个部分互不影响了

那么设\(f[lx][rx][ly][]ry]\)表示删到只剩矩形\([lx,ly,rx,ry]\)中的元素时，最少要删多少，然后枚举在哪里分割矩形转移即可

具体可以看题解的图理解，复杂度\(O(n^6)\)

记忆化搜索+剪枝似乎比直接dp快到不知道哪里去了

//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=45,inf=0x3f3f3f3f;

char a[N][N];int f[N][N][N][N],s[N][N];

int px,py,n,m,res;

inline int qs(R int x,R int y,R int xx,R int yy){

	return s[xx][yy]+s[x-1][y-1]-s[xx][y-1]-s[x-1][yy];

}

inline int min(R int x,R int y){return x<y?x:y;}

inline int get(R int lx,R int ly,R int rx,R int ry){

	return min(min(qs(lx,ly,px,py),qs(px,py,rx,ry)),

			min(qs(lx,py,px,ry),qs(px,ly,rx,py)));

}

int main(){

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

	scanf("%d%d",&n,&m);

	fp(i,1,n)scanf("%s",a[i]+1);

	fp(i,1,n)fp(j,1,m){

		if(a[i][j]=='P')px=i,py=j;

		s[i][j]=s[i-1][j]+s[i][j-1]+(a[i][j]=='#')-s[i-1][j-1];

	}

	memset(f,0x3f,sizeof(f));

	f[1][1][n][m]=0,res=inf;

	fp(lx,1,n)fp(ly,1,m)fd(rx,n,lx)fd(ry,m,ly)

		if(f[lx][ly][rx][ry]!=inf){

			R int ret=f[lx][ly][rx][ry];

			if(px>=lx&&px<=rx&&py>=ly&&py<=ry)cmin(res,ret+get(lx,ly,rx,ry));

				else cmin(res,ret);

			ret+=qs(lx,ly,rx,ry);

			fp(x,lx,rx+1)fp(y,ly,ry+1)

				if(!((x==lx||x==rx+1)&&(y==ly&&y==ry+1))){

					R int val=qs(lx,ly,x-1,y-1)+qs(x,y,rx,ry);

					if(x>lx&&y>ly&&!(px>=x&&px<=rx&&py>=y&&py<=ry))

						cmin(f[lx][ly][x-1][y-1],ret-val);

					if(x<=rx&&y<=ry&&!(px<x&&px>=lx&&py<y&&py>=ly))

						cmin(f[x][y][rx][ry],ret-val);

					val=qs(lx,y,x-1,ry)+qs(x,ly,rx,y-1);

					if(x>lx&&y<=ry&&!(px>=x&&px<=rx&&py<y&&py>=ly))

						cmin(f[lx][y][x-1][ry],ret-val);

					if(x<=rx&&y>ly&&!(px<x&&px>=lx&&py>=y&&py<=ry))

						cmin(f[x][ly][rx][y-1],ret-val);

				}

		}

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

	return 0;

}

\(I\)

方便起见把人和排名都设为\(0\)到\(2^n-1\)

记\(a_i\)表示排名为\(i\)的人，则对于任意\(k\)，有\(a_i\leq a_{i|2^k}(2^k \notin i)\)

这个考虑归纳证明，不妨令\(i=2p\)，则排名为\(i\)的人就是左边排名为\(p\)的人和右边排名为\(p\)的人里较小的那个，而排名为\(i|2^k\)的是左边排名为\(p+2^{k-1}\)和右边排名为\(p+2^{k-1}\)的，根据归纳证明不管左边右边都有\(a_p\leq a_{p|2^{k-1}}\)，所以有\(a_i\leq a_{i|2^k}\)成立

然后我们对于每个\(i\)把\(a_i\)的取值范围求出来，之后扫描线加贪心求出每个\(a_i\)的值就好了，最后原序列中第\(i\)位的值就是将\(i\)二进制翻转之后的\(a\)（类似于\(FFT\)的蝴蝶操作）

//quming

#include<bits/stdc++.h>

#define R register

#define pb emplace_back

#define fi first

#define se second

#define gg return puts("NO"),0;

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

typedef pair<int,int> pi;

const int N=25,L=(1<<18)+5;

int low[L],hig[L],r[L],val[L];

vector<pi>vc[L];int n,lim;

priority_queue<pi,vector<pi>,greater<pi> >q;

int main(){

	scanf("%d",&n),lim=(1<<n);

	fp(i,0,lim-1){

		scanf("%d",&val[i]),--val[i];

		r[i]=(r[i>>1]>>1)|((i&1)<<(n-1));

	}

	fd(i,lim-1,0){

		hig[i]=(~val[i]?val[i]:lim-1);

		fp(k,0,n-1)if(i>>k&1^1)cmin(hig[i],hig[i|(1<<k)]);

	}

	fp(i,0,lim-1){

		if(~val[i])low[i]=val[i];

		fp(k,0,n-1)if(i>>k&1)cmax(low[i],low[i^(1<<k)]);

	}

	fp(i,0,lim-1){

		if(low[i]>hig[i])gg;

		vc[low[i]].pb(pi(hig[i],i));

	}

	fp(i,0,lim-1){

		for(auto v:vc[i])q.push(v);

		if(q.empty()||q.top().fi<i)gg;

		val[q.top().se]=i,q.pop();

	}

	puts("YES");

	fp(i,0,lim-1)printf("%d ",val[r[i]]+1);

	return 0;

}

\(J\)

据说可以直接点分暴艹……

就是对于当前点分中心，找到连上的边边权最小的那个点，再把当前连通块中所有点和那个点连边，最后跑一遍\(kruskal\)即可

//quming

#include<bits/stdc++.h>

#define R register

#define pb emplace_back

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

typedef long long ll;

const int N=2e5+5;

struct node{

	int u,v;ll w;

	inline node(R int uu,R int vv,R ll ww):u(uu),v(vv),w(ww){}

	inline bool operator <(const node &b)const{return w<b.w;}

};vector<node>E;vector<int>st;

struct eg{int v,nx,w;}e[N<<1];int head[N],tot;

inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;}

ll dis[N];int sz[N],vis[N],mx[N],fa[N],a[N];

int n,rt,size;

inline int find(R int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void findrt(int u,int fa){

	sz[u]=1,mx[u]=0;

	go(u)if(!vis[v]&&v!=fa){

		findrt(v,u);

		sz[u]+=sz[v],cmax(mx[u],sz[v]);

	}

	cmax(mx[u],size-sz[u]);

	if(mx[u]<mx[rt])rt=u;

}

void get(int u,int fa){

	st.pb(u);

	go(u)if(!vis[v]&&v!=fa)dis[v]=dis[u]+e[i].w,get(v,u);

}

void solve(int u){

	vis[u]=1,dis[u]=0,st.clear(),get(u,0);

	R int p=0;R ll mn=1e18;

	for(auto v:st)if(cmin(mn,dis[v]+=a[v]))p=v;

	for(auto v:st)E.pb(node(p,v,dis[p]+dis[v]));

	R int s=size;

	go(u)if(!vis[v]){

		rt=0,size=(sz[v]<=sz[u]?sz[v]:s-sz[u]);

		findrt(v,0),solve(rt);

	}

}

int main(){

	scanf("%d",&n),mx[0]=n+1;

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

	for(R int i=1,u,v,w;i<n;++i){

		scanf("%d%d%d",&u,&v,&w);

		add(u,v,w),add(v,u,w);

	}

	rt=0,size=n,findrt(1,0),solve(rt);

	sort(E.begin(),E.end());

	fp(i,1,n)fa[i]=i;

	R ll res=0;

	for(auto e:E)if(find(e.u)!=find(e.v))res+=e.w,fa[find(e.u)]=find(e.v);

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

	return 0;

}

巴特西