篮球杯双指针专题

绝地灬酷狼 2024-03-26 14:38 88阅读 0赞

**总的来说，双指针分为while(1)类型和尺取法类型**

**可以解决各种问题,前提是满足单调性（如子序列问题）**

[活动 - AcWing][- AcWing]

![b213d6fc238bdc9530036c9933678ca8.png][]

思路：

while(1)型的双指针

注意边界问题

注意考虑是否去掉前缀和后缀，即会不会少算贡献

去掉前缀和后缀：

while(L<=N&&a[L]==0) L++;
    while(R>=1&&a[R]==0) R--;

然后拿L代替1，R代替N，去做while(1)型的双指针

其基本形式为：

while(1){
            if(l>R||r>R) break;
            while(l<=R&&条件) l++;
            r=l;
            while(r<=R&&条件) r++;
            if(条件) 计算贡献
            l=r;
        }

还有一种类似的写法：

F(i,L,R){
            if(w[i]==2){
                if(!L_idx) continue;
                v.push_back(i - L_idx);
                L_idx = 0;
            }
            else{
                if(!L_idx) L_idx = i;
            }
        }

就是去枚举到所有的满足条件的区间，然后去计算贡献

[799. 最长连续不重复子序列 - AcWing题库][799. _ - AcWing]

![ba531b9c2b08b1097348bd10ef403602.png][]

思路：

尺取法式双指针

尺取法：详情见[(65条消息) 尺取法总结\_lamentropetion的博客-CSDN博客][65_ _lamentropetion_-CSDN]

尺取法维护区间map信息

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    const double eps=1e-8;
    using namespace std;
    map<int,int> mp;
    int n;
    int a[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int ans=-1e9;
        for(int l=1,r=1;l<=n;l++){
            while(r<=n&&!mp[a[r]]){
                mp[a[r]]++;
                r++;
            }
            ans=max(ans,r-1-l+1);
            mp[a[l]]--;
        }
        cout<<ans<<'\n';
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[800. 数组元素的目标和 - AcWing题库][800. _ - AcWing]

![373e94a0b195ea168ad7f07b158d683b.png][]

思路：

双指针枚举超时

可以先去枚举一个指针，然后另一个指针就确定了

去二分另一个指针即可

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    const double eps=1e-8;
    using namespace std;
    int n,m,x;
    int a[mxn],b[mxn];
    void solve(){
        cin>>n>>m>>x;
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<m;i++) cin>>b[i];
        int ans=0;
        vector<pair<int,int> > v;
        for(int i=0;i<n;i++){
            int pos1=lower_bound(b,b+m,x-a[i])-b;
            int pos2=upper_bound(b,b+m,x-a[i])-b;
            for(int j=pos1;j<=pos2-1;j++){
                v.push_back({i,j});
            }
        }
        for(int i=0;i<v.size();i++) cout<<v[i].first<<" "<<v[i].second<<" \n"[i==v.size()-1];
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[2816. 判断子序列 - AcWing题库][2816. _ - AcWing]

![53b727da7b806eb4d9c4cccd3c6f546a.png][]

思路：

双指针去check子序列

很多子序列问题都可以用双指针来解决

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    const double eps=1e-8;
    using namespace std;
    int n,m;
    int a[mxn],b[mxn];
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) cin>>b[i];
        a[n+1]=1e9,b[m+1]=-1e9;
        for(int l=1,r=1;l<=n;l++){
            while(r<=m&&b[r]!=a[l]) r++;
            if(r>m&&b[r]!=a[l]){
                cout<<"No"<<'\n';
                return;
            }
            r++;
        }
        cout<<"Yes"<<'\n';
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[- AcWing]: https://www.acwing.com/activity/content/2869/
[b213d6fc238bdc9530036c9933678ca8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/913f73dc1c4346afa8d9c6323fedb177.png
[799. _ - AcWing]: https://www.acwing.com/problem/content/801/
[ba531b9c2b08b1097348bd10ef403602.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6e6e4ac066c8412e947723415e4c2da6.png
[65_ _lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/128209723
[800. _ - AcWing]: https://www.acwing.com/problem/content/802/
[373e94a0b195ea168ad7f07b158d683b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/29a5527173c142cb859166a810dabe41.png
[2816. _ - AcWing]: https://www.acwing.com/problem/content/2818/
[53b727da7b806eb4d9c4cccd3c6f546a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/576c964d6ad1426b8b7796da1b3bf31f.png