官方题解 | 巅峰赛#25题解

NoonMaple

2025-09-15 12:35:55

发布于：浙江

62阅读

0回复

0点赞

巅峰赛25题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	兔子之谜	普及-
T2	求职	普及/提高-
T3	午枫的LCA	普及+/提高
T4	太空传送	普及+/提高
T5	括号序列	普及+/提高
T6	博弈	提高+/省选-

T1 兔子之谜

题目大意

有 $n$ 只兔子，每只兔子有两个耳朵，每个耳朵会指向上下左右四个方向之一，每个方向代表四进制中的一个数。他们从左到右排成一排一共有 $2n$ 个耳朵，按顺序给出所有耳朵的方向，求耳朵隐含的四进制数转化为十进制数是多少。

题目思路

根据题意先模拟得到四进制数，然后再转换成十进制数即可。四进制转十进制可类比二进制转十进制。需要注意本题需要使用 long long 数据类型存答案。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    string s;cin>>s;

    long long res=0;
    for(int i=0;i<s.size();i++){
        res=res*4;
        if(s[i]=='R') res+=0;
        else if(s[i]=='D') res+=1;
        else if(s[i]=='L') res+=2;
        else if(s[i]=='U') res+=3;
    }
    cout<<res<<endl;
}

T2 求职

题目大意

有 $n$ 家公司和 $m$ 为求职者，每家公司有两个能力要求，每位求职者也有两个能力值，求职者只有都满足这两个要求才可以通过面试，求每位求职者可以通过多少家公司的面试。

题目思路

我们可以把两个能力值看成一个二维的坐标，那么对于某家公司的要求 $(a,b)$ ，能力值为 $(x,y)$ 的求职者只有同时满足 $x\geq a$ 且 $y\geq b$ 才可以通过面试，即 $(x,y)$ 在左上角为 $(a,b)$ 到右下角为 $(1000,1000)$ 的范围内即可满足条件。

所以我们不妨用二维差分+前缀和的思想来求出每位求职者可以通过面试的公司数量，对每家公司的要求 $(a,b)$ 点上的差分数组加一，最后求出前缀和， $O(1)$ 查询每位求职者的可通过面试数量。

时间复杂度 $O(10^6)$

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int a[N][N];

int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        a[x][y]++;
    }
    
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }

    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        cout<<a[x][y]<<endl;
    }
}

T3 午枫的LCA

题目大意

有两颗不同的树 $A$ 和树 $B$ ，每个点都有一个权值，现在两棵树都有 $m$ 个节点被标记且被标记的节点编号相同。询问这 $m$ 个节点，对于每个被标记节点 $x_i$ ，如果只有这个节点的标记删除，剩下 $m-1$ 个标记节点在树 $A$ 中的最近公共祖先的权值是否大于树 $B$ 中的最近公共祖先的权值。

题目思路

不难发现，若删除 $x_i$ 节点的标记，那么要求的 $LCA$ 是

$lca(x_1,x_2,\dots,x_{i-1},x_{i+1},\dots,x_{n-1},x_n)\\ =lca(lca(x_1,x_2,\dots,x_{i-1}),lca(x_{i+1},\dots,x_{n-1},x_n))$

所以我们可以预处理 $m$ 个标记节点的前缀 $LCA$ 和后缀 $LCA$ ，然后枚举删除标记的节点再求一遍 $LCA$ ，然后比较两棵树上 $LCA$ 的权值即可。

时间复杂度 $O((n+k)logn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e18+10;
const int N = 200010;

vector<int>v[2][N];
int q[N],a[N],b[N];
int pre[2][N],suf[2][N];
int fa[2][N],dep[2][N],sz[2][N],son[2][N],top[2][N];

void dfs1(int id,int u){
	sz[id][u]=1;
	dep[id][u]=dep[id][fa[id][u]]+1;

	for(auto x:v[id][u]){
		if(x==fa[id][u]) continue;
		fa[id][x]=u;
		dfs1(id,x);
		sz[id][u]+=sz[id][x];
		if(sz[id][x]>sz[id][son[id][u]]) son[id][u]=x;
	}
}
void dfs2(int id,int u,int h){
	top[id][u]=h;
	if(son[id][u]) dfs2(id,son[id][u],h);
	for(auto x:v[id][u]){
		if(x==fa[id][u] || x==son[id][u]) continue;
		dfs2(id,x,x);
	}
}

int lca(int id,int x,int y){
	while(top[id][x]!=top[id][y]){
		if(dep[id][top[id][x]]>dep[id][top[id][y]]) x=fa[id][top[id][x]];
		else y=fa[id][top[id][y]];
	}
	return dep[id][x]<dep[id][y] ? x : y;
}

int main(){
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=2;i<=n;i++){
        int x;cin>>x;
		v[0][i].push_back(x);
		v[0][x].push_back(i);
	}
	dfs1(0,1);
	dfs2(0,1,1);
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=2;i<=n;i++){
        int x;cin>>x;
		v[1][i].push_back(x);
		v[1][x].push_back(i);
	}
    for(int i=1;i<=k;i++) cin>>q[i];
	dfs1(1,1);
	dfs2(1,1,1);

	pre[0][1]=pre[1][1]=q[1];
	for(int i=2;i<=k;i++){
		pre[0][i]=lca(0,pre[0][i-1],q[i]);
		pre[1][i]=lca(1,pre[1][i-1],q[i]);
	}
	suf[0][k]=suf[1][k]=q[k];
	for(int i=k-1;i>=1;i--){
		suf[0][i]=lca(0,suf[0][i+1],q[i]);
		suf[1][i]=lca(1,suf[1][i+1],q[i]);
	}

	int res=0;
	for(int i=1;i<=k;i++){
		int la,lb;
		if(i==1){
			la=suf[0][i+1];
			lb=suf[1][i+1];
		}
		else if(i==k){
			la=pre[0][i-1];
			lb=pre[1][i-1];
		}
		else{
			la=lca(0,pre[0][i-1],suf[0][i+1]);
			lb=lca(1,pre[1][i-1],suf[1][i+1]);
		}
		
		if(a[la]>b[lb]) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

T4 太空传送

题目大意

两人从 $1$ 号太空站出发，第 $i$ 个太空站传送范围为 $(i,i+a_i]$ 且等概率传送，求两人使用相同传送次数到达 $n$ 号太空站的概率。

题目思路

通过概率DP思想求解。

设 $dp_{i,j}$ 表示传送了 $j$ 次到达 $i$ 号太空站的概率。

状态转移： $dp_{k,j+1}+=dp_{i,j}$ ，其中 $i<k\leq i+a_i$ 。如果直接这么转移时间复杂度是 $O(n^3)$ 。

但不难发现，转移实际上是一段连续的区间，所以我们可以通过差分前缀和优化。

最终答案为 $\sum_{i=1}^n f(n,i)^2$ 。时间复杂度 $O(n^2)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 8010;
const int INF = 1e18+10;
const int mod = 998244353;

int a[N];
long long Inv[N];
long long dp[N][N];

long long fpow(long long a,long long x){
    long long res=a%mod,ans=1;
    while(x){
        if(x&1) ans=ans*res%mod;
        res=res*res%mod;
        x >>= 1;
    }
    return ans;
}

long long inv(long long a){return fpow(a,mod-2);}

int main(){
    int n;cin>>n;
    for(int i=1;i<n;i++){
        cin>>a[i];
        Inv[a[i]]=inv(a[i]);
    }

    dp[0][1]=1;
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            int p=dp[i-1][j]*Inv[a[j]]%mod;
            
            dp[i][j+1]=(dp[i][j+1]+p)%mod;
            dp[i][j+a[j]+1]=(dp[i][j+a[j]+1]-p+mod)%mod;
        }
        for(int j=i+1;j<=n;j++){
            dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
        }
    }

    long long ans=0;
    for(int i=1;i<=n;i++) ans=(ans+dp[i][n]*dp[i][n]%mod)%mod;
    cout<<ans<<endl;
}

T5 括号序列

题目大意

求长度为 $n$ 的括号序列 $a$ 可能是多少个长度为 $m$ 的合法括号序列 $b$ 的子序列。

题目思路

读题时需要注意的一个点是括号序列 $a$ 不一定是合法的，但求的括号序列 $b$ 一定是要合法的。

我们可以将 ( 看成权值为 $1$ ，将 ) 看成权值为 $-1$ ，那么一个合法的括号序列需要满足以下条件：

序列和为 $0$ 。
最小前缀和为不小于 $0$ 。

我们考虑用动态规划解决这个问题。

设 $dp_{i,j,k}$ 表示括号序列 $b$ 中已经有 $i$ 个字符，括号序列 $a$ 的前 $j$ 个字符是括号序列 $b$ 的子序列，括号序列 $b$ 的权值前缀和为 $k$ 。

那么有以下四种转移：

$i+1$ 位置为 ( ，且 $j=n$ 或 $s_{j+1}\ne$ ( ，则 $dp_{i+1,j,k+1}+=dp_{i,j,k}$ 。
$i+1$ 位置为 ( ，且 $j<n$ 且 $s_{j+1}=$ ( ，则 $dp_{i+1,j+1,k+1}+=dp_{i,j,k}$ 。
$i+1$ 位置为 ) ，且 $j=n$ 或 $s_{j+1}\ne$ ) ，则 $dp_{i+1,j,k-1}+=dp_{i,j,k}$ 。
$i+1$ 位置为 ) ，且 $j<n$ 且 $s_{j+1}=$ ) ，则 $dp_{i+1,j+1,k-1}+=dp_{i,j,k}$ 。

时间复杂度 $O(nm^2)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 310;
const int mod = 1e9+7;

int dp[N][N][N];

void solve(){
    int n,m;cin>>n>>m;
    string s;cin>>s;s=' '+s;
    for(int i=0;i<=m+1;i++){
        for(int j=0;j<=n+1;j++){
            for(int k=0;k<=m+1;k++){
                dp[i][j][k]=0;
            }
        }
    }
    
    dp[0][0][0]=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<=min(i,n);j++){
            for(int k=0;k<=i;k++){
                if(!dp[i][j][k]) continue;
                
                if(k && (j==n || s[j+1]!=')')) (dp[i+1][j][k-1]+=dp[i][j][k])%=mod;
                if(k<m && (j==n || s[j+1]!='(')) (dp[i+1][j][k+1]+=dp[i][j][k])%=mod;
                if(k && j<n && s[j+1]==')') (dp[i+1][j+1][k-1]+=dp[i][j][k])%=mod;
                if(k<m && j<n && s[j+1]=='(') (dp[i+1][j+1][k+1]+=dp[i][j][k])%=mod;
            }
        }
    }
    cout<<dp[m][n][0]<<endl;
}

int main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}

T6 博弈

题目大意

有 $n$ 盘饼干，双方轮流拿取，每次拿完后可以选择是否将剩余饼干合并到别的盘中，若最终无法拿取的人则输掉游戏。给出 $q$ 次询问，求出询问区间 $[l,r]$ 中有多少子段先手必胜。

题目思路

先考虑固定盘数时双方如何博弈。

若只有 $1$ 盘饼干，先手必胜。

若有 $2$ 盘饼干，谁把某一盘的饼干取完了谁就输了，所以每一盘饼干有一块是不能取的。不妨令 $a_i=a_i-1$ ，这样问题就变成 $nim$ 游戏问题，也就是说 $XOR_{i=l}^{r}(a_i-1)=0$ 的话，先手必败，反之先手必胜。

若有 $3$ 盘饼干，先手可以从最多的那盘取出若干饼干，将剩下的局面变成盘数为 $2$ 且上文提到的异或和为 $0$ 的情况，那么先手必胜。

若有 $4$ 盘饼干，谁先将盘数 $-1$ 谁就输了，所以还是看异或和是否为 $0$ 。

以此类推，不难发现，当堆数为奇数时，先手必胜，否则令 $a_i=a_i-1$ ，看异或和是否为 $0$ 。

所以我们只需要前缀异或，离线查询，用莫队求解。

时间复杂度 $O(n\sqrt{n})$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = 2000010;

struct P{
    int l,r,id;
}qry[N];

int be[N],L[N],R[N];

bool cmp(P a,P b){
    if(be[a.l]!=be[b.l]) return be[a.l]<be[b.l];
    return be[a.r]<be[b.r];
}

int a[N],s[N];
int cnt[2][M];
long long sum;
void add(int x){
    sum+=cnt[x&1][s[x]];
    cnt[x&1][s[x]]++;
}
void del(int x){
    cnt[x&1][s[x]]--;
    sum-=cnt[x&1][s[x]];
}

long long ans[N];

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]^(a[i]-1);
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        cin>>qry[i].l>>qry[i].r;
        qry[i].l--;
        qry[i].id=i;
    }
    
    int block=sqrt(n);
    int tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1;
        R[i]=min(n,i*block);
        for(int j=L[i];j<=R[i];j++) be[j]=i;
    }
    sort(qry,qry+q,cmp);

    long long l=1,r=0;
    for(int i=0;i<q;i++){
        P Q=qry[i];
        while(l>Q.l) add(--l);
        while(r<Q.r) add(++r);
        while(l<Q.l) del(l++);
        while(r>Q.r) del(r--);

        long long res=(r-l+1)*(r-l)/2-sum;
        ans[Q.id]=res;
    }

    for(int i=0;i<q;i++) cout<<ans[i]<<endl;
}

有帮助，赞一个

去预览

0/2000

全部评论 4

༺ཌༀཉི༒白·羊༒༃ༀད༻
题库里T5不是蓝吗？@yaonainai

17小时前来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
@yaonainaiT3有一种更直观的解法，利用“多个点的LCA=其中DFS序最大的点和其中DFS序最小的点的LCA”这一结论就直接秒了

17小时前来自上海
1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  可以看下这个
  
  17小时前来自上海
  0
- yaonainai
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  ?
  
  17小时前来自浙江
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复yaonainai
  怎么了？
  
  17小时前来自上海
  0
AC是最好的
顾家豪老师，找到你啦！

17小时前来自福建
0
宋雨琦才是真神
老师你怎么连着出两次题？

19小时前来自天津
0
- i闪天天开心
  回复宋雨琦才是真神
  水平高的出题人连着出多少次题都可以，之前Yuilice不也是
  
  18小时前来自江苏
  0