1914.md (6517B)
1 Source: https://codeforces.com/blog/entry/123530 2 3 [1914A - Problemsolving Log](/contest/1914/problem/A "Codeforces Round 916 (Div. 3)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 n = int(input()) 16 s = input() 17 print(sum([s.count(chr(ord('A') + i)) >= i + 1 for i in range(26)])) 18 ``` 19 20 [1914B - Preparing for the Contest](/contest/1914/problem/B "Codeforces Round 916 (Div. 3)") 21 22 Idea: [Roms](/profile/Roms "Master Roms") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (BledDest)** 29 30 ``` 31 #include<bits/stdc++.h> 32 33 using namespace std; 34 35 void solve() 36 { 37 int n, k; 38 cin >> n >> k; 39 vector<int> a(n); 40 for(int i = 0; i < n; i++) a[i] = n - i; 41 reverse(a.end() - k - 1, a.end()); 42 for(int i = 0; i < n; i++) 43 { 44 if(i) cout << " "; 45 cout << a[i]; 46 } 47 cout << endl; 48 } 49 50 int main() 51 { 52 int t; 53 cin >> t; 54 for(int i = 0; i < t; i++) 55 solve(); 56 return 0; 57 } 58 ``` 59 60 [1914C - Quests](/contest/1914/problem/C "Codeforces Round 916 (Div. 3)") 61 62 Idea: [Roms](/profile/Roms "Master Roms") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution (Neon)** 69 70 ``` 71 fun main() = repeat(readLine()!!.toInt()) { 72 val (n, k) = readLine()!!.split(" ").map { it.toInt() } 73 val a = readLine()!!.split(" ").map { it.toInt() } 74 val b = readLine()!!.split(" ").map { it.toInt() } 75 var (res, sum, mx) = intArrayOf(0, 0, 0) 76 for (i in 0 until minOf(n, k)) { 77 sum += a[i] 78 mx = maxOf(mx, b[i]) 79 res = maxOf(res, sum + mx * (k - i - 1)) 80 } 81 println(res) 82 } 83 ``` 84 85 [1914D - Three Activities](/contest/1914/problem/D "Codeforces Round 916 (Div. 3)") 86 87 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 88 89 **Tutorial** 90 91 Tutorial is loading... 92 93 **Solution (awoo)** 94 95 ``` 96 for _ in range(int(input())): 97 n = int(input()) 98 a = list(map(int, input().split())) 99 b = list(map(int, input().split())) 100 c = list(map(int, input().split())) 101 102 def get_best3(a): 103 mx1, mx2, mx3 = -1, -1, -1 104 for i in range(len(a)): 105 if mx1 == -1 or a[i] > a[mx1]: 106 mx3 = mx2 107 mx2 = mx1 108 mx1 = i 109 elif mx2 == -1 or a[i] > a[mx2]: 110 mx3 = mx2 111 mx2 = i 112 elif mx3 == -1 or a[i] > a[mx3]: 113 mx3 = i 114 return (mx1, mx2, mx3) 115 116 ans = 0 117 for x in get_best3(a): 118 for y in get_best3(b): 119 for z in get_best3(c): 120 if x != y and x != z and y != z: 121 ans = max(ans, a[x] + b[y] + c[z]) 122 print(ans) 123 ``` 124 125 [1914E1 - Game with Marbles (Easy Version)](/contest/1914/problem/E1 "Codeforces Round 916 (Div. 3)") 126 127 [1914E2 - Game with Marbles (Hard Version)](/contest/1914/problem/E2 "Codeforces Round 916 (Div. 3)") 128 129 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 130 131 **Tutorial** 132 133 Tutorial is loading... 134 135 **Solution (adedalic)** 136 137 ``` 138 #include<bits/stdc++.h> 139 140 using namespace std; 141 142 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 143 #define sz(a) int((a).size()) 144 145 typedef long long li; 146 147 // S = sum a_i - sum b_i 148 // if Bob made all steps: then S = 0 - sum (b_i - 1) 149 // each Alice step: S += (a_i - 1) + (b_i - 1) i. e. the bigger (a_i + b_i) the better 150 151 int n; 152 vector<int> a, b; 153 154 inline bool read() { 155 if(!(cin >> n)) 156 return false; 157 a.resize(n); 158 b.resize(n); 159 fore (i, 0, n) 160 cin >> a[i]; 161 fore (i, 0, n) 162 cin >> b[i]; 163 return true; 164 } 165 166 inline void solve() { 167 vector<int> ids(n); 168 iota(ids.begin(), ids.end(), 0); 169 170 sort(ids.begin(), ids.end(), [&](int i, int j) { 171 return a[i] + b[i] > a[j] + b[j]; 172 }); 173 174 li S = 0; 175 fore (i, 0, n) { 176 if (i & 1) 177 S -= b[ids[i]] - 1; 178 else 179 S += a[ids[i]] - 1; 180 } 181 cout << S << endl; 182 } 183 184 int main() { 185 #ifdef _DEBUG 186 freopen("input.txt", "r", stdin); 187 int tt = clock(); 188 #endif 189 // ios_base::sync_with_stdio(false); 190 // cin.tie(0), cout.tie(0); 191 cout << fixed << setprecision(15); 192 int t; 193 cin >> t; 194 for(int i = 0; i < t; i++) 195 { 196 if(read()) { 197 solve(); 198 199 #ifdef _DEBUG 200 cerr << "TIME = " << clock() - tt << endl; 201 tt = clock(); 202 #endif 203 } 204 } 205 return 0; 206 } 207 ``` 208 209 [1914F - Programming Competition](/contest/1914/problem/F "Codeforces Round 916 (Div. 3)") 210 211 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 212 213 **Tutorial** 214 215 Tutorial is loading... 216 217 **Solution (Neon)** 218 219 ``` 220 #include <bits/stdc++.h> 221 222 using namespace std; 223 224 const int N = 222222; 225 226 int n; 227 int sz[N]; 228 vector<int> g[N]; 229 230 void init(int v) { 231 sz[v] = 1; 232 for (int u : g[v]) { 233 init(u); 234 sz[v] += sz[u]; 235 } 236 } 237 238 int calc(int v, int k) { 239 int tot = 0, mx = -1; 240 for (int u : g[v]) { 241 tot += sz[u]; 242 if (mx == -1 || sz[mx] < sz[u]) mx = u; 243 } 244 if (tot == 0) return 0; 245 if (sz[mx] - k <= tot - sz[mx]) 246 return (tot - k) / 2; 247 int add = tot - sz[mx]; 248 return add + calc(mx, max(0, k + add - 1)); 249 } 250 251 int main() { 252 ios::sync_with_stdio(false); cin.tie(0); 253 int t; 254 cin >> t; 255 while (t--) { 256 cin >> n; 257 for (int i = 0; i < n; ++i) g[i].clear(); 258 for (int i = 1; i < n; ++i) { 259 int p; cin >> p; 260 g[p - 1].push_back(i); 261 } 262 init(0); 263 cout << calc(0, 0) << '\n'; 264 } 265 } 266 ``` 267 268 [1914G1 - Light Bulbs (Easy Version)](/contest/1914/problem/G1 "Codeforces Round 916 (Div. 3)") 269 270 [1914G2 - Light Bulbs (Hard Version)](/contest/1914/problem/G2 "Codeforces Round 916 (Div. 3)") 271 272 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 273 274 **Tutorial** 275 276 Tutorial is loading... 277 278 **Solution (BledDest)** 279 280 ``` 281 #include<bits/stdc++.h> 282 283 using namespace std; 284 285 const int MOD = 998244353; 286 287 int add(int x, int y) 288 { 289 return (((x + y) % MOD) + MOD) % MOD; 290 } 291 292 int mul(int x, int y) 293 { 294 return (x * 1ll * y) % MOD; 295 } 296 297 mt19937_64 rnd(98275314); 298 299 long long gen() 300 { 301 long long x = 0; 302 while(x == 0) 303 x = rnd(); 304 return x; 305 } 306 307 vector<int> c; 308 vector<int> g; 309 310 int process_block(int l, int r) 311 { 312 int ans = 0; 313 while(l < r) 314 { 315 if(g[l] != -1 && g[l] < r) 316 l = g[l]; 317 else 318 { 319 ans++; 320 l++; 321 } 322 } 323 return ans; 324 } 325 326 void solve() 327 { 328 int n; 329 scanf("%d", &n); 330 int size = 0, cnt = 1; 331 c.resize(n * 2); 332 g.resize(n * 2, -1); 333 for(int i = 0; i < 2 * n; i++) 334 { 335 scanf("%d", &c[i]); 336 --c[i]; 337 } 338 339 vector<long long> val(n); 340 for(int i = 0; i < n; i++) val[i] = gen(); 341 342 map<long long, int> last; 343 long long cur = 0; 344 last[0] = 0; 345 for(int i = 0; i < n * 2; i++) 346 { 347 cur ^= val[c[i]]; 348 if(cur == 0) 349 { 350 size++; 351 cnt = mul(cnt, process_block(last[0], i + 1)); 352 last.clear(); 353 } 354 else if(last.count(cur)) 355 { 356 g[last[cur]] = i + 1; 357 } 358 last[cur] = i + 1; 359 } 360 361 printf("%d %d\n", size, cnt); 362 c.clear(); 363 g.clear(); 364 } 365 366 int main() 367 { 368 int t; 369 scanf("%d", &t); 370 for(int i = 0; i < t; i++) solve(); 371 } 372 ```