1948.md (6856B)
1 Source: https://codeforces.com/blog/entry/127182 2 3 [1948A - Special Characters](/contest/1948/problem/A "Educational Codeforces Round 163 (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 int n; 23 cin >> n; 24 if (n % 2 == 1) { 25 cout << "NO" << '\n'; 26 continue; 27 } 28 cout << "YES" << '\n'; 29 for (int i = 0; i < n / 2; ++i) 30 for (int j = 0; j < 2; ++j) 31 cout << "AB"[i & 1]; 32 cout << '\n'; 33 } 34 } 35 ``` 36 37 [1948B - Array Fix](/contest/1948/problem/B "Educational Codeforces Round 163 (Rated for Div. 2)") 38 39 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution (Neon)** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 int main() { 53 int t; 54 cin >> t; 55 while (t--) { 56 int n; 57 cin >> n; 58 vector<int> a(n); 59 for (auto& x : a) cin >> x; 60 vector<int> b({a[n - 1]}); 61 for (int i = n - 2; i >= 0; --i) { 62 if (a[i] > b.back()) { 63 b.push_back(a[i] % 10); 64 b.push_back(a[i] / 10); 65 } else { 66 b.push_back(a[i]); 67 } 68 } 69 cout << (is_sorted(b.rbegin(), b.rend()) ? "YES" : "NO") << '\n'; 70 } 71 } 72 ``` 73 74 [1948C - Arrow Path](/contest/1948/problem/C "Educational Codeforces Round 163 (Rated for Div. 2)") 75 76 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution (Neon)** 83 84 ``` 85 #include <bits/stdc++.h> 86 87 using namespace std; 88 89 int main() { 90 int t; 91 cin >> t; 92 while (t--) { 93 int n; 94 cin >> n; 95 vector<char> ok1(n / 2), ok2(n / 2); 96 for (int i = 0; i < 2; ++i) { 97 string s; 98 cin >> s; 99 for (int j = 0; j < n; ++j) if ((i + j) & 1) { 100 ok1[(i + j) / 2] |= (s[j] == '>'); 101 ok2[(j - i + 1) / 2] |= (s[j] == '>'); 102 } 103 } 104 bool ans = true; 105 for (int i = 0; i < n / 2; ++i) ans &= ok1[i] && ok2[i]; 106 cout << (ans ? "YES" : "NO") << '\n'; 107 } 108 } 109 ``` 110 111 [1948D - Tandem Repeats?](/contest/1948/problem/D "Educational Codeforces Round 163 (Rated for Div. 2)") 112 113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Solution (awoo)** 120 121 ``` 122 for _ in range(int(input())): 123 s = input() 124 n = len(s) 125 ans = 0 126 for d in range(1, n // 2 + 1): 127 cnt = 0 128 for i in range(n - d): 129 cnt += s[i] == s[i + d] or s[i] == '?' or s[i + d] == '?' 130 if i - d >= 0: 131 cnt -= s[i - d] == s[i] or s[i - d] == '?' or s[i] == '?' 132 if i - d >= -1 and cnt == d: 133 ans = 2 * d 134 print(ans) 135 ``` 136 137 [1948E - Clique Partition](/contest/1948/problem/E "Educational Codeforces Round 163 (Rated for Div. 2)") 138 139 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 140 141 **Tutorial** 142 143 Tutorial is loading... 144 145 **Solution (BledDest)** 146 147 ``` 148 #include<bits/stdc++.h> 149 150 using namespace std; 151 152 void solve() 153 { 154 int n, k; 155 cin >> n >> k; 156 vector<int> a(n), c(n); 157 for(int i = 0; i < n; i++) 158 { 159 a[i] = i + 1; 160 c[i] = i / k + 1; 161 } 162 int q = *max_element(c.begin(), c.end()); 163 for(int i = 1; i <= q; i++) 164 { 165 int l = find(c.begin(), c.end(), i) - c.begin(); 166 int r = c.rend() - find(c.rbegin(), c.rend(), i); 167 int m = (l + r) / 2; 168 reverse(a.begin() + l, a.begin() + m); 169 reverse(a.begin() + m, a.begin() + r); 170 } 171 for(int i = 0; i < n; i++) 172 cout << a[i] << " \n"[i == n - 1]; 173 cout << q << "\n"; 174 for(int i = 0; i < n; i++) 175 cout << c[i] << " \n"[i == n - 1]; 176 } 177 178 int main() 179 { 180 int t; 181 cin >> t; 182 for(int i = 0; i < t; i++) 183 solve(); 184 } 185 ``` 186 187 [1948F - Rare Coins](/contest/1948/problem/F "Educational Codeforces Round 163 (Rated for Div. 2)") 188 189 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 190 191 **Tutorial** 192 193 Tutorial is loading... 194 195 **Solution (Neon)** 196 197 ``` 198 #include <bits/stdc++.h> 199 200 using namespace std; 201 202 const int MOD = 998244353; 203 204 int add(int x, int y) { 205 x += y; 206 if (x >= MOD) x -= MOD; 207 return x; 208 } 209 210 int mul(int x, int y) { 211 return x * 1LL * y % MOD; 212 } 213 214 int binpow(int x, int y) { 215 int z = 1; 216 while (y) { 217 if (y & 1) z = mul(z, x); 218 x = mul(x, x); 219 y >>= 1; 220 } 221 return z; 222 } 223 224 int main() { 225 ios::sync_with_stdio(false); cin.tie(0); 226 int n, q; 227 cin >> n >> q; 228 vector<int> a(n), b(n); 229 for (auto& x : a) cin >> x; 230 for (auto& x : b) cin >> x; 231 vector<int> suma(n + 1), sumb(n + 1); 232 for (int i = 0; i < n; ++i) { 233 suma[i + 1] = suma[i] + a[i]; 234 sumb[i + 1] = sumb[i] + b[i]; 235 } 236 int m = sumb[n]; 237 vector<int> f(m + 1), invf(m + 1); 238 f[0] = 1; 239 for (int i = 1; i <= m; ++i) f[i] = mul(f[i - 1], i); 240 invf[m] = binpow(f[m], MOD - 2); 241 for (int i = m; i > 0; --i) invf[i - 1] = mul(invf[i], i); 242 vector<int> sumc(m + 2); 243 for (int i = 0; i <= m; ++i) 244 sumc[i + 1] = add(sumc[i], mul(f[m], mul(invf[i], invf[m - i]))); 245 int pw2 = binpow(binpow(2, MOD - 2), m); 246 while (q--) { 247 int l, r; 248 cin >> l >> r; 249 --l; 250 int k = 2 * (suma[r] - suma[l]) - suma[n]; 251 int cur = sumb[r] - sumb[l]; 252 int mx = max(0, min(k + cur, m + 1)); 253 int cnt = sumc[mx]; 254 cout << mul(cnt, pw2) << ' '; 255 } 256 } 257 ``` 258 259 [1948G - MST with Matching](/contest/1948/problem/G "Educational Codeforces Round 163 (Rated for Div. 2)") 260 261 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 262 263 **Tutorial** 264 265 Tutorial is loading... 266 267 **Solution (BledDest)** 268 269 ``` 270 #include<bits/stdc++.h> 271 272 using namespace std; 273 274 int n, c; 275 int g[21][21]; 276 277 const int INF = int(1e9); 278 279 int primMST(int vertex_cover_mask) 280 { 281 vector<int> d(n, INF); 282 vector<bool> used(n, false); 283 d[0] = 0; 284 int ans = 0; 285 for(int i = 0; i < n; i++) 286 { 287 int idx = -1; 288 for(int j = 0; j < n; j++) 289 { 290 if(!used[j] && d[j] < INF && (idx == -1 || d[j] < d[idx])) 291 idx = j; 292 } 293 if(idx == -1) return INF; 294 used[idx] = true; 295 ans += d[idx]; 296 for(int k = 0; k < n; k++) 297 { 298 if(used[k]) 299 continue; 300 if((vertex_cover_mask & (1 << idx)) == 0 && (vertex_cover_mask & (1 << k)) == 0) 301 continue; 302 d[k] = min(d[k], g[idx][k]); 303 } 304 } 305 return ans; 306 } 307 308 int main() 309 { 310 cin >> n >> c; 311 for(int i = 0; i < n; i++) 312 { 313 for(int j = 0; j < n; j++) 314 { 315 cin >> g[i][j]; 316 if(g[i][j] == 0) g[i][j] = INF; 317 } 318 } 319 int ans = INF; 320 for(int mask = 0; mask < (1 << n); mask++) 321 { 322 int cur = primMST(mask); 323 if(cur != INF) ans = min(ans, cur + c * __builtin_popcount(mask)); 324 } 325 cout << ans << endl; 326 } 327 ```