1073.md (11954B)
1 Source: https://codeforces.com/blog/entry/62742 2 3 [1073A - Diverse Substring](/contest/1073/problem/A "Educational Codeforces Round 53 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (PikMike)** 10 11 ``` 12 n = int(input()) 13 s = input() 14 for i in range(n - 1): 15 if (s[i] != s[i + 1]): 16 print("YES") 17 print(s[i], s[i + 1], sep="") 18 exit(0) 19 print("NO") 20 ``` 21 22 [1073B - Vasya and Books](/contest/1073/problem/B "Educational Codeforces Round 53 (Rated for Div. 2)") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (Ajosteen)** 29 30 ``` 31 #include <bits/stdc++.h> 32 33 using namespace std; 34 35 const int N = int(2e5) + 9; 36 37 int n; 38 int a[N]; 39 int b[N]; 40 bool u[N]; 41 42 int main() { 43 // freopen("input.txt", "r", stdin); 44 scanf("%d", &n); 45 for(int i = 0; i < n; ++i) { 46 scanf("%d", a + i); 47 } 48 for(int i = 0; i < n; ++i){ 49 scanf("%d", b + i); 50 } 51 52 int pos = 0; 53 for(int i = 0; i < n; ++i){ 54 int x = b[i]; 55 if(u[x]){ 56 printf("0 "); 57 continue; 58 } 59 60 int cnt = 0; 61 while(true){ 62 ++cnt; 63 u[a[pos]] = true; 64 if(a[pos] == x) break; 65 ++pos; 66 } 67 68 ++pos; 69 printf("%d ", cnt); 70 } 71 72 puts(""); 73 return 0; 74 } 75 ``` 76 77 [1073C - Vasya and Robot](/contest/1073/problem/C "Educational Codeforces Round 53 (Rated for Div. 2)") 78 79 **Tutorial** 80 81 Tutorial is loading... 82 83 **Solution (Ajosteen)** 84 85 ``` 86 #include <bits/stdc++.h> 87 88 using namespace std; 89 90 const int N = int(1e5) + 9; 91 92 string s; 93 int n; 94 int x, y; 95 96 void upd(pair<int, int> &pos, char mv, int d){ 97 if(mv == 'U') 98 pos.second += d; 99 if(mv == 'D') 100 pos.second -= d; 101 if(mv == 'L') 102 pos.first -= d; 103 if(mv == 'R') 104 pos.first += d; 105 } 106 107 bool can(pair<int, int> u, pair<int, int> v, int len){ 108 int d = abs(u.first - v.first) + abs(u.second - v.second); 109 if(d % 2 != len % 2) return false; 110 return len >= d; 111 } 112 113 bool ok(int len){ 114 pair<int, int> pos = make_pair(0, 0); 115 for(int i = len; i < n; ++i) 116 upd(pos, s[i], 1); 117 118 int l = 0, r = len; 119 while(true){ 120 if(can(pos, make_pair(x, y), len)) 121 return true; 122 123 if(r == n) break; 124 upd(pos, s[l++], 1); 125 upd(pos, s[r++], -1); 126 } 127 128 return false; 129 } 130 131 int main() { 132 //freopen("input.txt", "r", stdin); 133 134 cin >> n; 135 cin >> s; 136 cin >> x >> y; 137 138 if(!ok(n)){ 139 puts("-1"); 140 return 0; 141 } 142 143 int l = -1, r = n; 144 while(r - l > 1){ 145 int mid = (l + r) / 2; 146 if(ok(mid)) r = mid; 147 else l = mid; 148 } 149 150 cout << r << endl; 151 return 0; 152 } 153 ``` 154 155 [1073D - Berland Fair](/contest/1073/problem/D "Educational Codeforces Round 53 (Rated for Div. 2)") 156 157 **Tutorial** 158 159 Tutorial is loading... 160 161 **Solution (PikMike)** 162 163 ``` 164 #include <bits/stdc++.h> 165 166 #define forn(i, n) for (int i = 0; i < int(n); i++) 167 168 using namespace std; 169 170 const int N = 200 * 1000 + 13; 171 172 typedef long long li; 173 174 int n; 175 int a[N]; 176 177 void get(li T, li& pr, li& cnt){ 178 pr = 0, cnt = 0; 179 forn(i, n){ 180 if (T >= a[i]){ 181 T -= a[i]; 182 pr += a[i]; 183 ++cnt; 184 } 185 } 186 } 187 188 int main() { 189 li T; 190 scanf("%d%lld", &n, &T); 191 forn(i, n) 192 scanf("%d", &a[i]); 193 194 int mn = *min_element(a, a + n); 195 li ans = 0; 196 while (T >= mn){ 197 li pr, cnt; 198 get(T, pr, cnt); 199 ans += cnt * (T / pr); 200 T %= pr; 201 } 202 printf("%lld\n", ans); 203 return 0; 204 } 205 ``` 206 207 [1073E - Segment Sum](/contest/1073/problem/E "Educational Codeforces Round 53 (Rated for Div. 2)") 208 209 **Tutorial** 210 211 Tutorial is loading... 212 213 **Solution (Vovuh)** 214 215 ``` 216 #include <bits/stdc++.h> 217 218 using namespace std; 219 220 #define x first 221 #define y second 222 223 typedef pair<long long, int> pt; 224 225 const int N = 20; 226 const int M = 1 << 10; 227 const int MOD = 998244353; 228 229 int k; 230 int pw10[N]; 231 int bitCnt[M]; 232 233 pt dp[N][M][2]; 234 235 int add(int a, int b) { 236 a += b; 237 if (a >= MOD) a -= MOD; 238 if (a < 0) a += MOD; 239 return a; 240 } 241 242 int mul(int a, int b) { 243 return a * 1ll * b % MOD; 244 } 245 246 int calc(const string &s) { 247 for (int i = 0; i < N; ++i) { 248 for (int j = 0; j < M; ++j) { 249 dp[i][j][0] = dp[i][j][1] = { 0ll, 0 }; 250 } 251 } 252 253 int len = s.size(); 254 dp[0][0][1] = { 1ll, 0 }; 255 for (int i = 0; i < len; ++i) { 256 int cdig = s[i] - '0'; 257 for (int mask = 0; mask < M; ++mask) { 258 if (dp[i][mask][0].x == 0 && dp[i][mask][1].x == 0) continue; 259 for (int dig = (i == 0); dig <= 9; ++dig) { 260 int nmask = mask | (1 << dig); 261 long long cnt = dp[i][mask][0].x; 262 int sum = add(dp[i][mask][0].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD))); 263 dp[i + 1][nmask][0].x += cnt; 264 dp[i + 1][nmask][0].y = add(dp[i + 1][nmask][0].y, sum); 265 } 266 267 for (int dig = (i == 0); dig <= cdig; ++dig) { 268 int nmask = mask | (1 << dig); 269 long long cnt = dp[i][mask][1].x; 270 int sum = add(dp[i][mask][1].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD))); 271 dp[i + 1][nmask][dig == cdig].x += cnt; 272 dp[i + 1][nmask][dig == cdig].y = add(dp[i + 1][nmask][dig == cdig].y, sum); 273 } 274 } 275 } 276 277 int ans = 0; 278 for (int mask = 0; mask < M; ++mask) { 279 if (bitCnt[mask] > k) continue; 280 ans = add(ans, dp[len][mask][0].y); 281 ans = add(ans, dp[len][mask][1].y); 282 } 283 return ans; 284 } 285 286 int calc(long long n) { 287 int len = to_string(n).size(); 288 int ans = 0; 289 for (int l = 1; l < len; ++l) { 290 ans = add(ans, calc(string(l, '9'))); 291 } 292 ans = add(ans, calc(to_string(n))); 293 return ans; 294 } 295 296 int main() { 297 #ifdef _DEBUG 298 freopen("input.txt", "r", stdin); 299 // freopen("output.txt", "w", stdout); 300 #endif 301 302 pw10[0] = 1; 303 for (int i = 1; i < N; ++i) { 304 pw10[i] = mul(pw10[i - 1], 10); 305 } 306 for (int i = 0; i < M; ++i) { 307 bitCnt[i] = __builtin_popcount(i); 308 } 309 310 long long l, r; 311 cin >> l >> r >> k; 312 int ans = add(calc(r), -calc(l - 1)); 313 cout << ans << endl; 314 315 return 0; 316 } 317 ``` 318 319 [1073F - Choosing Two Paths](/contest/1073/problem/F "Educational Codeforces Round 53 (Rated for Div. 2)") 320 321 **Tutorial** 322 323 Tutorial is loading... 324 325 **Solution (Vovuh)** 326 327 ``` 328 #include <bits/stdc++.h> 329 330 using namespace std; 331 332 #define x first 333 #define y second 334 #define size(a) int((a).size()) 335 336 typedef pair<int, int> pt; 337 338 const int N = 200 * 1000 + 11; 339 340 int n; 341 vector<int> g[N]; 342 343 int p[N]; 344 int dist[N]; 345 346 bool bad[N]; 347 int value[N]; 348 pt res[N]; 349 vector<pt> best[N]; 350 351 void dfs(int v, int par = -1, int d = 0) { 352 p[v] = par; 353 dist[v] = d; 354 for (auto to : g[v]) { 355 if (to == par) { 356 continue; 357 } 358 dfs(to, v, d + 1); 359 } 360 } 361 362 int getFarthest(int v) { 363 dfs(v); 364 int res = v; 365 for (int i = 0; i < n; ++i) { 366 if (bad[i]) { 367 continue; 368 } 369 if (dist[res] < dist[i]) { 370 res = i; 371 } 372 } 373 return res; 374 } 375 376 pt get(int v) { 377 return { dist[v], value[v] }; 378 } 379 380 int getBetter(int v, int u) { 381 if (get(v) > get(u)) { 382 return v; 383 } 384 return u; 385 } 386 387 int getBest(int v, int par) { 388 int res = v; 389 for (auto to : g[v]) { 390 if (to == par || bad[to]) { 391 continue; 392 } 393 res = getBetter(res, getBest(to, v)); 394 } 395 return res; 396 } 397 398 pt calc(int v) { 399 dfs(v); 400 401 vector<int> ch; 402 for (auto to : g[v]) { 403 if (!bad[to]) { 404 ch.push_back(to); 405 } 406 } 407 if (size(ch) == 1) { 408 return { v, ch[0] }; 409 } 410 411 vector<int> pref(size(ch)); 412 vector<int> suf(size(ch)); 413 vector<int> best(size(ch)); 414 for (int i = 0; i < size(ch); ++i) { 415 int to = ch[i]; 416 best[i] = pref[i] = suf[i] = getBest(to, v); 417 } 418 for (int i = 1; i < size(ch); ++i) { 419 pref[i] = getBetter(pref[i], pref[i - 1]); 420 suf[size(ch) - i - 1] = getBetter(suf[size(ch) - i - 1], suf[size(ch) - i]); 421 } 422 423 pt ans = { -1, -1 }; 424 pt res = { 0, 0 }; 425 for (int i = 0; i < size(ch); ++i) { 426 int bst = -1; 427 if (i == 0) { 428 bst = suf[i + 1]; 429 } else if (i + 1 == size(ch)) { 430 bst = pref[i - 1]; 431 } else { 432 bst = getBetter(pref[i - 1], suf[i + 1]); 433 } 434 pt curRes = { dist[bst] + dist[best[i]], value[bst] + value[best[i]] }; 435 if (res < curRes) { 436 res = curRes; 437 ans = { best[i], bst }; 438 } 439 } 440 441 return ans; 442 } 443 444 int main() { 445 #ifdef _DEBUG 446 freopen("input.txt", "r", stdin); 447 // freopen("output.txt", "w", stdout); 448 #endif 449 450 cin >> n; 451 for (int i = 0; i < n - 1; ++i) { 452 int x, y; 453 cin >> x >> y; 454 --x, --y; 455 g[x].push_back(y); 456 g[y].push_back(x); 457 } 458 459 int root = -1; 460 for (int i = 0; i < n; ++i) { 461 if (size(g[i]) > 2) { 462 root = i; 463 dfs(i); 464 break; 465 } 466 } 467 468 for (int i = 0; i < n; ++i) { 469 if (size(g[i]) != 1) { 470 continue; 471 } 472 int v = i; 473 while (size(g[v]) < 3) { 474 bad[v] = true; 475 v = p[v]; 476 } 477 best[v].push_back({dist[i] - dist[v], i}); 478 } 479 480 for (int i = 0; i < n; ++i) { 481 if (size(best[i]) >= 2) { 482 sort(best[i].rbegin(), best[i].rend()); 483 value[i] = best[i][0].first + best[i][1].first; 484 res[i] = { best[i][0].second, best[i][1].second }; 485 } 486 } 487 488 int u = getFarthest(root); 489 int v = getFarthest(u); 490 vector<int> path; 491 while (v != u) { 492 path.push_back(v); 493 v = p[v]; 494 } 495 path.push_back(u); 496 497 pt ans = calc(path[size(path) / 2]); 498 499 printf("%d %d\n", res[ans.x].x + 1, res[ans.y].x + 1); 500 printf("%d %d\n", res[ans.x].y + 1, res[ans.y].y + 1); 501 502 return 0; 503 } 504 ``` 505 506 [1073G - Yet Another LCP Problem](/contest/1073/problem/G "Educational Codeforces Round 53 (Rated for Div. 2)") 507 508 **Tutorial** 509 510 Tutorial is loading... 511 512 **Solution (adedalic)** 513 514 ``` 515 #include<bits/stdc++.h> 516 using namespace std; 517 518 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 519 #define sz(a) int((a).size()) 520 521 #define x first 522 #define y second 523 524 typedef long long li; 525 typedef pair<int, int> pt; 526 527 template<class A, class B> ostream& operator <<(ostream &out, const pair<A, B> &p) { 528 return out << "(" << p.x << ", " << p.y << ")"; 529 } 530 template<class A> ostream& operator <<(ostream &out, const vector<A> &v) { 531 out << "["; 532 fore(i, 0, sz(v)) { 533 if(i) out << ", "; 534 out << v[i]; 535 } 536 return out << "]"; 537 } 538 539 const int N = 200 * 1000 + 555; 540 const int LOGN = 18; 541 542 int n, q; 543 char s[N]; 544 545 bool read() { 546 if(!(cin >> n >> q)) 547 return false; 548 assert(scanf("%s", s) == 1); 549 return true; 550 } 551 552 int c[N], id[N], lcp[N]; 553 int mn[LOGN][N]; 554 int lg2[N]; 555 556 void buildSuffArray() { 557 s[n++] = '$'; 558 559 for(int l = 1; l < 2 * n; l <<= 1) { 560 vector< pair<pt, int> > d; 561 fore(i, 0, n) 562 d.emplace_back(l == 1 ? pt(s[i], 0) : pt(c[i], c[(i + (l >> 1)) % n]), i); 563 stable_sort(d.begin(), d.end()); 564 565 c[d[0].y] = 0; 566 fore(i, 1, n) 567 c[d[i].y] = c[d[i - 1].y] + (d[i].x != d[i - 1].x); 568 if(c[d.back().y] == n - 1) 569 break; 570 } 571 572 fore(i, 0, n) 573 id[c[i]] = i; 574 575 int l = 0; 576 fore(i, 0, n) { 577 if(c[i] == n - 1) 578 continue; 579 l = max(0, l - 1); 580 int j = id[c[i] + 1]; 581 582 while(i + l < n && j + l < n && s[i + l] == s[j + l]) 583 l++; 584 lcp[c[i]] = l; 585 } 586 587 n--; 588 lg2[0] = lg2[1] = 0; 589 fore(i, 2, N) { 590 lg2[i] = lg2[i - 1]; 591 if((1 << (lg2[i] + 1)) <= i) 592 lg2[i]++; 593 } 594 595 fore(i, 0, n) 596 mn[0][i] = lcp[i]; 597 fore(pw, 1, LOGN) fore(i, 0, n) { 598 mn[pw][i] = mn[pw - 1][i]; 599 if(i + (1 << (pw - 1)) < n) 600 mn[pw][i] = min(mn[pw][i], mn[pw - 1][i + (1 << (pw - 1))]); 601 } 602 } 603 604 int getMin(int l, int r) { 605 int ln = lg2[r - l]; 606 return min(mn[ln][l], mn[ln][r - (1 << ln)]); 607 } 608 609 int getLCP(int i, int j) { 610 if(i == j) return n - i; 611 i = c[i], j = c[j]; 612 return getMin(min(i, j), max(i, j)); 613 } 614 615 bool cmp(const pt &a, const pt &b) { 616 if(a.x == b.x) 617 return a.y < b.y; 618 int l = getLCP(a.x, b.x); 619 return s[a.x + l] < s[b.x + l]; 620 } 621 622 void solve() { 623 buildSuffArray(); 624 625 fore(_, 0, q) { 626 int k, l; 627 assert(scanf("%d%d", &k, &l) == 2); 628 vector<int> a(k), b(l); 629 fore(i, 0, k) 630 assert(scanf("%d", &a[i]) == 1), a[i]--; 631 fore(j, 0, l) 632 assert(scanf("%d", &b[j]) == 1), b[j]--; 633 634 li ans = 0; 635 vector<pt> c; 636 for(auto v : a) 637 c.emplace_back(v, 1); 638 for(auto v : b) 639 c.emplace_back(v, 0); 640 sort(c.begin(), c.end(), cmp); 641 642 fore(k, 0, 2) { 643 li sum = 0; 644 map<int, int> cnt; 645 646 fore(i, 0, sz(c)) { 647 int id = c[i].x, tp = c[i].y; 648 if(tp == 0) 649 ans += sum; 650 else { 651 cnt[n - id]++; 652 sum += (n - id); 653 } 654 if(i + 1 < sz(c)) { 655 int len = getLCP(c[i].x, c[i + 1].x); 656 while(!cnt.empty()) { 657 auto it = --cnt.end(); 658 if(it->x <= len) 659 break; 660 661 sum -= it->x * 1ll * it->y; 662 cnt[len] += it->y; 663 sum += it->y * 1ll * len; 664 cnt.erase(it); 665 } 666 } 667 } 668 reverse(c.begin(), c.end()); 669 } 670 printf("%lld\n", ans); 671 } 672 } 673 674 int main() { 675 #ifdef _DEBUG 676 freopen("input.txt", "r", stdin); 677 int tt = clock(); 678 #endif 679 cout << fixed << setprecision(15); 680 681 if(read()) { 682 solve(); 683 684 #ifdef _DEBUG 685 cerr << "TIME = " << clock() - tt << endl; 686 #endif 687 } 688 return 0; 689 } 690 ```