|
一、预处理 所谓预处理，顾名思义，就是事先计算好需要的值或事先处理某些东西，有时候你会发现你做一个题目出现了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 #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 < return 0; }
POJ 1426 题意：有k个坏人k个好人坐成一圈，前k个为好人（编号1~k），后k个为坏人(编号k+1~2k)，给定m，从编号为1的人开始报数，报到m的人就要自动死去，之后从下一个人继续开始新一轮的报数。问当m为什么值时，k个坏人会在好人死亡之前全部死掉？ 分析：遇到存在环的题目的时候，可以直接直线化处理。当然也可以直接利用循环链表或者数组进行环的模拟，不过这样的程序写起来有点复杂。 这个题目直接暴力模拟求解必定TLE，需要一点数学的知识，这在里就不详细说了，即使这样，还是会超时，正确的方法便是预处理出仅有的14个答案，但既然已经知道了所有答案，而且又只有14个，那么直接把答案交上去就行了。 #include 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('%d\n', 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 #include #include #include 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: %d\n', ++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 #include 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('%d\n', 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 #include #include 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 %I64d\n', l,ans); } return 0; }
C、关于预处理的总结 预处理的目的是为了减少重复的计算从而减少时间复杂度，有时一个简单的预处理能使得算法性能显著提高。首先我们可以按思路直接写一个程序，如果复杂度太大，那么算法的优化可以从这个过程出发，思考可以对哪个算法的部分进行改进，而预处理便是一种对应的非常重要的技巧。像预处理区间和便是非常常见的，而且正如上面所示的几个题一样，一次预处理出全部的答案也是很常见的，要注意思考每个部分的联系。
二、前缀和 有前缀和, 前缀GCD, 前缀奇数个数, 前缀偶数个数, 前缀差, 等等, 都要根据自己的思想来去解决!!!，前缀思想真的还是挺考人的, 如果想不到的话.....记住 : 一般涉及到区间的什么值时, 就要用前缀思想.
HDU 4223 思路 : 目的是找一个子串, 其和的绝对值最小. 其实不用前缀思想也好写出来, 但是我一下就想了下前缀, 因为子串还是一个区间赛. 所以求一个前缀和, 并排序, 然后一个一个相减, 这样的差值就是某一个子串的最小值。 因为是排好序了的, 所以要最小一定是在某一个前缀和差值里, 然后加上一个绝对值就是了. 总之：看到区间就要联想的前缀思想。
#include #include #include #include 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 = abs(ans[i]-ans[i-1]); } printf('Case %d: ',cas++); printf('%d\n',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 #include 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 scanf('%d',&a[i]); } sort(a,a+n); //记得排序哦. int ans = 0; for(int i=0;i if(a[i] > ans + 1) //如上面所说. 主要原因是连续的数之间是有一定的联系的. break; ans += a[i]; } printf('%d\n',ans+1); } }
HDU 6025 思想：因为是要删除其中一个数，然后是总Gcd最大，一个个删肯定会T，所以删除一个，相当于求前一个区间和后一个区间的GCD，所以我们想到用求前缀GCD和后缀GCD的方法，这样我们只需要扫一遍就可以求出来最后答案。
#include #include #include #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('%d\n',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 #include #include #include 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('%d\n',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 #include #include #include #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('%d\n',ans[n]%mod); } }
|
|
|
