A28688. 给定包含n个整数的数列，从中选取-段连续子数列，使其元素之和能被k整除。请找出符合要求的最长连续子数列并输出其长度以及子数列本身;如果符合要求的最长连续子数列有多个，则输出起始位置最靠后的那个子数列。如果不存在符合要求的子数列，则输出-1。例如:n=7,k=7,数列为7、3、4、1、5、14、9;连续子数列 {7}、{7, 3, 4}、{3, 4}、和{5，14, 9} 的和都能被7整除…
填空题
困难
知识点
题目描述
题目描述
给定包含n个整数的数列，从中选取-段连续子数列，使其元素之和能被k整除。
请找出符合要求的最长连续子数列并输出其长度以及子数列本身;如果符合要求的最长连续子数列有多个，则输出起始位置最靠后的那个子数列。如果不存在符合要求的子数列，则输出-1。
例如:n=7,k=7,数列为7、3、4、1、5、14、9;
连续子数列 {7}、{7, 3, 4}、{3, 4}、和{5，14, 9} 的和都能被7整除;
其中最长的连续子数列有 {7，3， 4} 和 {5，14，9}， 起始位置最靠后的是{5，14，9}。
故符合要求的最长连续子数列长度为3,子数列为5 14 9。
输入描述
第一行输入两个整数n和k，整数之间以一个空格隔开
第二行输入n个整数(1≤整数≤)104，整数之间以一个空格隔开
输出描述
如果存在符合要求的最长连续子数列,则输出为两行第一行输出一个整数，表示最长连续子数列的长度第二行输出若干个整数，表示起始位置最靠后的最长连续子数列,整数之间以一个空格隔开
如果不存在，则输出-1
输入样例
7 7
7 3 4 1 5 14 9输出样例
3
5 14 9参考答案
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int s[N],a[N],n,k; //定义数组s用于存储前缀和对k取模的结果，a用于存储输入的数列
unordered_map<int,int> mp; //使用unordered_map<int,int> mp来存储每个前缀和第一次出现的位置。
int l,r,ans; //定义变量l、r和ans分别用于记录最长子数组的起始位置、结束位置和长度。
int main()
{
cin>>n>>k; //读取数列的长度n和要整除的数k
mp[0]=0; //初始化哈希表，将前缀和为0（即初始状态）的位置设为0。
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=(s[i-1]+a[i])%k; //遍历数组a，读取每个元素，并计算前缀和对k取模的结果存储在s数组中
if(!mp.count(s[i])) //如果之前还没有出现过记录， mp.count(const key_type& k)：对于 unordered_map，总是返回 0 或 1，表示键 k 是否存在。
{
mp[s[i]]=i; //检查当前前缀和s[i]是否已经在哈希表中。如果不在，则记录其位置。
}
else
{
if(ans<i-mp[s[i]]) //出现过则说明这段区间是k的倍数，更新最大值
{
ans=i-mp[s[i]];
l=mp[s[i]],r=i; //更新起始位置，结束位置
}
else if(ans==i-mp[s[i]])//区间长度一样 则更新l更靠后
{
if(mp[s[i]]>l)
{
l=mp[s[i]],r=i; //更新为后面的位置
}
}
}
}
cout<<ans<<endl;
for(int i=l+1;i<=r;i++)
cout<<a[i]<<' ';
return 0;
}
上一题
下一题