2283.md (11648B)
1 Source: https://codeforces.com/blog/entry/158495 2 3 [2283A - Numbers on the Board](/contest/2283/problem/A "Educational Codeforces Round 196 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 t = int(input()) 13 for i in range(t): 14 l, r = map(int, input().split()) 15 if r < 0 or l > 0: 16 print(r - l) 17 else: 18 m = min(r, -l) 19 print(max(0, r - l - 2 * m - 1)) 20 ``` 21 22 [2283B - Rhythmic String](/contest/2283/problem/B "Educational Codeforces Round 196 (Rated for Div. 2)") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution** 29 30 ``` 31 #include<bits/stdc++.h> 32 33 using namespace std; 34 35 void solve() 36 { 37 int n; 38 cin >> n; 39 vector<int> a(n); 40 for(int i = 0; i < n; i++) 41 cin >> a[i]; 42 int ans = 1; 43 for(int i = 0; i < n; i++) 44 { 45 int cur = 0; 46 for(int j = 0; j < n; j++) 47 if(a[j] % a[i] == 0) 48 cur++; 49 ans = max(ans, cur); 50 } 51 cout << n - ans << endl; 52 } 53 54 int main() 55 { 56 ios_base::sync_with_stdio(0); 57 cin.tie(0); 58 int t; 59 cin >> t; 60 for(int i = 0; i < t; i++) 61 solve(); 62 } 63 ``` 64 65 [2283C - Big XOR](/contest/2283/problem/C "Educational Codeforces Round 196 (Rated for Div. 2)") 66 67 **Tutorial** 68 69 Tutorial is loading... 70 71 **Solution** 72 73 ``` 74 #include<bits/stdc++.h> 75 76 using namespace std; 77 78 void solve() 79 { 80 int n; 81 cin >> n; 82 int k = 0; 83 for(int i = 1; i <= n; i++) k |= i; 84 int m = 0; 85 vector<int> ans(n, 0); 86 for(int i = 1; i <= n; i++) m ^= i; 87 int d = 0; 88 cout << k << endl; 89 while((k >> d) & 1) d++; 90 cout << d << endl; 91 for(int i = d; i >= 1; i--) 92 if(((m >> i) & 1) == 0) 93 { 94 int x = (1 << (i - 1)); 95 cout << x << endl; 96 ans[x - 1] = 1; 97 m ^= x; 98 m ^= (x << 1); 99 } 100 for(int i = 0; i < n; i++) 101 cout << ans[i] << " "; 102 cout << endl; 103 } 104 105 int main() 106 { 107 ios_base::sync_with_stdio(0); 108 cin.tie(0); 109 int t; 110 cin >> t; 111 for(int i = 0; i < t; i++) 112 solve(); 113 } 114 ``` 115 116 [2283D - Black, Gray and White](/contest/2283/problem/D "Educational Codeforces Round 196 (Rated for Div. 2)") 117 118 **Tutorial** 119 120 Tutorial is loading... 121 122 **Solution (awoo)** 123 124 ``` 125 #include <bits/stdc++.h> 126 127 using namespace std; 128 129 #define forn(i, n) for(int i = 0; i < int(n); i++) 130 131 int main() { 132 #ifdef _DEBUG 133 freopen("input.txt", "r", stdin); 134 #endif 135 cin.tie(0); 136 ios::sync_with_stdio(false); 137 138 int tc; 139 cin >> tc; 140 while (tc--){ 141 int n; 142 cin >> n; 143 vector<vector<int>> g(n); 144 forn(i, n - 1){ 145 int v, u; 146 cin >> v >> u; 147 --v, --u; 148 g[v].push_back(u); 149 g[u].push_back(v); 150 } 151 if (n % 2 == 0){ 152 cout << n + 1 << '\n'; 153 continue; 154 } 155 int ans = n; 156 for (int k : {n + 1, n + 2}){ 157 int u = k == n + 1 ? n / 2 : 0; 158 vector<int> clr(n, -1); 159 queue<int> q; 160 clr[u] = 0; 161 int c = 1; 162 forn(i, n) if (clr[i] == -1){ 163 q.push(i); 164 clr[i] = c; 165 while (!q.empty()){ 166 int v = q.front(); 167 q.pop(); 168 for (int u : g[v]) if (clr[u] == -1){ 169 clr[u] = c; 170 q.push(u); 171 } 172 } 173 ++c; 174 } 175 bool any = false; 176 for (int i = 1; i <= n; ++i) if (k - i <= n && k - i != i) 177 any |= clr[i - 1] != clr[k - i - 1]; 178 if (any) 179 ans = k; 180 } 181 cout << ans << '\n'; 182 } 183 } 184 ``` 185 186 [2283E - Partition of a Binary String](/contest/2283/problem/E "Educational Codeforces Round 196 (Rated for Div. 2)") 187 188 **Tutorial** 189 190 Tutorial is loading... 191 192 **Solution** 193 194 ``` 195 #include<bits/stdc++.h> 196 197 using namespace std; 198 199 const int N = 5043; 200 const int MOD = 998244353; 201 int bell[N]; 202 int C[N][N]; 203 int dp[N]; 204 205 int add(int x, int y) 206 { 207 x += y; 208 while(x >= MOD) x -= MOD; 209 while(x < 0) x += MOD; 210 return x; 211 } 212 213 int mul(int x, int y) 214 { 215 return (x * 1ll * y) % MOD; 216 } 217 218 void precalc() 219 { 220 for(int i = 0; i < N; i++) 221 { 222 C[i][0] = C[i][i] = 1; 223 for(int j = 1; j < i; j++) 224 C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]); 225 } 226 bell[0] = 1; 227 for(int i = 1; i < N; i++) 228 for(int k = 0; k < i; k++) 229 bell[i] = add(bell[i], mul(C[i - 1][k], bell[i - k - 1])); 230 dp[0] = 1; 231 for(int i = 1; i < N; i++) 232 { 233 if(i >= 2) dp[i] = add(dp[i], dp[i - 2]); 234 if(i >= 3) dp[i] = add(dp[i], dp[i - 3]); 235 } 236 } 237 238 void solve() 239 { 240 int n; 241 cin >> n; 242 string s; 243 cin >> s; 244 int zero = 0, one = 0, cur = 0; 245 int ans = 1; 246 int val = 0; 247 for(int i = 0; i < n; i++) 248 { 249 bool neq_adj = false; 250 if(i > 0 && s[i] != s[i - 1]) neq_adj = true; 251 if(i + 1 < n && s[i] != s[i + 1]) neq_adj = true; 252 if(i > 0 && s[i] == s[i - 1]) 253 { 254 ans = mul(ans, dp[cur]); 255 cur = 0; 256 } 257 if(neq_adj) 258 { 259 cur++; 260 val += 2; 261 } 262 else 263 { 264 ans = mul(ans, dp[cur]); 265 cur = 0; 266 if(s[i] == '0') zero++; 267 else one++; 268 val++; 269 } 270 } 271 ans = mul(ans, dp[cur]); 272 ans = mul(ans, bell[zero]); 273 ans = mul(ans, bell[one]); 274 cout << val << " " << ans << endl; 275 } 276 277 int main() 278 { 279 ios_base::sync_with_stdio(0); 280 cin.tie(0); 281 precalc(); 282 int t; 283 cin >> t; 284 for(int i = 0; i < t; i++) 285 solve(); 286 } 287 ``` 288 289 [2283F - Minimize the Graph](/contest/2283/problem/F "Educational Codeforces Round 196 (Rated for Div. 2)") 290 291 **Tutorial** 292 293 Tutorial is loading... 294 295 **Solution** 296 297 ``` 298 #include<bits/stdc++.h> 299 300 using namespace std; 301 302 const int INF = int(1e9); 303 304 struct FenwickSum 305 { 306 vector<int> f; 307 int n; 308 309 void add(int i, int x) 310 { 311 for(; i < n; i |= (i + 1)) 312 f[i] += x; 313 } 314 315 int get(int i) 316 { 317 int ans = 0; 318 for(; i >= 0; i = (i & (i + 1)) - 1) 319 ans += f[i]; 320 return ans; 321 } 322 323 int get(int l, int r) 324 { 325 return get(r) - get(l - 1); 326 } 327 328 FenwickSum(int n = 0) : n(n) 329 { 330 f.resize(n); 331 } 332 }; 333 334 struct event 335 { 336 int moment; 337 int type; 338 int idx; 339 event(int moment = 0, int type = 0, int idx = 0) : moment(moment), type(type), idx(idx) {}; 340 }; 341 342 bool operator<(const event& a, const event& b) 343 { 344 if(a.moment != b.moment) return a.moment < b.moment; 345 if(a.type != b.type) return a.type < b.type; 346 return a.idx < b.idx; 347 } 348 349 void solve() 350 { 351 int n; 352 cin >> n; 353 vector<int> l(n), r(n); 354 for(int i = 1; i < n; i++) 355 { 356 cin >> l[i] >> r[i]; 357 l[i]--; 358 } 359 360 vector<int> h(n, INF); 361 set<int> s; 362 for(int i = 0; i < n; i++) s.insert(i); 363 for(int i = 1; i < n; i++) 364 { 365 int lf = l[i]; 366 int rg = r[i]; 367 while(true) 368 { 369 auto it = s.lower_bound(lf); 370 if(it == s.end() || *it >= rg) break; 371 h[*it] = i; 372 s.erase(it); 373 } 374 } 375 376 vector<event> events; 377 for(int i = 0; i < n; i++) 378 events.push_back(event(h[i], 0, i)); 379 for(int i = 1; i < n; i++) 380 events.push_back(event(r[i] - 1, 1, i)); 381 382 long long ans = 0; 383 384 FenwickSum f(n + 1); 385 for(int i = 0; i < n; i++) 386 f.add(i, 1); 387 388 sort(events.begin(), events.end()); 389 for(auto e : events) 390 if(e.type == 0) 391 f.add(e.idx, -1); 392 else 393 { 394 int lf = l[e.idx]; 395 int rg = r[e.idx]; 396 ans += f.get(lf, rg - 1); 397 } 398 399 cout << ans << endl; 400 } 401 402 int main() 403 { 404 ios_base::sync_with_stdio(0); 405 cin.tie(0); 406 int t; 407 cin >> t; 408 for(int i = 0; i < t; i++) 409 solve(); 410 } 411 ``` 412 413 [2283G - Order Statistics on the Graph](/contest/2283/problem/G "Educational Codeforces Round 196 (Rated for Div. 2)") 414 415 **Tutorial** 416 417 Tutorial is loading... 418 419 **Solution** 420 421 ``` 422 #include<bits/stdc++.h> 423 424 using namespace std; 425 426 const int N = 20; 427 const int V = 1 << N; 428 const int Q = int(1e5); 429 430 int adj_mask[N]; 431 int idx[N]; 432 int nxt[V]; 433 vector<int> gt[V]; 434 vector<pair<long long, int>> que[N]; 435 int ans[N * Q]; 436 bool used[V]; 437 int cycle_pos[V]; 438 vector<int> cycle; 439 vector<int> dfs_stack; 440 441 vector<int> get_unique(const vector<int>& a) 442 { 443 vector<int> b = a; 444 sort(b.begin(), b.end()); 445 b.erase(unique(b.begin(), b.end()), b.end()); 446 return b; 447 } 448 449 vector<int> get_masks(const vector<int>& a) 450 { 451 int n = a.size(); 452 auto b = get_unique(a); 453 int m = b.size(); 454 vector<int> masks(m - 1); 455 for(int i = 0; i < m - 1; i++) 456 { 457 int mask = 0; 458 for(int j = 0; j < n; j++) 459 if(a[j] > b[i]) 460 mask |= (1 << j); 461 masks[i] = mask; 462 } 463 return masks; 464 } 465 466 vector<int> restore(const vector<int>& a, const vector<int>& masks) 467 { 468 int n = a.size(); 469 auto b = get_unique(a); 470 int m = b.size(); 471 vector<int> ans(n, b[0]); 472 for(int i = 0; i < m - 1; i++) 473 for(int j = 0; j < n; j++) 474 if((masks[i] >> j) & 1) 475 ans[j] = b[i + 1]; 476 return ans; 477 } 478 479 void dfs(int x) 480 { 481 used[x] = true; 482 int depth = dfs_stack.size(); 483 dfs_stack.push_back(x); 484 for(auto y : gt[x]) 485 if(!used[y]) 486 dfs(y); 487 for(auto [t, i] : que[x]) 488 { 489 if(t <= depth) 490 ans[i] = dfs_stack[depth - t]; 491 else 492 { 493 long long add = t - depth; 494 int pos = (cycle_pos[dfs_stack[0]] + add) % cycle.size(); 495 ans[i] = cycle[pos]; 496 } 497 } 498 dfs_stack.pop_back(); 499 } 500 501 void solve() 502 { 503 int n, m, q; 504 cin >> n >> m >> q; 505 for(int i = 0; i < n; i++) 506 cin >> idx[i]; 507 for(int i = 0; i < m; i++) 508 { 509 int x, y; 510 cin >> x >> y; 511 --x; 512 --y; 513 adj_mask[y] |= (1 << x); 514 } 515 516 vector<long long> t(q); 517 vector<vector<int>> a(q, vector<int>(n)); 518 for(int i = 0; i < q; i++) 519 { 520 cin >> t[i]; 521 for(int j = 0; j < n; j++) 522 cin >> a[i][j]; 523 } 524 525 int qid = 0; 526 for(int i = 0; i < q; i++) 527 { 528 auto masks = get_masks(a[i]); 529 for(auto mask : masks) 530 { 531 que[mask].push_back(make_pair(t[i], qid)); 532 qid++; 533 } 534 } 535 536 for(int i = 0; i < (1 << n); i++) 537 { 538 int ni = 0; 539 for(int j = 0; j < n; j++) 540 { 541 int cur_mask = adj_mask[j] & i; 542 if(__builtin_popcount(cur_mask) >= idx[j]) 543 ni |= (1 << j); 544 } 545 nxt[i] = ni; 546 gt[ni].push_back(i); 547 } 548 549 for(int i = 0; i < (1 << n); i++) 550 { 551 if(used[i]) continue; 552 int j = i; 553 while(!used[j]) 554 { 555 used[j] = true; 556 j = nxt[j]; 557 } 558 int k = j; 559 cycle = {}; 560 do 561 { 562 cycle_pos[k] = cycle.size(); 563 cycle.push_back(k); 564 k = nxt[k]; 565 } 566 while(k != j); 567 for(auto c : cycle) dfs(c); 568 } 569 570 qid = 0; 571 for(int i = 0; i < q; i++) 572 { 573 auto masks = get_masks(a[i]); 574 vector<int> res; 575 for(int i = 0; i < masks.size(); i++) 576 { 577 res.push_back(ans[qid]); 578 qid++; 579 } 580 vector<int> res2 = restore(a[i], res); 581 for(auto x : res2) cout << x << " "; 582 cout << "\n"; 583 } 584 } 585 586 int main() 587 { 588 ios_base::sync_with_stdio(0); 589 cin.tie(0); 590 int t = 1; 591 // cin >> t; 592 for(int i = 0; i < t; i++) 593 solve(); 594 } 595 ```