首页 > 代码库 > 尺取法 TwoPoint

尺取法 TwoPoint

2024-07-10 00:05:44   214人阅读

就是两个指针表示区间[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 }
poj3320

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 }
pos2566

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 }
poj2739

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 }
poj2100

 

 


联系
我们