Skip to content

S2OJ - 1230. 小奇的数列

题解约 1 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

小奇总是在数学课上思考奇怪的问题。

给定一个长度为 nn 的数列,以及 mm 次询问,每次给出三个数 llrrpp,询问 (al+al+1++ar)(modp)(a_{l'} + a_{l' + 1} + \dots + a_{r'}) \pmod p 的最小值(其中 llrrl \leq l' \leq r' \leq r)。

即模意义下的区间子串和最小值。

输入格式

第一行包含两个正整数 nnmm,表示数列的长度和询问的个数。

第二行包含 nn 个整数 a1,,ana_1, \dots, a_n

接下来 mm 行,每行三个数 llrrpp,代表一次询问。

输出格式

对于每次询问,输出一行一个整数表示要求的结果。

输入输出样例

输入样例 #1

4 2
8 15 9 9
1 3 10
1 4 17

输出样例 #1

2
1

数据范围及约定

  • 对于 20%20\% 的数据,n100,m100,p200n \leq 100, m \leq 100, p \leq 200
  • 对于 40%40\% 的数据,n200,m1000,p500n \leq 200, m \leq 1000, p \leq 500
  • 对于 70%70\% 的数据,n100000,m10000,p200n \leq 100000, m \leq 10000, p \leq 200
  • 对于 100%100\% 的数据,n500000,m10000,p500,1ai109n \leq 500000, m \leq 10000, p \leq 500, 1 \leq a_i \leq 10^9

思路

20 分

对于每个询问,在区间内暴力枚举子串求和、取模即可。复杂度为 O(mn3)O(mn^3)

40 分

考虑在 20 分做法的基础上优化。不难发现,区间求和可以使用前缀和优化。复杂度为 O(mn2)O(mn^2)

70 分

通过 抽屉原理 可知,当询问的区间长度大于等于 pp 时(即 rlpr - l \geq p 时),一定有两个前缀和相减等于 00,此时直接输出 00 即可。

再考虑枚举 rr,可知当 kksumr\mathit{sum}_{r} 的前驱时 sumrk\mathit{sum}_{r} - k 最小。时间复杂度为 O(mp2)O(mp^2)

100 分

使用 std::set 维护前驱即可。时间复杂度为 O(mplogp)O(mp \log p)

代码

40 分
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

const int N = 100005;

int n, m, l, r, p, a[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (m--) {
        cin >> l >> r >> p;
        int ans = p;
        for (int i = l; i <= r; i++) {
            int sum = 0;
            for (int j = i; j <= r; j++) {
                sum = (sum + a[j]) % p;
                ans = std::min(ans, sum);
            }
        }
        cout << ans << endl;
    }
    return 0;
}
70 分

OJ 上的数据比较水,所以这样也能 A 掉。

提交记录:0616685

#include <cstring>
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

const int N = 500005;
const int P = 505;

int n, m, l, r, p, a[N];
long long sum[N];
bool vis[P];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (m--) {
        long long ans = 0x3f3f3f3f;
        memset(vis, 0x00, sizeof(vis));
        vis[0] = true;
        cin >> l >> r >> p;
        if (r - l >= p) {
            cout << 0 << endl;
            continue;
        }
        sum[l - 1] = 0;
        for (int i = l; i <= r; i++) {
            sum[i] = (sum[i - 1] + a[i]) % p;
            for (int j = sum[i]; j >= 0; j--) {
                if (vis[j]) {
                    ans = std::min(ans, sum[i] - j);
                }
            }
            vis[sum[i]] = true;
        }
        cout << ans << endl;
    }
    return 0;
}
100 分

提交记录:d5b8f54

#include <iostream>
#include <set>

using std::cin;
using std::cout;
using std::endl;

const int N = 500005;

int n, m, l, r, p, a[N];
long long sum[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (m--) {
        long long ans = 0x3f3f3f3f;
        cin >> l >> r >> p;
        if (r - l >= p) {
            cout << 0 << endl;
            continue;
        }
        std::set<long long> s;
        s.insert(0);
        sum[l - 1] = 0;
        for (int i = l; i <= r; i++) {
            sum[i] = (sum[i - 1] + a[i]) % p;
            ans = std::min(ans, sum[i] - *(--s.upper_bound(sum[i])));
            s.insert(sum[i]);
        }
        cout << ans << endl;
    }
    return 0;
}