专栏文章

题解：B4310 [蓝桥杯青少年组国赛 2024] 第五题

MMiraZon
B4310题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipmpghy
此快照首次捕获于
2025/12/03 14:31
3 个月前
此快照最后确认于
2025/12/03 14:31
3 个月前
查看原文
题目入口

解析

同余定理，
若 aa % kk == mm ,bb % kk == mm,( bb - aa ) % kk = = 00 算出前i项和对k取模的值然后存在一个新数组里
CPP
cin>>n>>k;
   for(int i=1;i<=n;i++){
       cin>>a[i];
       sum[i]=sum[i-1]+a[i];
       b[i]=sum[i]%k;
   }
问题就变成了求一个非负整数数组中两个相等的数之间间隔最大，
每次找到的时候顺便记录下两个数的下标，
方便后续输出最长的子序列
对于求解后面这个问题怎么做呢?
如果b[i]=0b[i]=0就先不判断，
b[i]=0b[i]=0代表着前i项和是k的倍数
我们可以存储每个数最后一次的位置
CPP
map<int,int> m;
for(int i=1;i<=n;i++){
        if(b[i]!=0){
            m[b[i]]=i;
        }
    }
然后遍历一遍数组，
判断当前数出现的位置与当前数最后一次出现的位置之差
如果变大了就存储下来并且更新左右下标
题目要求输出位置靠后的最长子序列 我们只需要在相等的时候也更新就可以保证了
CPP
for(int i=1;i<=n;i++){
        if(m[b[i]]-i>=ans&&b[i]!=0){
            l=i,r=m[b[i]];
            ans=m[b[i]]-i;
        }
    }
最后在与所有b[i]=0比较一遍取一个最大的值出来就可以啦
CPP
for(int i=1;i<=n;i++){
        if(b[i]==0&&i>ans){
            l=0;r=i;
            ans=i;
        }
    }
如果ans=0ans=0说明不存在符合要求的子序列
最后按我们记录的左右下标ll,
rr依次输出原数组中的值即可

ac代码

CPP
#include<bits/stdc++.h>
using namespace std;
int n,k,l,r,ans;
int a[100005],sum[100005],b[100005];
map<int,int> m;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        b[i]=sum[i]%k;
    }
    for(int i=1;i<=n;i++){
        if(b[i]!=0){
            m[b[i]]=i;
        }
    }
    for(int i=1;i<=n;i++){
        if(m[b[i]]-i>=ans&&b[i]!=0){
            l=i,r=m[b[i]];
            ans=m[b[i]]-i;
        }
    }
    for(int i=1;i<=n;i++){
        if(b[i]==0&&i>ans){
            l=0;r=i;
            ans=i;
        }
    }
    if(ans==0){
        cout<<-1;
        return 0;
    }
    cout<<ans<<endl;
    for(int i=l+1;i<=r;i++){
        cout<<a[i]<<" ";
    }
}
最后说一句：不要抄袭

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...