2267.md (10270B)
1 Source: https://codeforces.com/blog/entry/157126 2 3 Thanks a lot for participating! 4 5 [2267A - Turn Into a Palindrome](/contest/2267/problem/A "Codeforces Round 1123 (Div. 2)") 6 7 * Idea: [KluydQ](/profile/KluydQ "Expert KluydQ") 8 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ") 9 10 **Solution** 11 12 Tutorial is loading... 13 14 **Implementation** 15 16 ``` 17 #include <bits/stdc++.h> 18 19 using namespace std; 20 21 signed main() { 22 int T; 23 cin >> T; 24 while (T--) { 25 int n; 26 cin >> n; 27 char c; cin >> c; 28 string s; cin >> s; 29 int ans = 0; 30 for (int i = 0; i < n / 2; ++i) { 31 if (s[i] == s[n - i - 1]) continue; 32 if (s[i] == c || s[n - i - 1] == c) ans++; 33 else ans+=2; 34 } 35 cout << ans << '\n'; 36 } 37 } 38 ``` 39 40 **Did you like the problem?** 41 42 * Great problem 43 * Good problem 44 * Bad problem 45 * Didn't solve 46 47 [2267B - Fashionable Array](/contest/2267/problem/B "Codeforces Round 1123 (Div. 2)") 48 49 * Idea: [YF_YUSUF](/profile/YF_YUSUF "Expert YF_YUSUF") 50 * Solution + Editorial: [YF_YUSUF](/profile/YF_YUSUF "Expert YF_YUSUF"), [KluydQ](/profile/KluydQ "Expert KluydQ") 51 52 **Solution** 53 54 Tutorial is loading... 55 56 **Implementation** 57 58 ``` 59 #include <bits/stdc++.h> 60 61 using namespace std; 62 63 int n, a[101], cnt[101]; 64 65 void solve() 66 { 67 cin >> n; 68 69 for(int i = 1; i <= n; i ++) 70 { 71 cin >> a[i]; 72 cnt[a[i]] ++; 73 } 74 for(int i = 1; i <= n; i ++) 75 { 76 for(int j = 100; j >= 1; j --) 77 { 78 if(cnt[j] >= i) cout << j << ' '; 79 } 80 } 81 for(int i = 1; i <= n; i ++) cnt[a[i]] = 0; 82 83 cout << '\n'; 84 } 85 int main() 86 { 87 int t; 88 cin >> t; 89 while(t --) solve(); 90 } 91 ``` 92 93 **Did you like the problem?** 94 95 * Great problem 96 * Good problem 97 * Bad problem 98 * Didn't solve 99 100 [2267C - GCD Treasury](/contest/2267/problem/C "Codeforces Round 1123 (Div. 2)") 101 102 * Idea: [Dibamboo](/profile/Dibamboo "Pupil Dibamboo") 103 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ") 104 105 **Solution** 106 107 Tutorial is loading... 108 109 **Implementation** 110 111 ``` 112 #include <bits/stdc++.h> 113 #define ll long long 114 115 const int N = 3e5 + 12; 116 using namespace std; 117 118 int n, x, a[N], p[N]; 119 ll cnt[N]; 120 121 vector <int> vc[N]; 122 123 void solve() 124 { 125 cin >> n >> x; 126 127 for(int i = 1; i <= n; i ++) 128 { 129 cin >> a[i]; 130 int r = a[i]; 131 a[i] = __gcd(a[i], x); 132 133 for(auto j : vc[a[i]]) 134 { 135 cnt[j] += r; 136 } 137 } 138 ll ans = 0; 139 140 for(auto j : vc[x]) 141 { 142 ans = max(ans, cnt[j]); 143 } 144 for(int i = 1; i <= n; i ++) 145 { 146 for(auto j : vc[a[i]]) cnt[j] = 0; 147 } 148 cout << ans << '\n'; 149 } 150 signed main() 151 { 152 ios_base::sync_with_stdio(0), cin.tie(0); 153 154 for(int i = 2; i <= N - 12; i ++) 155 { 156 if(!p[i]) 157 { 158 for(int j = i; j <= N - 12; j += i) 159 { 160 p[j] = 1; 161 vc[j].push_back(i); 162 } 163 } 164 } 165 int test = 0; 166 if(!test) cin >> test; 167 while(test --) solve(); 168 } 169 // solved by KluydQ 170 ``` 171 172 **Did you like the problem?** 173 174 * Great problem 175 * Good problem 176 * Bad problem 177 * Didn't solve 178 179 [2267D - Backrooms Hill](/contest/2267/problem/D "Codeforces Round 1123 (Div. 2)") 180 181 * Idea: [Aldk](/profile/Aldk "Candidate Master Aldk") 182 * Solution + Editorial: [Aldk](/profile/Aldk "Candidate Master Aldk"), [KluydQ](/profile/KluydQ "Expert KluydQ") 183 184 **Solution** 185 186 Tutorial is loading... 187 188 **Implementation** 189 190 ``` 191 #include <bits/stdc++.h> 192 193 using namespace std; 194 195 void solve() 196 { 197 int n; 198 cin >> n; 199 200 int a[n + 5]; 201 int pos[n + 5]; 202 203 for(int i = 1; i <= n; i ++) 204 { 205 cin >> a[i]; 206 pos[a[i]] = i % 2; 207 } 208 int balance = 0; 209 210 for(int x = n; x > 0; x --) 211 { 212 if(pos[x] % 2 == 0) balance ++; 213 if(pos[x] % 2 == 1) balance --; 214 215 if(abs(balance) > 1) 216 { 217 cout << "NO\n"; 218 return; 219 } 220 } 221 cout << "YES\n"; 222 } 223 int main() 224 { 225 int t; 226 cin >> t; 227 while(t --) solve(); 228 } 229 ``` 230 231 **Did you like the problem?** 232 233 * Great problem 234 * Good problem 235 * Bad problem 236 * Didn't solve 237 238 [2267E - Clean Substrings](/contest/2267/problem/E "Codeforces Round 1123 (Div. 2)") 239 240 * Idea: [KluydQ](/profile/KluydQ "Expert KluydQ") 241 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ") 242 243 **Solution** 244 245 Tutorial is loading... 246 247 **Implementation** 248 249 ``` 250 #include <bits/stdc++.h> 251 252 #define int long long 253 #define sz(x) (int)(x.size()) 254 #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d ) 255 #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d ) 256 257 using namespace std; 258 259 const int N = 2e5 + 12; 260 const int mod = 1e9 + 7; 261 262 int n, q, ans, cnt0, cnt1, pr[N]; 263 string s; 264 265 void solve() 266 { 267 cin >> n >> q >> s; 268 ans = cnt0 = cnt1 = 0; 269 270 FOR(i, 1, n - 1, 1) 271 { 272 pr[i] = 0; 273 274 if(s[i - 1] != s[i]) 275 { 276 pr[i] = 1; 277 ans += i * (n - i); 278 } 279 } 280 FOR(i, 0, n - 1, 1) 281 { 282 if(s[i] == '0') cnt0 ++; 283 if(s[i] == '1') cnt1 ++; 284 } 285 cout << (ans + cnt0 * cnt1) / 2 << ' '; 286 287 FOR(i, 1, q, 1) 288 { 289 int pos; 290 cin >> pos; 291 292 if(pos != 1) 293 { 294 if(pr[pos - 1] == 0) pr[pos - 1] = 1, ans += (pos - 1) * (n - pos + 1); 295 else pr[pos - 1] = 0, ans -= (pos - 1) * (n - pos + 1); 296 } 297 if(pos != n) 298 { 299 if(pr[pos] == 0) pr[pos] = 1, ans += pos * (n - pos); 300 else pr[pos] = 0, ans -= pos * (n - pos); 301 } 302 if(s[pos - 1] == '0') cnt0 --, cnt1 ++, s[pos - 1] = '1'; 303 else cnt1 --, cnt0 ++, s[pos - 1] = '0'; 304 305 cout << (ans + cnt0 * cnt1) / 2 << ' '; 306 } 307 cout << '\n'; 308 } 309 signed main() 310 { 311 ios_base::sync_with_stdio(0), cin.tie(0); 312 313 int t = 0; 314 if(!t) cin >> t; 315 while(t --) solve(); 316 } 317 ``` 318 319 **Did you like the problem?** 320 321 * Great problem 322 * Good problem 323 * Bad problem 324 * Didn't solve 325 326 [2267F1 - XOR Transformations (Easy Version)](/contest/2267/problem/F1 "Codeforces Round 1123 (Div. 2)") 327 328 * Idea: [KluydQ](/profile/KluydQ "Expert KluydQ") 329 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ") 330 331 **Solution** 332 333 Tutorial is loading... 334 335 **Implementation** 336 337 ``` 338 #include <bits/stdc++.h> 339 340 using namespace std; 341 342 const int N = 2048; 343 int n, m, tim, a[N], cnt[N], ans[N]; 344 345 void transform() 346 { 347 vector <int> v; 348 349 for(int i = 1; i <= n; i ++) 350 { 351 for(int j = i + 1; j <= n; j ++) 352 { 353 v.push_back(a[i] ^ a[j]); 354 } 355 } 356 sort(v.begin(), v.end()); 357 for(int i = 1; i <= n; i ++) a[i] = v[i - 1]; 358 } 359 void solve() 360 { 361 cin >> n >> m; 362 363 for(int i = 1; i <= n; i ++) 364 { 365 cin >> a[i]; 366 } 367 sort(a + 1, a + n + 1); 368 int lim = 0; 369 370 ans[lim] = a[n] - a[1]; 371 372 while(a[n] != 0) 373 { 374 lim ++, transform(); 375 ans[lim] = a[n] - a[1]; 376 } 377 for(int i = 1; i <= m; i ++) 378 { 379 int x; 380 cin >> x; 381 382 if(x >= lim) cout << ans[lim] << '\n'; 383 else cout << ans[x] << '\n'; 384 } 385 } 386 signed main() 387 { 388 ios_base::sync_with_stdio(0), cin.tie(0); 389 390 int test = 0; 391 if(!test) cin >> test; 392 while(test --) solve(); 393 } 394 ``` 395 396 **Did you like the problem?** 397 398 * Great problem 399 * Good problem 400 * Bad problem 401 * Didn't solve 402 403 [2267F2 - XOR Transformations (Hard Version)](/contest/2267/problem/F2 "Codeforces Round 1123 (Div. 2)") 404 405 * Idea: [KluydQ](/profile/KluydQ "Expert KluydQ") 406 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ") 407 408 **Solution** 409 410 Tutorial is loading... 411 412 **Implementation** 413 414 ``` 415 #include <bits/stdc++.h> 416 417 using namespace std; 418 419 const int N = 3e5 + 12; 420 421 int n, m, tim, a[N], cnt[N], ans[N]; 422 int t[N * 30], son[N * 30][2]; 423 424 void update(int x, int v = 1) 425 { 426 t[v] ++; 427 428 for(int i = 29; i >= 0; i --) 429 { 430 if((x >> i) & 1) 431 { 432 if(!son[v][1]) son[v][1] = ++ tim; 433 v = son[v][1]; 434 } 435 else 436 { 437 if(!son[v][0]) son[v][0] = ++ tim; 438 v = son[v][0]; 439 } 440 t[v] ++; 441 } 442 } 443 int get(int x, int k, int v = 1) 444 { 445 int res = 0; 446 447 for(int i = 29; i >= 0; i --) 448 { 449 int b = (x >> i) & 1; 450 451 if(t[son[v][b]] >= k) v = son[v][b], res += (1 << i) * b; 452 else k -= t[son[v][b]], v = son[v][b ^ 1], res += (1 << i) * (b ^ 1); 453 } 454 return res ^ x; 455 } 456 void transform() 457 { 458 for(int v = 1; v <= tim; v ++) t[v] = son[v][0] = son[v][1] = 0; 459 set <pair <int, int>> st; tim = 1; 460 461 for(int i = 1; i <= n; i ++) update(a[i]), cnt[i] = 2; 462 for(int i = 1; i <= n; i ++) st.insert({get(a[i], 2), i}); 463 464 vector <int> upd; 465 466 for(int _ = 1; _ <= 2 * n; _ ++) 467 { 468 auto it = st.begin(); 469 int i = (*it).second; 470 471 upd.push_back((*it).first); 472 st.erase(it), cnt[i] ++; 473 474 if(cnt[i] > n) continue; 475 st.insert({get(a[i], cnt[i]), i}); 476 } 477 for(int i = 1; i <= n; i ++) a[i] = upd[(i - 1) * 2]; 478 } 479 void solve() 480 { 481 cin >> n >> m; 482 483 for(int i = 1; i <= n; i ++) 484 { 485 cin >> a[i]; 486 } 487 sort(a + 1, a + n + 1); 488 int lim = 0; 489 490 ans[lim] = a[n] - a[1]; 491 492 while(a[n] != 0) 493 { 494 lim ++, transform(); 495 ans[lim] = a[n] - a[1]; 496 } 497 for(int i = 1; i <= m; i ++) 498 { 499 int x; 500 cin >> x; 501 502 if(x >= lim) cout << ans[lim] << '\n'; 503 else cout << ans[x] << '\n'; 504 } 505 } 506 signed main() 507 { 508 ios_base::sync_with_stdio(0), cin.tie(0); 509 510 int test = 0; 511 if(!test) cin >> test; 512 while(test --) solve(); 513 } 514 ``` 515 516 **Did you like the problem?** 517 518 * Great problem 519 * Good problem 520 * Bad problem 521 * Didn't solve 522 523 [2267G - New LRT](/contest/2267/problem/G "Codeforces Round 1123 (Div. 2)") 524 525 * Idea: [Aldk](/profile/Aldk "Candidate Master Aldk") 526 * Solution + Editorial: [Aldk](/profile/Aldk "Candidate Master Aldk"), [KluydQ](/profile/KluydQ "Expert KluydQ") 527 528 **Solution** 529 530 Tutorial is loading... 531 532 **Implementation** 533 534 ``` 535 #include <bits/stdc++.h> 536 537 #define sz(x) (int)(x.size()) 538 #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d ) 539 #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d ) 540 541 using namespace std; 542 543 const int N = (1 << 20) + 5; 544 const int mod = 1e9 + 7; 545 546 int n, m, c[N], dp[N], cnt[N], st[N][21]; 547 548 void add(int &x, int y) 549 { 550 x += y; 551 if(x >= mod) x -= mod; 552 } 553 void solve() 554 { 555 cin >> n >> m; 556 557 FOR( i, 1, m, 1 ) 558 { 559 cin >> c[i]; 560 } 561 dp[0] = cnt[0] = 1; 562 563 FOR( i, 1, n, 1 ) 564 { 565 st[i][0] = 0; 566 567 FOR( j, 0, 19, 1 ) 568 { 569 st[i][j + 1] = st[i][j]; 570 if(!((m >> j) & 1) || i < (1 << j)) continue; 571 572 else 573 { 574 add(st[i][j + 1], st[i - (1 << j)][j]); 575 add(st[i][j + 1], dp[i - (1 << j)]); 576 } 577 } 578 dp[i] = st[i][20]; 579 } 580 FOR( i, 1, n, 1 ) 581 { 582 st[i][0] = 0; 583 584 FOR( j, 0, 19, 1 ) 585 { 586 st[i][j + 1] = st[i][j]; 587 if(!((m >> j) & 1) || i < (1 << j)) continue; 588 589 else 590 { 591 add(st[i][j + 1], st[i - (1 << j)][j]); 592 add(st[i][j + 1], cnt[i - (1 << j)]); 593 } 594 } 595 cnt[i] = st[i][20]; 596 add(cnt[i], dp[i]); 597 } 598 int ans = 0; 599 600 FOR( i, 1, m, 1 ) 601 { 602 if((m & i) == i) add(ans, c[i] * 1ll * cnt[n - i] % mod); 603 } 604 cout << ans << '\n'; 605 } 606 signed main() 607 { 608 ios_base::sync_with_stdio(0), cin.tie(0); 609 610 int t = 0; 611 if(!t) cin >> t; 612 while(t --) solve(); 613 } 614 ``` 615 616 **Did you like the problem?** 617 618 * Great problem 619 * Good problem 620 * Bad problem 621 * Didn't solve