一、预处理
所谓预处理，顾名思义，就是事先计算好需要的值或事先处理某些东西，有时候你会发现你做一个题目出现了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("%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<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: %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<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("%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<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 %I64d\n", 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("%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<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("%d\n",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("%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<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("%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<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("%d\n",ans[n]%mod);
}
}
支付宝扫一扫
