d.cpp (2674B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 12 int main() { 13 14 // s of length n 15 // operation: 16 // select a lowercase letter x != 'a' (no looping) 17 // replace all x in s with the prior letter in alphabet 18 // find min ops to make s a palindrome 19 20 21 // 5 22 // 4 23 // abca 24 25 // abca 26 // x = c 27 // abba 28 // return 1 29 30 // idea: start decreasing the largest number in the list 31 // where the number doesn't match it's palndromic friend on the other side 32 33 // 4 34 // abdc 35 // 0 1 3 2 36 // 0 1 2 2 37 // 0 1 1 1 38 // 0 0 0 0 39 // 3 40 41 42 // 7 43 // racecar 44 // all chars match 45 46 // 4 47 // cbad 48 // 2 1 0 1 49 // 1 1 0 1 50 // 0 0 0 0 51 52 // 4 53 // zaza 54 55 // idea: start decreasing the largest number in the list 56 // where the number doesn't match it's palndromic friend on the other side 57 58 int testCases, n; 59 string current; 60 cin >> testCases; 61 62 for(int z = 0; z < testCases; ++z) { 63 cin >> n; 64 cin >> current; 65 vector<int> characters (n,0); 66 67 for(int i = 0; i < current.size(); ++i) { 68 characters[i] = (current[i]-'a'); 69 } 70 71 // this algo can't be O(n^2) 72 73 int res = 0; 74 75 // already matched: 76 // changes don't matter so whatever on them 77 // not matched yet: 78 // bring larger down to the other 79 // we want to target the largest value that differs first 80 81 // perhaps we just sub to get to the other and add an interval change to a list 82 // we'd then do lookups in there for non-matching to bring them down 83 84 // vector<pair<int,int>> unmatched 85 86 vector<pair<int,int>> unmatched {}; 87 88 // unmatched, first is always smaller 89 const size_t n = current.size(); 90 for (int i = 0; i < n / 2; ++i) { 91 int a = characters[i]; 92 int b = characters[n - 1 - i]; 93 if (a != b) { 94 auto [lo, hi] = minmax(a, b); 95 unmatched.push_back({lo, hi}); 96 } 97 } 98 99 vector<bool> canMoveFree (26,false); 100 101 102 for(int i = 0; i < unmatched.size(); ++i) { 103 int hi = unmatched[i].second; 104 int lo = unmatched[i].first; 105 while(hi > lo) { 106 if(!canMoveFree[hi]) { 107 canMoveFree[hi] = true; 108 res += 1; 109 } 110 hi -= 1; 111 } 112 } 113 114 cout << res << endl; 115 116 117 118 } 119 }