官方题解 | 第三届飞翔杯普及组
2025-11-25 16:20:45
发布于：浙江
巅峰赛25题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度
T1 兔子之谜 普及-
T2 求职 普及/提高-
T3 午枫的LCA 普及+/提高
T4 太空传送 普及+/提高
T5 括号序列 普及+/提高
T6 博弈 提高+/省选-
T1 兔子之谜
题目大意
有 nn 只兔子，每只兔子有两个耳朵，每个耳朵会指向上下左右四个方向之一，每个方向代表四进制中的一个数。他们从左到右排成一排一共有 2n2n 个耳朵，按顺序给出所有耳朵的方向，求耳朵隐含的四进制数转化为十进制数是多少。
题目思路
根据题意先模拟得到四进制数，然后再转换成十进制数即可。四进制转十进制可类比二进制转十进制。需要注意本题需要使用 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 求职
题目大意
有 nn 家公司和 mm 为求职者，每家公司有两个能力要求，每位求职者也有两个能力值，求职者只有都满足这两个要求才可以通过面试，求每位求职者可以通过多少家公司的面试。
题目思路
我们可以把两个能力值看成一个二维的坐标，那么对于某家公司的要求 (a,b)(a,b) ，能力值为 (x,y)(x,y) 的求职者只有同时满足 x\geq ax≥a 且 y\geq by≥b 才可以通过面试，即 (x,y)(x,y) 在左上角为 (a,b)(a,b) 到右下角为 (1000,1000)(1000,1000) 的范围内即可满足条件。
所以我们不妨用二维差分+前缀和的思想来求出每位求职者可以通过面试的公司数量，对每家公司的要求 (a,b)(a,b) 点上的差分数组加一，最后求出前缀和，O(1)O(1) 查询每位求职者的可通过面试数量。
时间复杂度 O(10^6)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
题目大意
有两颗不同的树 AA 和 树 BB ，每个点都有一个权值，现在两棵树都有 mm 个节点被标记且被标记的节点编号相同。询问这 mm 个节点，对于每个被标记节点 x_ix
i
，如果只有这个节点的标记删除，剩下 m-1m−1 个标记节点在树 AA 中的最近公共祖先的权值是否大于树 BB 中的最近公共祖先的权值。
题目思路
不难发现，若删除 x_ix
i
节点的标记，那么要求的 LCALCA 是
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))
lca(x
1
,x
2
,…,x
i−1
,x
i+1
,…,x
n−1
,x
n
)
=lca(lca(x
1
,x
2
,…,x
i−1
),lca(x
i+1
,…,x
n−1
,x
n
))
所以我们可以预处理 mm 个标记节点的前缀 LCALCA 和后缀 LCALCA ，然后枚举删除标记的节点再求一遍 LCALCA ，然后比较两棵树上 LCALCA 的权值即可。
时间复杂度 O((n+k)logn)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(xfa[id][u] || xson[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 太空传送
题目大意
两人从 11 号太空站出发，第 ii 个太空站传送范围为 (i,i+a_i](i,i+a
i
] 且等概率传送，求两人使用相同传送次数到达 nn 号太空站的概率。
题目思路
通过概率DP思想求解。
设 dp_{i,j}dp
i,j
表示传送了 jj 次到达 ii 号太空站的概率。
状态转移：dp_{k,j+1}+=dp_{i,j}dp
k,j+1
+=dp
i,j
，其中 i<k\leq i+a_ii<k≤i+a
i
。如果直接这么转移时间复杂度是 O(n^3)O(n
3
) 。
但不难发现，转移实际上是一段连续的区间，所以我们可以通过差分前缀和优化。
最终答案为 \sum_{i=1}^n f(n,i)^2∑
i=1
n
f(n,i)
2
。时间复杂度 O(n^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=ansres%mod;
res=resres%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 括号序列
题目大意
求长度为 nn 的括号序列 aa 可能是多少个长度为 mm 的合法括号序列 bb 的子序列。
题目思路
读题时需要注意的一个点是括号序列 aa 不一定是合法的，但求的括号序列 bb 一定是要合法的。
我们可以将 ( 看成权值为 11 ，将 ) 看成权值为 -1−1 ，那么一个合法的括号序列需要满足以下条件：
序列和为 00 。
最小前缀和为不小于 00 。
我们考虑用动态规划解决这个问题。
设 dp_{i,j,k}dp
i,j,k
表示括号序列 bb 中已经有 ii 个字符，括号序列 aa 的前 jj 个字符是括号序列 bb 的子序列，括号序列 bb 的权值前缀和为 kk 。
那么有以下四种转移：
i+1i+1 位置为 ( ，且 j=nj=n 或 s_{j+1}\nes
j+1
= ( ，则 dp_{i+1,j,k+1}+=dp_{i,j,k}dp
i+1,j,k+1
+=dp
i,j,k
。
i+1i+1 位置为 ( ，且 j<nj<n 且 s_{j+1}=s
j+1
= ( ，则 dp_{i+1,j+1,k+1}+=dp_{i,j,k}dp
i+1,j+1,k+1
+=dp
i,j,k
。
i+1i+1 位置为 ) ，且 j=nj=n 或 s_{j+1}\nes
j+1
= ) ，则 dp_{i+1,j,k-1}+=dp_{i,j,k}dp
i+1,j,k−1
+=dp
i,j,k
。
i+1i+1 位置为 ) ，且 j<nj<n 且 s_{j+1}=s
j+1
= ) ，则 dp_{i+1,j+1,k-1}+=dp_{i,j,k}dp
i+1,j+1,k−1
+=dp
i,j,k
。
时间复杂度 O(nm^2)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 博弈
题目大意
有 nn 盘饼干，双方轮流拿取，每次拿完后可以选择是否将剩余饼干合并到别的盘中，若最终无法拿取的人则输掉游戏。给出 qq 次询问，求出询问区间 [l,r][l,r] 中有多少子段先手必胜。
题目思路
先考虑固定盘数时双方如何博弈。
若只有 11 盘饼干，先手必胜。
若有 22 盘饼干，谁把某一盘的饼干取完了谁就输了，所以每一盘饼干有一块是不能取的。不妨令 a_i=a_i-1a
i
=a
i
−1 ，这样问题就变成 nimnim 游戏问题，也就是说 XOR_{i=l}^{r}(a_i-1)=0XOR
i=l
r
(a
i
−1)=0 的话，先手必败，反之先手必胜。
若有 33 盘饼干，先手可以从最多的那盘取出若干饼干，将剩下的局面变成盘数为 22 且上文提到的异或和为 00 的情况，那么先手必胜。
若有 44 盘饼干，谁先将盘数 -1−1 谁就输了，所以还是看异或和是否为 00 。
以此类推，不难发现，当堆数为奇数时，先手必胜，否则令 a_i=a_i-1a
i
=a
i
−1 ，看异或和是否为 00 。
所以我们只需要前缀异或，离线查询，用莫队求解。
时间复杂度 O(n\sqrt{n})O(n
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;
}
这里空空如也
有帮助，赞一个