?
# | 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 |
// 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; }
?
?
?
?