NOIP复赛复习(十六)预处理与前缀和

一、预处理

所谓预处理,顾名思义,就是事先计算好需要的值或事先处理某些东西,有时候你会发现你做一个题目出现了TLE,原因就是重复的计算会导致效率不高(或者说你的预处理不够“优雅”)。

A、直接把结果预处理

XTUOJ 1052

题意:某一个数字集合定义如下:

1.0属于这个集合;

2.如果x属于这个集合,那么2x+1,3x+1也属于这个集合;

3.集合只包含按增序排列的前100000个元素。

集合按增序排列,根据输入的元素序号,输出对应的元素值。

输入

每行一个整数n(n<100000),表示元素的序号(从0开始记数),如果是-1,则输入结束。

输出

每行输出对应元素的值。

Sample Input

0
1
2
3
4
5
-1

Sample Output

0
1
3
4
7
9

分析:很明显,不能也不好直接判断是否存在于这个集合中,只需要把所有存在于这个集合中标记,并且预处理这些元素的序号,之后输出就行了,那么一次预处理便可以知道所有序号对应的元素了。
#include<iostream>
#define MAX 2000001
using name space std;
int a[100010], b[3*MAX];
int main() {
int n, i, j;
b[0] = 1;
for (i = 0; i < MAX; i++)
if (b[i] == 1) b[2*i+1] = b[3*i+1] =1;
for (i = 0, j = 0; i < 100000; j++)
if (b[j] == 1) a[i++] = j;
while (cin >> n, n != 1) cout <<a[n] << endl;
return 0;
}

POJ 1426

题意:有k个坏人k个好人坐成一圈,前k个为好人(编号1~k),后k个为坏人(编号k+1~2k),给定m,从编号为1的人开始报数,报到m的人就要自动死去,之后从下一个人继续开始新一轮的报数。问当m为什么值时,k个坏人会在好人死亡之前全部死掉?

分析:遇到存在环的题目的时候,可以直接直线化处理。当然也可以直接利用循环链表或者数组进行环的模拟,不过这样的程序写起来有点复杂。

这个题目直接暴力模拟求解必定TLE,需要一点数学的知识,这在里就不详细说了,即使这样,还是会超时,正确的方法便是预处理出仅有的14个答案,但既然已经知道了所有答案,而且又只有14个,那么直接把答案交上去就行了。
#include<cstdio>
int ans[15] = {0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657,2504881, 13482720};
int main() {
int n;
while (scanf("%d", &n), n)printf("%dn", ans[n]);
return 0;
}

UVA 12716

题意:给定一个整数n,求出有多少对整数a,b满足1<=b<=a<=n且gcd(a,b)=aXOR b.

分析:最容易想到的方法是枚举a,b,双重循环加上求gcd,总复杂度为O(n*n*logn),绝对无法承受。如何减少枚举呢?注意到亦或运算的性质,如果a^b=c,那么a^c=b,既然c为a,b的最大公约数的话,那么我们可以从枚举a和c出发,那么就是枚举所有因子c及其可能的倍数a,和素数筛法一样,这样复杂度为O(nlogn*logn),n最大为30000000,复杂度还是有点高,怎么减少复杂度呢?这就要通过一点数学知识或者找规律发现了,通过打印出所有满足条件的a,b,c可以发现a+b=c,所以可以将复杂度降为O(n*logn),但是题目是多样例输入,如果每次都需要O(n*logn)计算答案的话,还是会超时,观察便可得知其实在计算n以内满足条件的a,b对数时比n小的数以内的对数都已经计算出来了,也就是说不需要重复计算了,那么我们可以通过一次预处理,在计算的过程中统计每个a组合时的对数,之后循环遍历一次全部加起来就可以知道每个n以内的答案了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using name space std;
const int N = 30000000;
int a[N+5];
void pretreat() {
for (int i = 1; i <= 15000000; i++){
for (int j = i<<1; j <= N; j+= i) {
if ((j ^ (j-i)) == i) a[j]++;
}
}
for (int i = 2; i <= N; i++) a[i] +=a[i-1];
}
int main() {
pretreat();
int t, ca = 0;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
printf("Case %d: %dn", ++ca,a[n]);
}
return 0;
}

B、把需要用的预处理

比较常见的基本就是三个:预处理素数、预处理组合数、预处理前缀和。

首先举个比较经典的例子:素数打表

判断是否素数有3种方式:O(sqrt(n)的简单素性测试、埃氏筛法,以及Miller_Rabin 算法进行素数测试。

如果需要进行大量的用到素数或者判断素数,则可以埃氏筛法打表出所有的素数。

XTUOJ 1237

题目描述:如果n和n+2都是素数,我们称其为孪生素数,比如3和5,5和7都是孪生素数。给你一个区间[a,b],请问期间有多少对孪生素数?

输入

第一行是一个整数K(K≤ 10000),表示样例的个数。以后每行一个样例,为两个整数,a和b,1≤a≤b≤5000000。

输出

每行输出一个样例的结果。

样例输入

5
13
110
1100
11000
15000000

样例输出

0
2
8
35
32463

分析:计算区间内个数的题目一般满足区间减法性质,但是不能一概而论,具体题目具体分析,就像这题一对孪生素数是跨越了3个数,要分情况考虑。

首先直接标记出所有的素数,令g[x]为1到x+2这个区间内孪生素数的对数,要统计出数量,遍历一次即可,只需要一次预处理就可以计算出所有的g[x],之后便可以O(1)计算出所有1到x+2这个区间内孪生素数的对数了。

如果输入的区间长度小于2,那么必定没有,如果长度大于2,稍加思考便可以得知答案即为g[b-2]-g[a-1]。
#include<cstdio>
#include<cmath>
const int N = 5000001;
int f[N], g[N];
int main() {
int up = sqrt(N);
for (int i = 2; i <= up; i++)
if(!f[i]) for (int j = i*i; j <= N; j+= i) f[j] = 1;
for (int i = 3; i < N-1; i += 2)
g[i+1] = g[i] = g[i-1] + !(f[i]||f[i+2]);
int t;
scanf("%d", &t);
while (t--) {
int a, b;
scanf("%d %d", &a,&b);
b-a < 2 ? puts("0") :printf("%dn", g[b-2] -g[a-1]);
}
return 0;
}

CF 231C

题意:给定一个数组,每次可以给任意元素加1,这样的操作不能超过k次,求操作不超过k次后数组中一个数能够出现的最多次数,以及能够以这个次数出现的最小的数。

分析:这个题目明显具有单调性,这样的话就可以进行二分搜索求取最大次数了。怎么判断假定的解是否可行呢?既然只能是加1,而且又不超过k次,那么首先将数组排序,假设搜索的次数为m,那么i从第m个数循环到最后一个数,只要满足了次数不小于k就立即退出循环,这样找到的便一定是出现m次的最小的数,但是这个判断的过程就是第m个数与其之前的m-1个数的差之和要不大于k,如果每次都直接加上差进行判断必定超时,因为二分搜索加循环判断的时间复杂度太高,那么最好的优化就是直接之前预处理,求出第1个数到第m个数区间的和,后面判断的时候直接就是o(1)计算区间的和了。
#include<cstdio>
#include<algorithm>
#include<cstring>
using name space std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 100010;
LL a[N], sum[N];
int main() {
int n; LL k;
while (~scanf("%d %I64d", &n,&k)) {
for (int i = 1; i <= n; i++)scanf("%I64d", &a[i]);
sort(a + 1, a + 1+n);
int r = INF, l = 0;
sum[1] = a[1];
for (int i = 2; i <= n; i++) sum[i] =a[i] + sum[i-1];
LL ans;
while (r - l > 1) {
int m = (r+l) / 2;
if (m > n) { r = m; continue;}
int flag = 0;
for (int i = m; i <= n; i++){
if ((m-1)*a[i] - sum[i-1]+sum[i-m] <= k){
flag = 1; ans = a[i];
break;
}
}
flag ? l = m : r = m;
}
printf("%d %I64dn", l,ans);
}
return 0;
}

C、关于预处理的总结 

预处理的目的是为了减少重复的计算从而减少时间复杂度,有时一个简单的预处理能使得算法性能显著提高。首先我们可以按思路直接写一个程序,如果复杂度太大,那么算法的优化可以从这个过程出发,思考可以对哪个算法的部分进行改进,而预处理便是一种对应的非常重要的技巧。像预处理区间和便是非常常见的,而且正如上面所示的几个题一样,一次预处理出全部的答案也是很常见的,要注意思考每个部分的联系。

二、前缀和

有前缀和, 前缀GCD, 前缀奇数个数, 前缀偶数个数, 前缀差, 等等, 都要根据自己的思想来去解决!!!,前缀思想真的还是挺考人的, 如果想不到的话.....记住 : 一般涉及到区间的什么值时, 就要用前缀思想.

HDU 4223

思路 : 目的是找一个子串, 其和的绝对值最小. 其实不用前缀思想也好写出来, 但是我一下就想了下前缀, 因为子串还是一个区间赛. 所以求一个前缀和, 并排序, 然后一个一个相减, 这样的差值就是某一个子串的最小值。

因为是排好序了的, 所以要最小一定是在某一个前缀和差值里, 然后加上一个绝对值就是了.

总之:看到区间就要联想的前缀思想。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using name space std;
const int maxn=1e3+5;
int cas=1;
int ans[maxn];
int a[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
memset(ans,0,sizeof(ans));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
ans[i]=ans[i-1]+a[i];
sort(ans,ans+n+1);
for(int i=0;i<=n;i++)
printf("%d ",ans[i]);
printf("n");
int res=ans[1]-ans[0];
for(int i=1;i<=n;i++){
if(abs(ans[i]-ans[i-1])<res)
res = abs(ans[i]-ans[i-1]);
}
printf("Case %d: ",cas++);
printf("%dn",res);
}
}

题目描述 : 给你n个数(n < 1e5),问不能拼出的最小数是多少(从 1 开始算), 比如:1,2,3,4,5 不能拼出最小的数16。1,2,4,5 不能拼出的最小数为13。2,3,4,5不能拼出的数为 1。

输入的n有多组数据, 每一个数<1e9。

思路:前缀和思想. 如果后面的数字如果大于前缀和+1 说明他和区间没有交集前缀和+1 这个数字就达不到就不连续了, 就输出此时的前缀和+1。
#include<cstdio>
#include<algorithm>
using name space std;
const int maxn=1e5+5;
int a[maxn];
int main()
{
int n;
while(~scanf("%d",&n)){
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);  //记得排序哦.
int ans = 0;
for(int i=0;i<n;i++){
if(a[i] > ans + 1)  //如上面所说. 主要原因是连续的数之间是有一定的联系的.
break;
ans += a[i];
}
printf("%dn",ans+1);
}
}

HDU 6025

思想:因为是要删除其中一个数,然后是总Gcd最大,一个个删肯定会T,所以删除一个,相当于求前一个区间和后一个区间的GCD,所以我们想到用求前缀GCD和后缀GCD的方法,这样我们只需要扫一遍就可以求出来最后答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(x) memset(x,0,sizeof(x))
using name space std;
const int maxn=1e5+5;
const int inf=1e9;
int qian[maxn],hou[maxn];
int a[maxn];
int main()   //思路求前缀和后缀GCD这样删数的复杂度是n.
{
int t;
scanf("%d",&t);
while(t--){
CLR(qian);
CLR(hou);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
qian[1]=a[1];
hou[1]=a[n];
for(int i=2;i<=n;i++){
qian[i]=__gcd(qian[i-1],a[i]);
}
for(int i=2;i<=n;i++){
hou[i]=__gcd(hou[i-1],a[n-i+1]);
}
int maxx=max(qian[n-1],hou[n-1]);
for(int i=2;i<=n-1;i++){
int m=__gcd(qian[i-1],hou[n-i]);
if(m>maxx)
maxx=m;
}
printf("%dn",maxx);
}
}

SHU 1952

已知一个长度为N的数列A[1..N]。

现在给出Q次查询,每次查询一个区间[L, R]。

对于每一个区间,求使得(A[i] + A[j])为奇数的(i, j)的对数 (L <= i< j <= R)。

Input

多组数据,第一行有一个整数T表示数据组数。(T <= 5)

之后有T组数据,每组数据第一行为两个整数N和Q,表示数列长度及查询数量。

(1<= N, Q <= 100000)

接着有一行N个元素的数列A[1..N]。(1 <= A[i]<= 1000)

接下来Q行,每行有两个整数L, R,表示查询的区间。(1 <= L<= R <= N)

Output

对于每次询问,输出一行数字,表示区间”Odd Pair”的对数.

SampleInput

1
52
15 3 4 2
15
23
SampleOutput
6
0

思路:只有当一个奇数加一个偶数时才满足题目要求. 所以知道该区间中奇数和偶数的个数就可以直接算。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using name space std;
const int maxn=1e5+5;
int cas=1;
struct math{
int odd; //结构体中的变量会自动付初值.
int ans;
}s[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
if(x&1){
s[i].odd += s[i-1].odd +1;
//每一个继承前面那个的奇数和偶数个数.
s[i].ans += s[i-1].ans;
}
else{
s[i].ans += s[i-1].ans + 1;
s[i].odd += s[i-1].odd;
}
}
while(q--){
int l,r;
scanf("%d%d",&l,&r);
int a = s[r].odd - s[l-1].odd;
int b = s[r].ans - s[l-1].ans;
printf("%dn",a*b);
}
}
}

FZU 2129

思维题,也可以用前缀和思想,只是有点难理解。所以这儿就不给这种解法了,给一种易理解的解法。

思路:设ans(k)为k长度的子序列的个数,,a[k]为第k个子序列,那么如果a[k]和前面的数都不相同的情况下,ans(k)]=ans(k-1)*2+1;如果前面的数字出现过的话,那么就要减去最近一次出现a[k]这个数值的地方-1的子序列个数,因为这些算重复的了,而且+1也没有了,因为ans(a[k]上次出现的位置)包括了a[k]单独算一次的情况。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define mod 1000000007
using name space std;
const int maxn=1e6+5;
int cas=1;
int ans[maxn],a[maxn];
int vis[maxn];
int main()
{
int n;
while(~scanf("%d",&n)){
memset(ans,0,sizeof(ans));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
if(vis[a[i]]==0){
ans[i] = (ans[i-1]*2+1)%mod;
}
else{
ans[i] = ((ans[i-1]*2 -ans[vis[a[i]]-1])%mod+mod)%mod;
//这样做的目的是为了防止出现负数(我是试出来的)因为我找不到具体样列会出现负数.所以必须这才能A。
}
vis[a[i]] = i;
}
printf("%dn",ans[n]%mod);
}
}

本文链接:NOIP复赛复习(十六)预处理与前缀和

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:少儿编程网,谢谢!^^


*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
为什么越来越多家长选择信息学竞赛?
为什么越来越多家长选择信息学竞赛?
孩子学完各个阶段的编程课程能够参加哪些比赛?
孩子学完各个阶段的编程课程能够参加哪…
信息学竞赛必经之路–NOIP(内含2018报名方式说明)
信息学竞赛必经之路–NOIP(内含20…
我的孩子从来没有接触过编程,0基础能不能学?
我的孩子从来没有接触过编程,0基础能不…
新手想参加信息学竞赛NOIP ,如何入门进阶?
新手想参加信息学竞赛NOIP ,如何入门进…
NOIP2017 作者
NOI官网发布了2017年全国青少年信息学奥林匹克联赛(NOIP2017)的报名通知。NOIP2017将于2017年10月及11月分别举行初赛和复赛,有意向参加比赛的考生,即日起至10月10日可报名。