【二进制枚举+双指针】CF828div2 C. Flexible String

深碍√TFBOYSˉ_ 2024-03-22 19:17 78阅读 0赞

**原来Brute Force就是枚举**

**Brute Force！**

[Problem - C - Codeforces][]

题意：

![7141b563d11346efa319fa1d7d072fca.png][]

思路：

![f889e90b6f084582ae34766b35ac566b.png][]

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    map<int,int> mp;
    string s,t;
    
    int N,K,idx=0;
    int a[mxn];
    
    bool check(int state,int p){
        if(s[p]==t[p]) return true;
        if((state>>a[p])&1) return true;
        return false;
    }
    int get(char x){
        if(mp.count(x)) return mp[x];
        return mp[x]=idx++;
    }
    void solve(){
        s.clear();
        t.clear();
        mp.clear();
        idx=0;
        cin>>N>>K;
        cin>>s>>t;
        for(int i=0;i<N;i++){
            a[i]=get(s[i]);
        }
        int ans=0;
        for(int state=0;state<(1<<10);state++){
            if(__builtin_popcount(state)!=K) continue;
            int res=0;
            for(int l=0;l<N;l++){
                if(!check(state,l)) continue;
                int r=l;
                while(r+1<N&&check(state,r+1)) r++;
                int len=r-l+1;
                res+=(len+1)*len/2;
                l=r;
            }
            ans=max(ans,res);
        }
        cout<<ans<<'\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/1778/problem/C
[7141b563d11346efa319fa1d7d072fca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/8e4d14a7abf043e884eeccf42d850994.png
[f889e90b6f084582ae34766b35ac566b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/d97546c2d18b44d994c9efc2a6b08546.png