2170.md (8742B)
1 Source: https://codeforces.com/blog/entry/148798 2 3 [2170A - Maximum Neighborhood](/contest/2170/problem/A "Educational Codeforces Round 185 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution 1 (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int dx[] = {-1, 0, 1, 0}; 19 int dy[] = {0, -1, 0, 1}; 20 21 int main() { 22 int t; 23 cin >> t; 24 while (t--) { 25 int n; 26 cin >> n; 27 auto get = [&](int x, int y) { 28 if (x >= 0 && x < n && y >= 0 && y < n) return x * n + y + 1; 29 return 0; 30 }; 31 int ans = 0; 32 for (int i = 0; i < n; ++i) { 33 for (int j = 0; j < n; ++j) { 34 int cur = get(i, j); 35 for (int d = 0; d < 4; ++d) cur += get(i + dx[d], j + dy[d]); 36 ans = max(ans, cur); 37 } 38 } 39 cout << ans << '\n'; 40 } 41 } 42 ``` 43 44 **Solution 2 (Neon)** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 int main() { 52 int t; 53 cin >> t; 54 while (t--) { 55 int n; 56 cin >> n; 57 int ans = 1; 58 if (n == 2) ans = 9; 59 else if (n == 3 || n == 4) ans = 4 * n * n - n - 4; 60 else if (n > 4) ans = 5 * n * n - 5 * n - 5; 61 cout << ans << '\n'; 62 } 63 } 64 ``` 65 66 [2170B - Addition on a Segment](/contest/2170/problem/B "Educational Codeforces Round 185 (Rated for Div. 2)") 67 68 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 69 70 **Tutorial** 71 72 Tutorial is loading... 73 74 **Solution (FelixArg)** 75 76 ``` 77 #include<bits/stdc++.h> 78 using namespace std; 79 80 #define int long long 81 82 void solve(){ 83 int n; 84 cin >> n; 85 vector<int> a(n); 86 for (int i = 0; i < n; i++){ 87 cin >> a[i]; 88 } 89 90 int sum = 0; 91 int cnt_one = 0; 92 93 for (int i = 0; i < n; i++){ 94 if (a[i] > 0){ 95 cnt_one++; 96 } 97 sum += a[i]; 98 } 99 100 int sum2 = sum - cnt_one; 101 int sub = n - 1 - sum2; 102 103 cout << cnt_one - max(0ll, sub) << '\n'; 104 } 105 106 signed main() 107 { 108 #ifdef FELIX 109 auto _clock_start = chrono::high_resolution_clock::now(); 110 #endif 111 ios_base::sync_with_stdio(false); 112 cin.tie(0); 113 cout.tie(0); 114 115 int t = 1; 116 cin >> t; 117 while(t--){ 118 solve(); 119 } 120 121 #ifdef FELIX 122 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 123 chrono::high_resolution_clock::now() 124 - _clock_start).count() << "ms." << endl; 125 #endif 126 return 0; 127 } 128 ``` 129 130 [2170C - Quotient and Remainder](/contest/2170/problem/C "Educational Codeforces Round 185 (Rated for Div. 2)") 131 132 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Solution (adedalic)** 139 140 ``` 141 #include<bits/stdc++.h> 142 143 using namespace std; 144 145 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 146 #define sz(a) int((a).size()) 147 148 typedef long long li; 149 150 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 151 fore(i, 0, sz(v)) { 152 if(i) out << " "; 153 out << v[i]; 154 } 155 return out; 156 } 157 158 const int INF = int(1e9); 159 const li INF64 = li(1e18); 160 161 inline void solve() { 162 int n; li k; 163 cin >> n >> k; 164 vector<int> q(n), r(n); 165 fore (i, 0, n) 166 cin >> q[i]; 167 fore (i, 0, n) 168 cin >> r[i]; 169 170 sort(q.begin(), q.end()); 171 sort(r.begin(), r.end()); 172 173 auto check = [&](int cnt) { 174 fore (i, 0, cnt) { 175 if (li(q[i] + 1) * (r[cnt - 1 - i] + 1) - 1 > k) 176 return false; 177 } 178 return true; 179 }; 180 181 int lf = 0, rg = n + 1; 182 while (rg - lf > 1) { 183 int mid = (lf + rg) >> 1; 184 if (check(mid)) 185 lf = mid; 186 else 187 rg = mid; 188 } 189 cout << lf << endl; 190 } 191 192 int main() { 193 #ifdef _DEBUG 194 freopen("input.txt", "r", stdin); 195 int tt = clock(); 196 #endif 197 ios_base::sync_with_stdio(false); 198 cin.tie(0), cout.tie(0); 199 cout << fixed << setprecision(15); 200 201 int t = 1; cin >> t; 202 while (t--) { 203 solve(); 204 205 #ifdef _DEBUG 206 cerr << "TIME = " << clock() - tt << endl; 207 tt = clock(); 208 #endif 209 } 210 return 0; 211 } 212 ``` 213 214 [2170D - Almost Roman](/contest/2170/problem/D "Educational Codeforces Round 185 (Rated for Div. 2)") 215 216 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 217 218 **Tutorial** 219 220 Tutorial is loading... 221 222 **Solution (BledDest)** 223 224 ``` 225 #include<bits/stdc++.h> 226 227 using namespace std; 228 229 int cost(char c) 230 { 231 if(c == 'I') return 1; 232 return 5; 233 } 234 235 int eval(string s) 236 { 237 int n = s.size(); 238 int ans = 0; 239 for(int i = 0; i < n; i++) 240 if(s[i] == 'I' && i + 1 < n && s[i + 1] == 'V') 241 ans--; 242 else ans += cost(s[i]); 243 return ans; 244 } 245 246 void solve() 247 { 248 int n, q; 249 cin >> n >> q; 250 string s; 251 cin >> s; 252 int ans = 0; 253 for(int i = 0; i < n; i++) 254 { 255 if(s[i] == 'X') 256 { 257 s[i] = 'V'; 258 ans += 5; 259 } 260 } 261 int inc = 0; 262 int same = 0; 263 int qcount = 0; 264 for(int i = 0; i < n; i++) 265 { 266 if(s[i] != '?') continue; 267 int r = i; 268 while(r < n && s[r] == '?') r++; 269 int len = r - i; 270 if(i > 0 && s[i - 1] == 'I') len++; 271 if(r < n && s[r] == 'V') 272 { 273 inc--; 274 len++; 275 } 276 inc += len / 2; 277 same += len % 2; 278 qcount += (r - i); 279 i = r - 1; 280 } 281 for(int i = 0; i < n; i++) 282 if(s[i] == '?') s[i] = 'I'; 283 ans += eval(s); 284 for(int i = 0; i < q; i++) 285 { 286 int a, b, c; 287 cin >> a >> b >> c; 288 int used_v = max(0, min(b, qcount - c)); 289 int used_x = max(0, qcount - c - b); 290 int cur = ans; 291 cur += used_v * 4 + used_x * 9; 292 int rep = used_v + used_x; 293 cur -= min(inc, rep) * 2; 294 rep -= (inc + same); 295 cur += max(0, rep) * 2; 296 cout << cur << "\n"; 297 } 298 } 299 300 int main() 301 { 302 ios_base::sync_with_stdio(0); 303 cin.tie(0); 304 int t; 305 cin >> t; 306 for(int i = 0; i < t; i++) 307 solve(); 308 } 309 ``` 310 311 [2170E - Binary Strings and Blocks](/contest/2170/problem/E "Educational Codeforces Round 185 (Rated for Div. 2)") 312 313 Idea: [Roms](/profile/Roms "Master Roms") 314 315 **Tutorial** 316 317 Tutorial is loading... 318 319 **Solution (BledDest)** 320 321 ``` 322 #include<bits/stdc++.h> 323 324 using namespace std; 325 326 const int INF = 1e9; 327 const int MOD = 998244353; 328 329 int add(int x, int y) 330 { 331 x += y; 332 while(x >= MOD) x -= MOD; 333 while(x < 0) x += MOD; 334 return x; 335 } 336 337 void solve() 338 { 339 int n, m; 340 cin >> n >> m; 341 vector<int> max_left(n + 1, -1); 342 for(int i = 0; i < m; i++) 343 { 344 int l, r; 345 cin >> l >> r; 346 --l; 347 --r; 348 max_left[r] = max(max_left[r], l); 349 } 350 for(int i = 1; i <= n; i++) 351 max_left[i] = max(max_left[i], max_left[i - 1]); 352 vector<int> dp(n + 1); 353 vector<int> prefsum(n + 2); 354 dp[0] = 2; 355 prefsum[1] = 2; 356 for(int i = 1; i <= n; i++) 357 { 358 int j = max_left[i - 1] + 1; 359 dp[i] = add(prefsum[i], -prefsum[j]); 360 prefsum[i + 1] = add(prefsum[i], dp[i]); 361 } 362 cout << dp[n] << "\n"; 363 } 364 365 int main() 366 { 367 ios_base::sync_with_stdio(0); 368 cin.tie(0); 369 int t; 370 cin >> t; 371 for(int i = 0; i < t; i++) solve(); 372 } 373 ``` 374 375 [2170F - Build XOR on a Segment](/contest/2170/problem/F "Educational Codeforces Round 185 (Rated for Div. 2)") 376 377 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 378 379 **Tutorial** 380 381 Tutorial is loading... 382 383 **Solution (BledDest)** 384 385 ``` 386 #include<bits/stdc++.h> 387 388 using namespace std; 389 390 const int B = 13; 391 const int M = (1 << (B - 1)); 392 const int INF = 1e9; 393 394 int dp[B][M]; 395 396 void upd(int& a, int b) 397 { 398 if(a < b) a = b; 399 } 400 401 int main() 402 { 403 ios_base::sync_with_stdio(0); 404 cin.tie(0); 405 int n; 406 cin >> n; 407 vector<int> a(n); 408 for(int i = 0; i < n; i++) cin >> a[i]; 409 vector<vector<int>> id(n); 410 int q; 411 cin >> q; 412 vector<int> l(q), x(q); 413 for(int i = 0; i < q; i++) 414 { 415 int r; 416 cin >> l[i] >> r >> x[i]; 417 --l[i]; 418 --r; 419 id[r].push_back(i); 420 } 421 422 for(int i = 0; i < B; i++) 423 for(int j = 0; j < M; j++) 424 dp[i][j] = -INF; 425 dp[0][0] = INF; 426 vector<int> ans(q, 0); 427 for(int i = 0; i < n; i++) 428 { 429 int val = a[i]; 430 upd(dp[1][val], i); 431 for(int j = 1; j < B - 1; j++) 432 { 433 for(int k = 1; k < M; k++) 434 { 435 upd(dp[j + 1][k ^ val], dp[j][k]); 436 } 437 } 438 for(auto qr : id[i]) 439 { 440 int cur = x[qr]; 441 for(int j = B - 1; j >= 0; j--) 442 if(dp[j][cur] >= l[qr]) 443 ans[qr] = j; 444 } 445 } 446 447 for(int i = 0; i < q; i++) 448 cout << ans[i] << " "; 449 cout << endl; 450 } 451 ```