题解 | ACGO巅峰赛#28

userId_undefined

𝓔𝓣𝓗𝓐𝓝

出道萌新时空双修者秩序白银

2025-12-08 20:05:24

发布于：江苏

145阅读
0回复
0点赞

ACGO巅峰赛#28

本题解包含三道竞赛题：

题目编号 题目标题 难度
T1 Alice的石子合并 普及/提高-
T3 Alice的神秘二叉树 普及/提高-
T4 Alice的棋盘游戏 普及/提高-

T1 Alice的石子合并

题目大意

求出合并 n−1n-1 堆石子的最小代价。

解题思路

对于每一堆石子，不管往右还是往左合并，都不会影响其他堆石子的属性 (ai,bi)(a_i,b_i)，如果往左合并，则代价为 aia_i，如果往右合并，则代价为 bib_i，所以每堆石子的最小代价为 min(ai,bi)min(a_i,b_i)。但第一堆石子和最后一堆石子只能往一个方向合并，所以第一堆的最小代价为 b1b_1，最后一堆的最小代价为 ana_n。一共 nn 堆石子，合并最小代价前 n−1n-1 堆石子，即去掉最小代价最大的一堆石子，其他 n−1n-1 堆石子的最小代价和即为最小总代价。

参考代码

#include<iostream>
#define ll long long
using namespace std;
const ll N=200005;
ll n,a[N],b[N],ans,tmp,mx;
int main(){
	cin>>n;
	for(ll i=1;i<=n;++i)cin>>a[i];
	for(ll i=1;i<=n;++i)cin>>b[i];
	for(ll i=1;i<=n;++i){
		if(i==1)tmp=b[i];
		else if(i==n)tmp=a[i];
		else tmp=min(a[i],b[i]);
		ans+=tmp;
		mx=max(mx,tmp);
	}
	cout<<ans-mx;
	return 0;
}

T3 Alice的神秘二叉树

题目大意

给出一棵二叉树的中序遍历和层序遍历，求出先序遍历。

解题思路

假设 inxin_x 为根节点，则先序遍历的结果为 inx+[in1,in2,...,inx−2,inx−1]in_x+[in_1,in_2,...,in_{x-2},in_{x-1}] 的先序遍历 +[inx+1,inx+2,...,inn−1,inn]+[in_{x+1},in_{x+2},...,in_{n-1},in_n] 的先序遍历。

针对 [in1,in2,...,inx−2,inx−1][in_1,in_2,...,in_{x-2},in_{x-1}]，假设 inkin_k 为根节点，先序遍历的结果为 ink+[in1,in2,...,ink−2,ink−1]in_k+[in_1,in_2,...,in_{k-2},in_{k-1}] 的先序遍历 +[ink+1,ink+2,...,inx−1,inx]+[in_{k+1},in_{k+2},...,in_{x-1},in_x] 的先序遍历。

针对 [inx+1,inx+2,...,inn−1,inn][in_{x+1},in_{x+2},...,in_{n-1},in_n]，假设 inqin_q 为根节点，先序遍历的结果为 inq+[inx+1,inx+2,...,inq−2,inq−1]in_q+[in_{x+1},in_{x+2},...,in_{q-2},in_{q-1}] 的先序遍历 +[inq+1,inq+2,...,inn−1,inn]+[in_{q+1},in_{q+2},...,in_{n-1},in_n] 的先序遍历。

所以，只要知道某个区间 [inl,inl+1,...,inr−1,inr][in_l,in_{l+1},...,in_{r-1},in_{r}] 的根节点，就可以递归求出这个区间的先序遍历。

因为层序遍历的顺序为从根到叶、自左到右，所以区间 [inl,inl+1,...,inr−1,inr][in_l,in_{l+1},...,in_{r-1},in_{r}] 的根节点就是在 levellevel 序列中出现最早的键。

idxidx 记录每个键在 levellevel 序列中的下标，每次查询的时间复杂度为 O(log n)O(log\ n)。

参考代码

#include<iostream>
#include<map>
#define ll long long
using namespace std;
const ll N=200005;
ll n,in[N],level[N],mn;
map<ll,ll> idx; 
void work(ll l,ll r){
	if(l>r)return;
	mn=N;
	ll w;
	for(ll i=l;i<=r;++i){
		if(idx[in[i]]<mn){
			mn=idx[in[i]];
			w=i;
		}
	}
	cout<<in[w]<<' ';
	work(l,w-1);
	work(w+1,r);
	return;
}
int main(){
    cin>>n;
	for(ll i=1;i<=n;++i)cin>>in[i];
	for(ll i=1;i<=n;++i){
		cin>>level[i];
		idx[level[i]]=i;
	}
	work(1,n);
	return 0;
}

T4 Alice的棋盘游戏

题目大意

判断先手是否必胜，并输出首回合必胜的走法。

解题思路

为了方便讲解，假设 isw(i,j,k)isw(i,j,k) 指在 (i,j)(i,j) 位置，以前走过 kk 步时，先手是否能赢。11 表示能，00 表示不能。

求 isw(x,y,z)isw(x,y,z)：

  • 如果 2∣k2\mid k，即下一步是先手走，那么只要 isw(x+1,y,z+1),isw(x−1,y,z+1),isw(x,y−1,z+1),isw(x,y+1,z+1)isw(x+1,y,z+1),isw(x-1,y,z+1),isw(x,y-1,z+1),isw(x,y+1,z+1) 其中一个为 11，就可以判定 isw(x,y,z)=1isw(x,y,z)=1，因为先手走到这一步时可以选择能赢的走法，如果一个能赢的走法都没有，即 isw(x+1,y,z+1)=0,isw(x−1,y,z+1)=0,isw(x,y−1,z+1)=0,isw(x,y+1,z+1)=0isw(x+1,y,z+1)=0,isw(x-1,y,z+1)=0,isw(x,y-1,z+1)=0,isw(x,y+1,z+1)=0，不管怎么走都是自己输，那么 isw(x,y,z)=0isw(x,y,z)=0。
  • 如果 2∤k2\nmid k，即下一步是后手走，那么只要 isw(x+1,y,z+1),isw(x−1,y,z+1),isw(x,y−1,z+1),isw(x,y+1,z+1)isw(x+1,y,z+1),isw(x-1,y,z+1),isw(x,y-1,z+1),isw(x,y+1,z+1) 其中一个为 00，就可以判定 isw(x,y,z)=0isw(x,y,z)=0，因为后手走到这一步时可以选择先手输的走法，如果一个先手输的走法都没有，即 isw(x+1,y,z+1)=1,isw(x−1,y,z+1)=1,isw(x,y−1,z+1)=1,isw(x,y+1,z+1)=1isw(x+1,y,z+1)=1,isw(x-1,y,z+1)=1,isw(x,y-1,z+1)=1,isw(x,y+1,z+1)=1，不管怎么走都是先手赢，那么 isw(x,y,z)=0isw(x,y,z)=0。

求出 isw(sx,sy,0)isw(sx,sy,0) 即可。

参考代码

#include<iostream>
#define ll long long
using namespace std;
const ll N=25;
ll n,m,sx,sy,d[4][2]={0,1,1,0,0,-1,-1,0},tx,ty;
char a[N][N];
bool vis[N][N],can;
bool in(ll x,ll y){return x>=1&&x<=n&&y>=1&&y<=m;}
bool check(ll x,ll y,ll step){
	vis[x][y]=true;
	ll nx,ny;
	bool flag;
	if(step%2){
		for(ll i=0;i<4;++i){
			nx=x+d[i][0],ny=y+d[i][1];
			if(in(nx,ny)&&a[nx][ny]=='.'&&vis[nx][ny]==false){
				flag=check(nx,ny,step+1);
				if(!flag)return false;
			}
		}
	}
	else{
		for(ll i=0;i<4;++i){
			nx=x+d[i][0],ny=y+d[i][1];
			if(in(nx,ny)&&a[nx][ny]=='.'&&vis[nx][ny]==false){
				flag=check(nx,ny,step+1);
				if(flag){
				    if(!step)tx=nx,ty=ny;
				    return true;
			    }
			}
		}
	}
	vis[x][y]=false;
	return step%2;
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;++i){
		for(ll j=1;j<=m;++j){
			cin>>a[i][j];
			if(a[i][j]=='S')sx=i,sy=j;
		}
	}
	can=check(sx,sy,0);
	if(can)cout<<"WIN"<<endl<<sx<<' '<<sy<<' '<<tx<<' '<<ty<<endl;
	else cout<<"LOSE"<<endl;
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 6

热门讨论