养花

Posted on Edited on In

题目大意：小 C 在家种了 n 盆花, 每盆花有一个艳丽度 ai.在接下来的 m 天中, 每天早晨他会从一段编号连续的花中选择一盆摆放在客厅, 并在晚上放回. 同时每天有特定的光照强度 ki, 如果这一天里摆放在客厅的花艳丽度为 x, 则他能获得的喜悦度为 x mod ki.他希望知道, 每一天他能获得的最大喜悦度是多少.(1e5的数据两)

我的思路接近接近正解：对于每一个位置，提前预处理好，膜1~1e5得出来的每一个结果

然后去随便弄个数据结构去max

正解：分块，考虑把艳丽值桶排，用\(f_i\)表示艳丽值小于等于i的最大值是多少，用\(g_i\)表示这段区间被i模的最大值是多少

显然可以得到：\(g_i=max(f_{i\times j-1}\bmod i)(1\leq j\;and\;i\times j\leq 1e5)\)

代码如下：（来自_plxer大佬)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5;
const int S = 1e3;
int mx[103][N + 5], f[N + 5];
int n, m, a[N + 5];

int main()
{
    n = read(); m = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    int num = (n - 1) / S;
    for (int i = 0; i <= num; i ++)
    {
        memset(f, 0, sizeof f);
        int l = i * S + 1, r = min(n, (i + 1) * S);
        for (int j = l; j <= r; j ++) f[a[j]] = a[j];
        for (int j = 1; j <= N; j ++) f[j] = max(f[j - 1], f[j]);
        for (int j = 1; j <= N; j ++)
            for (int k = 0; k <= N; k += j)
                mx[i][j] = max(mx[i][j], f[min(k + j - 1, N)] - k);
    }
    for (int i = 1, l, r, k; i <= m; i ++)
    {
        int ans = 0;
        l = read(); r = read(); k = read();
        int lx = (l - 1) / S, rx = (r - 1) / S;
        for (int j = lx + 1; j < rx; j ++) ans = max(ans, mx[j][k]);
        for (int j = l; j <= min(r, (lx + 1) * S); j ++) ans = max(ans, a[j] % k);
        for (int j = max(l, rx * S + 1); j <= r; j ++) ans = max(ans, a[j] % k);
        printf("%d\n", ans);
    }

    return 0;
}