1251.md (8925B)
1 Source: https://codeforces.com/blog/entry/70860 2 3 [1251A - Broken Keyboard](/contest/1251/problem/A "Educational Codeforces Round 75 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Ne0n25)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 bool ans[26]; 19 20 void solve() { 21 string s; 22 cin >> s; 23 24 memset(ans, 0, sizeof(ans)); 25 26 for (int i = 0; i < s.size(); i++) { 27 int j = i; 28 while (j + 1 < s.size() && s[j + 1] == s[i]) 29 j++; 30 if ((j - i) % 2 == 0) 31 ans[s[i] - 'a'] = true; 32 i = j; 33 } 34 35 for (int i = 0; i < 26; i++) if (ans[i]) 36 cout << char('a' + i); 37 cout << endl; 38 } 39 40 int main() { 41 int q; 42 cin >> q; 43 while (q--) solve(); 44 } 45 ``` 46 47 [1251B - Binary Palindromes](/contest/1251/problem/B "Educational Codeforces Round 75 (Rated for Div. 2)") 48 49 Idea: [adedalic](/profile/adedalic "International Master adedalic") 50 51 **Tutorial** 52 53 Tutorial is loading... 54 55 **Solution (adedalic)** 56 57 ``` 58 fun main() { 59 val q = readLine()!!.toInt() 60 for (ct in 1..q) { 61 val n = readLine()!!.toInt() 62 var (odd, evenGood, evenBad) = listOf(0, 0, 0) 63 for (i in 1..n) { 64 val s = readLine()!! 65 when { 66 s.length % 2 == 1 -> odd++ 67 s.count { it == '0' } % 2 == 0 -> evenGood++ 68 else -> evenBad++ 69 } 70 } 71 println(n - if (odd == 0 && evenBad % 2 == 1) 1 else 0) 72 } 73 } 74 ``` 75 76 [1251C - Minimize The Integer](/contest/1251/problem/C "Educational Codeforces Round 75 (Rated for Div. 2)") 77 78 Idea: [Roms](/profile/Roms "Master Roms") 79 80 **Tutorial** 81 82 Tutorial is loading... 83 84 **Solution (Roms)** 85 86 ``` 87 #include <bits/stdc++.h> 88 89 using namespace std; 90 91 int t; 92 string a; 93 94 int main() { 95 cin >> t; 96 for(int tc = 0; tc < t; ++tc){ 97 cin >> a; 98 string s[2]; 99 for(auto x : a) 100 s[int(x - '0') & 1] += x; 101 102 reverse(s[0].begin(), s[0].end()); 103 reverse(s[1].begin(), s[1].end()); 104 105 string res = ""; 106 while(!(s[0].empty() && s[1].empty())){ 107 if(s[0].empty()){ 108 res += s[1].back(); 109 s[1].pop_back(); 110 continue; 111 } 112 if(s[1].empty()){ 113 res += s[0].back(); 114 s[0].pop_back(); 115 continue; 116 } 117 118 if(s[0].back() < s[1].back()){ 119 res += s[0].back(); 120 s[0].pop_back(); 121 } 122 else{ 123 res += s[1].back(); 124 s[1].pop_back(); 125 } 126 } 127 128 cout << res << endl; 129 } 130 return 0; 131 } 132 ``` 133 134 [1251D - Salary Changing](/contest/1251/problem/D "Educational Codeforces Round 75 (Rated for Div. 2)") 135 136 Idea: [Roms](/profile/Roms "Master Roms") 137 138 **Tutorial** 139 140 Tutorial is loading... 141 142 **Solution (Roms)** 143 144 ``` 145 #include <bits/stdc++.h> 146 147 using namespace std; 148 149 const int N = int(2e5) + 99; 150 const int INF = int(1e9) + 100; 151 152 int t; 153 int n; 154 long long s; 155 pair<int, int> p[N]; 156 157 bool ok(int mid){ 158 long long sum = 0; 159 int cnt = 0; 160 vector <int> v; 161 for(int i = 0; i < n; ++i){ 162 if(p[i].second < mid) 163 sum += p[i].first; 164 else if(p[i].first >= mid){ 165 sum += p[i].first; 166 ++cnt; 167 } 168 else 169 v.push_back(p[i].first); 170 } 171 172 assert(is_sorted(v.begin(), v.end())); 173 174 int need = max(0, (n + 1) / 2 - cnt); 175 if(need > v.size()) return false; 176 for(int i = 0; i < v.size(); ++i){ 177 if(i < v.size() - need) 178 sum += v[i]; 179 else 180 sum += mid; 181 } 182 183 return sum <= s; 184 } 185 186 int main() { 187 scanf("%d", &t); 188 for(int tc = 0; tc < t; ++tc){ 189 scanf("%d %lld", &n, &s); 190 for(int i = 0; i < n; ++i) 191 scanf("%d %d", &p[i].first, &p[i].second); 192 193 sort(p, p + n); 194 int lf = 1, rg = INF; ///WA -> 10^9 195 while(rg - lf > 1){ 196 int mid = (lf + rg) / 2; 197 if(ok(mid)) lf = mid; 198 else rg = mid; 199 } 200 201 printf("%d\n", lf); 202 } 203 return 0; 204 } 205 ``` 206 207 [1251E1 - Voting (Easy Version)](/contest/1251/problem/E1 "Educational Codeforces Round 75 (Rated for Div. 2)") 208 209 [1251E2 - Voting (Hard Version)](/contest/1251/problem/E2 "Educational Codeforces Round 75 (Rated for Div. 2)") 210 211 Idea: [Roms](/profile/Roms "Master Roms") 212 213 **Tutorial** 214 215 Tutorial is loading... 216 217 **Solution (Roms)** 218 219 ``` 220 #include <bits/stdc++.h> 221 222 using namespace std; 223 224 const int N = int(3e5) + 99; 225 226 int t, n; 227 vector <int> v[N]; 228 229 int main() { 230 int t; 231 scanf("%d", &t); 232 for(int tc = 0; tc < t; ++tc){ 233 scanf("%d", &n); 234 for(int i = 0; i < n; ++i) 235 v[i].clear(); 236 for(int i = 0; i < n; ++i){ 237 int x, s; 238 scanf("%d %d", &x, &s); 239 v[x].push_back(s); 240 } 241 242 multiset <int > q; 243 long long res = 0; 244 int pref = n; 245 int cnt = 0; 246 for(int i = n - 1; i >= 0; --i){ 247 pref -= v[i].size(); 248 int need = i - pref; 249 for(auto x : v[i]) q.insert(x); 250 251 while(cnt < need){ 252 ++cnt; 253 res += *q.begin(); 254 q.erase(q.begin()); 255 } 256 } 257 258 printf("%lld\n", res); 259 } 260 return 0; 261 } 262 ``` 263 264 [1251F - Red-White Fence](/contest/1251/problem/F "Educational Codeforces Round 75 (Rated for Div. 2)") 265 266 Idea: [Neon](/profile/Neon "Candidate Master Neon") and [BledDest](/profile/BledDest "International Grandmaster BledDest") 267 268 **Tutorial** 269 270 Tutorial is loading... 271 272 **Solution (BledDest)** 273 274 ``` 275 #include<bits/stdc++.h> 276 277 using namespace std; 278 279 const int LOGN = 20; 280 const int N = (1 << LOGN); 281 const int MOD = 998244353; 282 const int g = 3; 283 284 #define forn(i, n) for(int i = 0; i < int(n); i++) 285 286 inline int mul(int a, int b) 287 { 288 return (a * 1ll * b) % MOD; 289 } 290 291 inline int norm(int a) 292 { 293 while(a >= MOD) 294 a -= MOD; 295 while(a < 0) 296 a += MOD; 297 return a; 298 } 299 300 inline int binPow(int a, int k) 301 { 302 int ans = 1; 303 while(k > 0) 304 { 305 if(k & 1) 306 ans = mul(ans, a); 307 a = mul(a, a); 308 k >>= 1; 309 } 310 return ans; 311 } 312 313 inline int inv(int a) 314 { 315 return binPow(a, MOD - 2); 316 } 317 318 vector<int> w[LOGN]; 319 vector<int> iw[LOGN]; 320 vector<int> rv[LOGN]; 321 322 void precalc() 323 { 324 int wb = binPow(g, (MOD - 1) / (1 << LOGN)); 325 326 for(int st = 0; st < LOGN; st++) 327 { 328 w[st].assign(1 << st, 1); 329 iw[st].assign(1 << st, 1); 330 331 int bw = binPow(wb, 1 << (LOGN - st - 1)); 332 int ibw = inv(bw); 333 334 int cw = 1; 335 int icw = 1; 336 337 for(int k = 0; k < (1 << st); k++) 338 { 339 w[st][k] = cw; 340 iw[st][k] = icw; 341 342 cw = mul(cw, bw); 343 icw = mul(icw, ibw); 344 } 345 346 rv[st].assign(1 << st, 0); 347 348 if(st == 0) 349 { 350 rv[st][0] = 0; 351 continue; 352 } 353 int h = (1 << (st - 1)); 354 for(int k = 0; k < (1 << st); k++) 355 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 356 } 357 } 358 359 inline void fft(int a[N], int n, int ln, bool inverse) 360 { 361 for(int i = 0; i < n; i++) 362 { 363 int ni = rv[ln][i]; 364 if(i < ni) 365 swap(a[i], a[ni]); 366 } 367 368 for(int st = 0; (1 << st) < n; st++) 369 { 370 int len = (1 << st); 371 for(int k = 0; k < n; k += (len << 1)) 372 { 373 for(int pos = k; pos < k + len; pos++) 374 { 375 int l = a[pos]; 376 int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k])); 377 378 a[pos] = norm(l + r); 379 a[pos + len] = norm(l - r); 380 } 381 } 382 } 383 384 if(inverse) 385 { 386 int in = inv(n); 387 for(int i = 0; i < n; i++) 388 a[i] = mul(a[i], in); 389 } 390 } 391 392 int aa[N], bb[N], cc[N]; 393 394 inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) 395 { 396 int n = 1, ln = 0; 397 while(n < (sza + szb)) 398 n <<= 1, ln++; 399 for(int i = 0; i < n; i++) 400 aa[i] = (i < sza ? a[i] : 0); 401 for(int i = 0; i < n; i++) 402 bb[i] = (i < szb ? b[i] : 0); 403 404 fft(aa, n, ln, false); 405 fft(bb, n, ln, false); 406 407 for(int i = 0; i < n; i++) 408 cc[i] = mul(aa[i], bb[i]); 409 410 fft(cc, n, ln, true); 411 412 szc = n; 413 for(int i = 0; i < n; i++) 414 c[i] = cc[i]; 415 } 416 417 vector<int> T[N]; 418 419 int a[N]; 420 int b[N]; 421 int n, k; 422 int ans[N]; 423 int Q[N]; 424 int fact[N]; 425 int rfact[N]; 426 427 int auxa[N]; 428 int auxb[N]; 429 int auxc[N]; 430 431 int C(int n, int k) 432 { 433 if(n < 0 || k < 0 || k > n) return 0; 434 return mul(fact[n], mul(rfact[k], rfact[n - k])); 435 } 436 437 vector<int> newtonExp(int a, int b, int p) 438 { 439 vector<int> res(p + 1); 440 for(int i = 0; i <= p; i++) 441 res[i] = mul(C(p, i), mul(binPow(a, i), binPow(b, p - i))); 442 return res; 443 } 444 445 int main() 446 { 447 precalc(); 448 fact[0] = 1; 449 for(int i = 1; i < N; i++) fact[i] = mul(fact[i - 1], i); 450 for(int i = 0; i < N; i++) rfact[i] = inv(fact[i]); 451 452 scanf("%d %d", &n, &k); 453 for(int i = 0; i < n; i++) scanf("%d", &a[i]); 454 for(int i = 0; i < k; i++) scanf("%d", &b[i]); 455 int q; 456 scanf("%d", &q); 457 for(int i = 0; i < q; i++) scanf("%d", &Q[i]); 458 459 map<int, int> cnt; 460 for(int i = 0; i < n; i++) 461 cnt[a[i]]++; 462 463 for(int i = 0; i < k; i++) 464 { 465 int redL = b[i]; 466 int cnt1 = 0; 467 int cnt2 = 0; 468 for(auto x : cnt) 469 { 470 if(x.first >= redL) 471 break; 472 if(x.second == 1) 473 cnt1++; 474 else 475 cnt2++; 476 } 477 memset(auxa, 0, sizeof auxa); 478 memset(auxb, 0, sizeof auxb); 479 memset(auxc, 0, sizeof auxc); 480 vector<int> p1 = newtonExp(2, 1, cnt1); 481 vector<int> p2 = newtonExp(1, 1, cnt2 * 2); 482 int sa = p1.size(); 483 int sb = p2.size(); 484 int sc; 485 for(int j = 0; j < sa; j++) 486 auxa[j] = p1[j]; 487 for(int j = 0; j < sb; j++) 488 auxb[j] = p2[j]; 489 multiply(auxa, sa, auxb, sb, auxc, sc); 490 for(int j = 0; j < q; j++) 491 { 492 int cntW = Q[j] / 2 - redL - 1; 493 if(cntW >= 0 && cntW < sc) 494 ans[j] = norm(ans[j] + auxc[cntW]); 495 } 496 } 497 498 for(int i = 0; i < q; i++) 499 printf("%d\n", ans[i]); 500 } 501 ```