bad.cpp (1767B)
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 11 // idea: 12 // - just 1 + number of bits surrounded by opposite 13 // - uhh, no because then there are really long runs 14 // - so maybe just like the total number of runs of (length >= 3) + 1 15 // - is there some sort of 1010101 thing where we can only use that once? 16 // - actually yeah, it seems like that's exactly it 17 18 19 // concretely: 20 // start at 1 for base string 21 // increment on 101 strings and munch remaining 01010... 22 // increment on string of >=3 0s or >=3 1s 23 24 // 001011010 25 // that should be 2 26 27 // 0101010 baseline 28 29 // these compress to the same thing when flipping 30 // the first set of flipping and when we flip on the second set to: 31 // 01010 32 // 01010 33 34 using namespace std; 35 36 int main() { 37 int testCases; 38 string current = ""; 39 cin >> testCases; 40 41 for(int z = 0; z < testCases; ++z) { 42 cin >> current; 43 int res = 1; 44 45 bool isFlipping = false; 46 bool isRunning = false; 47 48 for(int i = 1; i < current.size()-1; ++i) { 49 50 if(current[i-1] == current[i+1] && current[i] != current[i-1]) { 51 if(isFlipping) 52 continue; 53 54 // munch flipping 55 res += 1; 56 isFlipping = true; 57 } 58 59 if(current[i-1] == current[i+1] && current[i] == current[i+1]) { 60 // munch run 61 if(isRunning) 62 continue; 63 res += 1; 64 isRunning = true; 65 isFlipping = false; 66 } else { 67 isRunning = false; 68 } 69 } 70 cout << res << endl; 71 } 72 }