1399.md (7929B)
1 Source: https://codeforces.com/blog/entry/81082 2 3 All ideas belong to [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"). 4 5 [1399A - Удалить наименьшее](/contest/1399/problem/A "Codeforces Round 661 (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 t; 25 cin >> t; 26 while (t--) { 27 int n; 28 cin >> n; 29 vector<int> a(n); 30 for (auto &it : a) cin >> it; 31 sort(a.begin(), a.end()); 32 bool ok = true; 33 for (int i = 1; i < n; ++i) { 34 ok &= (a[i] - a[i - 1] <= 1); 35 } 36 if (ok) cout << "YES" << endl; 37 else cout << "NO" << endl; 38 } 39 40 return 0; 41 } 42 ``` 43 44 [1399B - Уравнивание подарков](/contest/1399/problem/B "Codeforces Round 661 (Div. 3)") 45 46 **Tutorial** 47 48 Tutorial is loading... 49 50 **Solution** 51 52 ``` 53 #include <bits/stdc++.h> 54 55 using namespace std; 56 57 int main() { 58 #ifdef _DEBUG 59 freopen("input.txt", "r", stdin); 60 // freopen("output.txt", "w", stdout); 61 #endif 62 63 int t; 64 cin >> t; 65 while (t--) { 66 int n; 67 cin >> n; 68 vector<int> a(n), b(n); 69 for (auto &it : a) cin >> it; 70 for (auto &it : b) cin >> it; 71 int mna = *min_element(a.begin(), a.end()); 72 int mnb = *min_element(b.begin(), b.end()); 73 long long ans = 0; 74 for (int i = 0; i < n; ++i) { 75 ans += max(a[i] - mna, b[i] - mnb); 76 } 77 cout << ans << endl; 78 } 79 80 return 0; 81 } 82 ``` 83 84 [1399C - Лодочное соревнование](/contest/1399/problem/C "Codeforces Round 661 (Div. 3)") 85 86 **Tutorial** 87 88 Tutorial is loading... 89 90 **Solution** 91 92 ``` 93 #include <bits/stdc++.h> 94 95 using namespace std; 96 97 int main() { 98 #ifdef _DEBUG 99 freopen("input.txt", "r", stdin); 100 // freopen("output.txt", "w", stdout); 101 #endif 102 103 int t; 104 cin >> t; 105 while (t--) { 106 int n; 107 cin >> n; 108 vector<int> cnt(n + 1); 109 for (int i = 0; i < n; ++i) { 110 int x; 111 cin >> x; 112 ++cnt[x]; 113 } 114 int ans = 0; 115 for (int s = 2; s <= 2 * n; ++s) { 116 int cur = 0; 117 for (int i = 1; i < (s + 1) / 2; ++i) { 118 if (s - i > n) continue; 119 cur += min(cnt[i], cnt[s - i]); 120 } 121 if (s % 2 == 0) cur += cnt[s / 2] / 2; 122 ans = max(ans, cur); 123 } 124 cout << ans << endl; 125 } 126 127 return 0; 128 } 129 ``` 130 131 [1399D - Из бинарной строки в подпоследовательности](/contest/1399/problem/D "Codeforces Round 661 (Div. 3)") 132 133 **Tutorial** 134 135 Tutorial is loading... 136 137 **Solution** 138 139 ``` 140 #include <bits/stdc++.h> 141 142 using namespace std; 143 144 int main() { 145 #ifdef _DEBUG 146 freopen("input.txt", "r", stdin); 147 // freopen("output.txt", "w", stdout); 148 #endif 149 150 int t; 151 cin >> t; 152 while (t--) { 153 int n; 154 string s; 155 cin >> n >> s; 156 vector<int> ans(n); 157 vector<int> pos0, pos1; 158 for (int i = 0; i < n; ++i) { 159 int newpos = pos0.size() + pos1.size(); 160 if (s[i] == '0') { 161 if (pos1.empty()) { 162 pos0.push_back(newpos); 163 } else { 164 newpos = pos1.back(); 165 pos1.pop_back(); 166 pos0.push_back(newpos); 167 } 168 } else { 169 if (pos0.empty()) { 170 pos1.push_back(newpos); 171 } else { 172 newpos = pos0.back(); 173 pos0.pop_back(); 174 pos1.push_back(newpos); 175 } 176 } 177 ans[i] = newpos; 178 } 179 cout << pos0.size() + pos1.size() << endl; 180 for (auto it : ans) cout << it + 1 << " "; 181 cout << endl; 182 } 183 184 return 0; 185 } 186 ``` 187 188 [1399E1 - Деление весов (простая версия)](/contest/1399/problem/E1 "Codeforces Round 661 (Div. 3)") 189 190 **Tutorial** 191 192 Tutorial is loading... 193 194 **Solution** 195 196 ``` 197 #include <bits/stdc++.h> 198 199 using namespace std; 200 201 vector<int> w, cnt; 202 vector<vector<pair<int, int>>> g; 203 204 long long getdiff(int i) { 205 return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i]; 206 } 207 208 void dfs(int v, int p = -1) { 209 if (g[v].size() == 1) cnt[p] = 1; 210 for (auto [to, id] : g[v]) { 211 if (id == p) continue; 212 dfs(to, id); 213 if (p != -1) cnt[p] += cnt[id]; 214 } 215 } 216 217 int main() { 218 #ifdef _DEBUG 219 freopen("input.txt", "r", stdin); 220 // freopen("output.txt", "w", stdout); 221 #endif 222 223 int t; 224 cin >> t; 225 while (t--) { 226 int n; 227 long long s; 228 cin >> n >> s; 229 w = cnt = vector<int>(n - 1); 230 g = vector<vector<pair<int, int>>>(n); 231 for (int i = 0; i < n - 1; ++i) { 232 int x, y; 233 cin >> x >> y >> w[i]; 234 --x, --y; 235 g[x].push_back({y, i}); 236 g[y].push_back({x, i}); 237 } 238 dfs(0); 239 set<pair<long long, int>> st; 240 long long cur = 0; 241 for (int i = 0; i < n - 1; ++i) { 242 st.insert({getdiff(i), i}); 243 cur += w[i] * 1ll * cnt[i]; 244 } 245 cerr << cur << endl; 246 int ans = 0; 247 while (cur > s) { 248 int id = st.rbegin()->second; 249 st.erase(prev(st.end())); 250 cur -= getdiff(id); 251 w[id] /= 2; 252 st.insert({getdiff(id), id}); 253 ++ans; 254 } 255 cout << ans << endl; 256 } 257 258 return 0; 259 } 260 ``` 261 262 [1399E2 - Деление весов (сложная версия)](/contest/1399/problem/E2 "Codeforces Round 661 (Div. 3)") 263 264 **Tutorial** 265 266 Tutorial is loading... 267 268 **Solution** 269 270 ``` 271 #include <bits/stdc++.h> 272 273 using namespace std; 274 275 const int INF = 1e9; 276 277 int n; 278 vector<int> w, c, cnt; 279 vector<vector<pair<int, int>>> g; 280 281 long long getdiff(int i) { 282 return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i]; 283 } 284 285 void dfs(int v, int p = -1) { 286 if (g[v].size() == 1) cnt[p] = 1; 287 for (auto [to, id] : g[v]) { 288 if (id == p) continue; 289 dfs(to, id); 290 if (p != -1) cnt[p] += cnt[id]; 291 } 292 } 293 294 vector<long long> get(int clr) { 295 set<pair<long long, int>> st; 296 long long cur = 0; 297 for (int i = 0; i < n - 1; ++i) { 298 if (c[i] == clr) { 299 st.insert({getdiff(i), i}); 300 cur += w[i] * 1ll * cnt[i]; 301 } 302 } 303 vector<long long> res; 304 res.push_back(cur); 305 while (cur > 0 && !st.empty()) { 306 int id = st.rbegin()->second; 307 st.erase(prev(st.end())); 308 cur -= getdiff(id); 309 res.push_back(cur); 310 w[id] /= 2; 311 st.insert({getdiff(id), id}); 312 } 313 return res; 314 } 315 316 int main() { 317 #ifdef _DEBUG 318 freopen("input.txt", "r", stdin); 319 // freopen("output.txt", "w", stdout); 320 #endif 321 322 int t; 323 cin >> t; 324 while (t--) { 325 long long s; 326 cin >> n >> s; 327 w = c = cnt = vector<int>(n - 1); 328 g = vector<vector<pair<int, int>>>(n); 329 for (int i = 0; i < n - 1; ++i) { 330 int x, y; 331 cin >> x >> y >> w[i] >> c[i]; 332 --x, --y; 333 g[x].push_back({y, i}); 334 g[y].push_back({x, i}); 335 } 336 dfs(0); 337 vector<long long> v1 = get(1), v2 = get(2); 338 int pos = int(v2.size()) - 1; 339 int ans = INF; 340 for (int i = 0; i < int(v1.size()); ++i) { 341 while (pos > 0 && v1[i] + v2[pos - 1] <= s) --pos; 342 if (v1[i] + v2[pos] <= s) { 343 ans = min(ans, i + pos * 2); 344 } 345 } 346 cout << ans << endl; 347 } 348 349 return 0; 350 } 351 ``` 352 353 [1399F - Очередное подмножество отрезков](/contest/1399/problem/F "Codeforces Round 661 (Div. 3)") 354 355 **Tutorial** 356 357 Tutorial is loading... 358 359 **Solution** 360 361 ``` 362 #include <bits/stdc++.h> 363 364 using namespace std; 365 366 vector<vector<int>> rg; 367 vector<vector<int>> dp; 368 369 int calc(int l, int r) { 370 if (dp[l][r] != -1) return dp[l][r]; 371 dp[l][r] = 0; 372 if (l > r) return dp[l][r]; 373 bool add = count(rg[l].begin(), rg[l].end(), r); // can't be greater than 1 374 dp[l][r] = max(dp[l][r], add + (l + 1 > r ? 0 : calc(l + 1, r))); 375 for (auto nr : rg[l]) { 376 if (nr >= r) continue; 377 dp[l][r] = max(dp[l][r], add + calc(l, nr) + (nr + 1 > r ? 0 : calc(nr + 1, r))); 378 } 379 return dp[l][r]; 380 } 381 382 int main() { 383 #ifdef _DEBUG 384 freopen("input.txt", "r", stdin); 385 // freopen("output.txt", "w", stdout); 386 #endif 387 388 int t; 389 cin >> t; 390 while (t--) { 391 int n; 392 cin >> n; 393 vector<int> l(n), r(n); 394 vector<int> val; 395 for (int i = 0; i < n; ++i) { 396 cin >> l[i] >> r[i]; 397 val.push_back(l[i]); 398 val.push_back(r[i]); 399 } 400 sort(val.begin(), val.end()); 401 val.resize(unique(val.begin(), val.end()) - val.begin()); 402 for (int i = 0; i < n; ++i) { 403 l[i] = lower_bound(val.begin(), val.end(), l[i]) - val.begin(); 404 r[i] = lower_bound(val.begin(), val.end(), r[i]) - val.begin(); 405 } 406 int siz = val.size(); 407 dp = vector<vector<int>>(siz, vector<int>(siz, -1)); 408 rg = vector<vector<int>>(siz); 409 for (int i = 0; i < n; ++i) { 410 rg[l[i]].push_back(r[i]); 411 } 412 cout << calc(0, siz - 1) << endl; 413 } 414 415 return 0; 416 } 417 ```