1234.md (7053B)
1 Source: https://codeforces.com/blog/entry/70233 2 3 Suddenly, all problems expect A and D were invented by me. The author of A and D is [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"). 4 5 [1234A - Equalize Prices Again](/contest/1234/problem/A "Codeforces Round 590 (Div. 3)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int q; 25 cin >> q; 26 for (int i = 0; i < q; ++i) { 27 int n; 28 cin >> n; 29 int sum = 0; 30 for (int j = 0; j < n; ++j) { 31 int x; 32 cin >> x; 33 sum += x; 34 } 35 cout << (sum + n - 1) / n << endl; 36 } 37 38 return 0; 39 } 40 ``` 41 42 [1234B1 - Social Network (easy version)](/contest/1234/problem/B1 "Codeforces Round 590 (Div. 3)") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include <bits/stdc++.h> 52 53 using namespace std; 54 55 int main() { 56 #ifdef _DEBUG 57 freopen("input.txt", "r", stdin); 58 // freopen("output.txt", "w", stdout); 59 #endif 60 61 int n, k; 62 cin >> n >> k; 63 vector<int> ids; 64 for (int i = 0; i < n; ++i) { 65 int id; 66 cin >> id; 67 if (find(ids.begin(), ids.end(), id) == ids.end()) { 68 if (int(ids.size()) >= k) ids.pop_back(); 69 ids.insert(ids.begin(), id); 70 } 71 } 72 73 cout << ids.size() << endl; 74 for (auto it : ids) cout << it << " "; 75 cout << endl; 76 77 return 0; 78 } 79 ``` 80 81 [1234B2 - Social Network (hard version)](/contest/1234/problem/B2 "Codeforces Round 590 (Div. 3)") 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 using namespace std; 93 94 int main() { 95 #ifdef _DEBUG 96 freopen("input.txt", "r", stdin); 97 // freopen("output.txt", "w", stdout); 98 #endif 99 100 int n, k; 101 cin >> n >> k; 102 103 queue<int> q; 104 set<int> vals; 105 for (int i = 0; i < n; ++i) { 106 int id; 107 cin >> id; 108 if (!vals.count(id)) { 109 if (int(q.size()) >= k) { 110 int cur = q.front(); 111 q.pop(); 112 vals.erase(cur); 113 } 114 vals.insert(id); 115 q.push(id); 116 } 117 } 118 119 vector<int> res; 120 while (!q.empty()) { 121 res.push_back(q.front()); 122 q.pop(); 123 } 124 reverse(res.begin(), res.end()); 125 cout << res.size() << endl; 126 for (auto it : res) cout << it << " "; 127 cout << endl; 128 129 return 0; 130 } 131 ``` 132 133 [1234C - Pipes](/contest/1234/problem/C "Codeforces Round 590 (Div. 3)") 134 135 **Tutorial** 136 137 Tutorial is loading... 138 139 **Solution** 140 141 ``` 142 #include <bits/stdc++.h> 143 144 using namespace std; 145 146 int main() { 147 #ifdef _DEBUG 148 freopen("input.txt", "r", stdin); 149 // freopen("output.txt", "w", stdout); 150 #endif 151 152 int q; 153 cin >> q; 154 for (int i = 0; i < q; ++i) { 155 int n; 156 string s[2]; 157 cin >> n >> s[0] >> s[1]; 158 int row = 0; 159 int pos = 0; 160 for (pos = 0; pos < n; ++pos) { 161 if (s[row][pos] >= '3') { 162 if (s[row ^ 1][pos] < '3') { 163 break; 164 } else { 165 row ^= 1; 166 } 167 } 168 } 169 if (pos == n && row == 1) { 170 cout << "YES" << endl; 171 } else { 172 cout << "NO" << endl; 173 } 174 } 175 176 return 0; 177 } 178 ``` 179 180 [1234D - Distinct Characters Queries](/contest/1234/problem/D "Codeforces Round 590 (Div. 3)") 181 182 **Tutorial** 183 184 Tutorial is loading... 185 186 **Solution** 187 188 ``` 189 #include <bits/stdc++.h> 190 191 using namespace std; 192 193 int main() { 194 #ifdef _DEBUG 195 freopen("input.txt", "r", stdin); 196 // freopen("output.txt", "w", stdout); 197 #endif 198 199 string s; 200 cin >> s; 201 vector<set<int>> poss(26); 202 for (int i = 0; i < int(s.size()); ++i) { 203 poss[s[i] - 'a'].insert(i); 204 } 205 206 int q; 207 cin >> q; 208 for (int i = 0; i < q; ++i) { 209 int tp; 210 cin >> tp; 211 if (tp == 1) { 212 int pos; 213 char c; 214 cin >> pos >> c; 215 --pos; 216 poss[s[pos] - 'a'].erase(pos); 217 s[pos] = c; 218 poss[s[pos] - 'a'].insert(pos); 219 } else { 220 int l, r; 221 cin >> l >> r; 222 --l, --r; 223 int cnt = 0; 224 for (int c = 0; c < 26; ++c) { 225 auto it = poss[c].lower_bound(l); 226 if (it != poss[c].end() && *it <= r) ++cnt; 227 } 228 cout << cnt << endl; 229 } 230 } 231 232 return 0; 233 } 234 ``` 235 236 [1234E - Special Permutations](/contest/1234/problem/E "Codeforces Round 590 (Div. 3)") 237 238 **Tutorial** 239 240 Tutorial is loading... 241 242 **Solution** 243 244 ``` 245 #include <bits/stdc++.h> 246 247 using namespace std; 248 249 int main() { 250 #ifdef _DEBUG 251 freopen("input.txt", "r", stdin); 252 // freopen("output.txt", "w", stdout); 253 #endif 254 255 int n, m; 256 cin >> n >> m; 257 vector<int> a(m); 258 for (int i = 0; i < m; ++i) { 259 cin >> a[i]; 260 --a[i]; 261 } 262 263 vector<long long> res(n); 264 for (int j = 0; j < m - 1; ++j) { 265 res[0] += abs(a[j] - a[j + 1]); 266 } 267 268 vector<int> cnt(n); 269 vector<vector<int>> adj(n); 270 for (int i = 0; i < m - 1; ++i) { 271 int l = a[i], r = a[i + 1]; 272 if (l != r) { 273 adj[l].push_back(r); 274 adj[r].push_back(l); 275 } 276 if (l > r) swap(l, r); 277 if (r - l < 2) continue; 278 ++cnt[l + 1]; 279 --cnt[r]; 280 } 281 for (int i = 0; i < n - 1; ++i) { 282 cnt[i + 1] += cnt[i]; 283 } 284 285 for (int i = 1; i < n; ++i) { 286 res[i] = res[0] - cnt[i]; 287 for (auto j : adj[i]) { 288 res[i] -= abs(i - j); 289 res[i] += j + (j < i); 290 } 291 } 292 293 for (int i = 0; i < n; ++i) { 294 cout << res[i] << " "; 295 } 296 cout << endl; 297 298 return 0; 299 } 300 ``` 301 302 [1234F - Yet Another Substring Reverse](/contest/1234/problem/F "Codeforces Round 590 (Div. 3)") 303 304 **Tutorial** 305 306 Tutorial is loading... 307 308 **Solution** 309 310 ``` 311 #include <bits/stdc++.h> 312 313 using namespace std; 314 315 int main() { 316 #ifdef _DEBUG 317 freopen("input.txt", "r", stdin); 318 // freopen("output.txt", "w", stdout); 319 #endif 320 321 string s; 322 cin >> s; 323 324 vector<int> dp(1 << 20); 325 for (int i = 0; i < int(s.size()); ++i) { 326 vector<bool> used(20); 327 int mask = 0; 328 for (int j = 0; i + j < int(s.size()); ++j) { 329 if (used[s[i + j] - 'a']) break; 330 used[s[i + j] - 'a'] = true; 331 mask |= 1 << (s[i + j] - 'a'); 332 dp[mask] = __builtin_popcount(mask); 333 } 334 } 335 336 for (int mask = 0; mask < (1 << 20); ++mask) { 337 for (int pos = 0; pos < 20; ++pos) { 338 if ((mask >> pos) & 1) { 339 dp[mask] = max(dp[mask], dp[mask ^ (1 << pos)]); 340 } 341 } 342 } 343 344 int ans = 0; 345 for (int mask = 0; mask < (1 << 20); ++mask) { 346 if (dp[mask] == __builtin_popcount(mask)) { 347 int comp = ~mask & ((1 << 20) - 1); 348 ans = max(ans, dp[mask] + dp[comp]); 349 } 350 } 351 352 cout << ans << endl; 353 354 return 0; 355 } 356 ``` 357 358 **WA?** 359 360 ``` 361 #include <bits/stdc++.h> 362 363 using namespace std; 364 365 int main() { 366 #ifdef _DEBUG 367 freopen("input.txt", "r", stdin); 368 // freopen("output.txt", "w", stdout); 369 #endif 370 371 int tt = clock(); 372 373 string s; 374 cin >> s; 375 376 vector<int> dp(1 << 20); 377 vector<int> masks; 378 for (int i = 0; i < int(s.size()); ++i) { 379 vector<bool> used(20); 380 int mask = 0; 381 for (int j = 0; i + j < int(s.size()); ++j) { 382 if (used[s[i + j] - 'a']) break; 383 used[s[i + j] - 'a'] = true; 384 mask |= 1 << (s[i + j] - 'a'); 385 masks.push_back(mask); 386 } 387 } 388 sort(masks.begin(), masks.end()); 389 masks.resize(unique(masks.begin(), masks.end()) - masks.begin()); 390 sort(masks.begin(), masks.end(), [](int x, int y){ 391 return __builtin_popcount(x) > __builtin_popcount(y); 392 }); 393 394 int ans = __builtin_popcount(masks[0]); 395 for (int i = 0; i < int(masks.size()); ++i) { 396 if (clock() - tt > 1900) { 397 break; 398 } 399 for (int j = i + 1; j < int(masks.size()); ++j) { 400 if (!(masks[i] & masks[j])) { 401 ans = max(ans, __builtin_popcount(masks[i]) + __builtin_popcount(masks[j])); 402 break; 403 } 404 } 405 } 406 407 cout << ans << endl; 408 409 return 0; 410 } 411 ```