1335.md (8426B)
1 Source: https://codeforces.com/blog/entry/75993 2 3 [1335A - Candies and Two Sisters](/contest/1335/problem/A "Codeforces Round 634 (Div. 3)") 4 5 Idea: [vovuh](/profile/vovuh "Master vovuh") 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 t; 25 cin >> t; 26 while (t--) { 27 int n; 28 cin >> n; 29 cout << (n - 1) / 2 << endl; 30 } 31 32 return 0; 33 } 34 ``` 35 36 [1335B - Construct the String](/contest/1335/problem/B "Codeforces Round 634 (Div. 3)") 37 38 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 int main() { 52 #ifdef _DEBUG 53 freopen("input.txt", "r", stdin); 54 // freopen("output.txt", "w", stdout); 55 #endif 56 57 int t; 58 cin >> t; 59 while (t--) { 60 int n, a, b; 61 cin >> n >> a >> b; 62 for (int i = 0; i < n; ++i) { 63 cout << char('a' + i % b); 64 } 65 cout << endl; 66 } 67 68 return 0; 69 } 70 ``` 71 72 [1335C - Two Teams Composing](/contest/1335/problem/C "Codeforces Round 634 (Div. 3)") 73 74 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 75 76 **Tutorial** 77 78 Tutorial is loading... 79 80 **Solution** 81 82 ``` 83 #include <bits/stdc++.h> 84 85 using namespace std; 86 87 int main() { 88 #ifdef _DEBUG 89 freopen("input.txt", "r", stdin); 90 // freopen("output.txt", "w", stdout); 91 #endif 92 93 int t; 94 cin >> t; 95 while (t--) { 96 int n; 97 cin >> n; 98 vector<int> cnt(n + 1); 99 for (int i = 0; i < n; ++i) { 100 int x; 101 cin >> x; 102 ++cnt[x]; 103 } 104 int mx = *max_element(cnt.begin(), cnt.end()); 105 int diff = n + 1 - count(cnt.begin(), cnt.end(), 0); 106 cout << max(min(mx - 1, diff), min(mx, diff - 1)) << endl; 107 } 108 109 return 0; 110 } 111 ``` 112 113 [1335D - Anti-Sudoku](/contest/1335/problem/D "Codeforces Round 634 (Div. 3)") 114 115 Idea: [vovuh](/profile/vovuh "Master vovuh") 116 117 **Tutorial** 118 119 Tutorial is loading... 120 121 **Solution** 122 123 ``` 124 #include <bits/stdc++.h> 125 126 using namespace std; 127 128 int main() { 129 #ifdef _DEBUG 130 freopen("input.txt", "r", stdin); 131 // freopen("output.txt", "w", stdout); 132 #endif 133 134 int t; 135 cin >> t; 136 while (t--) { 137 for (int i = 0; i < 9; ++i) { 138 string s; 139 cin >> s; 140 for (auto &c : s) if (c == '2') c = '1'; 141 cout << s << endl; 142 } 143 } 144 145 return 0; 146 } 147 ``` 148 149 [1335E1 - Three Blocks Palindrome (easy version)](/contest/1335/problem/E1 "Codeforces Round 634 (Div. 3)") 150 151 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 152 153 **Tutorial** 154 155 Tutorial is loading... 156 157 **Solution** 158 159 ``` 160 #include <bits/stdc++.h> 161 162 using namespace std; 163 164 #define sz(a) int((a).size()) 165 #define forn(i, n) for (int i = 0; i < int(n); ++i) 166 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i) 167 168 int main() { 169 #ifdef _DEBUG 170 freopen("input.txt", "r", stdin); 171 // freopen("output.txt", "w", stdout); 172 #endif 173 174 int t; 175 cin >> t; 176 while (t--) { 177 int n; 178 cin >> n; 179 vector<int> a(n); 180 for (auto &it : a) cin >> it; 181 vector<vector<int>> cnt(26, vector<int>(n + 1)); 182 forn(i, n) { 183 forn(j, 26) cnt[j][i + 1] = cnt[j][i]; 184 ++cnt[a[i] - 1][i + 1]; 185 } 186 int ans = 0; 187 forn(i, 26) ans = max(ans, cnt[i][n - 1]); 188 forn(l, n) fore(r, l, n) { 189 int cntin = 0, cntout = 0; 190 forn(el, 26) { 191 cntin = max(cntin, cnt[el][r + 1] - cnt[el][l]); 192 cntout = max(cntout, min(cnt[el][l], cnt[el][n] - cnt[el][r + 1]) * 2); 193 } 194 ans = max(ans, cntin + cntout); 195 } 196 cout << ans << endl; 197 } 198 199 return 0; 200 } 201 ``` 202 203 [1335E2 - Three Blocks Palindrome (hard version)](/contest/1335/problem/E2 "Codeforces Round 634 (Div. 3)") 204 205 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 206 207 **Tutorial** 208 209 Tutorial is loading... 210 211 **Solution** 212 213 ``` 214 #include <bits/stdc++.h> 215 216 using namespace std; 217 218 #define sz(a) int((a).size()) 219 #define forn(i, n) for (int i = 0; i < int(n); ++i) 220 221 int main() { 222 #ifdef _DEBUG 223 freopen("input.txt", "r", stdin); 224 // freopen("output.txt", "w", stdout); 225 #endif 226 227 int t; 228 cin >> t; 229 while (t--) { 230 int n; 231 cin >> n; 232 vector<int> a(n); 233 for (auto &it : a) cin >> it; 234 vector<vector<int>> cnt(200, vector<int>(n + 1)); 235 vector<vector<int>> pos(200); 236 forn(i, n) { 237 forn(j, 200) cnt[j][i + 1] = cnt[j][i]; 238 ++cnt[a[i] - 1][i + 1]; 239 pos[a[i] - 1].push_back(i); 240 } 241 int ans = 0; 242 forn(i, 200) { 243 ans = max(ans, sz(pos[i])); 244 forn(p, sz(pos[i]) / 2) { 245 int l = pos[i][p] + 1, r = pos[i][sz(pos[i]) - p - 1] - 1; 246 forn(el, 200) { 247 int sum = cnt[el][r + 1] - cnt[el][l]; 248 ans = max(ans, (p + 1) * 2 + sum); 249 } 250 } 251 } 252 cout << ans << endl; 253 } 254 255 return 0; 256 } 257 ``` 258 259 [1335F - Robots on a Grid](/contest/1335/problem/F "Codeforces Round 634 (Div. 3)") 260 261 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 262 263 **Tutorial** 264 265 Tutorial is loading... 266 267 **Solution** 268 269 ``` 270 #include <bits/stdc++.h> 271 272 using namespace std; 273 274 int n, m, lognm; 275 vector<string> c, s; 276 vector<vector<int>> used, nxt; 277 278 void getnext(int x, int y, int &nx, int &ny) { 279 if (s[x][y] == 'U') nx = x - 1, ny = y; 280 if (s[x][y] == 'R') nx = x, ny = y + 1; 281 if (s[x][y] == 'D') nx = x + 1, ny = y; 282 if (s[x][y] == 'L') nx = x, ny = y - 1; 283 } 284 285 void dfs(int x, int y) { 286 used[x][y] = 1; 287 int nx = -1, ny = -1; 288 getnext(x, y, nx, ny); 289 assert(0 <= nx && nx < n && 0 <= ny && ny < m); 290 int v = x * m + y, to = nx * m + ny; 291 if (!used[nx][ny]) dfs(nx, ny); 292 nxt[v][0] = to; 293 } 294 295 int main() { 296 #ifdef _DEBUG 297 freopen("input.txt", "r", stdin); 298 // freopen("output.txt", "w", stdout); 299 #endif 300 301 int t; 302 cin >> t; 303 while (t--) { 304 cin >> n >> m; 305 lognm = 0; 306 int nm = n * m; 307 while ((1 << lognm) <= nm) ++lognm; 308 c = s = vector<string>(n); 309 for (auto &it : c) cin >> it; 310 for (auto &it : s) cin >> it; 311 312 used = vector<vector<int>>(n, vector<int>(m)); 313 nxt = vector<vector<int>>(n * m, vector<int>(lognm)); 314 for (int i = 0; i < n; ++i) { 315 for (int j = 0; j < m; ++j) { 316 if (!used[i][j]) dfs(i, j); 317 } 318 } 319 for (int deg = 1; deg < lognm; ++deg) { 320 for (int i = 0; i < n; ++i) { 321 for (int j = 0; j < m; ++j) { 322 int id = i * m + j; 323 nxt[id][deg] = nxt[nxt[id][deg - 1]][deg - 1]; 324 } 325 } 326 } 327 328 vector<vector<int>> black, white; 329 black = white = vector<vector<int>>(n, vector<int>(m)); 330 for (int i = 0; i < n; ++i) { 331 for (int j = 0; j < m; ++j) { 332 int v = i * m + j, to = v; 333 for (int deg = lognm - 1; deg >= 0; --deg) { 334 if ((nm >> deg) & 1) to = nxt[to][deg]; 335 } 336 if (c[i][j] == '0') ++black[to / m][to % m]; 337 else ++white[to / m][to % m]; 338 } 339 } 340 341 int all = 0, good = 0; 342 for (int i = 0; i < n; ++i) { 343 for (int j = 0; j < m; ++j) { 344 if (black[i][j]) { 345 ++all; 346 ++good; 347 } else if (white[i][j]) { 348 ++all; 349 } 350 } 351 } 352 cout << all << " " << good << endl; 353 } 354 355 return 0; 356 } 357 ``` 358 359 **Solution (actually _overrated_, fastest O(nm log nm))** 360 361 ``` 362 #include <iostream> 363 #include <vector> 364 #include <map> 365 #include <set> 366 #include <queue> 367 #include <algorithm> 368 #include <string> 369 #include <cmath> 370 #include <cstdio> 371 #include <iomanip> 372 #include <fstream> 373 #include <cassert> 374 #include <cstring> 375 #include <unordered_set> 376 #include <unordered_map> 377 #include <numeric> 378 #include <ctime> 379 #include <bitset> 380 #include <complex> 381 #include <chrono> 382 #include <random> 383 #include <functional> 384 385 using namespace std; 386 387 const int N = 1e6 + 7; 388 const int K = 24; 389 390 int f[N]; 391 int dp[N]; 392 int ndp[N]; 393 int sel[N]; 394 395 int fans[N]; 396 int sans[N]; 397 398 void solve() { 399 int n, m; 400 cin >> n >> m; 401 for (int i = 0; i < n; i++) { 402 string s; 403 cin >> s; 404 for (int j = 0; j < m; j++) { 405 sel[i * m + j] = (s[j] == '0'); 406 } 407 } 408 for (int i = 0; i < n; i++) { 409 string s; 410 cin >> s; 411 for (int j = 0; j < m; j++) { 412 int to = -1; 413 if (s[j] == 'U') to = (i - 1) * m + j; 414 if (s[j] == 'D') to = (i + 1) * m + j; 415 if (s[j] == 'L') to = i * m + (j - 1); 416 if (s[j] == 'R') to = i * m + (j + 1); 417 f[i * m + j] = to; 418 } 419 } 420 n *= m; 421 for (int i = 0; i < n; i++) { 422 dp[i] = f[i]; 423 } 424 for (int j = 0; j < K; j++) { 425 for (int i = 0; i < n; i++) { 426 ndp[i] = dp[dp[i]]; 427 } 428 for (int i = 0; i < n; i++) { 429 dp[i] = ndp[i]; 430 } 431 } 432 fill(fans, fans + n, 0); 433 fill(sans, sans + n, 0); 434 for (int i = 0; i < n; i++) { 435 fans[dp[i]]++; 436 sans[dp[i]] += sel[i]; 437 } 438 int fs = 0, ss = 0; 439 for (int i = 0; i < n; i++) { 440 fs += (fans[i] > 0); 441 ss += (sans[i] > 0); 442 } 443 cout << fs << ' ' << ss << '\n'; 444 } 445 446 signed main() { 447 ios_base::sync_with_stdio(false); 448 cin.tie(0); 449 450 int q; 451 cin >> q; 452 while (q--) { 453 solve(); 454 } 455 } 456 ```