Skip to content

S2OJ - 1230. 小奇的数列

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

题面

题目描述

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

给定一个长度为 nn 的数列，以及 mm 次询问，每次给出三个数 ll，rr 和 pp，询问 (al′+al′+1+⋯+ar′)(modp)(a_{l'} + a_{l' + 1} + \dots + a_{r'}) \pmod p 的最小值（其中 l≤l′≤r′≤rl \leq l' \leq r' \leq r）。

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

输入格式

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

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

接下来 mm 行，每行三个数 ll，rr 和 pp，代表一次询问。

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

2
1

数据范围及约定

  • 对于 20%20\% 的数据，n≤100,m≤100,p≤200n \leq 100, m \leq 100, p \leq 200；
  • 对于 40%40\% 的数据，n≤200,m≤1000,p≤500n \leq 200, m \leq 1000, p \leq 500；
  • 对于 70%70\% 的数据，n≤100000,m≤10000,p≤200n \leq 100000, m \leq 10000, p \leq 200；
  • 对于 100%100\% 的数据，n≤500000,m≤10000,p≤500,1≤ai≤109n \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 时（即 r−l≥pr - l \geq p 时），一定有两个前缀和相减等于 00，此时直接输出 00 即可。

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

100 分

使用 std::set 维护前驱即可。时间复杂度为 O(mplog⁡p)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;
}