官方题解 | 挑战赛#19

NoonMaple

2025-06-16 08:17:02

发布于：浙江

21阅读

0回复

0点赞

官方题解 | 挑战赛19题解

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

题目编号	题目标题	难度
T1	午枫的字符串加密	入门
T2	小午的质因子统计	普及-
T3	午枫的字符串移动	普及-
T4	午枫的01串翻转	普及/提高-
T5	午枫的双向奔赴	普及/提高-
T6	午枫的字符串制造	普及/提高-

T1 午枫的字符串加密

题目大意

给了一个 $m$ 加密后的字符串，求出加密前的字符串。

解题思路

由于小写英文字母只有 $26$ 个，所以加密也是 $26$ 次一个循环。我们可以将 $m$ 直接对 $26$ 取模，可以对每一个字符用循环模拟解密的过程，即将这个字母变成在字母表上循环左移 $m$ 位后的字母，时间复杂度 $O(m\%26)$ 。

当然，也可以通过直接计算直接得到加密前的字母，时间复杂度 $O(1)$ 。std 给出的是 $O(1)$ 的方法。

参考代码

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

void solve(){
    int n,m;cin>>n>>m;
    string s;cin>>s;

    m%=26;
    for(auto x:s){
        int u=x-'a';
        u=(u-m+26)%26;
        cout<<(char)(u+'a');
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}

T2 小午的质因子统计

题目大意

求所有数质因数分解后有多少个不同的质因子。

题解思路

可以用埃式筛先预处理出 $[1,10^6]$ 所有数的质因子有哪些，然后遍历数组用 $set$ 容器存储所有质因子，因为 $set$ 容器会自动去重，所以最后直接输出 $set$ 容器的 $size()$ 即可。

参考代码

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

vector<bool>st(1000010);
vector<int>f[1000010];

void init(){
    for(int i=2;i<=1000000;i++){
        if(st[i]) continue;
        for(int j=i;j<=1000000;j+=i){
            st[j]=true;
            f[j].push_back(i);
        }
    }
}

void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    unordered_set<int>s;
    for(int i=1;i<=n;i++){
        for(auto x:f[a[i]]){
            s.insert(x);
        }
    }

    cout<<s.size()<<endl;
}

signed main(){
    init();
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}

T3 午枫的字符串移动

题目大意

给定原串和最终串，最终串是通过原串循环右移且丢失若干字符得到的，求出原串最小的循环右移次数。

题解思路

由于 $n$ 最大是 $10000$ ，我们可以考虑 $O(n^2)$ 的做法。

首先，很容易发现 $m$ 最大可能是 $n-1$ ，所以我们可以通过枚举 $s'$ 对应原串 $s$ 的开头位置，类比做了 $C(s,m)$ 的操作，一位一位进行比较判断，如果某一位不匹配，那么就让 $s$ 的下一位去匹配，如果 $s$ 的每一位都判断过了还没有匹配到 $s'$ 的最后一位，那么说明不存在这么一个 $m$ 让 $s$ 变成 $s'$ 。

我们只要找到最小的 $m$ 即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int INF = 1e18+10;

void solve(){
    int n,k;cin>>n>>k;
    int m=n-k;
    string s,t;cin>>s>>t;

    int res=INF;
    for(int i=0;i<n;i++){
        int l=i,r=0;
        int cnt=0;
        for(int j=0;j<n;j++){
            if(s[l]!=t[r]){
                cnt++;
                l++;
            }
            else{
                l++;
                r++;
            }

            if(r==m) break;
            l%=n;
        }
        if(cnt<=k) res=min(res,(n-i)%n);
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}

T4 午枫的01串翻转

题目大意

给定一个 $01$ 串，可以进行指定操作，求出所有可能的 $01$ 串中距离最远的两个 $0$ 的距离是多少。

题解思路

我们其实最多只需要操作一次即可得到答案。

一共分三种情况：

没有 $0$ ，直接输出 $0$ 。
只有一个 $0$ $0$ ，此时很容易发现不操作的话距离一定是 $0$ $0$ ，所以我们尽量考虑操作。
- 如果这个 $0$ 在最后两个位置，要么无法操作，要么操作了一次也还是只能有一个 $0$ , 此时答案为 $0$ .
- 如果不在最后两个位置，考虑到其余位置都为 $1$ ，我们尽量操作更长的区间，能使两个 $0$ 的距离最大，那么以这个 $0$ 为区间左端点，最后一个 $1$ 为区间右端点，对这段区间进行一次操作，就会将区间内所有的 $1$ 都变为 $0$ ，此时答案为 $翻转区间长度-1$ .
有两个及以上个 $0$ ，此时我们可以让最左端的 $0$ 不动，记这个 $0$ 的位置为 $pos$ ，用后面的任意 $0$ 最为操作区间的左端点，最后一个 $1$ 最为区间右端点，不难发现，操作后距离最左端的 $0$ 最远的 $0$ 一定是最后一个字符，此时答案为 $n-pos$ .

综上所述，此题只需找到第一个 $0$ 的位置，按照上述情况分类讨论即可。

参考代码

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

void solve(){
    int n;cin>>n;
    string s;cin>>s;s=' '+s;
    int cnt=0;
    for(auto c:s){
        if(c=='0') cnt++;
    }
    if(cnt==0){
        cout<<"0"<<endl;
        return;
    }

    int pos=s.find('0');
    if(cnt==1){
        if(pos>n-2) cout<<0<<endl;
        else cout<<n-pos-1<<endl;
    }
    else cout<<n-pos<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}

T5 午枫的双向奔赴

题目大意

给定一张图，小午和小枫分别在 $1$ 号节点和 $n$ 号节点，求出两人会和的最小时间，并且按照编号从小到大输出所有花费最小时间的节点

题解思路

设 $d1_i$ 为从 $1$ 号节点出发到达 $i$ 号节点的最短时间， $dn_i$ 为从 $n$ 号节点出发到达 $i$ 号节点的最短时间。那么他们在 $i$ 号节点会和花费的时间为 $max(d1_i,dn_i)$ 。所以他们会和的最短时间为 $\min_{i=1}^{n} (max(d1_i,dn_i))$ 。

分别以 $1$ 号节点和 $n$ 号节点为起始节点用 $dijkstra$ 求出最短路，即 $d1_i$ 和 $dn_i$ ，然后再求出他们会和需要的最短时间，最后找出所需最短时间的节点，按照编号从小到大输出。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define int long long
#define endl '\n'
const int INF = 1e18+10;

void solve(){
    int n,m;cin>>n>>m;
    vector<vector<PII>>v(n+1);
    for(int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }

    auto DJ=[&](int bg,vector<int> &d){
        priority_queue<PII,vector<PII>,greater<PII>>q;
        vector<bool>st(n+1);
        d[bg]=0;
        q.push({d[bg],bg});
        
        while(!q.empty()){
            auto [_,t]=q.top();q.pop();
            if(st[t]) continue;
            st[t]=true;

            for(auto [x,c]:v[t]){
                if(d[x]>d[t]+c){
                    d[x]=d[t]+c;
                    q.push({d[x],x});
                }
            }
        }
    };

    vector<int>d1(n+1,INF),d2(n+1,INF);
    DJ(1,d1);
    DJ(n,d2);

    int mi=INF;
    for(int i=1;i<=n;i++){
        mi=min(mi,max(d1[i],d2[i]));
    }

    vector<int>res;
    for(int i=1;i<=n;i++){
        if(max(d1[i],d2[i])==mi) res.push_back(i);
    }
    sort(res.begin(),res.end());

    cout<<mi<<endl;
    for(auto x:res) cout<<x<<" ";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}

T6 午枫的字符串制造

题目大意

给定一个长度为 $n$ 的字符串，求有多少个连续子串可以通过重新排列得到回文串。

题解思路

首先，如果用 $O(n^2)$ 暴力枚举所有区间肯定是不可行的。于是我们需要考虑优化。

我们如何可以快速判断一个子串能否通过重新排列得到一个回文串？

不难发现，如果这个子串的长度是偶数，那么所有的字母的个数都是偶数就可以排列成回文串；如果这个子串的长度是奇数，那么只能有一个字母的个数是奇数，才可以排列成回文串。

那么我们可以用长度为 $26$ 的二进制状态表示每一个字母个数的奇偶。

奇偶性可以通过异或来表达。记 $State_i$ 为前 $i$ 个字母的奇偶状态，定义 $State_0=0$ ， $cnt_{State}$ 为 $State$ 这种状态的数量。我们可以通过枚举区间右端点 $i$ ，得到 $State_i$ ，那么我们可以考虑分回文串的奇偶长度分两个情况考虑：

回文串的长度为偶数，此时有 $cnt_{State_j}$ 个左端点 $j$ 可以形成回文串，其中 $0\leq j\leq i-1$ 且 $State_i=State_j$ 。
回文串的长度为奇数，此时我们可以枚举 $26$ 个字母为奇数状态的情况，设第 $k$ 个字母的个数是奇数的状态为 $mask=State_i\oplus (1<<k)$ ，那么有 $cnt_{mask}$ 个左端点 $j$ 可以形成回文串，其中 $0\leq j\leq i-1$ 且 $mask=State_j$ 。

字符串的长度为 $n$ 且每个状态最多延申出 $26$ 个状态，空间复杂度最大为 $O(26n)$ ，此题空间限制给了 $1GB$ ，因此是可以通过的。

时间复杂度为 $O(26n)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int n;cin>>n;
    string s;cin>>s;s=' '+s;

    vector<int>cnt((1ll<<26)+1);
    cnt[0]=1;
    int S=0;
    int res=0;
    for(int i=1;i<=n;i++){
        int x=s[i]-'a';
        S^=(1ll<<x);
        res+=cnt[S];
        
        for(int j=0;j<26;j++){
            int tmp=S^(1ll<<j);
            res+=cnt[tmp];
        }

        cnt[S]++;
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}