有前缀和, 前缀GCD, 前缀奇数个数, 前缀偶数个数, 前缀差, 等等, 都要根据自己的思想来去解决!!!，前缀思想真的还是挺考人的, 如果想不到的话.....记住 : 一般涉及到区间的什么值时, 就要用前缀思想.
HDU --- 4223
思路 : 目的是找一个子串, 其和的绝对值最小. 其实不用前缀思想也好写出来, 但是我一下就想了下前缀, 因为
子串还是一个区间赛. 所以求一个前缀和, 并排序, 然后一个一个相减, 这样的差值就是某一个子串的最小值.
因为是排好序了的, 所以要最小一定是在某一个前缀和差值里, 然后加上一个绝对值就是了.
总之 ： 看到区间就要联想的前缀思想.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace 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 namespace 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的方法， 这样我们只需要扫一遍就可以求出来最后答案.
AC Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(x) memset(x,0,sizeof(x))
using namespace 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 题目 ：(维护前缀和)
Description
已知一个长度为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”的对数.
Sample Input
1
5 2
1 5 3 4 2
1 5
2 3
Sample Output
6
0
思路 ： 只有当一个奇数加一个偶数时才满足题目要求. 所以知道该区间中奇数和偶数的个数就可以直接算.
AC Code
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace 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]单独算一次的情况
AC code
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define mod 1000000007
using namespace 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; //这样做的目的是为了防止出现负数(我是
//wa试出来的)因为我找不到具体样列会出现负数.所以必须这才能A .
}
vis[a[i]] = i;
}
printf("%d\n",ans[n]%mod);
}
}
