2231.md (8492B)
1 Source: https://codeforces.com/blog/entry/153910 2 3 **Problem A**: 4 5 **Editorial** 6 7 Tutorial is loading... 8 9 **Code** 10 11 ``` 12 t = int(input()) 13 for tt in range(t): 14 n = int(input()) 15 ans = [2 * i + 1 for i in range(n)] 16 print(*ans) 17 ``` 18 19 **Problem B** (Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")): 20 21 **Editorial** 22 23 Tutorial is loading... 24 25 **Code** 26 27 ``` 28 #include <bits/stdc++.h> 29 30 #define all(a) a.begin(), a.end() 31 #define rall(a) a.rbegin(), a.rend() 32 #define len(a) (int)(a.size()) 33 34 #ifdef LOCAL 35 #define __lg(n) log2(n) 36 #endif 37 38 using namespace std; 39 40 using ll = long long; 41 using ull = unsigned long long; 42 using ld = long double; 43 44 template<typename T> 45 using PQ = priority_queue<T, vector<T>, greater<>>; 46 47 void solve() { 48 int n; 49 cin >> n; 50 vector<int> a(n); 51 for (int i = 0; i < n; ++i) { 52 cin >> a[i]; 53 } 54 int mx = 0; 55 for (int i = 0; i < n — 1; ++i) { 56 mx = max(mx, a[i] — a[i + 1]); 57 } 58 for (int i = 1; i < n; ++i) { 59 if (a[i] < a[i — 1]) { 60 a[i] += mx; 61 } 62 } 63 if (is_sorted(all(a))) { 64 cout << "YES\n"; 65 } else { 66 cout << "NO\n"; 67 } 68 } 69 70 signed main() { 71 ios_base::sync_with_stdio(0); 72 cin.tie(0); 73 74 int t = 1; 75 cin >> t; 76 while (t--) solve(); 77 } 78 ``` 79 80 **Задача C**: 81 82 **Editorial** 83 84 Tutorial is loading... 85 86 **Code** 87 88 ``` 89 for _ in range(int(input())): 90 n = int(input()) 91 a = list(map(int, input().split())) 92 cnt1 = dict() 93 cnt2 = dict() 94 x = a[0] 95 a = a[1:] 96 s = set() 97 c = 0 98 while x not in s: 99 if x not in cnt1: 100 cnt1[x] = 0 101 cnt2[x] = 0 102 cnt1[x] += 1 103 cnt2[x] += c 104 s.add(x) 105 if x & 1: 106 x += 1 107 else: 108 x >>= 1 109 c += 1 110 for x in a: 111 s = set() 112 c = 0 113 while x not in s: 114 if x in cnt1: 115 cnt1[x] += 1 116 cnt2[x] += c 117 s.add(x) 118 if x & 1: 119 x += 1 120 else: 121 x >>= 1 122 c += 1 123 ans = 10 ** 18 124 for k, v in cnt1.items(): 125 if v == n: 126 ans = min(ans, cnt2[k]) 127 print(ans) 128 ``` 129 130 **Problem D** (Author: [sunkuangzheng](/profile/sunkuangzheng "Grandmaster sunkuangzheng")): 131 132 **Editorial** 133 134 Tutorial is loading... 135 136 **Code** 137 138 ``` 139 #include<bits/stdc++.h> 140 #ifdef DEBUG_LOCAL 141 #include <mydebug/debug.h> 142 #endif 143 using ll = long long; 144 const int N = 5e5+5; 145 using namespace std; 146 int T,n; string s; ll a[N],c[N],b[N],d[N]; 147 void los(){ 148 cin >> n >> s,s = " " + s; d[0] = 1; 149 for(int i = 1;i <= n;i ++) cin >> a[i],d[i] = 0; 150 for(int i = 1;i <= n;i ++) cin >> c[i]; 151 c[0] = -1e18,b[0] = 0; 152 for(int i = 1;i <= n;i ++){ 153 if(c[i] != c[i — 1]){ 154 if(c[i] < c[i-1]) return cout << "No\n",void(); 155 b[i] = c[i],d[i] = 1; 156 for(int j = i;j >= 0;j --){ 157 if(s[j] == '1'){ 158 if(d[j — 1] && b[j — 1] + a[j] != b[j]) return cout << "No\n",void(); 159 d[j — 1] = 1,b[j — 1] = b[j] — a[j]; 160 }else break; 161 } 162 } 163 }for(int i = 1;i <= n;i ++){ 164 if(s[i] == '1') b[i] = b[i-1] + a[i],d[i] = 1; 165 if(!d[i]) b[i] = -1e16; 166 a[i] = b[i] — b[i-1]; 167 if(max(c[i-1],b[i]) != c[i]) return cout << "No\n",void(); 168 } 169 cout << "Yes\n"; 170 for(int i = 1;i <= n;i ++){ 171 cout << a[i] << " \n"[i == n]; 172 } 173 }int main(){ 174 ios::sync_with_stdio(0),cin.tie(0); 175 for(cin >> T;T --;) los(); 176 } 177 ``` 178 179 **Problem E**: 180 181 **Editorial** 182 183 Tutorial is loading... 184 185 **Code** 186 187 ``` 188 #include <bits/stdc++.h> 189 190 #define all(a) a.begin(), a.end() 191 #define rall(a) a.rbegin(), a.rend() 192 #define len(a) (int)(a.size()) 193 194 using namespace std; 195 196 using ll = long long; 197 using ld = long double; 198 199 const int N = 2228; 200 201 vector<int> G[N]; 202 int tin[N], tout[N]; 203 int timer = 0; 204 int cntup[N][N]; 205 int cntdown[N][N]; 206 ll ans1 = 0, ans2 = 0, ans3 = 0; 207 208 void solve_path(int n, int v, int d) { 209 vector<int> dist(n); 210 auto dfs = [&](auto &self, int v, int p, int h = 0) -> void { 211 dist[v] = h; 212 for (int i : G[v]) { 213 if (i != p) self(self, i, v, h + 1); 214 } 215 }; 216 217 dfs(dfs, v, -1, 0); 218 219 for (int i = v + 1; i < n; ++i) { 220 if (dist[i] == d) { 221 ans1 += d - 1; 222 } 223 } 224 } 225 226 void dfs_tin(int v, int p) { 227 tin[v] = timer++; 228 229 for (int i : G[v]) { 230 if (i != p) dfs_tin(i, v); 231 } 232 tout[v] = timer; 233 } 234 235 void solve() { 236 int n, d; 237 cin >> n >> d; 238 --d; 239 for (int i = 0; i < n; ++i) G[i].clear(); 240 ans1 = 0, ans2 = 0, ans3 = 0, timer = 0; 241 242 for (int i = 0; i < n - 1; ++i) { 243 int a, b; 244 cin >> a >> b; 245 G[a - 1].push_back(b - 1); 246 G[b - 1].push_back(a - 1); 247 } 248 249 for (int i = 0; i < n; ++i) solve_path(n, i, d); 250 for (int i = 0; i < n; ++i) { 251 fill(cntup[i], cntup[i] + N, 0); 252 fill(cntdown[i], cntdown[i] + N, 0); 253 } 254 dfs_tin(0, -1); 255 256 for (int i = 0; i < n; ++i) { 257 auto dfs = [&](auto &self, int v, int p, int h) -> void { 258 if (tin[i] <= tin[v] && tin[v] < tout[i]) ++cntdown[i][h]; 259 else ++cntup[i][h]; 260 261 for (int j : G[v]) { 262 if (j != p) self(self, j, v, h + 1); 263 } 264 }; 265 266 dfs(dfs, i, -1, 0); 267 } 268 269 vector<int> h(n); 270 auto dfs = [&](auto &self, int v, int p, int hh = 0) -> vector<int> { 271 int m = len(G[v]); 272 vector<vector<int>> who(m); 273 vector<int> all; 274 all.push_back(v); 275 h[v] = hh; 276 277 for (int i = 0; i < len(G[v]); ++i) { 278 if (G[v][i] == p) continue; 279 280 who[i] = self(self, G[v][i], v, hh + 1); 281 for (int j : who[i]) all.push_back(j); 282 283 for (int j = 0; j < i; ++j) { 284 for (int v1 : who[i]) { 285 for (int v2 : who[j]) { 286 287 int D = h[v1] + h[v2] - 2 * hh; 288 if (D >= d) continue; 289 int need = d - D; 290 ans2 += cntup[v][need]; 291 int cnt3 = cntdown[v][need]; 292 cnt3 -= cntdown[G[v][i]][need - 1]; 293 cnt3 -= cntdown[G[v][j]][need - 1]; 294 ans3 += cnt3; 295 296 } 297 } 298 } 299 } 300 301 return all; 302 }; 303 304 dfs(dfs, 0, -1, 0); 305 cout << ans1 + ans2 + ans3 / 3 << '\n'; 306 } 307 308 int main() { 309 ios_base::sync_with_stdio(0); 310 cin.tie(0); 311 312 int t = 1; 313 cin >> t; 314 while (t--) solve(); 315 } 316 ``` 317 318 **Problem F** (Author: [Vladithur](/profile/Vladithur "Master Vladithur")): 319 320 **Editorial** 321 322 Tutorial is loading... 323 324 **Code** 325 326 ``` 327 #include <bits/stdc++.h> 328 329 #define all(x) (x).begin(), (x).end() 330 #define allr(x) (x).rbegin(), (x).rend() 331 #define gsize(x) (int)((x).size()) 332 333 const char nl = '\n'; 334 typedef long long ll; 335 typedef long double ld; 336 337 using namespace std; 338 339 const int K = 450; 340 341 void solve() { 342 int n, q; 343 cin >> n >> q; 344 345 vector<int> f(n, -1); // f[i] = -1 if impossible, 1 if i = a^2, 2 if i = a^2 + b^2 346 for (int a = 1; a * a < n; a++) { 347 for (int b = a; a * a + b * b < n; b++) { 348 f[a * a + b * b] = 2; 349 } 350 351 f[a * a] = 1; 352 } 353 354 vector<int> g(n, -1); // g[i] = -1 if impossible, else min `b` over i = a^2 - b^2 355 for (int b = 1; b * b < n; b++) { 356 for (int a = b; a * a - b * b < n; a++) { 357 int v = a * a - b * b; 358 if (g[v] < 0) g[v] = b * b; 359 } 360 } 361 362 while (q--) { 363 int a, b; 364 cin >> a >> b; 365 366 int ans = 4; 367 for (int d = -K; d <= K; d++) { 368 int x = a + abs(d) * d; 369 if (x <= 0 || x > n) continue; 370 371 int ta = x, tb = b; 372 if (ta > tb) swap(ta, tb); 373 374 int tans = 4; 375 { 376 int v = tb - ta; 377 if (g[v] > 0 && g[v] <= max(n - tb, ta - 1)) { 378 tans = 2; 379 } 380 381 if (f[v] > 0) { 382 tans = f[v]; 383 } 384 385 if (d != 0) tans++; 386 } 387 388 ans = min(ans, tans); 389 } 390 391 cout << ans << nl; 392 } 393 } 394 395 int main() { 396 ios::sync_with_stdio(0); cin.tie(0); 397 398 int t; 399 cin >> t; 400 while (t--) solve(); 401 } 402 ```