1296.md (7765B)
1 Source: https://codeforces.com/blog/entry/73627 2 3 [1296A - Array with Odd Sum](/contest/1296/problem/A "Codeforces Round 617 (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 int sum = 0; 30 bool odd = false, even = false; 31 for (int i = 0; i < n; ++i) { 32 int x; 33 cin >> x; 34 sum += x; 35 odd |= x % 2 != 0; 36 even |= x % 2 == 0; 37 } 38 if (sum % 2 != 0 || (odd && even)) cout << "YES" << endl; 39 else cout << "NO" << endl; 40 } 41 42 return 0; 43 } 44 ``` 45 46 [1296B - Food Buying](/contest/1296/problem/B "Codeforces Round 617 (Div. 3)") 47 48 Idea: [vovuh](/profile/vovuh "Master vovuh") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution** 55 56 ``` 57 #include <bits/stdc++.h> 58 59 using namespace std; 60 61 int main() { 62 #ifdef _DEBUG 63 freopen("input.txt", "r", stdin); 64 // freopen("output.txt", "w", stdout); 65 #endif 66 67 int t; 68 cin >> t; 69 while (t--) { 70 int s; 71 cin >> s; 72 int ans = 0; 73 int pw = 1000 * 1000 * 1000; 74 while (s > 0) { 75 while (s < pw) pw /= 10; 76 ans += pw; 77 s -= pw - pw / 10; 78 } 79 cout << ans << endl; 80 } 81 82 return 0; 83 } 84 ``` 85 86 [1296C - Yet Another Walking Robot](/contest/1296/problem/C "Codeforces Round 617 (Div. 3)") 87 88 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 89 90 **Tutorial** 91 92 Tutorial is loading... 93 94 **Solution** 95 96 ``` 97 #include <bits/stdc++.h> 98 99 using namespace std; 100 101 int main() { 102 #ifdef _DEBUG 103 freopen("input.txt", "r", stdin); 104 // freopen("output.txt", "w", stdout); 105 #endif 106 107 int t; 108 cin >> t; 109 while (t--) { 110 int n; 111 string s; 112 cin >> n >> s; 113 int l = -1, r = n; 114 map<pair<int, int>, int> vis; 115 pair<int, int> cur = {0, 0}; 116 vis[cur] = 0; 117 for (int i = 0; i < n; ++i) { 118 if (s[i] == 'L') --cur.first; 119 if (s[i] == 'R') ++cur.first; 120 if (s[i] == 'U') ++cur.second; 121 if (s[i] == 'D') --cur.second; 122 if (vis.count(cur)) { 123 if (i - vis[cur] + 1 < r - l + 1) { 124 l = vis[cur]; 125 r = i; 126 } 127 } 128 vis[cur] = i + 1; 129 } 130 if (l == -1) { 131 cout << -1 << endl; 132 } else { 133 cout << l + 1 << " " << r + 1 << endl; 134 } 135 } 136 137 return 0; 138 } 139 ``` 140 141 [1296D - Fight with Monsters](/contest/1296/problem/D "Codeforces Round 617 (Div. 3)") 142 143 Inspiration: [300iq](/profile/300iq "Legendary Grandmaster 300iq"), idea: [vovuh](/profile/vovuh "Master vovuh") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution** 150 151 ``` 152 #include <bits/stdc++.h> 153 154 using namespace std; 155 156 int main() { 157 #ifdef _DEBUG 158 freopen("input.txt", "r", stdin); 159 // freopen("output.txt", "w", stdout); 160 #endif 161 162 int n, a, b, k; 163 cin >> n >> a >> b >> k; 164 vector<int> h(n); 165 for (int i = 0; i < n; ++i) { 166 cin >> h[i]; 167 h[i] %= a + b; 168 if (h[i] == 0) h[i] += a + b; 169 h[i] = ((h[i] + a - 1) / a) - 1; 170 } 171 sort(h.begin(), h.end()); 172 int ans = 0; 173 for (int i = 0; i < n; ++i) { 174 if (k - h[i] < 0) break; 175 ++ans; 176 k -= h[i]; 177 } 178 179 cout << ans << endl; 180 181 return 0; 182 } 183 ``` 184 185 [1296E1 - String Coloring (easy version)](/contest/1296/problem/E1 "Codeforces Round 617 (Div. 3)") 186 187 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 188 189 **Tutorial** 190 191 Tutorial is loading... 192 193 **Solution (dp)** 194 195 ``` 196 #include <bits/stdc++.h> 197 198 using namespace std; 199 200 const int N = 222; 201 const int AL = 26; 202 203 bool dp[N][AL][AL]; 204 pair<pair<int, int>, int> p[N][AL][AL]; 205 206 int main() { 207 #ifdef _DEBUG 208 freopen("input.txt", "r", stdin); 209 // freopen("output.txt", "w", stdout); 210 #endif 211 212 int n; 213 string s; 214 cin >> n >> s; 215 dp[0][0][0] = 1; 216 for (int i = 0; i < n; ++i) { 217 int c = s[i] - 'a'; 218 for (int c1 = 0; c1 < AL; ++c1) { 219 for (int c2 = 0; c2 < AL; ++c2) { 220 if (!dp[i][c1][c2]) continue; 221 if (c >= c1) { 222 dp[i + 1][c][c2] = 1; 223 p[i + 1][c][c2] = make_pair(make_pair(c1, c2), 0); 224 } 225 if (c >= c2) { 226 dp[i + 1][c1][c] = 1; 227 p[i + 1][c1][c] = make_pair(make_pair(c1, c2), 1); 228 } 229 } 230 } 231 } 232 233 int x = -1, y = -1; 234 for (int c1 = 0; c1 < AL; ++c1) { 235 for (int c2 = 0; c2 < AL; ++c2) { 236 if (dp[n][c1][c2]) { 237 x = c1, y = c2; 238 } 239 } 240 } 241 242 if (x == -1) { 243 cout << "NO" << endl; 244 return 0; 245 } 246 247 string res; 248 for (int i = n; i > 0; --i) { 249 int prvx = p[i][x][y].first.first; 250 int prvy = p[i][x][y].first.second; 251 if (p[i][x][y].second) res += '1'; 252 else res += '0'; 253 x = prvx; 254 y = prvy; 255 } 256 257 reverse(res.begin(), res.end()); 258 cout << "YES" << endl << res << endl; 259 260 return 0; 261 } 262 ``` 263 264 **Solution (greedy)** 265 266 ``` 267 #include <bits/stdc++.h> 268 269 using namespace std; 270 271 int main() { 272 #ifdef _DEBUG 273 freopen("input.txt", "r", stdin); 274 // freopen("output.txt", "w", stdout); 275 #endif 276 277 int n; 278 string s; 279 cin >> n >> s; 280 string res; 281 char lst0 = 'a', lst1 = 'a'; 282 for (int i = 0; i < n; ++i) { 283 if (s[i] >= lst0) { 284 res += '0'; 285 lst0 = s[i]; 286 } else if (s[i] >= lst1) { 287 res += '1'; 288 lst1 = s[i]; 289 } else { 290 cout << "NO" << endl; 291 return 0; 292 } 293 } 294 295 cout << "YES" << endl << res << endl; 296 297 return 0; 298 } 299 ``` 300 301 [1296E2 - String Coloring (hard version)](/contest/1296/problem/E2 "Codeforces Round 617 (Div. 3)") 302 303 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 304 305 **Tutorial** 306 307 Tutorial is loading... 308 309 **Solution** 310 311 ``` 312 #include <bits/stdc++.h> 313 314 using namespace std; 315 316 int main() { 317 #ifdef _DEBUG 318 freopen("input.txt", "r", stdin); 319 // freopen("output.txt", "w", stdout); 320 #endif 321 322 int n; 323 string s; 324 cin >> n >> s; 325 326 vector<int> maxdp(26); 327 vector<int> dp(n, 1); 328 for (int i = 0; i < n; ++i) { 329 for (int c = 25; c > s[i] - 'a'; --c) { 330 dp[i] = max(dp[i], maxdp[c] + 1); 331 } 332 maxdp[s[i] - 'a'] = max(maxdp[s[i] - 'a'], dp[i]); 333 } 334 335 cout << *max_element(maxdp.begin(), maxdp.end()) << endl; 336 for (int i = 0; i < n; ++i) cout << dp[i] << " "; 337 cout << endl; 338 339 return 0; 340 } 341 ``` 342 343 [1296F - Berland Beauty](/contest/1296/problem/F "Codeforces Round 617 (Div. 3)") 344 345 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 346 347 **Tutorial** 348 349 Tutorial is loading... 350 351 **Solution** 352 353 ``` 354 #include <bits/stdc++.h> 355 356 using namespace std; 357 358 int n, m; 359 vector<int> val; 360 vector<vector<pair<int, int>>> g; 361 362 void dfs(int v, int pv, int pe, vector<pair<int, int>> &p) { 363 p[v] = make_pair(pv, pe); 364 for (auto it : g[v]) { 365 int to = it.first; 366 int idx = it.second; 367 if (to == pv) continue; 368 dfs(to, v, idx, p); 369 } 370 } 371 372 int main() { 373 #ifdef _DEBUG 374 freopen("input.txt", "r", stdin); 375 // freopen("output.txt", "w", stdout); 376 #endif 377 378 cin >> n; 379 g = vector<vector<pair<int, int>>>(n); 380 for (int i = 0; i < n - 1; ++i) { 381 int u, v; 382 cin >> u >> v; 383 --u, --v; 384 g[u].push_back(make_pair(v, i)); 385 g[v].push_back(make_pair(u, i)); 386 } 387 388 vector<vector<pair<int, int>>> p(n, vector<pair<int, int>>(n)); 389 for (int i = 0; i < n; ++i) { 390 dfs(i, -1, -1, p[i]); 391 } 392 393 val = vector<int>(n - 1, 1000000); 394 395 cin >> m; 396 vector<pair<pair<int, int>, int>> q(m); 397 for (int i = 0; i < m; ++i) { 398 cin >> q[i].first.first >> q[i].first.second >> q[i].second; 399 --q[i].first.first; 400 --q[i].first.second; 401 } 402 sort(q.begin(), q.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) { 403 return a.second < b.second; 404 }); 405 406 for (int i = 0; i < m; ++i) { 407 int u = q[i].first.first; 408 int v = q[i].first.second; 409 while (v != u) { 410 int pv = p[u][v].first; 411 int pe = p[u][v].second; 412 val[pe] = q[i].second; 413 v = pv; 414 } 415 } 416 417 for (int i = 0; i < m; ++i) { 418 int u = q[i].first.first; 419 int v = q[i].first.second; 420 int mx = 1000000; 421 while (v != u) { 422 int pv = p[u][v].first; 423 int pe = p[u][v].second; 424 mx = min(mx, val[pe]); 425 v = pv; 426 } 427 if (mx != q[i].second) { 428 cout << -1 << endl; 429 return 0; 430 } 431 } 432 433 for (int i = 0; i < n - 1; ++i) { 434 cout << val[i] << " "; 435 } 436 cout << endl; 437 438 return 0; 439 } 440 ```