Bitmask approach not working

Правка en2, от YogeshZT, 2024-07-06 08:53:31

I was solving 1778C - Flexible String and the editorial mentioned that one of the possible approaches of solving it involves bitmasking. I was able to code it using some parts of the code from another backtracking approach(one which has been mentioned in the editorial), my approach was to make a mask for the all the characters which have been pushed into the set and then proceed via the editorial code. However it isn't working. Can someone help me find the problem. Here is the code.

#include<bits/stdc++.h>
#define int long long  
using namespace std;

int min(int a,int b){
    if(a<b)return a;
    return b;
}
int max(int a,int b){
    if(a>b)return a;
    return b;
}

void answer(){
    int t=1;cin>>t;
    while(t--){
        int n,k;cin>>n>>k;
        string a,b;cin>>a>>b;
        unordered_set<int>uniq;
        for(auto it : a){
            uniq.insert(it);
        }
        string list;
        for(auto it : uniq){
            list.push_back(it);
        }
        k=min(k,uniq.size());
        int ans=0;
        for(int mask=0;mask<=(1<<k);mask++){
            if(__builtin_popcount(mask)==k){
                int mark[26];
                memset(mark,0,sizeof mark);
                for(int i=0;i<k;i++){
                    if((1<<i)&mask){
                        mark[list[i]-'a']=1;
                    }
                }
                ll tot_pair=0,match_count=0;
                for(ll i=0;i<a.size();i++) {
                    if(a[i]==b[i] || mark[a[i]-'a'])
                        match_count++;
                    else {
                        tot_pair+=match_count*(match_count+1)/2;
                        match_count=0;
                    }
                }
                tot_pair+=match_count*(match_count+1)/2;
                ans=max(ans,tot_pair);
            }
        }
        cout<<ans<<endl;
    }
    return ;
}
int32_t main(){
    answer();
}  

Теги bitmasks, backtracking

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский YogeshZT 2024-07-06 08:53:31 54
en1 Английский YogeshZT 2024-07-06 08:51:16 2028 Initial revision (published)