【双指针合并序列】CF731div3 B C

深碍√TFBOYSˉ_ 2024-03-27 13:34 26阅读 0赞

**woc了好不容易补完div3，结果一点了，没时间写题解了，留着明天写吧，反正题是补完的，所以，我滴任务完成辣！**

**双指针可以保证两个序列合并时相对位置不变！在合并过程中循环次数是一定的，所以一点点移动指针就行了**

[Problem - C - Codeforces][]

**这道题一开始读题读了20分钟才读懂意思，然后发觉是构造题就乱搞写了一坨答辩，好不容易过了样例wa2了，然后又搞了好久好久....只能说不懂双指针了**

**所以当感觉一道本来应该很简单的题代码却很答辩的时候就一定错，就该换解法了，或者跳题（**

**感觉后面的DE都比较简单，比赛的时候都可以出的，但是就是卡在C上了QwQ**

题意：

给你两个数组a和b，如果 ai==0 || bi==0 就是相当于加了一行代码，如果ai>0或bi>0就表明有修改ai和bi的代码，

思路：

**序列合并型双指针**

一开始的思路也是双指针，先去遍历a序列，遍历到不能遍历为止，然后算出还差多少0，然后去遍历b序列去补上缺的0，直到刚好补上，然后去循环这个过程

这个思路很简单，可是代码确实是答辩

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=1e2+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Mnf=1e18;
    const int Inf=-1e18;
    using namespace std;
    
    
    vector<int> v;
    int k,n,m,cnt=0;
    int a[mxn],b[mxn],pre_0[mxn];
    void solve(){
        cnt=0;
        v.clear();
        memset(pre_0,0,sizeof(pre_0));
        cin>>k>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) cin>>b[i];
    
        for(int i=1;i<=n;i++){
            pre_0[i]=pre_0[i-1]+(a[i]==0);
        }
        int l=1;
        int R=1;
        while(1){
            if(l>n) break;
            while(l<=n&&a[l]<=pre_0[l]+k+cnt) v.push_back(a[l]),l++;
            //for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
            if(l<n){
                int cnt1=0;
                int res=a[l]-(pre_0[l]+k+cnt);
                //cout<<"res: "<<res<<'\n';
                while(R<=n&&cnt1<res) cnt1+=(b[R]==0),v.push_back(b[R]),R++;
                cnt+=cnt1;
                //cout<<"cnt1: "<<cnt1<<'\n';
                if(R>n||cnt1<res){
                    cout<<"-1"<<'\n';
                    return;
                }
            }else{
                for(int i=R;i<=m;i++) v.push_back(b[i]);
                for(int i=l;i<=n;i++) v.push_back(a[i]);
                break;
            }
        }
        for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

正解也是维护两个双指针，不过是一点点移动，优先选0，再去选数

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

[Problem - B - Codeforces][]

题意：

给你一个字符串，让你判断是不是由题目中的条件拼接出来的。

![ecc26288f819e2dc2a8898ef6399f3f6.png][]

思路：

**while(1)扩展型双指针**

先去找到a的位置，然后双指针从中间向两侧扩展，如果两侧都没有扩展，说明循环结束，不用再扩展了

注意一下写法，扩展型的双指针都是这样写的

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=2e3+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Mnf=1e18;
    const int Inf=-1e18;
    using namespace std;
    
    string s;
    void solve(){
        s.clear();
        cin>>s;
        int n=s.size();
        s=" "+s;
        int ansi=-1;
        for(int i=1;i<=n;i++){
            if(s[i]=='a'){
                ansi=i;
                break;
            }
        }
        if(ansi==-1){
            cout<<"NO"<<'\n';
            return;
        }
        int l=ansi-1,r=ansi+1;
        int idx=1;
        int ok=1;
        while(1){
            //cout<<l<<" "<<r<<'\n';
            if(l<1&&r>n) break;
            int cnt1=0,cnt2=0;
            while(l>=1&&s[l]=='a'+(idx)) l--,idx++,cnt1++;
            //if(cnt1!=0) l++;
            while(r<=n&&s[r]=='a'+(idx)) r++,idx++,cnt2++;
            //if(cnt2!=0) r--;
            if(cnt1==0&&cnt2==0){
                //cout<<l<<" "<<r<<'\n';
                ok=0;
                break;
            }
        }
        if(ok) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1547/problem/C
[Problem - B - Codeforces]: https://codeforces.com/contest/1547/problem/B
[ecc26288f819e2dc2a8898ef6399f3f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/13beff1a8dfd4280ad800f542b13e728.png