2222.md (15031B)
1 Source: https://codeforces.com/blog/entry/153275 2 3 We hope you enjoyed these problems! 4 5 [2222A - Замечательный контест](/contest/2222/problem/A) 6 7 Author: [Lyz09](/profile/Lyz09 "Кандидат в мастера Lyz09") 8 9 **Hint 1** 10 11 Consider the case where $k=1$. 12 13 **Tutorial** 14 15 Tutorial is loading... 16 17 **Implementation** 18 19 ``` 20 #include<iostream> 21 using namespace std; 22 int t,n; 23 int main() 24 { 25 cin>>t; 26 while(t--) 27 { 28 cin>>n; 29 bool ans=false; 30 for(int i=1;i<=n;i++) 31 { 32 int x; 33 cin>>x; 34 if(x==100) 35 ans=true; 36 } 37 if(ans) 38 cout<<"Yes"<<endl; 39 else 40 cout<<"No"<<endl; 41 } 42 } 43 ``` 44 45 [2222B - Художественное сбалансированное дерево](/contest/2222/problem/B) 46 47 Author: [lizhous](/profile/lizhous "Эксперт lizhous") 48 49 **Hint 1** 50 51 Consider for a given $p$, which elements can be placed at $p$ with one reversal operation. 52 53 **Tutorial** 54 55 Tutorial is loading... 56 57 **Implementation** 58 59 ``` 60 #include<iostream> 61 #include<cstdio> 62 #include<algorithm> 63 #include<queue> 64 #define int long long 65 using namespace std; 66 int n,a,x,m,sum; 67 priority_queue <int> nm[2]; 68 bool hv[2]; 69 signed main() 70 { 71 ios::sync_with_stdio(false); 72 cin.tie(0); 73 cout.tie(0); 74 int T; 75 cin>>T; 76 while(T--) 77 { 78 sum=0; 79 hv[0]=hv[1]=0; 80 while(!nm[0].empty()) nm[0].pop(); 81 while(!nm[1].empty()) nm[1].pop(); 82 cin>>n>>m; 83 for(int i=1;i<=n;i++) 84 { 85 cin>>a; 86 nm[i&1].push(a); 87 sum+=a; 88 } 89 for(int i=1;i<=m;i++) 90 { 91 cin>>x; 92 if((!nm[x&1].empty()&&nm[x&1].top()>=0)||!hv[x&1]) 93 { 94 sum-=nm[x&1].top(); 95 nm[x&1].pop(); 96 hv[x&1]=1; 97 } 98 } 99 cout<<sum<<"\n"; 100 } 101 } 102 ``` 103 104 [2222C - Разбиение по медиане](/contest/2222/problem/C) 105 106 Author: [ma2021tyoi0037](/profile/ma2021tyoi0037 "Эксперт ma2021tyoi0037") 107 108 **Hint 1** 109 110 Consider how to determine whether the median of an interval equals $x$. 111 112 **Hint 2** 113 114 What could be the median of each subsequence? 115 116 **Tutorial** 117 118 Tutorial is loading... 119 120 **Implementation** 121 122 ``` 123 #include<iostream> 124 #include<cstring> 125 #include<algorithm> 126 #include<cmath> 127 using namespace std; 128 const int N=5e3+10; 129 int n,a[N],b[N],mid,dp[N]; 130 void run(){ 131 cin>>n; 132 for(int i=1;i<=n;i++)cin>>a[i]; 133 memcpy(b+1,a+1,n<<2); 134 sort(b+1,b+n+1); 135 mid=b[(n+1)>>1]; 136 for(int i=1;i<=n;i++){ 137 if(a[i]==mid){ 138 a[i]=0; 139 continue; 140 } 141 a[i]=(a[i]>mid?1:-1); 142 } 143 for(int i=1,flg=0;i<=n;i++){ 144 dp[i]=0; 145 flg=!a[i]; 146 if(flg and (i==1 or dp[i-1]))dp[i]=dp[i-1]+1; 147 for(int j=i-3,sm=a[i];j>=0;j-=2){ 148 flg+=!a[j+1]; 149 flg+=!a[j+2]; 150 sm+=a[j+1]+a[j+2]; 151 if(abs(sm)>=flg or (j and !dp[j]))continue; 152 dp[i]=max(dp[i],dp[j]+1); 153 } 154 // cout<<dp[i]<<" \n"[i==n]; 155 } 156 cout<<dp[n]<<'\n'; 157 } 158 int main(){ 159 cin.tie(0); 160 cout.tie(0); 161 ios::sync_with_stdio(0); 162 int T; 163 cin>>T; 164 while(T--)run(); 165 } 166 ``` 167 168 [2222D - Построение перестановки](/contest/2222/problem/D) 169 170 Author: [Lyz09](/profile/Lyz09 "Кандидат в мастера Lyz09") 171 172 **Hint 1** 173 174 Try to perform a prefix sum on $a$. 175 176 **Hint 2** 177 178 Consider what the upper bound of the answer is. 179 180 **Tutorial** 181 182 Tutorial is loading... 183 184 **Implementation** 185 186 ``` 187 #include<iostream> 188 #include<algorithm> 189 using namespace std; 190 #define N 200010 191 int t,n,a[N],p[N]; 192 pair<long long,int> b[N]; 193 int main() 194 { 195 ios::sync_with_stdio(false); 196 cin.tie(0); 197 cout.tie(0); 198 cin>>t; 199 while(t--) 200 { 201 cin>>n; 202 b[0].first=0; 203 for(int i=1;i<=n;i++) 204 { 205 cin>>a[i]; 206 b[i].first=b[i-1].first+a[i]; 207 b[i].second=i; 208 } 209 for(int i=n;i>=1;i--) 210 b[i].first=b[i-1].first; 211 sort(b+1,b+n+1); 212 for(int i=n;i>=1;i--) 213 p[b[i].second]=n-i+1; 214 for(int i=1;i<=n;i++) 215 cout<<p[i]<<" \n"[i==n]; 216 } 217 } 218 ``` 219 220 [2222E - Докопаться до правды](/contest/2222/problem/E) 221 222 Author: [Lyz09](/profile/Lyz09 "Кандидат в мастера Lyz09") 223 224 **Hint 1** 225 226 Try to use $0$ and $2^n-1$ in the solution. 227 228 **Tutorial** 229 230 Tutorial is loading... 231 232 **Implementation** 233 234 ``` 235 #include<iostream> 236 #include<set> 237 using namespace std; 238 int t,n; 239 set<long long> s; 240 int makeI(long long x) 241 { 242 cout<<"I "<<x<<endl; 243 int ans=0; 244 cin>>ans; 245 return ans; 246 } 247 int makeQ(long long y) 248 { 249 cout<<"Q "<<y<<endl; 250 int ans=0; 251 cin>>ans; 252 return ans; 253 } 254 int query(long long x) 255 { 256 int res=makeQ(x); 257 for(long long w:s) 258 if(w>=x) 259 res--; 260 return res; 261 } 262 long long guess(int n) 263 { 264 long long pre=0; 265 for(int i=n-1;i>=0;i--) 266 if(query(pre|(1ll<<i))>0) 267 { 268 pre|=(1ll<<i); 269 } 270 return pre; 271 } 272 int main() 273 { 274 cin>>t; 275 while(t--) 276 { 277 cin>>n; 278 s.clear(); 279 cout<<0<<endl; 280 s.insert(0); 281 int res1=makeI(0); 282 if(res1==1) 283 { 284 makeI((1ll<<n)-1); 285 long long w=guess(n); 286 cout<<"A "<<1<<" "<<w<<endl; 287 continue; 288 } 289 long long c=guess(n); 290 s.insert(c); 291 if(c==(1ll<<n)-1) 292 { 293 int res2=makeI(1); 294 if(res2!=res1) 295 { 296 cout<<"A "<<3<<" "<<c<<endl; 297 } 298 else 299 { 300 cout<<"A "<<2<<" "<<c<<endl; 301 } 302 continue; 303 } 304 int res2=makeI((1ll<<n)-1); 305 if(query((1ll<<n)-1)>0) 306 { 307 cout<<"A "<<2<<" "<<c<<endl; 308 } 309 else 310 { 311 cout<<"A "<<3<<" "<<c<<endl; 312 } 313 } 314 } 315 ``` 316 317 [2222F - Построение дерева](/contest/2222/problem/F) 318 319 Author: [hzy_____](/profile/hzy_____ "Ученик hzy_____") Preparation: [Rebex](/profile/Rebex "Кандидат в мастера Rebex") 320 321 **Hint 1** 322 323 Under what circumstances can an edge with cost $w$ be added between vertex $u$ and vertex $v$ in a new graph? 324 325 **Hint 2** 326 327 Consider divide and conquer. 328 329 **Tutorial** 330 331 Tutorial is loading... 332 333 **Implementation** 334 335 ``` 336 #include <iostream> 337 #include <algorithm> 338 #include <cstdio> 339 #include <vector> 340 341 using namespace std; 342 343 const int S=300005; 344 345 int n,m,k; 346 vector<pair<int,int> > vec[S]; 347 int fa[S],hei[S],pt[S],fa2[S]; 348 int top,*pot[S*3],val[S*3]; 349 long long ans; 350 351 int fnd(int x){return fa[x]==x?x:fnd(fa[x]);} 352 int fnd2(int x){return fa2[x]==x?x:fa2[x]=fnd2(fa2[x]);} 353 354 inline void push(int &x){pot[++top]=&x,val[top]=x;} 355 inline void pop(){*pot[top]=val[top],top--;} 356 357 inline void merge(int x,int y,int w) 358 { 359 int rx=fnd(x),ry=fnd(y); 360 if(rx==ry) return; 361 int px=pt[rx],py=pt[ry]; 362 if(px!=0&&py!=0) 363 { 364 int rx=fnd2(px),ry=fnd2(py); 365 if(rx!=ry) ans+=w,fa2[rx]=fa2[ry]; 366 } 367 if(hei[rx]>hei[ry]) swap(rx,ry); 368 push(hei[ry]),hei[ry]=max(hei[ry],hei[rx]+1); 369 push(pt[ry]),pt[ry]=max(pt[ry],pt[rx]); 370 push(fa[rx]),fa[rx]=ry; 371 } 372 373 void doit(int l,int r,int w) 374 { 375 if(l==r) return; 376 int tp=top; 377 int mid=l+r>>1; 378 for(int i=r;i>=mid+1;i--) 379 for(auto t:vec[i]) merge(t.first,t.second,w); 380 doit(l,mid,w); 381 while(top>tp) pop(); 382 for(int i=l;i<=mid;i++) 383 { 384 if(!vec[i].empty()&&w==i) w++; 385 for(auto t:vec[i]) merge(t.first,t.second,w); 386 } 387 doit(mid+1,r,w); 388 while(top>tp) pop(); 389 } 390 391 inline void slove() 392 { 393 cin>>n>>m>>k; 394 for(int i=0;i<=m;i++) vec[i].clear(); 395 for(int i=1,x,y,w;i<=m;i++) cin>>x>>y>>w,vec[w].emplace_back(x,y); 396 vector<int> tmp; 397 for(int i=1,x;i<=k;i++) cin>>x,tmp.push_back(x); 398 sort(tmp.begin(),tmp.end()); 399 tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end()); 400 k=tmp.size(); 401 for(int i=1;i<=n;i++) pt[i]=0; 402 for(int i=0;i<k;i++) pt[tmp[i]]=i+1; 403 for(int i=1;i<=n;i++) fa[i]=i,hei[i]=1; 404 for(int i=1;i<=k;i++) fa2[i]=i; 405 ans=0; 406 doit(0,m,0); 407 for(int i=1;i<=k;i++) if(fnd2(i)!=fnd2(1)) return cout<<"-1\n",void(); 408 cout<<ans<<'\n'; 409 } 410 411 int main() 412 { 413 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); 414 int T; 415 cin>>T; 416 while(T-->0) slove(); 417 return 0; 418 } 419 ``` 420 421 [2222G - Статистика на дереве](/contest/2222/problem/G) 422 423 Author: [Lyz09](/profile/Lyz09 "Кандидат в мастера Lyz09") Developer: [Z-301](/profile/Z-301 "Легендарный гроссмейстер Z-301") 424 425 **Hint 1** 426 427 What is the value of a path that passes through the centroid of a tree? 428 429 **Hint 2** 430 431 What is the value of a path that does not pass through the centroid of a tree? 432 433 **Hint 3** 434 435 This is a convolution problem. Enumerate only the terms in the polynomial with non-zero coefficients and prove that the time complexity is correct. 436 437 **Tutorial** 438 439 Tutorial is loading... 440 441 **Implementation** 442 443 ``` 444 #include <algorithm> 445 #include <cstring> 446 #include <cstdio> 447 #include <vector> 448 #include <queue> 449 using namespace std; 450 typedef long long ll; 451 typedef vector<int> vi; 452 class edge{ 453 public: 454 edge(int x, int y, int z, int zz){v = x, w = y, c = z, nxt = zz;} 455 int v, w, c, nxt; 456 }; 457 class graph{ 458 private: 459 vector<int> head;vector<edge> e; 460 public: 461 void init(int n){head.clear(), e.clear();for (int i = 0;i <= n;i ++) head.emplace_back(-1);} 462 graph(){}graph(int n){init(n);} 463 inline int addedge(int u, int v, int w = 0, int c = 0){e.emplace_back(v, w, c, head[u]), head[u] = e.size() - 1;return e.size() - 1;} 464 inline int add2edge(int u, int v, int w = 0){int tmp = addedge(u, v, w);addedge(v, u, w);return tmp;} 465 inline int addfedge(int u, int v, int w, int c = 0){int tmp = addedge(u, v, w, c);addedge(v, u, 0, -c);return tmp;} 466 inline int& h(int u){return head[u];} 467 inline edge& operator[](int i){return e[i];} 468 }G; 469 const int N = 100005;ll ans[N];vi a[N];vector<ll> b[N]; 470 int t, n, al, mns, rt, sz[N], cnt[N]; 471 void dfs(int u, int fa){int mx = 0;sz[u] = 1; 472 for (int i = G.h(u);i != -1;i = G[i].nxt){ 473 int v = G[i].v;if (v == fa) continue; 474 dfs(v, u), sz[u] += sz[v], mx = max(mx, sz[v]); 475 }mx = max(mx, al - sz[u]); 476 if (mx < mns) rt = u, mns = mx; 477 } 478 void dfs1(int u, int fa, int mx, int rt){ 479 a[rt].push_back(max(mx, sz[u])); 480 for (int i = G.h(u);i != -1;i = G[i].nxt){ 481 int v = G[i].v;if (v == fa) continue; 482 dfs1(v, u, max(mx, sz[u] - sz[v]), rt); 483 } 484 } 485 void calc(vi& a, vector<ll>& s, vi& b, int o){ 486 int p = upper_bound(a.begin(), a.end(), o) - a.begin(); 487 for (int i = 0, j;i < b.size();i ++){ 488 j = upper_bound(a.begin(), a.end(), b[i]) - a.begin(); 489 if (b[i] > o) ans[o] -= j, ans[b[i]] += j;j = max(j, p); 490 if (j < a.size()) ans[o] -= a.size() - j, s[j] ++; 491 } 492 } 493 void dfs2(int u, int fa){vi vc; 494 for (int i = G.h(u);i != -1;i = G[i].nxt){ 495 int v = G[i].v, w = sz[v];if (v == fa) continue; 496 ans[n - w - w] += 1ll * cnt[w] * w, cnt[w] += w, vc.push_back(w); 497 }sort(vc.begin(), vc.end()), vc.erase(unique(vc.begin(), vc.end()), vc.end()); 498 for (int x : vc) for (int y : vc) if (x < y) 499 ans[n - x - y] += 1ll * cnt[x] * cnt[y]; 500 for (int v : vc) ans[n - v] += (u != rt) * cnt[v], cnt[v] = 0; 501 for (int i = G.h(u);i != -1;i = G[i].nxt){ 502 int v = G[i].v;if (v != fa) dfs2(v, u);} 503 } 504 void solve(int u){vi to; 505 for (int i = G.h(u);i != -1;i = G[i].nxt){ 506 int v = G[i].v;to.push_back(v), dfs1(v, u, 0, v); 507 sort(a[v].begin(), a[v].end()), b[v].resize(a[v].size(), 0); 508 } 509 for (int x : to) if (sz[x] * 3 >= n) for (int y : to) if (x < y || sz[y] * 3 < n) calc(a[x], b[x], a[y], n - sz[x] - sz[y]); 510 for (int v : to){ll ls = 0; 511 for (ll& x : b[v]) ls = x += ls; 512 for (int i = 0;i < a[v].size();i ++) 513 ans[max(a[v][i], n - sz[v])] ++, 514 ans[a[v][i]] += b[v][i];a[v].clear(), b[v].clear(); 515 }dfs2(rt, 0); 516 } 517 int main(){scanf("%d", &t); 518 while (t --){scanf("%d", &n), G.init(n); 519 for (int i = n - 1, u, v;i --;) 520 scanf("%d%d", &u, &v), G.add2edge(u, v);memset(ans, 0, n + 1 << 3); 521 al = n, mns = N, dfs(1, 0), dfs(rt, 0), solve(rt), ans[n] += n; 522 for (int i = 1;i <= n;i ++) printf("%lld ", ans[i]);putchar('\n'); 523 } 524 } 525 ``` 526 527 [2222H - Сортировка подсчётом?](/contest/2222/problem/H) 528 529 Author: [CutieSmileHaruka](/profile/CutieSmileHaruka "Гроссмейстер CutieSmileHaruka") 530 531 **Hint 1** 532 533 You are given an array $a$. How to count the number of arrays $b$ that satisfy $f(b) = a$ and $ \forall 1 \le i \le n, b_i \le r_i $.? 534 535 **Hint 2** 536 537 You are given an array $a$. How to count the number of arrays $b$ that satisfy $f(f(b)) = a$ and $ \forall 1 \le i \le n, b_i \le r_i $.? 538 539 **Hint 3** 540 541 How many arrays $a$ satisfy there exists an array $b$ such that $f(f(b)) = a$? 542 543 **Hint 4** 544 545 [The partition numbers](https://oeis.org/A000041). 546 547 **Tutorial** 548 549 Tutorial is loading... 550 551 **Implementation** 552 553 ``` 554 // 全身全霊!MORE MORE JUMP!! 555 #include <algorithm> 556 #include <cstring> 557 #include <cstdio> 558 #include <vector> 559 #include <queue> 560 #define mod 998244353 561 using namespace std; 562 typedef __int128_t lll; 563 template<typename T, const int M> 564 struct BHasher{inline int operator()(T x){return x % M;}}; 565 template<typename T1, typename T2, int M, typename Hsr = BHasher<T1, M>> 566 struct HashMap{ 567 struct node{int nx;T1 ky;T2 vl;}; 568 int h[M];vector<node> nd;Hsr hsh; 569 HashMap(){memset(h, -1, sizeof(h));} 570 void clear(){memset(h, -1, sizeof(h)), nd.clear();} 571 inline bool find(T1 k){int p = hsh(k); 572 for (int i = h[p];i != -1;i = nd[i].nx) 573 if (nd[i].ky == k) return 1;return 0; 574 } 575 inline T2& operator[](T1 k){int p = hsh(k); 576 for (int i = h[p];i != -1;i = nd[i].nx) 577 if (nd[i].ky == k) return nd[i].vl; 578 nd.push_back((node){h[p], k, T2()}); 579 return nd[h[p] = nd.size() - 1].vl; 580 } 581 }; 582 const int N = 55, K = 1005, M = 1296000;HashMap<lll, int, 1919839> id; 583 int t, n, m, k, c, a[N], fa[M], to[M][N], C[N][N], f[M], ans[K], rt, cnt; 584 unsigned char b[M][N], bb[N], ps[M][N], sk[N], tmp[N], sm[M], ct[M], dep[M]; 585 void dfs(int p, int sm){ 586 if (p > n){m ++; 587 memcpy(ps[m], sk, sizeof(sk)); 588 memcpy(b[m], bb, sizeof(bb)); 589 return; 590 } 591 for (int x = 0;x <= n && sm <= n;x ++, sm += p){ 592 if (x) sk[++ c] = p; 593 bb[p] = x, dfs(p + 1, sm); 594 if (x) sk[c --] = 0; 595 } 596 } 597 inline lll hsh(unsigned char* A){lll st = 0; 598 for (int i = 1;i <= n;i ++) 599 st <<= 1, st |= 1, st <<= A[i];return st; 600 } 601 inline unsigned char gdep(int x){return dep[x] ? dep[x] : dep[x] = gdep(fa[x]) + 1;} 602 inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;} 603 int main(){scanf("%d", &t), n = N - 5; 604 for (int i = 0;i <= n;i ++){C[i][0] = 1; 605 for (int j = 1;j <= i;j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;} 606 while (t --){scanf("%d%d", &n, &k), m = cnt = 0, dfs(1, 0); 607 memset(dep, 0, m + 1 << 1), memset(f, 0, m + 1 << 2), memset(ans, 0, k + 1 << 2); 608 for (int i = 1;i <= n;i ++) scanf("%d", &a[i]); 609 for (int i = 1;i <= m;i ++){ 610 lll st = hsh(b[i]);id[st] = i; 611 for (int j = n, p = -1;j >= 1;j --){ 612 p += b[i][j] + 1;if (b[i][j]) 613 to[i][j] = id[((st >> p) << p - 1) | (st & ((lll)1 << p) - 1)]; 614 } 615 } 616 for (int i = 1;i <= m;i ++){ 617 memset(tmp, 0, sizeof(tmp)), sm[i] = ct[i] = 0; 618 for (int j = 1;j <= n;j ++) 619 tmp[b[i][j]] ++, sm[i] += j * b[i][j], ct[i] += b[i][j]; 620 if (sm[i] == 1) rt = i; 621 fa[i] = id[hsh(tmp)]; 622 }f[1] = dep[1] = dep[rt] = 1; 623 for (int i = n, ss = 0;i >= 1;i --){ 624 for (int o = 1;o <= n;o ++) ss += a[o] == i; 625 for (int j = m;j >= 1;j --) 626 if (ct[j] <= n - i + 1 && sm[j] <= ss) 627 for (int k = 1, x, now;ps[j][k];k ++) 628 if (now = f[to[j][x = ps[j][k]]]) 629 f[j] = (f[j] + 1ll * now * C[ss - sm[j] + x][x]) % mod; 630 } 631 for (int i = 2;i <= m;i ++) add(ans[gdep(i) + 2], f[i]); 632 for (int i = 1;i <= n;i ++) cnt += a[i] > 0; 633 add(ans[3], mod - cnt), add(ans[2], cnt - (a[1] > 0)), add(ans[1], 1 + (a[1] > 0)); 634 for (int i = 1;i <= k;i ++) printf("%d ", ans[i]);putchar('\n'); 635 } 636 } 637 ```