题解：B4310 [蓝桥杯青少年组国赛 2024] 第五题
MiraZon
·
·
题解
题目入口
解析
同余定理，
若 a % k == m ,b % k == m,( b - a ) % k = = 0 算出前i项和对k取模的值然后存在一个新数组里
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]=0就先不判断，
我们可以存储每个数最后一次的位置
```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=0$说明不存在符合要求的子序列
最后按我们记录的左右下标$l$,
$r$依次输出原数组中的值即可
## 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]<<" ";
}
}
```
最后说一句：**不要抄袭**