Codeforces Round 920 div3 ---- F Sum of Progression --- 题解

目录

F. Sum of Progression

题目大意：

思路解析：

代码实现：

F. Sum of Progression

题目大意：

????????

思路解析：

? ? ? ? 看到查询，首先想到的是预处理，要找到一个快速查找的方法，这样才能保证多次查询?的时间开销较小。

? ? ? ? 然后他是根据步长来得到答案，如果步长较长，那么n / d就会变得较小，此时直接遍历得到答案是可以接受的时间复杂度。所以当 d>=?(约为447）时，直接采取暴力求解此时k<=447。我代码里面取的350.

? ? ? ? 如果步长较小，此时k就会很大，此时我们可以想到不能再用暴力求解了，通过答案性质来寻找如何进行预处理。

? ? ? ? ? 如果s = 1， d = 2， k = 3， 那么答案为 a1 + 2 * a3 + 3 * a5

? ? ? ? ? 如果 a5后面还有其他元素，其实我们只能较方便得到 A = a1 + 2*a3 + 3*a5 + 4*a7 + 5*a9......

? ? ? ? ?同理我们也可以较方便得到B =? a7 + 2*a9 + ...... 和 C =?a7 + a9 + .........

? ? ? ? ? ?则可以发现 A - B - 3 * C，此时我们就可以得到答案，所以我们只需要后缀和预处理，就能实现快速查询? ? 这里请结合代码理解

????????????????

代码实现：

????????

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int t = (int)in.nval;
        for (int o = 0; o < t; o++) {
            in.nextToken();
            int n = (int)in.nval;
            in.nextToken();
            int q  = (int)in.nval;
            int[] arr = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                arr[i] = (int)in.nval;
            }
            long[][] a = new long[n + 1][320];
            long[][] b = new long[n + 1][320]; // 如果步长过大，此时直接遍历计算 时间复杂度并不高
            for (int i = 0; i < 320; i++) {
                b[n][i] = arr[n];
                a[n][i] = arr[n];
            }
            for (int i = n - 1; i >=  1; i--) {

                for (int j = 1; j < 320; j++) {
                    long f = 0;
                    if (i + j <= n) f = a[i + j][j];
                    a[i][j] = arr[i] + f;
                    long m = 0;
                    if (i + j <= n) m = b[i + j][j];
                    b[i][j] = a[i][j] + m;
                }
            }

            for (int i = 0; i < q; i++) {
                in.nextToken();
                int s = (int)in.nval;
                in.nextToken();
                int d = (int)in.nval;
                in.nextToken();
                int k = (int)in.nval;
                if (d >= 320){
                    long res = 0;
                    for (int j = s, m = 1; j <= n; j+=d, m++) {
                        res += (long) arr[j] * m;
                        if (m == k) break;
                    }
                    System.out.print(res + " ");
                }else{
                    if (s + k * d <= n){
                        System.out.print(b[s][d] - b[s + k * d][d] - k * a[s + k * d][d] + " ");
                    }else {
                        System.out.print(b[s][d] + " ");
                    }

                }
            }
            System.out.println();
        }
    }

}