General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
232163532 Practice:
FreshOrange
1383C - 68 C++20 (GCC 11-64) Accepted 1528 ms 524 KB 2023-11-10 03:08:43 2023-11-10 03:08:43
→ Source
// LUOGU_RID: 134248929
/*********************************
 *zz  * =====  ====   =_   +     *
 *af  *   =    =      = =        *
 *an  *   =    =~~~   ====       *
 *ti  *   =    ====   =   =      *
 *********************************

 some template that may be useful.

 including combinatorics, some data structures, number theory, polynomial

 update on 11, 8, 2023

      */
#include<bits/stdc++.h>

using namespace std;

using E=long long;
using ui=uint32_t;
using lint=__int128;
constexpr E inf=1e16,mod=998244353;

namespace DSU{
  class dsu{
    private:
    vector<ui> par;
    int n;
    public:
    dsu(int sz){
      n=sz;
      par.resize(n+1);
      iota(par.begin(),par.end(),0);
    }
    int get(int x){
      return x==par[x]?x:par[x]=get(par[x]);
    }
    void merge(int x,int y){
      if(get(x)==get(y)) return ;
      par[get(x)]=y;
    }
  };
};
using namespace DSU;

bool chk(int msk,const vector<bitset<20>> &g){
  auto w=g;
  for(int i=0; i<20; i++){
    if(msk>>i&1) for(int j=0; j<20; j++) w[j][i]=0;
  }
  for(int k=0; k<20; k++){
    for(int i=0; i<20; i++){
      if(!w[i][k]) continue;
      w[i]=w[i]|w[k];
      if(w[i][i]) return 0;
    }
  }
  return 1;
}

pair<string,string> generator(){
  string ret1,ret2;
  for(int i=0; i<20; i++){
    for(int j=0; j<20; j++){
      ret1+=(char)('a'+i);
      ret2+=(char)('a'+j);
    }
  }
  return make_pair(ret1,ret2);
}

void solve(){
  int n;
  string str1,str2;
  cin>>n>>str1>>str2;
  /*auto PP=generator();
  str1=PP.first,str2=PP.second,n=str1.size();*/
  vector<bitset<20>> ver(20);
  for(int i=0; i<n; i++){
    if(str1[i]==str2[i]) continue;
    ver[str1[i]-'a'][str2[i]-'a']=1;
  }
  /*
  for(int i=0; i<20; i++){
    sort(ver[i].begin(),ver[i].end());
    ver[i].erase(unique(ver[i].begin(),ver[i].end()),ver[i].end());
  }*/
  int T=(1<<20),ans=38,cc=0;
  dsu D(20);
  for(int p=0; p<20; p++){
    for(int i=0; i<20; i++){
      if(!ver[p][i]) continue;
      D.merge(p,i);
    }
  }
  unordered_map<int,int> cnt;
  for(int p=0; p<20; p++){
    cnt[D.get(p)]++;
  }
  for(auto pt:cnt) cc+=pt.second-1;
  vector<bool> tag(T);
  for(int i=0; i<T; i++){
    if(ans<=cc+__builtin_popcount(i)) continue;
    if(!chk(i,ver)) continue;
    //if(sum<ans) cout<<i<<' '<<sum<<endl;
    ans=min(ans,cc+__builtin_popcount(i));
    if(!i) break;
  }
  cout<<ans<<endl;
}

int main(){
  cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);

  int T;
  cin>>T;
  while(T--) solve();

  return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details