P3131-Subsequences Summing to Sevens S - 从萌新到萌新的成长历程

题目传送门

题目思路

首先来看这限制，明显不能暴力模拟。

所以利用前缀和。

思路是开一个dp数组，写入上半三角区，i->0-n,j->i-0，这个全部加上去，最后全部的前缀和都存在数组里，再去找就行了。

会有两个问题，首先50000的规模，导致了会MLE。。然后因为每次只操作一列，因此可以只用N的数组来存。

操作一顿，还是寄，TLE了，草，但是没办法，n方的复杂度，200ms肯定是过不了的。。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> dp(n, 0);
    int flong = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> dp[i];
        if (dp[i] % 7 == 0 && flong == 0)
            flong = 1;
        for (int j = i - 1; j >= 0; j--)
        {
            dp[j] += dp[i];
            if (dp[j] % 7 == 0 && i - j + 1 > flong)
                flong = i - j + 1;
        }
    }
    cout << flong << endl;
    return 0;
}

因此要优化到n的复杂度。。-_-||

当两个前缀和模7相同时，区间就能被7整除，求出前缀和每个余数对应的最小的索引和最大的索引从而算出最长区间长度，可以边读入边记录。端点模7为0到6的最长区间长度的最大值就是答案

注意要将0的左端点初始化为0，不是未初始化状态

AC代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    long long s = 0;
    int flong = 0;
    int dpl[7] = {0, -1, -1, -1, -1, -1, -1};
    int dp4[7] = {-1, -1, -1, -1, -1, -1, -1};
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        s = (s + a) % 7;
        if (dpl[s] == -1)
            dpl[s] = i;
        dp4[s] = i;
    }
    for (int i = 0; i < 7; i++)
        flong = max(flong, dp4[i] - dpl[i]);
    cout << flong << endl;
    return 0;
}