挑战赛#15 全题解
2025-03-22 00:12:45
发布于：广东
挑战赛#15 全题解
前记
太爽了极限 AK。
这里着重会讲万恶的 T5。
正式部分
T1
T1 小特想散步
很简单的一道题啊，字符串输入判断即可。
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
string a;
cin>>a;
if(a[n-1]=='o')cout<<"Yes";
else cout<<"No";
}
T2
T2 老猞狸的问题
同样很简单的题，每次遇到不同的贪心性交换后一位，如果不行直接 No，同时统计次数，次数 时也要 No。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string s,t;
int cnt;
int main(){
cin>>s>>t;
for(int i=0;i<s.size()-1;i++){
if(s[i]!=t[i]){
if(s[i+1]==t[i]){
swap(s[i],s[i+1]);
cnt++;
}
else{
cout<<"No";
return 0;
}
}
if(cnt>1){
cout<<"No";
return 0;
}
}
cout<<"Yes";
}
T3
T3 源石虫比赛
这能有黄？
看到数据范围 ，直接 自信过了。
理论上也可以加一个排序和二分，有人有时间打吧。
贪心性很明显，每次选择最小的比两接力位置之差大于或等于的原石虫就可以了。
注意一下它的输出结构。
#include<iostream>
using namespace std;
int n;
int a[10005],b[10005];
bool vis[10005];
int main(){
ios::sync_with_stdio(0);
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++)cin>>b[i];
for(int i=2;i<=n;i++){
int mi=1e9+5,id=0;
for(int j=1;j<=n;j++){
if(vis[j])continue;
if(b[j]>=a[i]-a[i-1] && b[j]<mi){
mi=b[j];
id=j;
}
}
if(id==0){
cout<<"NO"<<endl<<i-1;
return 0;
}
vis[id]=1;
}
cout<<"YES";
}
T4
T4 简单集合之和
总算有点难度的题，不过数据范围 ，显然 的爆搜会 TLE，同时用背包的话 也得凉。
其实不难让人想到是 折半搜索（meet in the middle） 算法。
该算法主要思路是：
- 将 范围的数分成两半；
- 将两半数 dfs，用两个数组统计其中的答案，两个数组的大小就是 是可以实现的;
- 将其中一个数组排序（我这里选 ），然后遍历另一个数组进行 二分操作（这个后面讲）;
- 最后统计一下答案就可以了。
对于这道题来讲，由于我们搜出来的答案对 取模，所以 。
同时不难证明，我们我们每次遍历的数 小于 的情况一定比大于等于 的情况模 要更大，所以二分操作就是选出令 中最大的 ，注意可以重复选，也可以不选（）。
但注意 也可以不选。
最后时间复杂度是 ，可以通过本题。
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
ll x;
ll a[50];
ll ans1[1<<18],cnt1;
ll ans2[1<<18],cnt2;
void dfs1(int p,int r,ll s,bool zt){
//cout<<p<<" "<<s<<" "<<cnt1<<endl;
if(zt)ans1[++cnt1]=s;
if(p>r) return;
dfs1(p+1,r,s,0);
dfs1(p+1,r,(s+a[p])%x,1);
}
void dfs2(int p,int r,ll s,bool zt){
if(zt)ans2[++cnt2]=s;
if(p>r) return;
dfs2(p+1,r,s,0);
dfs2(p+1,r,(s+a[p])%x,1);
}
ll ef(ll x){
int l=0,r=cnt2;
while(l<r){
int mid=l+r+1>>1;
if(ans2[mid]>=x)r=mid-1;
else l=mid;
}
return ans2[l];
}
int main(){
cin>>n>>x;
for(int i=1;i<=n;i++)cin>>a[i];
//cout<<(n>>1)<<endl;
dfs1(1,n>>1,0,0);
dfs2((n>>1)+1,n,0,0);
sort(ans2+1,ans2+cnt2+1);
ll ans=0;
//cout<<"Hi"<<endl;
for(int i=0;i<=cnt1;i++){
//cout<<ans1[i]<<endl;
//cout<<ef(x-ans1[i])<<endl;
ans=max(ans,ans1[i]+ef(x-ans1[i]));
}
cout<<ans;
}
T5
万万差点没想到原来是线段树。
首先没看到 “保证每次操作后都会满足对于 存在从 连向 的边” 的出来罚站，没救了。
那么既然有这个条件，那就说明对于任何 ，一定能从 到 。
问题到这已经非常线性了。
那么我们要做的就只有维护每个数能到的编号最小的数了，这里我用了一个 map 来记录维护，本质是红黑树，能在稳定 来维护。
那么对于每次加边删边，只有 的时候要改变，同时发现操作改变了的时候要修改到线段树。
接下来说一下查询，可以知道 号节点一定能到任何 的节点，所以我们只要知道我们能到的编号最小的节点就行了。第一次只用查询区间 中能到的编号最小的数最小值。区间？正好就是线段树的工作（你用树状数组或者 ST 表可能也行）。但是要知道不仅如此，设第一次答案为 ，则它到了这个节点之后还能到区间 ，以此类推，可以到 ，终止条件就是 ，这时候能到 的任一节点，所以答案就是 。
补充：
其实这样写有可能会被卡到 的，出题人好心没卡。如果谁有时间可以试试做个记忆化，每次查询后 的区间可以记忆化，然后在真实修改了某一个数的能到的编号最小的数就覆盖掉。
#include<iostream>
#include<map>
using namespace std;
const int N=500005;
int n,q;
int op;
int x,y;
map<int,int> m[N];
struct tree{
int l,r;
int mi;
}t[N<<2];
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
t[p].mi=l;
if(l==r){
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void change(int p,int x,int c){
if(t[p].l==x && t[p].r==x){
t[p].mi=c;
return;
}
int mid=t[p].l+t[p].r>>1;
if(x<=mid) change(p<<1,x,c);
else change(p<<1|1,x,c);
t[p].mi=min(t[p<<1].mi,t[p<<1|1].mi);
}
int check(int p,int l){
if(t[p].l>=l){
return t[p].mi;
}
int mid=t[p].l+t[p].r>>1;
int res=1e9;
if(l<=mid) res=min(res,check(p<<1,l));
res=min(res,check(p<<1|1,l));
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
build(1,1,n);
for(int i=1;i<=n;i++) m[i][i]=1;
for(int i=1;i<=q;i++){
cin>>op;
if(op==1){
cin>>x>>y;
if(x<=y)continue;
m[x][y]++;
if(m[x][y]==1 && y==m[x].begin()->first){
change(1,x,y);
}
}
if(op==2){
cin>>x>>y;
if(x<=y)continue;
m[x][y]--;
if(m[x][y]==0){
if(y==m[x].begin()->first){
m[x].erase(y);
change(1,x,(m[x].begin())->first);
}
else m[x].erase(y);
}
}
if(op==3){
cin>>x;
int l=x,r=n;
while(1){
int t=check(1,l);
if(t==l)break;
l=t,r=l-1;
}
cout<<n-l+1<<'\n';
}
}
}
T6
T6 串串
很明显，前缀长度增大时，答案单调不增，所以二分就可以。
但模式串字符串匹配，那就是 KMP 了，不多讲。
我之前想过 AC 自动机的，不过因为比较聪明不会拓扑建图，所以就算了。
#include<iostream>
#include<cstring>
using namespace std;
string a,b;
int ne[100005];
int n;
int ans;
int main(){
cin>>a>>b>>n;
a=" "+a;
b=" "+b;
int l=0,r=min(a.size(),b.size());
while(l<r){
int mid=l+r+1>>1;
//cout<<l<<" "<<r<<endl;
for(int i=2,j=0;i<=mid;i++){
ne[i]=0;
while(j && b[i]!=b[j+1]) j=ne[j];
if(b[i]==b[j+1])j++;
ne[i]=j;
}
int cnt=0;
for(int i=1,j=0;i<a.size();i++){
while(j && a[i]!=b[j+1]) j=ne[j];
if(a[i]==b[j+1])j++;
if(j==mid){
cnt++;
j=ne[j];
}
}
if(cnt>=n){
l=mid;
ans=mid;
}
else r=mid-1;
}
if(ans==0)cout<<"IMPOSSIBLE";
else{
for(int i=1;i<=ans;i++)cout<<b[i];
}
}
总结
这次挑战赛出的还不错。
全部评论 5
在 T5 搜索场景中，由于 0 必定是最小值，我们可以借助线段树来查询某个区间的最小值是否为 0，进而利用这个特性完成二分查找。
具体而言，对于给定的区间 [L, R]，根据线段树的性质，其最多只会拆分成 log n 个区间。我们可以从右向左对这 log n 个合法区间依次进行搜索，通过不断缩小范围，最终找到满足条件的合法位置。
整个单次操作的时间复杂度为 O(log n)。所以，我们只需要实现一个支持区间加法操作以及二分查找功能的线段树，就能够完成上述搜索任务。
2025-02-25 来自 浙江
0
有帮助，赞一个