1328.md (7242B)
1 Source: https://codeforces.com/blog/entry/75246 2 3 [1328A - Divisibility Problem](/contest/1328/problem/A "Codeforces Round 629 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 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 a, b; 28 cin >> a >> b; 29 if (a % b == 0) cout << 0 << endl; 30 else cout << b - a % b << endl; 31 } 32 33 return 0; 34 } 35 ``` 36 37 [1328B - K-th Beautiful String](/contest/1328/problem/B "Codeforces Round 629 (Div. 3)") 38 39 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 #define forn(i, n) for (int i = 0; i < int(n); i++) 53 54 int main() { 55 int t; 56 cin >> t; 57 forn(tt, t) { 58 int n, k; 59 cin >> n >> k; 60 string s(n, 'a'); 61 for (int i = n - 2; i >= 0; i--) { 62 if (k <= (n - i - 1)) { 63 s[i] = 'b'; 64 s[n - k] = 'b'; 65 cout << s << endl; 66 break; 67 } 68 k -= (n - i - 1); 69 } 70 } 71 } 72 ``` 73 74 [1328C - Ternary XOR](/contest/1328/problem/C "Codeforces Round 629 (Div. 3)") 75 76 Idea: [vovuh](/profile/vovuh "Master vovuh") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution** 83 84 ``` 85 #include <bits/stdc++.h> 86 87 using namespace std; 88 89 int main() { 90 #ifdef _DEBUG 91 freopen("input.txt", "r", stdin); 92 // freopen("output.txt", "w", stdout); 93 #endif 94 95 int t; 96 cin >> t; 97 while (t--) { 98 int n; 99 string x; 100 cin >> n >> x; 101 string a(n, '0'), b(n, '0'); 102 for (int i = 0; i < n; ++i) { 103 if (x[i] == '1') { 104 a[i] = '1'; 105 b[i] = '0'; 106 for (int j = i + 1; j < n; ++j) { 107 b[j] = x[j]; 108 } 109 break; 110 } else { 111 a[i] = b[i] = '0' + (x[i] - '0') / 2; 112 } 113 } 114 cout << a << endl << b << endl; 115 } 116 117 return 0; 118 } 119 ``` 120 121 [1328D - Carousel](/contest/1328/problem/D "Codeforces Round 629 (Div. 3)") 122 123 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 124 125 **Tutorial** 126 127 Tutorial is loading... 128 129 **Solution** 130 131 ``` 132 #include <bits/stdc++.h> 133 134 using namespace std; 135 136 int solve() { 137 int n; 138 cin >> n; 139 vector<int> a(n); 140 for (int i = 0; i < n; ++i) { 141 cin >> a[i]; 142 } 143 144 if (count(a.begin(), a.end(), a[0]) == n) { 145 cout << 1 << endl; 146 for (int i = 0; i < n; ++i) { 147 cout << 1 << " "; 148 } 149 cout << endl; 150 return 0; 151 } 152 153 if (n % 2 == 0) { 154 cout << 2 << endl; 155 for (int i = 0; i < n; ++i) { 156 cout << i % 2 + 1 << " "; 157 } 158 cout << endl; 159 return 0; 160 } 161 162 for (int i = 0; i < n; ++i) { 163 if (a[i] == a[(i + 1) % n]) { 164 vector<int> ans(n); 165 for (int j = 0, pos = i + 1; pos < n; ++pos, j ^= 1) { 166 ans[pos] = j + 1; 167 } 168 for (int j = 0, pos = i; pos >= 0; --pos, j ^= 1) { 169 ans[pos] = j + 1; 170 } 171 cout << 2 << endl; 172 for (int pos = 0; pos < n; ++pos) { 173 cout << ans[pos] << " "; 174 } 175 cout << endl; 176 return 0; 177 } 178 } 179 180 cout << 3 << endl; 181 for (int i = 0; i < n - 1; ++i) { 182 cout << i % 2 + 1 << " "; 183 } 184 cout << 3 << endl; 185 return 0; 186 } 187 188 int main() { 189 #ifdef _DEBUG 190 freopen("input.txt", "r", stdin); 191 // freopen("output.txt", "w", stdout); 192 #endif 193 194 int q; 195 cin >> q; 196 for (int qq = 0; qq < q; qq++) { 197 solve(); 198 } 199 200 return 0; 201 } 202 ``` 203 204 [1328E - Tree Queries](/contest/1328/problem/E "Codeforces Round 629 (Div. 3)") 205 206 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and [vovuh](/profile/vovuh "Master vovuh") 207 208 **Tutorial** 209 210 Tutorial is loading... 211 212 **Solution** 213 214 ``` 215 #include <bits/stdc++.h> 216 217 using namespace std; 218 219 int T; 220 vector<int> p, d; 221 vector<int> tin, tout; 222 vector<vector<int>> g; 223 224 void dfs(int v, int par = -1, int dep = 0) { 225 p[v] = par; 226 d[v] = dep; 227 tin[v] = T++; 228 for (auto to : g[v]) { 229 if (to == par) continue; 230 dfs(to, v, dep + 1); 231 } 232 tout[v] = T++; 233 } 234 235 bool isAnc(int v, int u) { 236 return tin[v] <= tin[u] && tout[u] <= tout[v]; 237 } 238 239 int main() { 240 #ifdef _DEBUG 241 freopen("input.txt", "r", stdin); 242 // freopen("output.txt", "w", stdout); 243 #endif 244 245 int n, m; 246 cin >> n >> m; 247 T = 0; 248 p = d = vector<int>(n); 249 tin = tout = vector<int>(n); 250 g = vector<vector<int>>(n); 251 for (int i = 0; i < n - 1; ++i) { 252 int x, y; 253 cin >> x >> y; 254 --x, --y; 255 g[x].push_back(y); 256 g[y].push_back(x); 257 } 258 dfs(0); 259 260 for (int i = 0; i < m; ++i) { 261 int k; 262 cin >> k; 263 vector<int> v(k); 264 for (auto &it : v) { 265 cin >> it; 266 --it; 267 } 268 269 int u = v[0]; 270 for (auto it : v) if (d[u] < d[it]) u = it; 271 for (auto &it : v) { 272 if (it == u) continue; 273 if (p[it] != -1) it = p[it]; 274 } 275 bool ok = true; 276 for (auto it : v) ok &= isAnc(it, u); 277 if (ok) cout << "YES" << endl; 278 else cout << "NO" << endl; 279 } 280 281 return 0; 282 } 283 ``` 284 285 [1328F - Make k Equal](/contest/1328/problem/F "Codeforces Round 629 (Div. 3)") 286 287 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 288 289 **Tutorial** 290 291 Tutorial is loading... 292 293 **Solution** 294 295 ``` 296 #include <bits/stdc++.h> 297 298 using namespace std; 299 300 const long long INF64 = 1e18; 301 302 int main() { 303 #ifdef _DEBUG 304 freopen("input.txt", "r", stdin); 305 // freopen("output.txt", "w", stdout); 306 #endif 307 308 int n, k; 309 cin >> n >> k; 310 vector<int> a(n); 311 for (auto &it : a) cin >> it; 312 313 sort(a.begin(), a.end()); 314 vector<pair<int, int>> cnt; 315 for (auto it : a) { 316 if (cnt.empty() || cnt.back().first != it) { 317 cnt.push_back({it, 1}); 318 } else { 319 ++cnt.back().second; 320 } 321 } 322 vector<long long> prefsum, sufsum; 323 vector<int> prefcnt, sufcnt; 324 for (int i = 0; i < int(cnt.size()); ++i) { 325 long long cursum = cnt[i].first * 1ll * cnt[i].second; 326 int curcnt = cnt[i].second; 327 if (prefsum.empty()) { 328 prefsum.push_back(cursum); 329 prefcnt.push_back(curcnt); 330 } else { 331 prefsum.push_back(prefsum.back() + cursum); 332 prefcnt.push_back(prefcnt.back() + curcnt); 333 } 334 } 335 for (int i = int(cnt.size()) - 1; i >= 0; --i) { 336 long long cursum = cnt[i].first * 1ll * cnt[i].second; 337 int curcnt = cnt[i].second; 338 if (sufsum.empty()) { 339 sufsum.push_back(cursum); 340 sufcnt.push_back(curcnt); 341 } else { 342 sufsum.push_back(sufsum.back() + cursum); 343 sufcnt.push_back(sufcnt.back() + curcnt); 344 } 345 } 346 reverse(sufsum.begin(), sufsum.end()); 347 reverse(sufcnt.begin(), sufcnt.end()); 348 349 long long ans = INF64; 350 for (int i = 0; i < int(cnt.size()); ++i) { 351 int cur = max(0, k - cnt[i].second); 352 353 int needl = 0; 354 if (i > 0) needl = min(cur, prefcnt[i - 1]); 355 int needr = max(0, cur - needl); 356 long long res = 0; 357 if (i > 0 && needl > 0) { 358 res += prefcnt[i - 1] * 1ll * (cnt[i].first - 1) - prefsum[i - 1]; 359 res += needl; 360 } 361 if (i + 1 < int(cnt.size()) && needr > 0) { 362 res += sufsum[i + 1] - sufcnt[i + 1] * 1ll * (cnt[i].first + 1); 363 res += needr; 364 } 365 ans = min(ans, res); 366 367 needr = 0; 368 if (i + 1 < int(cnt.size())) needr = min(cur, sufcnt[i + 1]); 369 needl = max(0, cur - needr); 370 res = 0; 371 if (i > 0 && needl > 0) { 372 res += prefcnt[i - 1] * 1ll * (cnt[i].first - 1) - prefsum[i - 1]; 373 res += needl; 374 } 375 if (i + 1 < int(cnt.size()) && needr > 0) { 376 res += sufsum[i + 1] - sufcnt[i + 1] * 1ll * (cnt[i].first + 1); 377 res += needr; 378 } 379 ans = min(ans, res); 380 } 381 382 cout << ans << endl; 383 384 return 0; 385 } 386 ```