ACGO挑战赛#19 全题解

亚洲卷王 AK IOI

2025-06-15 22:00:17

发布于：北京

21阅读

0回复

0点赞

T1-午枫的字符串加密

首先能想到，移动 $26$ 次等于没动。所以 $m$ 可以先对 $26$ 取模。

然后我们直接用减法计算原字符串，如果某一个字符 $c$ 出现了 c<'a' 的情况，说明在加密过程中由 z 变 a 了，此时直接加上 $26$ 即可。

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

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

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
string s;
int main(){
    cin>>n>>m>>s;
    m%=26;
    for(auto &i:s){
        if(i-m<'a') cout<<(char)(i-m+26);
        else cout<<(char)(i-m);
    }
    return 0;
}

T2-小午的质因子统计

$O(\sqrt{n})$ 的质因数分解相信大家人人都会，就不赘述了。

但是 $O(n\sqrt{n})$ 在这题会超时，所以我们需要 $O(n \log n)$ 计算。

考虑到根号算法耗时在寻找质因子的时候，所以筛法记录每个数的最小质因子。采用埃氏筛。

时间复杂度： $O(n \log n)$

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

Code:

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[1000005],p[1000005];
bool isp[1000005],vis[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    isp[0]=isp[1]=true;
    for(int i=2;i<=1000000;i++){
        if(!isp[i]){
            for(int j=i;j<=1000000;j+=i){
                if(p[j]==0) p[j]=i;
                else p[j]=min(i,p[j]);
            }
        }
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(a[i]>1){
            vis[p[a[i]]]=true;
            a[i]/=p[a[i]];
        }
    }
    for(int i=1;i<=1000000;i++) if(vis[i]) ans++;
    cout<<ans;
    return 0;
}

T3-午枫的字符串移动

这题有一个很引人注目的点： $n \leq 10^4$ 。这意味着允许 $O(n^2)$ 算法！

首先考虑到移动 $n$ 次等于不动，所以求得 $0 \leq m<n$ 。

直接枚举 $m$ ，然后模拟移动的过程，最后判断是否和 $s'$ 恰好相差 $k$ 字符。

判断可以使用双指针，如果 $s_l=s'_r$ ，则成功匹配；反之匹配失败，需要在 $s'_r$ 前添加一个字符。统计添加的字符数量是否恰好为 $k$ 即可。

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

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

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,l,r,sum;
char c;
string s,t;
int main(){
    cin>>n>>k>>s>>t;
    for(ll i=0;i<n;i++){
        l=r=sum=0;
        while(l<n&&r<n-k){
            if(s[l]==t[r]) l++,r++;
            else sum++,l++;
        }
        sum+=n-l;
        if(sum==k){
            cout<<i;
            return 0;
        }
        c=s.back();
        for(ll j=n-1;j>=1;j--) s[j]=s[j-1];
        s[0]=c;
    }
    return 0;
}

T4-午枫的01串翻转

如果字符串没有 0，那么显然答案为 $0$ ；

如果字符串只有 $1$ 个 0，那么我们要争取做一次操作让 0 变多。考虑到 $r$ 的位置一定会变成 0，所以如果 $r$ 越靠后，距离越远。统计 0 后面的 1 的位置，如果少于 $2$ 个则无可奈何，否则选择最后一个 1 与最前的一个 1 即可。

如果字符串有 $2$ 个或者更多 0，那么显然，我们至少可以将其中之一作为 $l$ 。第一个 0 显然是需要我们保留下来作为最远距离的，所以我们选择其他的任意一个 0 作为 $l$ 。如果结尾是 0，那么无需操作也能得到最远距离；如果结尾是 1，那么令其为 $r$ ，一次操作之后，结尾又会变成 0。综上所述，我们需要的 0 一定是第一个 0 和结尾。

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

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

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,l,r,ans;
string s;
vector<ll> v;
int main(){
    cin>>n>>s;
    if(count(s.begin(),s.end(),'0')==0){
        cout<<0;
        return 0;
    }
    if(count(s.begin(),s.end(),'0')==1){
        l=s.find('0');
        for(ll i=l+1;i<n;i++) if(s[i]=='1') v.push_back(i);
        if(v.size()<=1) cout<<0;
        else cout<<v.back()-l-1;
        return 0;
    }
    cout<<n-1-s.find('0');
    return 0;
}

T5-午枫的双向奔赴

约定：从 $u$ 走到 $v$ 的最短路长度 $L$ 记作 $L=u \rightarrow v$ 。

如果我们知道 $L_1=1 \rightarrow k$ 和 $L_2=n \rightarrow k$ ，那么他们需要多长时间才能见面呢？显然，有一个人会先到，然后等待另一个人到。所以是 $\max(L_1,l_2)$ 。

如果我们对于所有的 $k$ 都能知道 $L_1,L_2$ 的话，就可以 $O(n)$ 打擂台求出最短时间了。当然求出编号也不是难事，以后不再赘述。

很显然， $L_1$ 可以跑一遍单源最短路， $L_2$ 同样可以。

所以我们跑两遍单源最短路就行了！

时间复杂度： $O((n+m) \log m)$

空间复杂度： $O(n+m)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
const ll MAXN=2e5+25;
struct node{
    ll nxt,to,w;
};
ll n,m,u,v,w,tot,ans=LLONG_MAX;
ll hd[MAXN],dist[2][MAXN];
bool vis[MAXN];
node edge[MAXN<<1];
priority_queue<pll,vector<pll>,greater<pll>> pq;
inline void add(const ll &u,const ll &v,const ll &w){
    edge[++tot]={hd[u],v,w};
    hd[u]=tot;
    return;
}
inline void dij(const ll &r,const ll &beg){
    pll u,v;
    memset(dist[r],0x3f,sizeof(dist[r]));
    memset(vis,false,sizeof(vis));
    dist[r][beg]=0;
    pq.push(mkp(0,beg));
    while(!pq.empty()){
        u=pq.top();
        pq.pop();
        if(vis[u.se]) continue;
        vis[u.se]=true;
        for(ll i=hd[u.se];i;i=edge[i].nxt){
            v=mkp(u.fi+edge[i].w,edge[i].to);
            if(v.fi<dist[r][v.se]){
                dist[r][v.se]=v.fi;
                if(vis[v.se]) continue;
                pq.push(v);
            }
        }
    }
    return;
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dij(0,1);
    dij(1,n);
    for(ll i=1;i<=n;i++) ans=min(max(dist[0][i],dist[1][i]),ans);
    cout<<ans<<'\n';
    for(ll i=1;i<=n;i++) if(max(dist[0][i],dist[1][i])==ans) cout<<i<<' ';
    return 0;
}

T6-午枫的字符串制造

显而易见的，回文串最多只有一个字符出现次数是奇数。

奇偶性我们可以简单地用 $0/1$ 代替。所以，我们有 $26$ 个字母，每个字母有 $0/1$ 两种状态。所以我们可以使用状态压缩！（题目1024MB也是一种提醒）

所以， $dp_{mask}$ 表示当目前前缀状态为 $mask$ 的时候的合法子串数量（目前，是指目前处理到了哪一位）。

首先记录一下目前的前缀 $p$ ，然后将答案加上 $dp_p$ 。

同时，我们知道，有可能会有一个字母出现奇数次。枚举这个字母，并记录答案。

最后，记得用 $p$ 更新 $dp_p$ 的值。

注意下，一开始 $dp_0=1$ ，因为任何字母都出现 $0$ 次。

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

空间复杂度： $O(n+2^{26})$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,cnt,ans;
string s;
int dp[1<<26];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s;
    dp[0]=1;
    for(ll i=0;i<n;i++){
        cnt^=1<<(s[i]-'a');
        ans+=dp[cnt];
        for(ll j=0;j<26;j++) ans+=dp[cnt^(1<<j)];
        dp[cnt]++;
    }
    cout<<ans;
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

BaiRX
笑点解析：我暴力抢 T2 首 A

2天前来自北京
0
- 亚洲卷王 AK IOI
  回复BaiRX
  你抢nmn
  
  2天前来自北京
  0

T1-午枫的字符串加密

T2-小午的质因子统计

T3-午枫的字符串移动

T4-午枫的01串翻转

T5-午枫的双向奔赴

T6-午枫的字符串制造

全部评论 1

热门讨论