首页 > 代码库 > 尺取法 TwoPoint
尺取法 TwoPoint
就是两个指针表示区间[l,r]的开始与结束然后根据题目来将端点移动,是一种十分有效的做法。适合连续区间的问题
3320
这道意思是一本书有n页,每一页上有一个知识点标号a[i]可能重复,要求选择一个最小的区间使得能够覆盖所有知识点
分析:[l,r]区间推进,统计区间中能够覆盖的知识点数,对于每一个l,r都是满足可以覆盖所有知识点的最小r,处理好区间知识点数的统计就好了
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<cmath> 9 #include<vector>10 #define maxn 100001011 #define maxm 10001012 #define mod 100000000000000000013 #define INF 0x3f3f3f3f3f14 using namespace std;15 int n;16 int a[maxn];17 map<int,int>mp;18 set<int>num;19 int main (){20 while(scanf("%d",&n)!=EOF){21 num.clear();22 mp.clear();23 for(int i=0;i<n;++i){24 scanf("%d",&a[i]);25 num.insert(a[i]);26 }27 int l=0,r=0;28 int m = num.size();29 int cnt=0;30 int ans=n;31 while(l<n){32 while(r<n&&cnt<m){33 if(mp[a[r]]==0){34 cnt++;35 }36 mp[a[r]]++;37 r++;38 }39 if(cnt<m)break;40 ans =min(ans,r-l);41 mp[a[l]]--;42 if(mp[a[l]]==0){43 cnt--;44 }45 l++;46 }47 printf("%d\n",ans);48 }49 50 }
2566
给你一个数组(可为负数)m次询问,每次询问一个区间使得区间和的绝对值最接近给定的值,有多种随意输出一种
分析:预处理前缀和sum[i]这样可以O(1)查询区间和,然后sum数组从小到大排序(因为abs(sum[i]-sum[j])=abs(sum[j]-sum[i])所以顺序不影响答案,但可以方便尺取)然后就是O(n)推进,每次有最小值是更新答案区间信息就可以了
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<cmath> 9 #include<vector>10 #define maxn 100001011 #define maxm 10001012 #define mod 100000000000000000013 #define INF 0x3f3f3f3f14 using namespace std;15 int n,m;16 int a[maxn];17 pair<int,int>p[maxn];18 void query(int x){19 int l=0,r=1,mmin=INF;20 int ansl,ansr,ansx;21 while(l<=n&&r<=n){22 int y = p[r].first-p[l].first;23 if(abs(y-x)<mmin){24 mmin=abs(y-x);25 ansx=y;26 ansl = p[l].second;27 ansr = p[r].second;28 }29 if(y>x)l++;30 else if(y<x)r++;31 else break;32 if(l==r)r++;33 }34 if(ansl>ansr)swap(ansl,ansr);35 printf("%d %d %d\n",ansx,ansl+1,ansr);36 }37 int main (){38 while(scanf("%d%d",&n,&m)!=EOF){39 if(n==0&&m==0)break;40 p[0]=pair<int,int>(0,0);41 int sum=0;42 for(int i=1;i<=n;++i){43 scanf("%d",&a[i]);44 sum+=a[i];45 p[i]=pair<int,int>(sum,i);46 }47 sort(p,p+n+1);48 while(m--){49 int x;50 scanf("%d",&x);51 query(x);52 }53 }54 }
2739
给你一个数,询问有多少个连续质数序列和等于该数例如53=5 + 7 + 11 + 13 + 17
分析:筛法求质数,然后直接twopoint就可以了,统计可以相等的个数
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<cmath> 9 #include<vector>10 #define maxn 100001011 #define maxm 10001012 #define mod 100000000000000000013 #define INF 0x3f3f3f3f14 using namespace std;15 int n,m;16 int prime[maxn];17 bool is_prime[maxn];18 int get_prime(int n){19 int ans=0;20 for(int i=2;i<=n;++i)is_prime[i]=true;21 is_prime[0]=is_prime[1]=false;22 for(int i=2;i<=n;++i){23 if(is_prime[i]){24 prime[ans++]=i;25 for(int j=2*i;j<=n;j+=i)is_prime[j]=false;26 }27 }28 return ans;29 }30 void query(int x){31 int ans=0;32 int l=0,r=0,sum=0;33 while(1){34 while(r<m&&sum<x){35 sum+=prime[r++];36 }37 if(sum<x)break;38 else if(sum==x)ans++;39 sum-=prime[l++];40 }41 printf("%d\n",ans);42 }43 int main (){44 m=get_prime(10010);45 while(scanf("%d",&n)!=EOF){46 if(n==0)break;47 query(n);48 }49 }
2100
给你一个数,询问有多少种连续自然数的平方和等于这个数,输出所有可能
分析:由上面的基础很简单了,对于每个数枚举区间,求和,推进区间,如果可以的话将区间记录最后输出就可以了,注意使用long long ,复杂度O(1e7)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<cmath> 9 #include<vector>10 #define maxn 100001011 #define maxm 10001012 #define mod 100000000000000000013 #define INF 0x3f3f3f3f14 using namespace std;15 vector<pair<long long ,long long > >ans;16 void query(long long x){17 long long l=1,r=1;18 long long sum=0;19 long long sq=0;20 while(1){21 while(sum<x){22 sq=r*r;23 sum+=sq;24 r++;25 }26 if(sq>x)break;27 if(sum==x){28 ans.push_back(make_pair(l,r));29 }30 sum-=l*l;31 l++;32 }33 long long m = ans.size();34 printf("%lld\n",m);35 for(long long i=0;i<m;++i){36 long long ll = ans[i].first;37 long long rr = ans[i].second;38 printf("%lld",rr-ll);39 for(long long j=ll;j<rr;++j){40 printf(" %lld",j);41 }42 printf("\n");43 }44 }45 int main (){46 long long n;47 while(scanf("%lld",&n)!=EOF){48 if(n==0)break;49 query(n);50 }51 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。