1800.md (9679B)
1 Source: https://codeforces.com/blog/entry/113477 2 3 [1800A - Is It a Cat?](/contest/1800/problem/A "Codeforces Round 855 (Div. 3)") 4 5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 17 void solve(){ 18 int n; 19 cin >> n; 20 string s; 21 cin >> s; 22 transform(s.begin(), s.end(), s.begin(), [] (char c) { 23 return tolower(c); 24 }); 25 s.erase(unique(s.begin(), s.end()), s.end()); 26 cout << (s == "meow" ? "YES" : "NO") << "\n"; 27 } 28 29 int main(){ 30 int t; 31 cin >> t; 32 while(t--) solve(); 33 } 34 ``` 35 36 [1800B - Count the Number of Pairs](/contest/1800/problem/B "Codeforces Round 855 (Div. 3)") 37 38 Idea: [myav](/profile/myav "Pupil myav") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution** 45 46 ``` 47 #include <bits/stdc++.h> 48 using namespace std; 49 const int N = 26; 50 51 void solve(){ 52 int n, k; 53 cin >> n >> k; 54 string s; 55 cin >> s; 56 vector<int>big(N, 0), small(N, 0); 57 for(auto &i : s){ 58 if('A' <= i && 'Z' >= i) big[i - 'A']++; 59 else small[i - 'a']++; 60 } 61 int answer = 0; 62 for(int i = 0; i < N; i++){ 63 int pairs = min(small[i], big[i]); 64 answer += pairs; 65 small[i] -=pairs; big[i] -= pairs; 66 int add = min(k, max(small[i], big[i]) / 2); 67 k -= add; answer += add; 68 } 69 cout << answer << endl; 70 } 71 int main(){ 72 int t; 73 cin >> t; 74 while(t--) solve(); 75 return 0; 76 } 77 ``` 78 79 [1800C1 - Powering the Hero (easy version)](/contest/1800/problem/C1 "Codeforces Round 855 (Div. 3)") 80 81 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution** 88 89 ``` 90 def solve(): 91 n = int(input()) 92 s = [int(x) for x in input().split()] 93 ans = 0 94 buffs = [0] * n 95 for e in s: 96 if e > 0: 97 buffs += [e] 98 j = len(buffs) - 1 99 while buffs[j] < buffs[j - 1]: 100 buffs[j], buffs[j - 1] = buffs[j - 1], buffs[j] 101 j -= 1 102 else: 103 ans += buffs.pop() 104 print(ans) 105 106 t = int(input()) 107 for _ in range(t): 108 solve() 109 ``` 110 111 [1800C2 - Powering the Hero (hard version)](/contest/1800/problem/C2 "Codeforces Round 855 (Div. 3)") 112 113 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Solution** 120 121 ``` 122 from queue import PriorityQueue 123 124 def solve(): 125 n = int(input()) 126 s = [int(x) for x in input().split()] 127 ans = 0 128 buffs = PriorityQueue() 129 for e in s: 130 if e > 0: 131 buffs.put(-e) 132 elif not buffs.empty(): 133 ans -= buffs.get() 134 print(ans) 135 136 t = int(input()) 137 for _ in range(t): 138 solve() 139 ``` 140 141 [1800D - Remove Two Letters](/contest/1800/problem/D "Codeforces Round 855 (Div. 3)") 142 143 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution** 150 151 ``` 152 #include <iostream> 153 #include <vector> 154 #include <queue> 155 #include <map> 156 #include <set> 157 158 using namespace std; 159 160 void solve() { 161 int n; 162 cin >> n; 163 string s; 164 cin >> s; 165 int res = n - 1; 166 for (int i = 1; i + 1 < n; ++i) { 167 if (s[i - 1] == s[i + 1]) { 168 res--; 169 } 170 } 171 cout << res << '\n'; 172 } 173 174 int main(int argc, char* argv[]) { 175 int t; 176 cin >> t; 177 for (int i = 0; i < t; ++i) { 178 solve(); 179 } 180 } 181 ``` 182 183 [1800E1 - Unforgivable Curse (easy version)](/contest/1800/problem/E1 "Codeforces Round 855 (Div. 3)") 184 185 Idea: [Aris](/profile/Aris "Candidate Master Aris"), [mutant](/profile/mutant "International Master mutant") 186 187 **Tutorial** 188 189 Tutorial is loading... 190 191 **Solution** 192 193 ``` 194 #include <bits/stdc++.h> 195 196 using namespace std; 197 198 #define sz(v) (int)v.size() 199 #define all(v) v.begin(),v.end() 200 #define eb emplace_back 201 202 void slow_solve(int n, int k, string s, string t) { 203 set<string> was; 204 205 queue<string> q; 206 q.push(s); 207 was.insert(s); 208 209 auto add = [&](string& s, int i, int j) { 210 if (i >= 0 && i < j && j < n) { 211 swap(s[i], s[j]); 212 if (!was.count(s)) { 213 was.insert(s); 214 q.push(s); 215 } 216 swap(s[i], s[j]); 217 } 218 219 }; 220 221 while (!q.empty()) { 222 s = q.front(); q.pop(); 223 for (int i = 0; i < n; ++i) { 224 add(s, i, i+k); 225 add(s, i, i+k+1); 226 add(s, i-k, i); 227 add(s, i-k-1, i); 228 } 229 } 230 cout << (was.count(t) ? "Yes" : "No") << '\n'; 231 } 232 233 void solve() { 234 int n,k; cin >> n >> k; 235 string s; cin >> s; 236 string t; cin >> t; 237 238 if (n <= 5) { 239 slow_solve(n, k, s, t); 240 return; 241 } 242 map<char, int> cnt; 243 for (char c : s) { 244 cnt[c]++; 245 } 246 247 for (char c : t) { 248 cnt[c]--; 249 } 250 251 bool ok = true; 252 for (auto [c, x] : cnt) { 253 ok &= x == 0; 254 } 255 cout << (ok ? "Yes" : "No") << '\n'; 256 } 257 258 int main() { 259 int t; 260 cin >> t; 261 262 while (t--) { 263 solve(); 264 } 265 } 266 ``` 267 268 [1800E2 - Unforgivable Curse (hard version)](/contest/1800/problem/E2 "Codeforces Round 855 (Div. 3)") 269 270 Idea: [Aris](/profile/Aris "Candidate Master Aris"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 271 272 **Tutorial** 273 274 Tutorial is loading... 275 276 **Solution** 277 278 ``` 279 #include <bits/stdc++.h> 280 281 using namespace std; 282 283 #define sz(v) (int)v.size() 284 #define all(v) v.begin(),v.end() 285 #define eb emplace_back 286 287 void solve() { 288 int n, k; cin >> n >> k; 289 string s; cin >> s; 290 string t; cin >> t; 291 vector<int> cnt(26, 0); 292 293 bool ok = true; 294 for (int i = 0; i < n; ++i) { 295 if (i >= k || i+k < n){ 296 cnt[s[i] - 'a']++; 297 cnt[t[i] - 'a']--; 298 } else { 299 ok &= s[i] == t[i]; 300 } 301 } 302 303 cout << (ok && count(all(cnt), 0) == 26 ? "YES" : "NO") << '\n'; 304 } 305 306 int main() { 307 int t; 308 cin >> t; 309 310 while (t--) { 311 solve(); 312 } 313 } 314 ``` 315 316 [1800F - Dasha and Nightmares](/contest/1800/problem/F "Codeforces Round 855 (Div. 3)") 317 318 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") 319 320 **Tutorial** 321 322 Tutorial is loading... 323 324 **Solution** 325 326 ``` 327 #pragma GCC optimize("O3") 328 #pragma GCC optimize("unroll-loops") 329 #pragma GCC target("avx2,avx,fma,bmi2") 330 331 #include <bits/stdc++.h> 332 #include <immintrin.h> 333 #include <ext/pb_ds/assoc_container.hpp> 334 using namespace std; 335 using namespace __gnu_pbds; 336 337 #define endl '\n' 338 //#define int long long 339 #define all(arr) arr.begin(), arr.end() 340 #define multitest() int _gorilla_silverback; cin >> _gorilla_silverback; while (_gorilla_silverback --> 0) 341 #define pikachu push_back 342 #define ls(id) (id << 1 | 1) 343 #define rs(id) ((id << 1) + 2) 344 #define sqr(x) ((x) * (x)) 345 #define dlg(x) (31 - __builtin_clz(x)) 346 #define ulg(x) (32 - __builtin_clz(x)) 347 348 typedef pair<int, int> ipair; 349 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap; 350 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 351 352 const int MAXN = 200200; 353 const int L = 26; 354 355 int n; 356 string srr[MAXN]; 357 int arr[MAXN], brr[MAXN], crr[MAXN]; 358 359 void build() { 360 for (int i = 0; i < n; ++i) { 361 for (char c: srr[i]) { 362 arr[i] ^= (1 << (c - 'a')); 363 brr[i] |= (1 << (c - 'a')); 364 } 365 } 366 } 367 368 long long calc(int c) { 369 int k = 0; 370 for (int i = 0; i < n; ++i) 371 if (brr[i] >> c & 1 ^ 1) crr[k++] = arr[i]; 372 sort(crr, crr + k); 373 int mask = -1 & ((1 << L) - 1) ^ (1 << c); 374 long long ans = 0; 375 for (int i = 0; i < k; ++i) { 376 auto itl = lower_bound(crr, crr + k, crr[i] ^ mask); 377 auto itr = upper_bound(crr, crr + k, crr[i] ^ mask); 378 ans += itr - itl; 379 } 380 return ans >> 1LL; 381 } 382 383 long long solve() { 384 long long ans = 0; 385 for (int c = 0; c < L; ++c) 386 ans += calc(c); 387 return ans; 388 } 389 390 signed main() { 391 ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); 392 cin >> n; 393 for (int i = 0; i < n; ++i) 394 cin >> srr[i]; 395 build(); 396 cout << solve() << endl; 397 } 398 ``` 399 400 [1800G - Symmetree](/contest/1800/problem/G "Codeforces Round 855 (Div. 3)") 401 402 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 403 404 **Tutorial** 405 406 Tutorial is loading... 407 408 **Solution** 409 410 ``` 411 #include <bits/stdc++.h> 412 413 #define int long long 414 #define pb emplace_back 415 #define mp make_pair 416 #define x first 417 #define y second 418 #define all(a) a.begin(), a.end() 419 #define rall(a) a.rbegin(), a.rend() 420 421 typedef long double ld; 422 typedef long long ll; 423 424 using namespace std; 425 426 mt19937 rnd(time(nullptr)); 427 428 const int inf = 2e18; 429 const ll M = 1e9; 430 const ld pi = atan2(0, -1); 431 const ld eps = 1e-6; 432 433 int last; 434 map<vector<int>, int> eq; 435 map<int, bool> symmetrical; 436 437 int dfs(int v, int p, vector<vector<int>> &sl){ 438 vector<int> children; 439 for(int u: sl[v]){ 440 if(u == p) continue; 441 children.emplace_back(dfs(u, v, sl)); 442 } 443 sort(all(children)); 444 if(!eq.count(children)){ 445 map<int, int> cnt; 446 for(int e: children){ 447 cnt[e]++; 448 } 449 int odd = 0, bad = 0; 450 for(auto e: cnt){ 451 if(e.y & 1){ 452 odd++; 453 bad += !symmetrical[e.x]; 454 } 455 } 456 eq[children] = last; 457 symmetrical[last] = odd < 2 && bad == 0; 458 last++; 459 } 460 return eq[children]; 461 } 462 463 void solve(int tc){ 464 int n; 465 cin >> n; 466 eq.clear(); 467 symmetrical.clear(); 468 eq[vector<int>(0)] = 0; 469 symmetrical[0] = true; 470 last = 1; 471 vector<vector<int>> sl(n); 472 for(int i = 1; i < n; ++i){ 473 int u, v; 474 cin >> u >> v; 475 sl[--u].emplace_back(--v); 476 sl[v].emplace_back(u); 477 } 478 cout << (symmetrical[dfs(0, 0, sl)]? "YES" : "NO"); 479 } 480 481 bool multi = true; 482 483 signed main() { 484 int t = 1; 485 if (multi)cin >> t; 486 for (int i = 1; i <= t; ++i) { 487 solve(i); 488 cout << "\n"; 489 } 490 return 0; 491 } 492 ```