挑战赛#19全题解
2025-06-17 14:00:39
发布于:上海
T1
题目分析
题目要求我们将给出的只有小写字母的字符串t解密
解题思路
由于任何一个字母进行26加密后都会回到原来的值,所以可以直接将m模26,然后根据ASCII码进行解密即可
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
string t;
int main()
{
cin>>n>>m>>t;
m%=26;
for(int i=0;i<n;i++)
{
int p=int(t[i])-97;
p=(p+26-m)%26;
t[i]=char(p+97);
}
cout<<t;
return 0;
}
T2
题目分析
题目给了我们一串数,让我们统计数组中所有的数有多少个共同的质因子
解题思路
我们可以用埃氏筛预处理出1-10^6中的所有质数,并且在这个过程中记录下每个数最小的质因子,这样后面分解质因子时就不用再求最小质因子了
AC代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e6;
int n,a[mod+5],min_prime[mod+5],is_prime[mod+5],b[mod+5],ans;
int main()
{
cin>>n;
is_prime[1]=0;
for(int i=2;i<=mod;i++)
{
if(!is_prime[i])
{
for(int j=i;j<=mod;j+=i)
{
if(min_prime[j]==0)min_prime[j]=i;
else min_prime[j]=min(min_prime[j],i);
}
}
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(a[i]!=1)
{
if(b[min_prime[a[i]]]==0)
{
b[min_prime[a[i]]]=1;
ans++;
}
a[i]/=min_prime[a[i]];
}
}
cout<<ans;
return 0;
}
T3
题目分析
题意可转化为求当初始字符串S向右循环移动至少几次后,能让S'成为S的字符子序列
解题思路
因为n的数据量是1到10^4,所以我们可以考虑时间复杂度为O(n*n)的方案。我们可以将两个字符串S拼在一起,来解决字符串循环移动的问题,然后创建一个判断子序列的函数(因为子序列不可颠倒顺序,所以用双指针就解决了),每次拿移动后的字符串去判断
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
string s,t;
bool check(int v)//判断子序列的函数
{
int i=v,j=0;
while(i<v+n && j<n-k)//双指针逐位比较
{
if(s[i%(2*n)]==t[j])j++;
i++;
}
return j==n-k;
}
int main()
{
cin>>n>>k;
cin>>s>>t;
s=s+s;//字符串移动用拼接秒了
for(int i=0;i<n;i++)
{
if(check(n-i))
{
cout<<i<<endl;
return 0;
}
}
return 0;
}
T4
题目分析
题目给出一个二进制串,我们可以进行任意次(可以不做)的操作:
选择一段区间 [l,r],[l,r] 满足
1≤l<r≤n,sl=0,sr=1
对于这段区间的每一位 si(l≤i≤r),将其变为 si异或1
让我们求距离最远的两个零的距离的最大值
解题思路
在做这道题之前,建议大家先去看看挑战赛#18的T4
这两题除了问题不一样,其他完全没有区别(当时我把任意次看成了一次,被坑惨了)
本题可以分为三种情况讨论
1:没有零的
这种情况直接没法操作,输出零就行
2:有一个零
如果这个零在最后一位或者倒数第二位,也只能输出零(零的数量不可能增加)
否则直接对[零的位置,二进制串的长度]作一次操作,得出答案是(二进制串的长度-零的位置-1)(注意我这里的索引从一开始)
3:有多个零
第一个零保持不变,对[其他任何一个零的位置,二进制串的长度]做一次操作,得出答案是(二进制串的长度-第一个零的位置)
AC代码
#include<bits/stdc++.h>
using namespace std;
string s;
int n,t,first_0=-1;
int main()
{
cin>>n>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='0' && first_0==-1)first_0=i;
if(s[i]=='0')t++;
}
if(t==0 || first_0==n-1)
{
cout<<0;
return 0;
}
if(t==1)
{
cout<<n-first_0-2;
return 0;
}
cout<<n-first_0-1;
return 0;
}
T5
题目分析
题目给出一个n个点,m条边的带权无向图。有一个人从点1出发,有一个人从点n出发,他们选择一个点会和,问他们会合的最短时间(最小权重)是多少,要选择哪个点会和
解题思路
我们可以分别求出1点到任意点所花的最少时间,和n点到任意点所花的最少时间,在第i点回合所需的最少时间就是1点到i点的最少时间和n点到i点的最小时间中的最大值。因为n的数据量是2*10^5,而且给出的是一个稀疏图,所以不能用邻接矩阵存储,而因该选择向量+结构体的组合。至于计算最少时间的算法可以使用DIjkstra算法,此算法使用广搜的思路,并且使用优先队列优化时间复杂度,其时间复杂度为O((n+m)logn),这是可以接受的,在最终选择会合点时,可以用一个集合存储最优会合点(虽然我没用)
AC代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,b[200005],t;
long long ansl[200005],ansr[200005],ans=1e18;
struct node
{
long long sum,d;
bool operator < (const node & a)const
{
return sum>a.sum;
}
};
int main()
{
cin>>n>>m;
priority_queue<node>q;
vector<vector<pair<long long,long long> > >a(n+1);
for(int i=1;i<=m;i++)
{
long long l,r,k;
cin>>l>>r>>k;
a[l].push_back({r,k});
a[r].push_back({l,k});
}
for(int i=1;i<=n;i++)ansl[i]=1e18,ansr[i]=1e18;
ansl[1]=0;
q.push({0,1});
while(!q.empty())
{
long long sum=q.top().sum,d=q.top().d;
q.pop();
if(sum!=ansl[d])continue;
for(auto& i : a[d])
{
long long newd=i.first;
long long newsum=i.second+ansl[d];
if(newsum<ansl[newd])
{
ansl[newd]=newsum;
q.push({newsum,newd});
}
}
}
ansr[n]=0;
q.push({0,n});
while(!q.empty())
{
long long sum=q.top().sum,d=q.top().d;
q.pop();
if(sum!=ansr[d])continue;
for(auto& i : a[d])
{
long long newd=i.first;
long long newsum=i.second+ansr[d];
if(newsum<ansr[newd])
{
ansr[newd]=newsum;
q.push({newsum,newd});
}
}
}
vector<int>city;
for(int i=1;i<=n;i++)
{
if(max(ansl[i],ansr[i])<ans)
{
ans=max(ansl[i],ansr[i]);
city.clear();
city.push_back(i);
}
else if(max(ansl[i],ansr[i])==ans)city.push_back(i);
}
cout<<ans<<endl;
for(int i=0;i<city.size();i++)cout<<city[i]<<" ";
return 0;
}
T6
题目分析
题目给出一个长度为n的只有小写字母的字符串S,让我们求出它的回文子串数量
解题思路
很明显回文串最多只能有一个小写字母出现奇数次
一开始我想用数组来存储,但后来发现使用一个二进制数来进行状态压缩更加便捷。我们可以定义一个26位二进制数status,它的每一位代表一个字母出现的次数(只表示奇偶就行了),每次先读取一个字符,然后将二进制数中代表它的位置异或1(1变0,0变1)
再利用前缀和的思路存储每次更新后的status。但如果只是每次status更新后与之前的status进行异或操作判断是否为回文串(结果为0或是二的整数次方)的话,时间复杂度就是O(n*n),这是不可接受的。
后来我发现任何一个status都只能与27个数进行异或操作才满足结果为0或是二的整数次方:status本身(结果为0),status异或1,status异或2,status异或4……(结果为2的整数次方),这个时候就想到了桶的思想(将出现过的status以桶的形式存储)
我们创建一个数组b,每次读入一个字符后都将b[status]加一,寻找回文串时就去数组b里找前面提到的27个数的出现次数加到答案里即可
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,b[1<<26];
string s;
long long ans,status;
int main()
{
cin>>n>>s;
b[0]=1;
for(int i=0;i<n;i++)
{
int wei=s[i]-'a';
status=status^(1<<wei);
ans+=b[status];
for(int j=0;j<26;j++)ans+=b[status^(1<<j)];
b[status]++;
}
cout<<ans;
return 0;
}
本人是蒟蒻,题解中有错误的地方欢迎各位大佬指出
点个赞吧(doge)
全部评论 14
虽迟但到 ddd
2025-06-22 来自 上海
0d
2025-06-22 来自 上海
0d
2025-06-22 来自 上海
0d
2025-06-22 来自 上海
0%%%
2025-06-17 来自 北京
0d
2025-06-17 来自 上海
0d
2025-06-17 来自 上海
0干啥呢
2025-06-17 来自 上海
0d
2025-06-17 来自 上海
0d
2025-06-17 来自 上海
0d
2025-06-17 来自 上海
0d
2025-06-16 来自 上海
0d
2025-06-16 来自 上海
0d
2025-06-16 来自 上海
0
有帮助,赞一个