双指针总结

双指针有两类一类是指向两段序列一类是指向一段序列

题目一

题目链接：https://codeforces.com/edu/course/2/lesson/9/1/practice/contest/307092/problem/B

题意：给定 a b 数组递增排序问对b中每一个数有多少个a[i] 小于b[i]

思路：因为有单调性，很明显双指针即可用的是第一维是for 的形式，这样更好更新ans[i]

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11  
12 int n,m;
13 int a[maxn],b[maxn];
14 int ans[maxn];
15  
16  
17 int main()
18 {
19     ios::sync_with_stdio(false);
20     cin.tie(0);
21     cin>>n>>m;
22     for(int i=0;i>a[i];
23     for(int i=0;i>b[i];
24  
25     for(int i=0,j=0;i)
26     {
27         while(j;
28         ans[i]=j;
29     }
30     for(int i=0;i" ";
31  
32  
33  
34  
35  
36 }

题目二

题目链接：https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/A

题意：找出最长的区间使得区间和至多为s 输出最长的长度

思路：直接双指针当区间和>s 时j往前移动即可

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11  
12 int ans=0;
13 int n;
14 ll s;
15 int a[maxn];
16  
17  
18 int main()
19 {
20     ios::sync_with_stdio(false);
21     cin.tie(0);
22     cin>>n>>s;
23     for(int i=1;i<=n;i++) cin>>a[i];
24     ll sum=0;
25     for(int i=1,j=1;i<=n;i++)
26     {
27         sum+=a[i];
28         while(j<=i&&sum>s) sum-=a[j],j++;
29         ans=max(ans,i-j+1);
30     }
31     cout<'\n';
32  
33  
34 }

题目三

题目链接：https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/B

题意：找出最短的区间使得区间长度至少为s

思路：和上一题区别开是当sum-a[j]>=s 时才能把j 左移

否则可能会漏掉答案没有更新，如当前sum>=s 但减去a[j]后不满足然后没有更新到这个答案

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11  
12 int ans=1e9;
13 int n;
14 ll s;
15 int a[maxn];
16  
17  
18 int main()
19 {
20     ios::sync_with_stdio(false);
21     cin.tie(0);
22     cin>>n>>s;
23     for(int i=1;i<=n;i++) cin>>a[i];
24     ll sum=0;
25     for(int i=1,j=1;i<=n;i++)
26     {
27         sum+=a[i];
28         while(j<=i&&sum-a[j]>=s) sum-=a[j],j++;
29         if(sum>=s) ans=min(ans,i-j+1);
30     }
31     if(ans==1e9) ans=-1;
32     cout<'\n';
33  
34  
35 }

题目四

题目链接：https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/C

题意：有多少个不同的区间区间和至多为s

思路：当sum>s 移动左指针每一个右端点的时候如果 j~i 满足 j~i之间的也肯定满足

所以 ans+=i-j+1

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11  
12 int n;
13 ll s;
14 int a[maxn];
15  
16  
17 int main()
18 {
19     ios::sync_with_stdio(false);
20     cin.tie(0);
21     cin>>n>>s;
22     for(int i=1;i<=n;i++) cin>>a[i];
23     ll sum=0;
24     ll ans=0;
25     for(int i=1,j=1;i<=n;i++)
26     {
27         sum+=a[i];
28         while(j<=i&&sum>s) sum-=a[j],j++;
29         ans+=i-j+1;
30     }
31  
32     cout<'\n';
33  
34  
35 }

题目五

题目链接：https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/D

题意：有多少个不同的区间区间和至少为s

思路: 一样要注意当sum-a[j]>=s 的时候才可以移动左指针

然后根据单调性，当 j~i满足的时候更左边的区间也一定满足

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11  
12 int n;
13 ll s;
14 int a[maxn];
15  
16  
17 int main()
18 {
19     ios::sync_with_stdio(false);
20     cin.tie(0);
21     cin>>n>>s;
22     for(int i=1;i<=n;i++) cin>>a[i];
23     ll sum=0;
24     ll ans=0;
25     for(int i=1,j=1;i<=n;i++)
26     {
27         sum+=a[i];
28         while(j<=i&&sum-a[j]>=s) sum-=a[j],j++;
29         if(sum>=s) ans+=j;
30     }
31  
32     cout<'\n';
33  
34  
35 }

题目六

题目链接：https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/F

题意：要求区间最大值减最小值至多是k 可以发现当区间收缩的时候 mx只会减小 mi只会增加

所以mx-mi 只会减小所以满足单调性所以ans+=i-j+1 可以用multiset维护区间最大值和最小值

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11  
12 int n;
13 ll k;
14 ll a[maxn];
15  
16  
17  
18 int main()
19 {
20     ios::sync_with_stdio(false);
21     cin.tie(0);
22     cin>>n>>k;
23     for(int i=1;i<=n;i++) cin>>a[i];
24     ll ans=0;
25     multisets;
26     for(int i=1,j=1;i<=n;i++)
27     {
28         s.insert(a[i]);
29         ll tmp=*s.rbegin()-*s.begin();
30         while(j<=i&&tmp>k)
31         {
32             s.erase(s.find(a[j]));
33             j++;
34             tmp=*s.rbegin()-*s.begin();
35         }
36         ans+=i-j+1;
37     }
38     cout<'\n';
39  
40 }

题目七

题目链接：https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/G

题意：要求区间的gcd为1 找出最短的区间

不断缩短区间即可，用线段树维护区间gcd 每次查询某个区间即可不需要修改操作

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 
12 struct ac
13 {
14     int l,r;
15     ll gcd;
16 };
17 ac tr[maxn*4];
18 ll a[maxn];
19 
20 
21 void pushup(int x)
22 {
23     tr[x].gcd=__gcd(tr[x<<1].gcd,tr[x<<1|1].gcd);
24 }
25 
26 void build(int x,int l,int r)
27 {
28     tr[x]={l,r,0};
29     if(l==r)
30     {
31         tr[x].gcd=a[l];
32         return;
33     }
34     int mid=l+r>>1;
35     build(x<<1,l,mid);
36     build(x<<1|1,mid+1,r);
37     pushup(x);
38 }
39 ll query(int x,int l,int r)
40 {
41     int L=tr[x].l,R=tr[x].r;
42     if(l<=L&&R<=r)
43     {
44         return tr[x].gcd;
45     }
46     int mid=L+R>>1;
47     ll ans=0;
48     if(l<=mid) ans=query(x<<1,l,r);
49     if(r>mid) ans=__gcd(ans,query(x<<1|1,l,r));
50     return ans;
51 }
52 
53 
54 
55 
56 
57 int main()
58 {
59     ios::sync_with_stdio(false);
60     cin.tie(0);
61     int n;
62     cin>>n;
63     for(int i=1;i<=n;i++) cin>>a[i];
64     build(1,1,n);
65     int ans=1e9;
66     for(int i=1,j=1;i<=n;i++)
67     {
68         ll x=query(1,j,i);
69         while(j1,j+1,i)==1)
70         {
71             j++;
72             x=query(1,j,i);
73         }
74         if(x==1) ans=min(ans,i-j+1);
75     }
76     if(ans==1e9) ans=-1;
77     cout<'\n';
78 
79 
80 
81 
82 
83 }

题目八

B总结

双指针总结

相关

标签