P3131 [USACO16JAN] Subsequences Summing to Sevens S - 洛谷

问题分析

问题

给定n头奶牛的编号，找到最长的连续子段，使得子段编号总和是7的倍数，输出这个最长子段的长度。

分析

题目要求找出连续子序列的和能被7整除的最大长度。关键在于利用前缀和的性质，通过模运算（同余定理）优化计算。

前缀和：快速计算特定区间和

同余定理：（A-B）%7=0等价于A%7=B%7

快速找到满足要求（连续子序列的和能被7整除）的连续子区间

核心思路

若两个前缀和模7的结果相同，则这两个位置之间的子序列和能被7整除。因此只需记录每个模数第一次出现的位置，后续遇到相同模数时计算区间长度。

注意：在记录时就直接记录每个模数第一次出现的位置，定住一个起始值可以简化后续计算。一定不要同时记录，在后续寻找最大区间长度时难度升级。

数组实现版本

• 使用固定大小的数组存储模数首次出现的位置。
• 初始化数组为-1，表示模数未出现。
• 模数为0时默认位置为0，确保从序列开头开始的子序列能被正确处理。

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long sum=0;
        int s[]=new int[7];
        int len=0;
        for(int i=1;i<=6;i++){
            s[i]=-1;
        }
        for(int i=1;i<=n;i++){
            long id=sc.nextLong();
            sum+=id;
            int mod=(int)(sum%7);
            if(s[mod]!=-1){
                len=Math.max(len,i-s[mod]);
            }else{
                s[mod]=i;
            }
        }
        System.out.println(len);
    }
}

HashMap实现版本

• 使用哈希表动态存储模数及其首次出现的位置。
• 初始化时将模数0的位置设为0，处理逻辑与数组版本一致。
• 哈希表更灵活，适用于模数范围不确定的情况。

import java.util.Scanner;
import java.util.HashMap;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        HashMap<Integer,Integer>map=new HashMap<>();
        map.put(0,0);
        long sum=0;
        int len=0;
        for(int i=1;i<=n;i++){
            long id=sc.nextLong();
            sum+=id;
            int mod=(int)(sum%7);
            if(map.containsKey(mod)){
                len=Math.max(len,i-map.get(mod));
            }else{
                map.put(mod,i);
            }
        }
        System.out.println(len);
    }
}

关键细节

初始化处理 模数0的初始位置必须设为0，否则会遗漏从序列开头到某位置的子序列。例如，若前缀和本身能被7整除，区间长度为当前索引减0。

数据类型选择 前缀和可能超出int范围，使用long避免溢出。

性能对比

• 数组版本在模数范围固定时更高效，时间复杂度O(n)，空间复杂度O(7)。
• 哈希表版本通用性更强，但常数时间略高，适合模数范围较大的场景。