1327.md (11157B)
1 Source: https://codeforces.com/blog/entry/75147 2 3 [1327A - Sum of Odd Integers](/contest/1327/problem/A "Educational Codeforces Round 84 (Rated for Div. 2)") 4 5 Idea: [vovuh](/profile/vovuh "Master vovuh") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (vovuh)** 12 13 ``` 14 for i in range(int(input())): 15 n, k = map(int, input().split()) 16 print('YES' if k * k <= n and n % 2 == k % 2 else 'NO') 17 ``` 18 19 [1327B - Princesses and Princes](/contest/1327/problem/B "Educational Codeforces Round 84 (Rated for Div. 2)") 20 21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (pikmike)** 28 29 ``` 30 from sys import stdin, stdout 31 32 t = int(stdin.readline()) 33 for _ in range(t): 34 n = int(stdin.readline()) 35 used = [False for i in range(n)] 36 v = -1 37 for i in range(n): 38 l = [int(x) - 1 for x in stdin.readline().split()][1:] 39 for j in l: 40 if not used[j]: 41 used[j] = True 42 break 43 else: 44 v = i 45 if v == -1: 46 stdout.write("OPTIMAL\n") 47 else: 48 u = used.index(False) 49 stdout.write("IMPROVE\n" + str(v + 1) + " " + str(u + 1) + "\n") 50 ``` 51 52 [1327C - Game with Chips](/contest/1327/problem/C "Educational Codeforces Round 84 (Rated for Div. 2)") 53 54 Idea: [Neon](/profile/Neon "Candidate Master Neon") 55 56 **Tutorial** 57 58 Tutorial is loading... 59 60 **Solution (Ne0n25)** 61 62 ``` 63 n, m, _ = map(int, input().split()) 64 65 print(2 * (n - 1) + (n + 1) * (m - 1)) 66 print("U" * (n - 1) + "L" * (m - 1), end="") 67 for i in range(n): 68 if i != 0: 69 print("D", end="") 70 if i % 2 == 0: 71 print("R" * (m - 1), end="") 72 else: 73 print("L" * (m - 1), end="") 74 ``` 75 76 [1327D - Infinite Path](/contest/1327/problem/D "Educational Codeforces Round 84 (Rated for Div. 2)") 77 78 Idea: [adedalic](/profile/adedalic "International Master adedalic") 79 80 **Tutorial** 81 82 Tutorial is loading... 83 84 **Solution (adedalic)** 85 86 ``` 87 #include<bits/stdc++.h> 88 89 using namespace std; 90 91 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 92 #define sz(a) int((a).size()) 93 94 #define x first 95 #define y second 96 97 typedef long long li; 98 typedef pair<int, int> pt; 99 100 const int INF = int(1e9); 101 const li INF64 = li(1e18); 102 103 int n; 104 vector<int> p, c; 105 106 inline bool read() { 107 if(!(cin >> n)) 108 return false; 109 p.resize(n); 110 c.resize(n); 111 112 fore(i, 0, n) { 113 cin >> p[i]; 114 p[i]--; 115 } 116 fore(i, 0, n) 117 cin >> c[i]; 118 return true; 119 } 120 121 inline void solve() { 122 vector<int> used(n, 0); 123 124 int ans = INF; 125 fore(st, 0, n) { 126 if(used[st]) 127 continue; 128 129 vector<int> cycle; 130 int v = st; 131 while(!used[v]) { 132 used[v] = 1; 133 cycle.push_back(v); 134 v = p[v]; 135 } 136 137 fore(step, 1, sz(cycle) + 1) { 138 if(sz(cycle) % step != 0) 139 continue; 140 141 fore(s, 0, step) { 142 bool eq = true; 143 for(int pos = s; pos + step < sz(cycle); pos += step) { 144 if(c[cycle[pos]] != c[cycle[pos + step]]) 145 eq = false; 146 } 147 if(eq) { 148 ans = min(ans, step); 149 break; 150 } 151 } 152 } 153 } 154 cout << ans << endl; 155 } 156 157 int main() { 158 #ifdef _DEBUG 159 freopen("input.txt", "r", stdin); 160 int tt = clock(); 161 #endif 162 ios_base::sync_with_stdio(false); 163 cin.tie(0), cout.tie(0); 164 cout << fixed << setprecision(15); 165 166 int tc; cin >> tc; 167 168 while(tc--) { 169 read(); 170 solve(); 171 172 #ifdef _DEBUG 173 cerr << "TIME = " << clock() - tt << endl; 174 tt = clock(); 175 #endif 176 } 177 return 0; 178 } 179 ``` 180 181 [1327E - Count The Blocks](/contest/1327/problem/E "Educational Codeforces Round 84 (Rated for Div. 2)") 182 183 Idea: [adedalic](/profile/adedalic "International Master adedalic") 184 185 **Tutorial** 186 187 Tutorial is loading... 188 189 **Solution (Roms)** 190 191 ``` 192 MOD = 998244353 193 p = [1] * 200005 194 for i in range(1, 200005): 195 p[i] = (p[i - 1] * 10) % MOD 196 197 n = int(input()) 198 for i in range(1, n): 199 res = 2 * 10 * 9 * p[n - i - 1] 200 res += (n - 1 - i) * 10 * 9 * 9 * p[n - i - 2] 201 print(res % MOD, end = ' ') 202 print(10) 203 ``` 204 205 [1327F - AND Segments](/contest/1327/problem/F "Educational Codeforces Round 84 (Rated for Div. 2)") 206 207 Idea: [Neon](/profile/Neon "Candidate Master Neon") 208 209 **Tutorial** 210 211 Tutorial is loading... 212 213 **Solution (Ne0n25)** 214 215 ``` 216 #include <bits/stdc++.h> 217 218 using namespace std; 219 220 #define x first 221 #define y second 222 #define sz(a) int((a).size()) 223 #define all(a) (a).begin(), (a).end() 224 #define forn(i, n) for (int i = 0; i < int(n); ++i) 225 226 typedef pair<int, int> pt; 227 228 const int MOD = 998244353; 229 const int N = 500 * 1000 + 13; 230 231 int n, k, m; 232 pair<pt, int> q[N]; 233 234 int ones[N]; 235 int mx[N], sum[N]; 236 237 int add(int x, int y) { 238 x += y; 239 if (x >= MOD) x -= MOD; 240 if (x < 0) x += MOD; 241 return x; 242 } 243 244 int calc(int t) { 245 memset(ones, 0, sizeof(ones)); 246 memset(mx, -1, sizeof(mx)); 247 248 forn(i, m) { 249 int l = q[i].x.x, r = q[i].x.y; 250 if (q[i].y & (1 << t)) { 251 ones[l]++; 252 ones[r + 1]--; 253 } else { 254 mx[r] = max(mx[r], l); 255 } 256 } 257 258 int j = -1; 259 forn(i, n) { 260 int cur = 0; 261 if (!ones[i]) { 262 cur = sum[i]; 263 if (j == -1) cur = add(cur, 1); 264 else cur = add(cur, -sum[j]); 265 } 266 267 sum[i + 1] = add(sum[i], cur); 268 ones[i + 1] += ones[i]; 269 j = max(j, mx[i]); 270 } 271 272 return add(sum[n], j != -1 ? -sum[j] : 1); 273 } 274 275 int main() { 276 scanf("%d%d%d", &n, &k, &m); 277 forn(i, m) { 278 scanf("%d%d%d", &q[i].x.x, &q[i].x.y, &q[i].y); 279 --q[i].x.x; --q[i].x.y; 280 } 281 282 int ans = 1; 283 forn(i, k) ans = (ans * 1ll * calc(i)) % MOD; 284 printf("%d\n", ans); 285 } 286 ``` 287 288 [1327G - Letters and Question Marks](/contest/1327/problem/G "Educational Codeforces Round 84 (Rated for Div. 2)") 289 290 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 291 292 **Tutorial** 293 294 Tutorial is loading... 295 296 **Solution (BledDest)** 297 298 ``` 299 #include<bits/stdc++.h> 300 301 using namespace std; 302 303 const int N = 8000043; 304 const int K = 15; 305 const int M = 1043; 306 307 int k; 308 char buf[N], buf2[M]; 309 vector<string> t; 310 vector<int> c; 311 string s; 312 313 map<char, int> nxt[M]; 314 int lnk[M]; 315 int p[M]; 316 char pchar[M]; 317 map<char, int> go[M]; 318 int term[M]; 319 int ts = 1; 320 int A[M][K]; 321 int F[M][K]; 322 int dp[M]; 323 324 int get_nxt(int x, char c) 325 { 326 if(!nxt[x].count(c)) 327 { 328 p[ts] = x; 329 pchar[ts] = c; 330 nxt[x][c] = ts++; 331 } 332 return nxt[x][c]; 333 } 334 335 void add_string(int i) 336 { 337 int cur = 0; 338 for(auto x : t[i]) 339 { 340 cur = get_nxt(cur, x); 341 } 342 term[cur] += c[i]; 343 } 344 345 int get_go(int x, char c); 346 347 int get_lnk(int x) 348 { 349 if(lnk[x] != -1) 350 return lnk[x]; 351 if(x == 0 || p[x] == 0) 352 return lnk[x] = 0; 353 return lnk[x] = get_go(get_lnk(p[x]), pchar[x]); 354 } 355 356 int get_dp(int x) 357 { 358 if(dp[x] != -1) 359 return dp[x]; 360 dp[x] = term[x]; 361 if(get_lnk(x) != x) 362 dp[x] += get_dp(get_lnk(x)); 363 return dp[x]; 364 } 365 366 int get_go(int x, char c) 367 { 368 if(go[x].count(c)) 369 return go[x][c]; 370 if(nxt[x].count(c)) 371 return go[x][c] = nxt[x][c]; 372 if(x == 0) 373 return go[x][c] = 0; 374 return go[x][c] = get_go(get_lnk(x), c); 375 } 376 377 void build_skip(const string& s, vector<int>& sA, vector<long long>& sF) 378 { 379 sA = vector<int>(ts); 380 for(int i = 0; i < ts; i++) 381 sA[i] = i; 382 sF = vector<long long>(ts); 383 for(auto c : s) 384 { 385 int ci = int(c - 'a'); 386 for(int i = 0; i < ts; i++) 387 { 388 sF[i] += F[sA[i]][ci]; 389 sA[i] = A[sA[i]][ci]; 390 } 391 } 392 } 393 394 long long solve(const string& s) 395 { 396 long long BAD = (long long)(-1e18); 397 398 vector<int> pos; 399 for(int i = 0; i < s.size(); i++) 400 if(s[i] == '?') 401 pos.push_back(i); 402 int cntQ = pos.size(); 403 vector<vector<int> > skip_A(cntQ + 1); 404 vector<vector<long long> > skip_F(cntQ + 1); 405 build_skip(s.substr(0, pos[0]), skip_A[0], skip_F[0]); 406 for(int i = 1; i < cntQ; i++) 407 build_skip(s.substr(pos[i - 1] + 1, pos[i] - pos[i - 1] - 1), skip_A[i], skip_F[i]); 408 build_skip(s.substr(pos.back() + 1, s.size() - pos.back() - 1), skip_A[cntQ], skip_F[cntQ]); 409 410 vector<vector<long long> > dp(1 << (K - 1), vector<long long>(ts, BAD)); 411 vector<int> used(1 << K); 412 dp[0][skip_A[0][0]] = skip_F[0][0]; 413 queue<int> q; 414 q.push(0); 415 used[0] = 1; 416 long long ans = BAD; 417 while(!q.empty()) 418 { 419 int k = q.front(); 420 q.pop(); 421 int step = __builtin_popcount(k); 422 if(step == cntQ) 423 { 424 for(int i = 0; i < ts; i++) 425 ans = max(ans, dp[k][i]); 426 continue; 427 } 428 for(int i = 0; i < K - 1; i++) 429 { 430 if(k & (1 << i)) continue; 431 int nk = (k ^ (1 << i)); 432 if(used[nk] == 0) 433 { 434 used[nk] = 1; 435 q.push(nk); 436 } 437 for(int j = 0; j < ts; j++) 438 { 439 if(dp[k][j] == BAD) 440 continue; 441 int nj = get_go(j, char('a' + i)); 442 int newSt = skip_A[step + 1][nj]; 443 long long add = get_dp(nj) + skip_F[step + 1][nj]; 444 dp[nk][newSt] = max(dp[nk][newSt], dp[k][j] + add); 445 } 446 } 447 } 448 return ans; 449 } 450 451 int main() 452 { 453 scanf("%d", &k); 454 t.resize(k); 455 c.resize(k); 456 for(int i = 0; i < k; i++) 457 { 458 scanf("%s %d", buf2, &c[i]); 459 t[i] = buf2; 460 } 461 scanf("%s", buf); 462 s = buf; 463 464 for(int i = 0; i < k; i++) 465 add_string(i); 466 for(int i = 0; i < ts; i++) 467 { 468 lnk[i] = -1; 469 dp[i] = -1; 470 } 471 for(int i = 0; i < ts; i++) 472 { 473 get_lnk(i); 474 for(char c = 'a'; c <= 'o'; c++) 475 get_go(i, c); 476 } 477 for(int i = 0; i < ts; i++) 478 get_dp(i); 479 for(int i = 0; i < ts; i++) 480 { 481 for(int j = 0; j < K; j++) 482 { 483 A[i][j] = get_go(i, char('a' + j)); 484 F[i][j] = dp[A[i][j]]; 485 } 486 } 487 int n = s.size(); 488 vector<int> leftQ(n, -1); 489 vector<int> rightQ(n, -1); 490 for(int i = 0; i < n; i++) 491 { 492 if(i != 0) 493 leftQ[i] = leftQ[i - 1]; 494 if(s[i] == '?') 495 leftQ[i] = i; 496 } 497 for(int i = n - 1; i >= 0; i--) 498 { 499 if(i != n - 1) 500 rightQ[i] = rightQ[i + 1]; 501 if(s[i] == '?') 502 rightQ[i] = i; 503 } 504 vector<int> bad(n, 0); 505 506 if(leftQ.back() == -1) 507 bad = vector<int>(n, 1); 508 509 long long ans = 0; 510 int curSt = 0; 511 string news = ""; 512 for(int i = 0; i < n; i++) 513 { 514 int ci = (s[i] == '?' ? 14 : int(s[i] - 'a')); 515 if(bad[i]) 516 ans += F[curSt][ci]; 517 curSt = A[curSt][ci]; 518 if(!bad[i]) 519 news.push_back(s[i]); 520 else if(i != 0 && !bad[i - 1]) 521 news.push_back('o'); 522 } 523 if(!news.empty()) 524 ans += solve(news); 525 printf("%lld\n", ans); 526 } 527 ```