算法C++
枚举
1.化段为点
前缀和 eg:给一个数列，算x到y个数的和
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> a(n);
vector<int> sum(n+1,0);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum[i+1]=sum[i]+a[i];
}
int x,y;
cin>>x>>y;
cout<<sum[y]-sum[x-1];
}给一段数字，q次访问，每次对[x,y]区间进行加减x，最后再重新给出新的一段数字
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> a(n+1,0);
vector<int> cha(n+1,0);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
cha[i-1]=a[i]-a[i-1];
}
int q;
cin>>q;
for(int i=0;i<q;i++)
{
int x,y,z;
cin>>x>>y>>z;
cha[x-1]+=z;
cha[y]-=z;
}
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+cha[i-1];
cout<<a[i]<<endl;
}
}n棵树,q次砍树区间为[x,y]，求之后树总数量
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct sb
{
int pos,num;
};
bool compare(sb x,sb y)
{
if(x.pos == y.pos )
{
return x.num < y.num ;
}
return x.pos < y.pos ;
}
int main()
{
int n,q;
cin>>n>>q;
vector<sb> a(q*2);
for(int i=0;i<q;i++)
{
int x,y;
cin>>x>>y;
if(x>y)
{
int t=x;
x=y;
y=t;
}
a[i].pos=x-1;
a[i].num=1;
a[i+q].pos=y;
a[i+q].num=-1;
}
sort(a.begin() , a.end() ,compare);
int cnt=a[0].pos;
int b=0;
for(int i=0;i<q*2;i++)
{
b=b+a[i].num;
if(b==1&&a[i].num==1&&i>0)
{
cnt+=a[i].pos-a[i-1].pos;
}
}
cnt+=n-a[2*q-1].pos;
cout<<cnt+1;
} 
输入n个数，有m区间可以缓存，求需要存多少
#include<iostream>
using namespace std;
int main()
{
int n,m,cnt=0;
cin>>n>>m;
int v[n],a[n];
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(v[x]==1)
{
continue;
}
a[cnt++]=x;
v[x]=1;
if(cnt>m)
{
v[a[cnt-m-1]]==0;
}
}
cout<<cnt;
}追逐法/双指针法/尺量法/蚯蚓法：一缩一进
#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,s;
cin>>n>>s;
int a[n];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int len=n+1,r=0;
int sum=0;
for(int l=0;l<n;l++)
{
while(r<n&&sum<s)
{
sum+=a[r];
r++;
}
if(sum>=s)
{
len=min(r-l,len);
}
else
{
break;
}
sum-=a[l];
}
if(len>n)
{
printf("0");
}
else
{
printf("%d",len);
}
return 0;
}原文地址：https://blog.csdn.net/Error_Fe/article/details/136310939
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！