Codeforces #80 Div1 D 分块 题解

本文主要是介绍Codeforces #80 Div1 D 分块 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：Problem - D - Codeforces

本题目思路以分块思想为框架，而具体实现却也卡了我很久，思路参见2014年国家队集训论文集中王悦同的《根号算法——不只是分块》。

太多技巧和方法需要掌握了，路漫漫其修远兮！

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #define ll long long
 5 ll arr[300010];
 6 ll dp[300010];
 7 using namespace std;
 8 struct qujian {
 9     int a;
10     int b;
11     int id;
12     ll sum;
13     int operator<(const qujian& s)
14     {
15         return id < s.id;
16     }
17 }qujians[300010];
18 int cmpare(qujian a, qujian b)
19 {
20     return a.b < b.b;
21 }
22 
23 inline int read()//inline 加速读入
24 {
25     int x = 0;char c = getchar();//x代表返回值，c代表读取的字符
26     while (c < '0' || c>'9') c = getchar();//读取所有非数部分
27     while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();//如果读取的字符为数，加入返回值
28     return x;
29 }
30 
31 int main(void)
32 {
33     int n;
34     cin >> n;
35     for (int i = 1;i <= n;i++)
36         arr[i]=read();
37     int m;
38     cin >> m;
39     int sqr_n = sqrt(n);
40     for (int i = 1;i <= m;i++)
41     {
42         qujians[i].id = i;
43         qujians[i].a = read();
44         qujians[i].b = read();
45     }
46     //为什么要建立这样的结构体呢？因为我试过了创建一个Di[i：300010][j：600]来代表mod j后余数为i的集合，然后直接O（1）得到答案，而超了内存限制了。
47     //走qujians这条结构体是为了把输入和输出分开，对于每个b我进行一次递推，推导出每个余数的sum值，然后再赋给qujians【i】.sum。
48     //其中的两次sort来使得成功将输入和输出分离，是我学到的新东西。
49     sort(qujians, qujians + m, cmpare);
50     int b = -1;
51     for (int i = 1;i <= m;i++)
52     {
53         if (qujians[i].b < sqr_n)
54         {
55             if (qujians[i].b == b)
56                 qujians[i].sum = dp[qujians[i].a];
57             else
58             {
59                 b = qujians[i].b;
60                 for (int j = n;j > 0;j--)
61                 {
62                     if (b + j > n)
63                         dp[j] = arr[j];
64                     else
65                         dp[j] = dp[j + b] + arr[j];
66                 }
67                 //此处的递推方法也是让我耳目一新的，路漫漫其修远兮。。。
68                 qujians[i].sum = dp[qujians[i].a];
69             }
70         }
71         else
72         {
73             qujians[i].sum = 0;
74             for (int j = qujians[i].a;j <= n;j += qujians[i].b)
75                 qujians[i].sum += arr[j];
76         }
77     }
78     sort(qujians, qujians + m);
79     for (int i = 1;i <= m;i++)
80          printf("%lld\n",qujians[i].sum );
81     return 0;
82 }

这篇关于Codeforces #80 Div1 D 分块 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！