题解 | #牛牛的子序列#

写了一大坨屎。

考虑两个序列可能通过操作变得相同的必要条件，显然操作只会延长一些数字的连续段，而这些连续段所对应的数字不会改变，所以我们先扫出来两个序列的所有连续段，先判断数量是否一致，再判断每个连续段所对应的数字是否一致，注意还要判断 $a$ 中每个连续段的长度都不能比对应的 $b$ 中的连续段的长度长。

最后考虑统计答案，很显然，假设当前扫到 $a$ 中某个数字 $x$ 的连续段长度为 $p$ ， $b$ 中对应的连续段长度为 $q$ ，操作是我们至多增加 $p$ 个 $x$ ，手摸一下，发现就是每次乘上 $2$ ，于是等价于我们要找到一个最小的 $k$ ，使得 $p \times 2^k \ge q$ ，其中 $k \ge 0$ 。

思路就是这些，代码：

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define mkp make_pair
#define pb push_back
using namespace std;
ll n,m,a[200005],b[200005],pw[34];
void solve(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>a[i];
    for(ll i=1;i<=m;i++) cin>>b[i];
    if(n>m){
        cout<<-1<<endl;
    }else{
        vector<pll> ap,bp;ll cnt=1;
        if(n==1){
            ap.pb(mkp(a[1],1));
        }else{
            for(ll i=1;i<=n;i++){
                if(a[i]==a[i-1]){
                    cnt++;
                }else{
                    if(i==1) continue;
                    ap.pb(mkp(a[i-1],cnt));
                    cnt=1;
                }
            }
            ap.pb(mkp(a[n],cnt)),cnt=0;
        }
        if(m==1){
            bp.pb(mkp(b[1],1));
        }else{
            cnt=1;
            for(ll i=1;i<=m;i++){
                if(b[i]==b[i-1]){
                    cnt++;
                }else{
                    if(i==1) continue;
                    bp.pb(mkp(b[i-1],cnt));
                    cnt=1;
                }
            }
            bp.pb(mkp(b[m],cnt));
        }
        // for(auto p:ap) cout<<p.first<<" "<<p.second<<"* ";cout<<endl;
        // for(auto p:bp) cout<<p.first<<" "<<p.second<<"* ";cout<<endl;
        if(ap.size()!=bp.size()){
            cout<<-1<<endl;
        }else{
            bool f=0;ll ans=0;
            for(ll i=0;i<ap.size();i++){
                pll ai=ap[i],bi=bp[i];
                if(ai.first!=bi.first||ai.second>bi.second){
                    f=1;break;
                }
                ll rt=0;
                // cout<<ai.second<<" "<<bi.second<<endl;
                for(ll j=0;j<=20;j++){
                    if(ai.second*pw[j]>=bi.second){
                        rt=j;break;
                    }
                }
                ans=max(ans,rt);
            }
            if(f){
                cout<<-1<<endl;
            }else{
                cout<<ans<<endl;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll T;cin>>T,pw[0]=1;
    for(ll i=1;i<=32;i++) pw[i]=pw[i-1]*2;
    while(T--) solve();
}