2.17NOIP模拟赛(by hzwer) T2 小奇的序列

【题目背景】

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

【问题描述】

　　给定一个长度为 n 的数列，以及 m 次询问，每次给出三个数 l，r 和 P，询问 (a[l'] + a[l'+1] + ... + a[r']) mod P 的最小值。其中 l <= l' <= r' <= r。

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

【输入格式】

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

　　第二行为 n 个整数，为 a[1]..a[n]。

　　接下来 m 行，每行三个数 l，r 和 P，代表一次询问。

【输出格式】

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

【样例输入】

　　4 2

　　8 15 9 9

　　1 3 10

　　1 4 17

【样例输出】

【数据范围】

　　对于 20%的数据 n<=100，m<=100，p<=200

　　对于 40%的数据 n<=200，m<=1000，p<=500

　　对于 70%的数据 n<=100000，m<=10000，p<=200

　　对于 100%的数据 n<=500000，m<=10000，p<=500，1<=a[i]<=10^9

【解析】

　　这道题第一眼看过去好像没什么思路。从部分分入手吧。

　　20分：直接暴力枚举每一个区间里的点，然后求最小值即可。

　　40分：可以使用前缀和优化，然后就可以很快地求一个区间里的和。

　　70分：假如数据是绝对随机，那么如果一个区间的长度大于p，该区间中一定可以组合出所有区间和%p的余数。其中一定会有余数为0的情况，输出0即可。经过实测，这种方法可以拿90分。

　　100分：将前缀和改为区间前缀和，那么设i为当前枚举到的点，那么区间[ l , i ]的余数sum[i]=(sum[i-1]+a[i])%p。记vis[i]表示余数为i的情况在前面是否出现过。对于每一个sum[i]，我们都枚举比他小的余数（从sum[i]到0，用j表示），如果vis[j]=1，表示有这种情况。假设余数为j的位置为p，那么由模运算的性质可得：区间[ p , i ]的余数为sum[i]-j。（为什么大于sum[i]的不需要？因为这不可能是更优的解）然后，用sum[i]-j去更新答案。由于余数是从大到小枚举的，且j越大sum[i]-j越小，即该区间余数越小，如果当前能够被更新，后面的就不会再对答案造成影响了，直接break即可。最后把vis[sum[i]]设为1。注意，如果当前答案已经为0了，就直接输出（不会再更优了）。另外，不要每次都去清空前缀和数组，只需要把sum[l-1]设为0即可。

　　P.S. 这道题的正解其实是平衡树，但我并不会这个东西......

【代码】

 1 #include <bits/stdc++.h>
 2 #define N 500002
 3 
 4 using namespace std;
 5 
 6 int n,m,a[N],l,r,p,i,j,k;
 7 long long sum[N];
 8 bool e[500002];
 9 
10 long long read()
11 {
12     char c=getchar();
13     long long w=0;
14     while(c<'0'||c>'9') c=getchar();
15     while(c<='9'&&c>='0')
16     {
17         w=w*10+c-'0';
18         c=getchar();
19     }
20     return w;
21 }
22 
23 long long min(long long a,long long b)
24 {
25     if(a<b) return a;
26     return b;
27 }
28 
29 int main()
30 {
31     freopen("seq.in","r",stdin);
32     freopen("seq.out","w",stdout);
33     n=read(),m=read();
34     
35     for(i=1; i<=n; i++) a[i]=read();
36     
37     while(m--)
38     {
39         l=read(),r=read(),p=read();
40         
41         if(r-l+1>p)
42         {
43             cout<<"0"<<endl;
44             continue;
45         }
46         
47         for(i=1; i<=p; i++) e[i]=0;
48          
49         e[0]=1,sum[l-1]=0;
50         
51         long long ans=1<<30;
52         
53         for(i=l; i<=r; i++)
54         {
55             sum[i]=(sum[i-1]+a[i])%p;
56             
57             for(j=sum[i]; j>=0; j--)
58             {
59                 if(e[j])
60                 {
61                     ans=min(ans,sum[i]-j);
62                     
63                     break;
64                 }
65             }
66             
67             if(ans==0) break;
68             
69             e[sum[i]]=1;
70         }
71         
72         printf("%lld
",ans);
73     }
74     
75     return 0;
76 }

P.S. 转载自LSlzf