Silver: Subsequences Summing to Sevens

P3131 USACO16JAN] Subsequences Summing to Sevens S

其实也是简单题，只需要发现一个规律：取模7之后再存​psum里面的话，当​psum[i]=psum[j]，​psum[j]-psum[i-1]是7的倍数。以下是推导：

a_1 \bmod 7=c\\ (a_1+a_2) \bmod 7=(a_1\bmod7+a_2\bmod7)\bmod7=d\\ (a_1+a_2+...+a_n)\bmod7=k=(a_1+a_2+...+a_j)\bmod7, j<k\\ \implies (a_j+...+a_n)\bmod7=0

那么问题变为了：

\max_{j<n,psum[j]=psum[n]}(n-j)

所以比起​\mathcal{O}(N^2)的枚举两端点，只需要遍历​[0,6]再遍历​[0,n]，时间上是​\mathcal{O}(n)。

代码：

/*
 * Created by: Friedforks
 * Date: 2024-11-11
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    vector<int> psum(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> psum[i];
        psum[i] += psum[i - 1];
        psum[i] %= 7;
    }

    // debug
    // for (int i = 0; i <= n; i++) {
    //     cout << psum[i] << " ";
    // }
    // cout << endl << endl;
    // cout << endl;
    // for (int i = 0; i <= n; i++) {
    //     cout << psum[i] % 7 << " ";
    // }

    // iterate all possible remainder 
    for (int i = 0; i <= 6; i++) {
        int first = -1, last = -1;
        // find the index of first occurence of i
        for (int j = 0; j <= n; j++) {
            if (psum[j] == i) {
                first = j;
                break;
            }
        }
        // find the index of last occurence of i
        for (int j = n; j >= 0; j--) {
            if (psum[j] == i) {
                last = j;
                break;
            }
        }
        // debug
        // cout << i << ' ' << first << ' ' << last << endl;
        if (first != -1 && last != -1) {
            // maximum of the difference between indices
            ans = max(ans, last - first);
        }
    }
    cout << ans << endl;
    return 0;
}