检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。
题面
题目描述
小奇总是在数学课上思考奇怪的问题。
给定一个长度为 的数列,以及 次询问,每次给出三个数 , 和 ,询问 的最小值(其中 )。
即模意义下的区间子串和最小值。
输入格式
第一行包含两个正整数 和 ,表示数列的长度和询问的个数。
第二行包含 个整数 。
接下来 行,每行三个数 , 和 ,代表一次询问。
输出格式
对于每次询问,输出一行一个整数表示要求的结果。
输入输出样例
输入样例 #1
4 2
8 15 9 9
1 3 10
1 4 17
输出样例 #1
2
1
数据范围及约定
- 对于 的数据,;
- 对于 的数据,;
- 对于 的数据,;
- 对于 的数据,。
思路
20 分
对于每个询问,在区间内暴力枚举子串求和、取模即可。复杂度为 。
40 分
考虑在 20 分做法的基础上优化。不难发现,区间求和可以使用前缀和优化。复杂度为 。
70 分
通过 抽屉原理 可知,当询问的区间长度大于等于 时(即 时),一定有两个前缀和相减等于 ,此时直接输出 即可。
再考虑枚举 ,可知当 是 的前驱时 最小。时间复杂度为 。
100 分
使用 std::set
维护前驱即可。时间复杂度为 。
代码
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;
}