有前綴和, 前綴GCD, 前綴奇數(shù)個(gè)數(shù), 前綴偶數(shù)個(gè)數(shù), 前綴差, 等等, 都要根據(jù)自己的思想來(lái)去解決!!!惊窖，前綴思想真的還是挺考人的, 如果想不到的話.....記住 : 一般涉及到區(qū)間的什么值時(shí), 就要用前綴思想.
HDU --- 4223
思路 : 目的是找一個(gè)子串, 其和的絕對(duì)值最小. 其實(shí)不用前綴思想也好寫出來(lái), 但是我一下就想了下前綴, 因?yàn)?br>
子串還是一個(gè)區(qū)間賽. 所以求一個(gè)前綴和, 并排序, 然后一個(gè)一個(gè)相減, 這樣的差值就是某一個(gè)子串的最小值.
因?yàn)槭桥藕眯蛄说? 所以要最小一定是在某一個(gè)前綴和差值里, 然后加上一個(gè)絕對(duì)值就是了.
總之 ： 看到區(qū)間就要聯(lián)想的前綴思想.
#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個(gè)數(shù)(n < 1e5)， 問不能拼出的最小數(shù)是多少(從 1 開始算), 比如 ： 1,2,3,4,5 不能拼出最小
的數(shù)為16 . 1,2,4,5 不能拼出的最小數(shù)為13. 2,3,4,5不能拼出的數(shù)為 1 .
輸入的n有多組數(shù)據(jù), 每一個(gè)數(shù)<1e9.*/
// 思路 ： 前綴和思想. 如果后面的數(shù)字如果大于前綴和+1 說(shuō)明他和區(qū)間沒有交集 前綴和+1 這個(gè)數(shù)字就達(dá)不到 就不連續(xù)了, 就輸出此時(shí)的前綴和+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) //如上面所說(shuō). 主要原因是連續(xù)的數(shù)之間是有一定的聯(lián)系的.
break;
ans += a[i];
}
printf("%d\n",ans+1);
}
}
HDU --- 6025
思想 ： 因?yàn)槭且獎(jiǎng)h除其中一個(gè)數(shù), 然后是總Gcd最大, 一個(gè)個(gè)刪肯定會(huì)T, 所以刪除一個(gè), 相當(dāng)于求前一個(gè)區(qū)間和后一個(gè)區(qū)間的GCD,
所以我們想到用求前綴GCD和后綴GCD的方法， 這樣我們只需要掃一遍就可以求出來(lái)最后答案.
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這樣刪數(shù)的復(fù)雜度是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 題目 ：(維護(hù)前綴和)
Description
已知一個(gè)長(zhǎng)度為N的數(shù)列A[1..N]虚青。
現(xiàn)在給出Q次查詢，每次查詢一個(gè)區(qū)間[L, R]哑诊。
對(duì)于每一個(gè)區(qū)間靠粪，求使得(A[i] + A[j])為奇數(shù)的(i, j)的對(duì)數(shù) (L <= i < j <= R)。
Input
多組數(shù)據(jù)休傍，第一行有一個(gè)整數(shù)T表示數(shù)據(jù)組數(shù)征绎。(T <= 5)
之后有T組數(shù)據(jù)，每組數(shù)據(jù)第一行為兩個(gè)整數(shù)N和Q磨取，表示數(shù)列長(zhǎng)度及查詢數(shù)量亚隙。
(1 <= N, Q <= 100000)
接著有一行N個(gè)元素的數(shù)列A[1..N]。(1 <= A[i] <= 1000)
接下來(lái)Q行最爬，每行有兩個(gè)整數(shù)L, R牲距，表示查詢的區(qū)間。(1 <= L <= R <= N)
Output
對(duì)于每次詢問逢净，輸出一行數(shù)字哥放，表示區(qū)間”O(jiān)dd Pair”的對(duì)數(shù).
Sample Input
1
5 2
1 5 3 4 2
1 5
2 3
Sample Output
6
0
思路 ： 只有當(dāng)一個(gè)奇數(shù)加一個(gè)偶數(shù)時(shí)才滿足題目要求. 所以知道該區(qū)間中奇數(shù)和偶數(shù)的個(gè)數(shù)就可以直接算.
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; //結(jié)構(gòu)體中的變量會(huì)自動(dòng)付初值.
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; //每一個(gè)繼承前面那個(gè)的奇數(shù)和偶數(shù)個(gè)數(shù).
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(這道題挺重要的!!!)
思維題. 也可以用前綴和思想, 只是有點(diǎn)難理解. 所以這兒就不給這種解法了. 給一種易理解的解法.
思路 :
設(shè)ans(k)為k長(zhǎng)度的子序列的個(gè)數(shù),,a[k]為第k個(gè)子序列歼指，那么如果a[k]和前面的數(shù)都不相同的情況下，ans(k)]=ans(k-1)*2+1甥雕；如果前面的數(shù)字出現(xiàn)過(guò)的話踩身，那么就要減去最近一次出現(xiàn)a[k]這個(gè)數(shù)值的地方-1的子序列個(gè)數(shù)，因?yàn)檫@些算重復(fù)的了社露，而且+1也沒有了挟阻，因?yàn)閍ns(a[k]上次出現(xiàn)的位置)包括了a[k]單獨(dú)算一次的情況
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; //這樣做的目的是為了防止出現(xiàn)負(fù)數(shù)(我是
//wa試出來(lái)的)因?yàn)槲艺也坏骄唧w樣列會(huì)出現(xiàn)負(fù)數(shù).所以必須這才能A .
}
vis[a[i]] = i;
}
printf("%d\n",ans[n]%mod);
}
}
