傳送門
題目：給定兩個字串A,B，我們可以改變A中任意數量相同的字符x變成字符y（必須滿足y > x），我們能否把A變成B，可以的話最少幾次，不可以輸出‘-1’，
思路：看了所有樣例后，再通過樣例1可以想到一個方法，我們有一個矩陣app['a'~'t']['a'~'t']記錄A與B的對應關系，例如：
A：aab
B: bcc
則我們記錄app['a']['b'] = 1, app['a']['c'] = 1, app['b']['c'] = 1,這樣我們就有了AB的關系矩陣，然后我們想到，如果在app['a']['a'~'t']中第一個存在的關系是app['a'][x] = 1，則說明'a'對應的其他字符一定大于x，不如我們貪心的把其他'a'對應的關系都變成app[x][y]，y是滿足app['a'][y] = 1的字符，這樣就是一個理想的解決方法（想到的時候感覺有點玄乎但感覺也對），
補：寫完題目后看其他人的寫法，發現可以并查集，，，好神奇
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 #include <string> 6 #include <vector> 7 #include <cmath> 8 #include <stack> 9 10 using namespace std; 11 12 #define ll long long 13 #define pb push_back 14 #define fi first 15 #define se second 16 17 const int N = 30; 18 int app[30][30]; 19 20 void solve() 21 { 22 int T; 23 cin >> T; 24 while(T--){ 25 for(int i = 0; i <= 27; ++i) 26 for(int j = 0; j <= 27; ++j) 27 app[i][j] = 0; 28 29 int n, ok = 1; 30 string A, B; 31 cin >> n >> A >> B; 32 for(int i = 0; i < n; ++i){ 33 if(A[i] > B[i]){ 34 ok = 0; 35 break; 36 } 37 if(A[i] < B[i]) app[A[i] - 'a'][B[i] - 'a'] = 1; 38 } 39 40 int cnt = 0; 41 for(int i = 0; i <= 26; ++i){ 42 int s = -1; 43 for(int j = 0; j <= 26; ++j){ 44 if(i == j) continue; 45 if(app[i][j]){ 46 cnt++; 47 s = j;// a->b; 48 break; 49 } 50 } 51 //改變其他的a->的關系 52 if(s == -1) continue; 53 for(int k = s + 1; k <= 26; ++k){ 54 if(app[i][k]) app[s][k] = 1; 55 } 56 } 57 58 //cout << "ans = "; 59 if(ok) cout << cnt << endl; 60 else cout << "-1" << endl; 61 } 62 63 64 65 } 66 67 int main() 68 { 69 ios::sync_with_stdio(false); 70 cin.tie(0); 71 cout.tie(0); 72 73 solve(); 74 75 return 0; 76 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10635.html
標籤：其他