1832.md (7149B)
1 Source: https://codeforces.com/blog/entry/116454 2 3 [1832A - New Palindrome](/contest/1832/problem/A "Educational Codeforces Round 148 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 string s; 23 cin >> s; 24 s = s.substr(0, s.size() / 2); 25 int k = unique(s.begin(), s.end()) - s.begin(); 26 cout << (k == 1 ? "NO" : "YES") << '\n'; 27 } 28 } 29 ``` 30 31 [1832B - Maximum Sum](/contest/1832/problem/B "Educational Codeforces Round 148 (Rated for Div. 2)") 32 33 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 34 35 **Tutorial** 36 37 Tutorial is loading... 38 39 **Solution (awoo)** 40 41 ``` 42 for _ in range(int(input())): 43 n, k = map(int, input().split()) 44 a = sorted(list(map(int, input().split()))) 45 ans = 0 46 pr = [0] * (n + 1) 47 for i in range(n): 48 pr[i + 1] = pr[i] + a[i] 49 for i in range(k + 1): 50 ans = max(ans, pr[n - (k - i)] - pr[2 * i]) 51 print(ans) 52 ``` 53 54 [1832C - Contrast Value](/contest/1832/problem/C "Educational Codeforces Round 148 (Rated for Div. 2)") 55 56 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 57 58 **Tutorial** 59 60 Tutorial is loading... 61 62 **Solution (Neon)** 63 64 ``` 65 #include <bits/stdc++.h> 66 67 using namespace std; 68 69 int main() { 70 ios::sync_with_stdio(false); cin.tie(0); 71 int t; 72 cin >> t; 73 while (t--) { 74 int n; 75 cin >> n; 76 vector<int> a(n); 77 for (int& x : a) cin >> x; 78 n = unique(a.begin(), a.end()) - a.begin(); 79 int ans = n; 80 for (int i = 0; i + 2 < n; ++i) { 81 ans -= (a[i] < a[i + 1] && a[i + 1] < a[i + 2]); 82 ans -= (a[i] > a[i + 1] && a[i + 1] > a[i + 2]); 83 } 84 cout << ans << '\n'; 85 } 86 } 87 ``` 88 89 [1832D1 - Red-Blue Operations (Easy Version)](/contest/1832/problem/D1 "Educational Codeforces Round 148 (Rated for Div. 2)") 90 91 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 [1832D2 - Red-Blue Operations (Hard Version)](/contest/1832/problem/D2 "Educational Codeforces Round 148 (Rated for Div. 2)") 98 99 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution (awoo)** 106 107 ``` 108 n, q = map(int, input().split()) 109 a = list(map(int, input().split())) 110 a.sort() 111 pr = [10**9 for i in range(n + 1)] 112 for i in range(n): 113 pr[i + 1] = min(pr[i], a[i] - i) 114 s = sum(a) - n * (n - 1) // 2 115 ans = [] 116 for k in map(int, input().split()): 117 if k < n: 118 ans.append(min(pr[k] + k, a[k])) 119 continue 120 if k % 2 == n % 2: 121 ns = s - pr[n] * n 122 ans.append(pr[n] + k - (max(0, (k - n) // 2 - ns) + n - 1) // n) 123 else: 124 nmn = min(pr[n - 1], a[n - 1] - k) 125 ns = (s + (n - 1) - k) - nmn * n 126 ans.append(nmn + k - (max(0, (k - (n - 1)) // 2 - ns) + n - 1) // n) 127 print(*ans) 128 ``` 129 130 [1832E - Combinatorics Problem](/contest/1832/problem/E "Educational Codeforces Round 148 (Rated for Div. 2)") 131 132 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Solution (BledDest)** 139 140 ``` 141 #include<bits/stdc++.h> 142 143 using namespace std; 144 145 const int MOD = 998244353; 146 147 int add(int x, int y, int mod = MOD) 148 { 149 return ((x + y) % mod + mod) % mod; 150 } 151 152 int mul(int x, int y, int mod = MOD) 153 { 154 return (x * 1ll * y) % mod; 155 } 156 157 int binpow(int x, int y, int mod = MOD) 158 { 159 int z = add(1, 0, mod); 160 while(y > 0) 161 { 162 if(y % 2 == 1) z = mul(z, x, mod); 163 y /= 2; 164 x = mul(x, x, mod); 165 } 166 return z; 167 } 168 169 vector<int> psum(vector<int> v) 170 { 171 vector<int> ans(1, 0); 172 for(auto x : v) ans.push_back(add(ans.back(), x)); 173 return ans; 174 } 175 176 int main() 177 { 178 int n; 179 cin >> n; 180 vector<int> a(n); 181 cin >> a[0]; 182 int x, y, m, k; 183 cin >> x >> y >> m >> k; 184 for(int i = 1; i < n; i++) 185 a[i] = add(mul(a[i - 1], x, m), y, m); 186 187 for(int i = 0; i <= k; i++) 188 a = psum(a); 189 long long ans = 0; 190 191 for(int i = 1; i <= n; i++) 192 ans ^= (a[i + 1] * 1ll * i); 193 cout << ans << endl; 194 } 195 ``` 196 197 [1832F - Zombies](/contest/1832/problem/F "Educational Codeforces Round 148 (Rated for Div. 2)") 198 199 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 200 201 **Tutorial** 202 203 Tutorial is loading... 204 205 **Solution (awoo)** 206 207 ``` 208 #include <bits/stdc++.h> 209 210 #define forn(i, n) for (int i = 0; i < int(n); i++) 211 212 using namespace std; 213 214 struct seg{ 215 int l, r; 216 }; 217 218 int n; 219 vector<long long> dp_before, dp_cur; 220 vector<vector<long long>> bst; 221 222 void compute(int l, int r, int optl, int optr){ 223 if (l > r) return; 224 int mid = (l + r) / 2; 225 pair<long long, int> best = {-1, -1}; 226 for (int k = optl; k <= min(mid, optr); k++) 227 best = max(best, {(k ? dp_before[k - 1] : 0) + bst[k][mid], k}); 228 dp_cur[mid] = best.first; 229 int opt = best.second; 230 compute(l, mid - 1, optl, opt); 231 compute(mid + 1, r, opt, optr); 232 } 233 234 struct node{ 235 long long c0; 236 int c1; 237 }; 238 239 vector<node> f; 240 241 void update(int x, int a, int b){ 242 for (int i = x; i < int(f.size()); i |= i + 1){ 243 f[i].c0 += b; 244 f[i].c1 += a; 245 } 246 } 247 248 void update(int l, int r, int a, int b){ 249 update(l, a, b); 250 update(r, -a, -b); 251 } 252 253 long long get(int pos, int x){ 254 long long res = 0; 255 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 256 res += f[i].c0 + f[i].c1 * 1ll * pos; 257 return res; 258 } 259 260 int main() { 261 int k, x, m; 262 scanf("%d%d%d%d", &n, &k, &x, &m); 263 vector<seg> a(n); 264 forn(i, n) scanf("%d%d", &a[i].l, &a[i].r); 265 sort(a.begin(), a.end(), [&](const seg &a, const seg &b){ 266 return a.l + a.r < b.l + b.r; 267 }); 268 269 vector<int> pos; 270 forn(i, n){ 271 pos.push_back(a[i].l); 272 pos.push_back(a[i].r - m); 273 } 274 sort(pos.begin(), pos.end()); 275 pos.resize(unique(pos.begin(), pos.end()) - pos.begin()); 276 int cds = pos.size(); 277 278 vector<array<int, 4>> npos(n); 279 forn(i, n){ 280 npos[i][0] = lower_bound(pos.begin(), pos.end(), a[i].l - m) - pos.begin(); 281 npos[i][1] = lower_bound(pos.begin(), pos.end(), a[i].l) - pos.begin(); 282 npos[i][2] = lower_bound(pos.begin(), pos.end(), a[i].r - m) - pos.begin(); 283 npos[i][3] = lower_bound(pos.begin(), pos.end(), a[i].r) - pos.begin(); 284 } 285 286 vector<long long> pr(n + 1); 287 forn(i, n) pr[i + 1] = pr[i] + x - (m + a[i].r - a[i].l); 288 289 auto upd = [&](int i){ 290 if (a[i].r - a[i].l >= m){ 291 update(npos[i][0], npos[i][1], 1, m - a[i].l); 292 update(npos[i][1], npos[i][2], 0, m); 293 update(npos[i][2], npos[i][3], -1, a[i].r); 294 } 295 else{ 296 update(npos[i][0], npos[i][2], 1, m - a[i].l); 297 update(npos[i][2], npos[i][1], 0, a[i].r - a[i].l); 298 update(npos[i][1], npos[i][3], -1, a[i].r); 299 } 300 }; 301 302 bst.resize(n, vector<long long>(n, -1)); 303 vector<vector<int>> opt(n, vector<int>(n)); 304 forn(r, n) for (int l = r; l >= 0; --l){ 305 if (l == r) f.assign(cds, {0, 0}); 306 upd(l); 307 int L = (l == r ? (l == 0 ? 0 : opt[l - 1][l - 1]) : opt[l][r - 1]); 308 int R = (l == r ? int(pos.size()) - 1 : opt[l + 1][r]); 309 for (int k = L; k <= R; ++k){ 310 long long cur = pr[r + 1] - pr[l] + get(pos[k], k); 311 if (cur > bst[l][r]){ 312 bst[l][r] = cur; 313 opt[l][r] = k; 314 } 315 } 316 } 317 318 dp_before.resize(n); 319 dp_cur.resize(n); 320 for (int i = 0; i < n; i++) 321 dp_before[i] = bst[0][i]; 322 323 for (int i = 1; i < k; i++){ 324 compute(0, n - 1, 0, n - 1); 325 dp_before = dp_cur; 326 } 327 328 printf("%lld\n", dp_before[n - 1]); 329 return 0; 330 } 331 ```