2021广东工业大学十月月赛 F-hnjhd爱序列(F-hnjhd love series of October 2021 Guangdong University of Technology)

题目:GDUTOJ | hnjhd爱序列 (gdutcode.cn)

一开始是用双指针从尾至头遍历,但发现会tle!!

后来朋友@77给出了一种用桶的做法,相当于是用空间换时间了。

其中用到的一个原理是:如果两个数对x同余,那这两个数的差必定可以被x整除;

于是利用了后缀和,当两个后缀和对m同余,那这两个后缀和的差,也就是那一段序列的和可以被m整除!(真的太妙了)

代码:

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
ll s[N], pre[N], buk[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll m, ans = 0, fl = 0, fr = 0;
    cin >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> s[i];
    }
    for (int i = m; i >= 1; --i)
    {
        pre[i] = pre[i + 1] + s[i];
    }
    for (int i = m; i >= 1; --i)
    {
        if (pre[i] % m == 0)
        {
            cout << i << " " << m << endl;
            break;
        }
        if (buk[pre[i] % m] != 0)
        {
            cout << i << " " << buk[pre[i] % m] - 1 << endl;
            break;
        }
        buk[pre[i] % m] = i;
    }
    return 0;
}
————————

Title: gdutoj | hnjhd love sequence (gdutcode. CN)

At first, I used double pointers to traverse from tail to head, but I found that it would tle!!

Later, the < strong > friend @ 77 < / strong > gave a bucket method, which is equivalent to trading space for time.

One of the principles used is: if two numbers are congruent to x, the difference between the two numbers must be divided by X;

So the suffix sum is used. When the two suffix sums are congruent to m, the difference between the two suffix sums, that is, the sum of that sequence, can be divided by m! (really wonderful)

code:

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
ll s[N], pre[N], buk[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll m, ans = 0, fl = 0, fr = 0;
    cin >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> s[i];
    }
    for (int i = m; i >= 1; --i)
    {
        pre[i] = pre[i + 1] + s[i];
    }
    for (int i = m; i >= 1; --i)
    {
        if (pre[i] % m == 0)
        {
            cout << i << " " << m << endl;
            break;
        }
        if (buk[pre[i] % m] != 0)
        {
            cout << i << " " << buk[pre[i] % m] - 1 << endl;
            break;
        }
        buk[pre[i] % m] = i;
    }
    return 0;
}