非官方题解 | 巅峰赛25部分题解

userId_undefined

༺ཌༀཉི༒白·羊༒༃ༀད༻

出道萌新荣耀黄金时空双修者快乐小狗GESP6级CSP-J一等奖

2025-09-16 06:11:59

发布于：上海

43阅读
0回复
0点赞

真服了发到灌水区了

OK今天也是来水一发题解好吧

总的来说，这次还算简单，但是最后一题莫队没写出来有点可惜

先说下个人认为的难度，大家可以参考下

T1<T2<T5<T4<T3<T6

题目 官方难度 个人认为思维难度 个人认为代码难度 综合难度
T1 橙 红 红 红
T2 黄 橙 橙 橙
T3 绿 黄/绿 蓝 绿
T4 绿 蓝 橙 蓝
T5 蓝 绿 橙 绿
T6 蓝 紫 蓝 蓝

话不多说，正文开始

T1

题目大意：

用一个字符串映射成一个44进制数，要求转1010进制

解法：

没啥好说的，模拟即可，注意powpow函数的精度问题。我因为这个WA了一发

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,ans;
string s;
map<char,int>mp;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	mp['R']=0,mp['D']=1,mp['L']=2,mp['U']=3;
	cin>>n;
	cin>>s;
	for(int i=0;i<s.size();i++){
		int cnt=1;
		for(int j=1;j<=2*n-i-1;j++)
			cnt*=4;
		ans+=cnt*mp[s[i]];
	}
	cout<<ans;
	return 0;
}

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

T2

题目大意：

有 nn 家公司，每家公司对工作质量和工作速度有两个要求ai,bia_i,b_i。同时有 mm 名面试者，每

名面试者有两个能力值xi,yix_i,y_i。一名面试者能通过一家公司的面试当且仅当他的两个能力值都达

到该公司的要求。求每名面试者能通过的公司数量。

解法：

也没啥好说的，直接使用二维前缀和维护即可

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,a[1009][1009],d[1009][1009];
signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>n>>m;
    while(n--){
        int x,y;
        cin>>x>>y;
        a[x][y]++;
    }
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=1000;j++)
            d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j];
    while(m--){
        int x,y;
        cin>>x>>y;
        cout<<d[x][y]<<endl;
    }
    return 0;
}

时间复杂度：O(n2)O(n^2)

空间复杂度：O(n2)O(n^2)

T3

这道题我认为我的解法比官方题解更简单、直观

题目大意：

有两棵节点数均为 nn 的树，根节点都是 11。给出每棵树节点的权值ai,bia_i,b_i。两棵树有相同的

mm 个被标记的节点markimark_i，对于每个markimark_i ，询问：如果只删除markimark_i，那么树A剩余

节点的LCA权值是否大于树B剩余节点的LCA权值

解法：

这道题要用到一个小结论

多个点的LCA=其中DFS序最大的点和其中DFS序最小的点的LCA

至于怎么证明，太长了这里写不下其实是我不会

你们只能看这个了

所以这题只用维护两棵树的LCA和DFS序就做完了

我用了set来维护DFS序

这题连树链剖分都用不上，太水

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m;
int a[200009],b[200009],depa[200009],depb[200009],faa[200009][20],fab[200009][20];
vector<int> va[200009],vb[200009];
int ina[200009],timea,inb[200009],timeb; 
int marks[200009];
set<pair<int,int>> adfs,bdfs;
void dfsa(int s,int f){
    depa[s]=depa[f]+1;
    ina[s]=++timea;
    faa[s][0]=f;
    for(int i=1;i<=19;i++)
        faa[s][i]=faa[faa[s][i-1]][i-1];
    for(auto p:va[s]){
        if(p==f)
			continue;
        dfsa(p,s);
    }
}
void dfsb(int s,int f){
    depb[s]=depb[f]+1;
    inb[s]=++timeb;
    fab[s][0]=f;
    for(int i=1;i<=19;i++)
        fab[s][i]=fab[fab[s][i-1]][i-1];
    for(auto p:vb[s]) {
        if(p==f)
			continue;
        dfsb(p,s);
    }
}
int lcaa(int a,int b){
    if(depa[a]<depa[b])
		swap(a, b);
    for(int i=19;i>=0;i--){
        if(depa[faa[a][i]]>=depa[b])
            a=faa[a][i];
    }
    if(a==b)
		return a;
    for(int i=19;i>=0;i--){
        if(faa[a][i]!=faa[b][i]){
            a=faa[a][i];
            b=faa[b][i];
        }
    }
    return faa[a][0];
}
int lcab(int a,int b){
    if(depb[a]<depb[b])
		swap(a,b);
    for(int i=19;i>=0;i--){
        if(depb[fab[a][i]]>=depb[b])
            a=fab[a][i];
    }
    if(a==b)
		return a;
    for(int i=19;i>=0;i--){
        if(fab[a][i]!=fab[b][i]){
            a=fab[a][i];
            b=fab[b][i];
        }
    }
    return fab[a][0];
}
int geta(){
    if(adfs.empty())
		return 1;
    auto minn=adfs.begin();
    auto maxn=adfs.rbegin();
    return lcaa(minn->second,maxn->second);
}
int getb(){
    if(bdfs.empty())
		return 1;
    auto minn=bdfs.begin();
    auto maxn=bdfs.rbegin();
    return lcab(minn->second,maxn->second);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
		cin>>a[i];
    for(int i=2;i<=n;i++){
        int p;
		cin>>p;
        va[p].push_back(i);
        va[i].push_back(p);
    }
    for(int i=1;i<=n;i++)
		cin>>b[i];
    for(int i=2;i<=n;i++){
        int p;
		cin>>p;
        vb[p].push_back(i);
        vb[i].push_back(p);
    }
    dfsa(1,0);
    dfsb(1,0);
    for(int i=1;i<=m;i++){
        cin>>marks[i];
        int node=marks[i];
        adfs.insert({ina[node],node});
        bdfs.insert({inb[node],node});
    }
    for(int i=1;i<=m;i++){
        int x=marks[i];
        adfs.erase({ina[x],x});
        bdfs.erase({inb[x],x});
        if(a[geta()]>b[getb()])
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
        adfs.insert({ina[x],x});
        bdfs.insert({inb[x],x});
    }
    return 0;
}

不要被我的代码吓到！长只是因为我不会懒得封装起来

时间复杂度：O(能过)O(能过)

空间复杂度：O(能过)O(能过)

其实是O(nlogn)O(nlogn)(应该是)

T4

题目大意：

有 nn 个太空站，起始在 11 号站，目标到达 nn 号站。每个站 ii 有一个能源值 aia_i，表示

从站 ii 可以传送到的范围是[i+1,i+ai][i+1, i+a_i]（等概率随机传送）。

求两个人独立使用传送器，恰好用相同次数到达站 nn 的概率（modmod 998244353998244353 ）。

解法：

一眼概率/期望 DP

定义：dp[t][i]dp[t][i]表示从i点走t次到n点的概率

初始化：

dp[n][0]=1dp[n][0]=1

状态转移方程很简单：直接推即可

dp[t][i]=1a[i]∑j=i+1min⁡(n,i+a[i])dp[t−1][j] dp[t][i] = \frac{1}{a[i]} \sum_{j=i+1}^{\min(n, i+a[i])} dp[t-1][j]

显然，这是O(n3)O(n³)/O(n2)O(n^2)的，我们可以预处理后缀和来优化：

后缀和：

lst[i][t]=dp[i][t]+lst[i+1][t]\text{lst}[i][t] = \text{dp}[i][t] + \text{lst}[i+1][t]

于是：

dp[i][t]=lst[i+1][t]−lst[min⁡(n,i+a[i])+1][t]a[i]\text{dp}[i][t] = \frac{\text{lst}[i+1][t] - \text{lst}[\min(n, i+a[i])+1][t]}{a[i]}

其中lst是后缀和。

最后预处理逆元即可

但是MLE，于是用滚动数组优化

注意一定要开滚动数组！！！8000*8000开不下！

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MOD=998244353;
int n;
int a[8009];
int ny[8009];
int dp[8009],lst[8009],nw[8009];
int ksm(int x,int k){
    int ans=1;
    while(k){
        if(k%2)
            ans=ans*x%MOD;
        x=x*x%MOD;
        k/=2;
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        ny[i]=ksm(i,MOD-2);
    dp[n]=1;
    for(int i=n;i>=1;i--)
        lst[i]=(dp[i]+lst[i+1])%MOD;
    int ans=0;
    for(int t=1;t<n;t++){
        for(int i=1;i<=n;i++)
            dp[i]=0;
        for(int i=n-1;i>=1;i--){
            int k=a[i];
            int x=(lst[i+1]-lst[min(n,i+k)+1]+MOD)%MOD;
            dp[i]=x*ny[k]%MOD;
        }
        for(int i=1;i<=n;i++)
            nw[i]=0;
        for(int i=n;i>=1;i--)
            nw[i]=(dp[i]+nw[i+1])%MOD;
        ans=(ans+dp[1]*dp[1])%MOD;
        for(int i=1;i<=n;i++)
            lst[i]=nw[i];
    }
    cout<<ans;
    return 0;
}

时间复杂度：O(n2)O(n^2)

空间复杂度：O(n)O(n)

T5

题目大意：

给定一个长度为 nn 的括号子序列 aa，要求构造一个长度为 mm 的合法括号序列 bb，使得

aa 是 bb 的子序列。求满足条件的 bb 的数量（modmod 1e9+71e9+7）。

解法：

这题依然毒瘤，要开滚动

一眼dp

定义：dp[i][j][k]dp[i][j][k]表示处理到第ii步时，已匹配了原字符串aa的前jj个字符，栈中有kk个左

括号的方案数

方程并不难推

若添加左括号

dp[i+1][j′][k+1]←dp[i+1][j′][k+1]+dp[i][j][k]\text{dp}[i+1][j'][k+1] \leftarrow \text{dp}[i+1][j'][k+1] + \text{dp}[i][j][k]

其中j′={j+1if j<n and a[j]=′(′jotherwise\text{其中} \quad j' = \begin{cases} j + 1 & \text{if } j < n \text{ and } a[j] = '(' \\ j & \text{otherwise} \end{cases}

条件：k+1≤m2\text{条件：} k + 1 \leq \frac{m}{2}

若添加右括号

dp[i+1][j′][k−1]←dp[i+1][j′][k−1]+dp[i][j][k]\text{dp}[i+1][j'][k-1] \leftarrow \text{dp}[i+1][j'][k-1] + \text{dp}[i][j][k]

其中j′={j+1if j<n and a[j]=′)′jotherwise\text{其中} \quad j' = \begin{cases} j + 1 & \text{if } j < n \text{ and } a[j] = ')' \\ j & \text{otherwise} \end{cases}

条件：k>0\text{条件：} k > 0

然后就做完了。。。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MOD=1e9+7;
int t,n,m;
string a;
int dp[2][309][209];
signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        cin>>a;
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;
        int nw=0,nxt=1;
        int kk=m/2;
        for(int i=0;i<m;i++){
            memset(dp[nxt],0,sizeof(dp[nxt]));
            for(int j=0;j<=n;j++){
                for(int k=0;k<=kk;k++){
                    if(dp[nw][j][k]==0)
						continue;
                    if(k+1<=kk){
                        int nj=j;
                        if(nj<n&&a[nj]=='(')
							nj++;
                        dp[nxt][nj][k+1]=(dp[nxt][nj][k+1]+dp[nw][j][k])%MOD;
                    }
                    if(k>0){
                        int nj=j;
                        if(nj<n&&a[nj]==')')
							nj++;
                        dp[nxt][nj][k-1]=(dp[nxt][nj][k-1]+dp[nw][j][k])%MOD;
                    }
                }
            }
            swap(nw,nxt);
        }
        cout<<dp[nw][n][0]<<endl;
    }
    return 0;
}

口胡T6

题目大意：

给定一个长度为nn的数组aa（每盘饼干的数量），AliceAlice和BobBob轮流操作（AliceAlice先

手）。每轮操作包括两步：

1.选择一个非空盘子，取走正数个饼干。

2.对于该盘剩下的饼干，可以选择不动，或者全部合并到另一个非空盘子。

有 qq 次询问，每次询问区间 [l,r][l, r]，问该区间有多少个连续子区间，使得在这个子区间上的游

戏AliceAlice必胜。

解法：

经过分析样例，可以蒙到证出这题就是NimNim博弈

所以只要求给定区间内异或和为11的区间数量即可，

显然是个莫队但我没写出来

但看到全站没人AC我就放心了

12分暴力代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,q,a[200009],d[200009]; 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        d[i]=(a[i]^d[i-1]);
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        if(n%2){
        	cout<<(r-l+1)*(r-l+2)/2<<endl;
        	continue;
		}
        unordered_map<int,int> mp;
        int cnt=0;
        for(int i=l-1;i<=r;i++)
            mp[d[i]]++;
        for(auto &p:mp)
            cnt+=p.second*(p.second-1)/2;
        cout<<(r-l+1)*(r-l+2)/2-cnt<<endl;
    }
    return 0;
}

好了本次题解就到这儿了，打字不易，留个赞再走吧

@AC君加个精求求了

userId_undefined
去预览
0/2000

全部评论 11

热门讨论