2260.md (10355B)
1 Source: https://codeforces.com/blog/entry/156529 2 3 [2260A - Monocarp's Contest](/contest/2260/problem/A "Educational Codeforces Round 194 (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 n = int(input()) 15 a = list(map(int, input().split())) 16 17 cnt0 = a.count(0) 18 if cnt0 >= 2: 19 print(a[0] + a[-1]) 20 else: 21 print(-1) 22 ``` 23 24 [2260B - Monocarp and Projects](/contest/2260/problem/B "Educational Codeforces Round 194 (Rated for Div. 2)") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution** 31 32 ``` 33 #include<bits/stdc++.h> 34 35 using namespace std; 36 37 void solve() 38 { 39 long long x, y, k; 40 cin >> x >> y >> k; 41 long long ans = 0; 42 for(long long i = 0; i < min(y, k); i++) 43 ans += (y + i) % (x + i); 44 long long full = max(0ll, k - y); 45 ans += full * (y - x); 46 cout << ans << endl; 47 } 48 49 int main() 50 { 51 ios_base::sync_with_stdio(0); 52 cin.tie(0); 53 int t; 54 cin >> t; 55 for(int i = 0; i < t; i++) 56 solve(); 57 } 58 ``` 59 60 [2260C - Maximize XOR, Minimize Operations](/contest/2260/problem/C "Educational Codeforces Round 194 (Rated for Div. 2)") 61 62 **Tutorial** 63 64 Tutorial is loading... 65 66 **Solution** 67 68 ``` 69 #include<bits/stdc++.h> 70 71 using namespace std; 72 73 void solve() 74 { 75 int x, y; 76 cin >> x >> y; 77 int s = x + y; 78 for(int d = (1 << 30); d >= 1; d >>= 1) 79 if((s & d) != 0 && x >= d) 80 x -= d; 81 cout << s << " " << x << endl; 82 } 83 84 int main() 85 { 86 ios_base::sync_with_stdio(0); 87 cin.tie(0); 88 int t; 89 cin >> t; 90 for(int i = 0; i < t; i++) 91 solve(); 92 } 93 ``` 94 95 [2260D - Signs of Prefix Sums](/contest/2260/problem/D "Educational Codeforces Round 194 (Rated for Div. 2)") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution** 102 103 ``` 104 #include<bits/stdc++.h> 105 106 using namespace std; 107 108 const int K = 3; 109 const int INF = int(1e9); 110 111 pair<int, int> get_segment(char c) 112 { 113 if(c == '0') return {K, K}; 114 if(c == '-') return {0, K - 1}; 115 return {K + 1, K * 2}; 116 } 117 118 void solve() 119 { 120 int n; 121 string s; 122 cin >> n >> s; 123 vector<vector<int>> dp(n + 1, vector<int>(2 * K + 1, INF)); 124 dp[0][K] = 0; 125 for(int i = 0; i < n; i++) 126 for(int j = 0; j < 2 * K + 1; j++) 127 { 128 if(dp[i][j] == INF) continue; 129 auto [l, r] = get_segment(s[i]); 130 for(int k = l; k <= r; k++) 131 { 132 if(k == j) continue; 133 int& d = dp[i + 1][k]; 134 d = min(d, max(dp[i][j], abs(k - j))); 135 } 136 } 137 int ans = *min_element(dp[n].begin(), dp[n].end()); 138 if(ans == INF) ans = -1; 139 cout << ans << endl; 140 } 141 142 int main() 143 { 144 ios_base::sync_with_stdio(0); 145 cin.tie(0); 146 int t; 147 cin >> t; 148 for(int i = 0; i < t; i++) 149 solve(); 150 } 151 ``` 152 153 [2260E - Cyclic Balance](/contest/2260/problem/E "Educational Codeforces Round 194 (Rated for Div. 2)") 154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Solution** 160 161 ``` 162 #include<bits/stdc++.h> 163 164 using namespace std; 165 166 int get(int c00, int c11, int cd) 167 { 168 int len = c00 + c11 + cd; 169 int lf = len / 4; 170 int rg = 1e8; 171 int ans = 1e8; 172 while(rg >= lf) 173 { 174 int mid = (lf + rg) / 2; 175 int need_break = max(0, c00 - mid) + max(0, c11 - mid); 176 if(need_break + cd / 2 <= mid) 177 { 178 ans = mid; 179 rg = mid - 1; 180 } 181 else 182 lf = mid + 1; 183 } 184 return ans; 185 } 186 187 void solve() 188 { 189 int n, q; 190 cin >> n >> q; 191 string s; 192 cin >> s; 193 vector<int> pref1(n + 1), prefdiff(n); 194 for(int i = 0; i < n; i++) 195 pref1[i + 1] = pref1[i] + (s[i] - '0'); 196 for(int i = 0; i + 1 < n; i++) 197 prefdiff[i + 1] = prefdiff[i] + (s[i] != s[i + 1]); 198 199 for(int i = 0; i < q; i++) 200 { 201 int l, r; 202 cin >> l >> r; 203 if(l == r) 204 cout << 3 << "\n"; 205 else 206 { 207 int c1 = pref1[r] - pref1[l - 1]; 208 int cd = prefdiff[r - 1] - prefdiff[l - 1]; 209 if(s[l - 1] != s[r - 1]) 210 cd++; 211 int c0 = (r - l + 1) - c1; 212 int c00 = c0 - (cd / 2); 213 int c11 = c1 - (cd / 2); 214 cout << get(c00, c11, cd) * 4 - (r - l + 1) << "\n"; 215 } 216 } 217 } 218 219 int main() 220 { 221 ios_base::sync_with_stdio(0); 222 cin.tie(0); 223 int t = 1; 224 //cin >> t; 225 for(int i = 0; i < t; i++) 226 solve(); 227 } 228 ``` 229 230 [2260F - Edge Three-Coloring](/contest/2260/problem/F "Educational Codeforces Round 194 (Rated for Div. 2)") 231 232 **Tutorial** 233 234 Tutorial is loading... 235 236 **Solution** 237 238 ``` 239 #include<bits/stdc++.h> 240 241 using namespace std; 242 243 const int N = 3010; 244 245 vector<pair<int, int>> g[N]; 246 int p[N]; 247 int pe[N]; 248 int used[N]; 249 int n, m; 250 vector<int> bad_edges; 251 int cycle[N]; 252 int xs[N], ys[N]; 253 254 void dfs1(int x) 255 { 256 for(auto [y, i] : g[x]) 257 if(p[y] == -1) 258 { 259 p[y] = x; 260 pe[y] = i; 261 dfs1(y); 262 } 263 else if(p[x] != y) 264 bad_edges.push_back(i); 265 } 266 267 void go_to_root(int x) 268 { 269 while(x != 0) 270 { 271 cycle[pe[x]] ^= 1; 272 x = p[x]; 273 } 274 } 275 276 void dfs2(int x) 277 { 278 used[x] = true; 279 for(auto [y, i] : g[x]) 280 if(cycle[i] == 0 && !used[y]) 281 dfs2(y); 282 } 283 284 void solve() 285 { 286 cin >> n >> m; 287 bad_edges.clear(); 288 for(int i = 0; i < n; i++) 289 { 290 g[i].clear(); 291 p[i] = -1; 292 pe[i] = -1; 293 } 294 for(int i = 0; i < m; i++) 295 { 296 int x, y; 297 cin >> x >> y; 298 --x; 299 --y; 300 xs[i] = x; 301 ys[i] = y; 302 g[x].push_back(make_pair(y, i)); 303 g[y].push_back(make_pair(x, i)); 304 } 305 306 p[0] = 0; 307 dfs1(0); 308 sort(bad_edges.begin(), bad_edges.end()); 309 bad_edges.erase(unique(bad_edges.begin(), bad_edges.end()), bad_edges.end()); 310 311 int k = bad_edges.size(); 312 for(int mask = 1; mask < (1 << k); mask++) 313 { 314 for(int edge = 0; edge < m; edge++) cycle[edge] = 0; 315 for(int bit = 0; bit < k; bit++) 316 if((mask >> bit) & 1) 317 { 318 go_to_root(xs[bad_edges[bit]]); 319 go_to_root(ys[bad_edges[bit]]); 320 cycle[bad_edges[bit]] ^= 1; 321 } 322 for(int vertex = 0; vertex < n; vertex++) 323 used[vertex] = 0; 324 dfs2(0); 325 bool good = true; 326 for(int vertex = 0; vertex < n; vertex++) 327 if(!used[vertex]) 328 good = false; 329 if(good) 330 { 331 cout << "YES\n"; 332 return; 333 } 334 } 335 cout << "NO\n"; 336 } 337 338 int main() 339 { 340 ios_base::sync_with_stdio(0); 341 cin.tie(0); 342 int t; 343 cin >> t; 344 for(int i = 0; i < t; i++) 345 solve(); 346 } 347 ``` 348 349 [2260G - Sortable Permutations](/contest/2260/problem/G "Educational Codeforces Round 194 (Rated for Div. 2)") 350 351 **Tutorial** 352 353 Tutorial is loading... 354 355 **Solution** 356 357 ``` 358 #include<bits/stdc++.h> 359 360 using namespace std; 361 362 const int MOD = 998244353; 363 364 int add(int x, int y) 365 { 366 x += y; 367 while(x >= MOD) x -= MOD; 368 while(x < 0) x += MOD; 369 return x; 370 } 371 372 int mul(int x, int y) 373 { 374 return (x * 1ll * y) % MOD; 375 } 376 377 int binpow(int x, int y) 378 { 379 int z = 1; 380 while(y > 0) 381 { 382 if(y % 2 == 1) z = mul(z, x); 383 x = mul(x, x); 384 y /= 2; 385 } 386 return z; 387 } 388 389 int inv(int x) 390 { 391 return binpow(x, MOD - 2); 392 } 393 394 const int N = 200043; 395 396 int mind[N]; 397 int fact[N]; 398 int ifact[N]; 399 400 void precalc() 401 { 402 for(int i = 2; i < N; i++) 403 for(int j = i; j < N; j += i) 404 if(mind[j] == 0) 405 mind[j] = i; 406 407 fact[0] = 1; 408 for(int i = 1; i < N; i++) 409 fact[i] = mul(fact[i - 1], i); 410 ifact[N - 1] = inv(fact[N - 1]); 411 for(int i = N - 1; i >= 1; i--) 412 ifact[i - 1] = mul(ifact[i], i); 413 } 414 415 int choose(int n, int k) 416 { 417 if(n < 0 || n < k || k < 0) return 0; 418 return mul(fact[n], mul(ifact[k], ifact[n - k])); 419 } 420 421 int n; 422 423 vector<int> factorize(int x) 424 { 425 vector<int> res; 426 while(x != 1) 427 { 428 res.push_back(mind[x]); 429 x /= mind[x]; 430 } 431 return res; 432 } 433 434 void gen(const vector<int>& d, int i, long long cur, int m, vector<pair<long long, int>>& res) 435 { 436 if(i == d.size()) res.push_back(make_pair(cur, m)); 437 else 438 { 439 gen(d, i + 1, cur, m, res); 440 gen(d, i + 1, cur * 1ll * d[i], -m, res); 441 } 442 } 443 444 void solve() 445 { 446 cin >> n; 447 vector<pair<pair<long long, int>, int>> edges; 448 for(int i = 1; i < n; i++) 449 { 450 auto f1 = factorize(i); 451 auto f2 = factorize(i + 1); 452 for(auto x : f2) f1.push_back(x); 453 sort(f1.begin(), f1.end()); 454 f1.erase(unique(f1.begin(), f1.end()), f1.end()); 455 vector<pair<long long, int>> pos; 456 gen(f1, 0, 1, 1, pos); 457 for(auto [x, s] : pos) 458 { 459 if(x == 1) continue; 460 edges.push_back(make_pair(make_pair(x, s), i)); 461 } 462 } 463 464 int ans = 1; 465 int l = 0; 466 sort(edges.begin(), edges.end()); 467 while(l < edges.size()) 468 { 469 int r = l; 470 while(r < edges.size() && edges[r].first.first == edges[l].first.first) 471 r++; 472 vector<int> e; 473 for(int i = l; i < r; i++) 474 e.push_back(edges[i].second); 475 long long i = edges[l].first.first; 476 int m = edges[l].first.second; 477 if(m != 0) 478 { 479 int absent = n / i; 480 int cur = mul(fact[n], ifact[n - absent]); 481 int lf = 0; 482 while(lf < e.size()) 483 { 484 int rg = lf; 485 int nxt = e[lf]; 486 while(rg < e.size() && e[rg] == nxt) 487 { 488 rg++; 489 nxt++; 490 } 491 vector<int> cnt(2); 492 for(int k = e[lf]; k <= e[rg - 1] + 1; k++) 493 { 494 if(k % i != 0) 495 cnt[k % 2]++; 496 } 497 //cout << cnt[0] << " " << cnt[1] << endl; 498 cur = mul(cur, choose(cnt[0] + cnt[1], cnt[0])); 499 lf = rg; 500 } 501 //cout << i << " " << cur << endl; 502 ans = add(ans, -1 * m * add(cur, -1)); 503 } 504 l = r; 505 } 506 cout << ans << endl; 507 } 508 509 int main() 510 { 511 ios_base::sync_with_stdio(0); 512 cin.tie(0); 513 precalc(); 514 int t = 1; 515 //cin >> t; 516 for(int i = 0; i < t; i++) 517 solve(); 518 } 519 ```