2146.md (13462B)
1 Source: https://codeforces.com/blog/entry/146648 2 3 [2146A - Equal Occurrences](/contest/2146/problem/A "Codeforces Round 1052 (Div. 2)") 4 5 **Hint 1** 6 7 Let's focus on the number of occurrences of each element: let $c_i$ be the number of time that element $i$ occurs in the array. To keep a subsequence is to decrease each $c_i$ by a non-negative integer. We need to make all the non-zero elements in $c$ the same while maximizing the sum of $c$. 8 9 **Hint 2** 10 11 For each integer $x$: suppose the value of all non-zero elements in $c$ is $x$, what is the length of the longest subsequence? 12 13 **Answer** 14 15 For those $c_i \lt x$, we decrease it to $0$; for those $c_i\ge x$, we decrease it to $x$. 16 17 **Tutorial** 18 19 Tutorial is loading... 20 21 **Implementation** 22 23 By [Caylex](/profile/Caylex "Master Caylex"). 24 25 ``` 26 def solve(): 27 n = int(input()) 28 ls = list(map(int, input().split())) 29 a = [0] * n 30 for x in ls: 31 a[x - 1] += 1 32 a = sorted(a) 33 s = sum(a) 34 ans = s 35 for i in range(n): 36 ans = min(ans, s - (n - i) * a[i]) 37 print(n - ans) 38 return 39 40 41 t = int(input()) 42 for _ in range(t): 43 solve() 44 ``` 45 46 [2146B - Merging the Sets](/contest/2146/problem/B "Codeforces Round 1052 (Div. 2)") 47 48 **Hint 1** 49 50 How to check if there is at least one way to choose the sets? 51 52 **Answer** 53 54 Obviously, we should choose all the sets. 55 56 **Hint 2** 57 58 How to greedily find two more solutions to choose the sets? 59 60 **Answer** 61 62 We should choose all the sets but one. 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Implementation** 69 70 By [Caylex](/profile/Caylex "Master Caylex"). 71 72 ``` 73 def solve(): 74 n, m = map(int, input().split()) 75 cnt = [0] * m 76 t = 0 77 v = [] 78 for i in range(n): 79 v.append([]) 80 inp = list(map(int, input().split())) 81 l = inp[0] 82 for j in range(1, l + 1): 83 x = inp[j] 84 x -= 1 85 t += not cnt[x] 86 cnt[x] += 1 87 v[i].append(x) 88 ans = t == m 89 for i in range(n): 90 for x in v[i]: 91 cnt[x] -= 1 92 t -= not cnt[x] 93 ans += t == m 94 for x in v[i]: 95 t += not cnt[x] 96 cnt[x] += 1 97 print("YES" if ans >= 3 else "NO") 98 return 99 100 t = int(input()) 101 for _ in range(t): 102 solve() 103 ``` 104 105 [2146C - Wrong Binary Search](/contest/2146/problem/C "Codeforces Round 1052 (Div. 2)") 106 107 **Hint 1** 108 109 How to check if an element $x$ is stable? For an element $p_i$, we only care about whether $p_i \lt x$, $p_i=x$ or $p_i \gt x$. 110 111 **Hint 2** 112 113 If an element is not stable, we can choose $m$ correctly in the first step to exclude $x$ from interval $[l,r]$. 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Implementation** 120 121 By [Caylex](/profile/Caylex "Master Caylex"). 122 123 ``` 124 def solve(): 125 n = int(input()) 126 s = str(input()) 127 l = 0 128 p = [] 129 for i in range(n): 130 p.append(i + 1) 131 while l < n: 132 if s[l] == "1": 133 l += 1 134 continue 135 r = l 136 while r + 1 < n and s[r + 1] == "0": 137 r += 1 138 if r - l + 1 == 1: 139 print("NO") 140 return 141 ok = 1 142 for i in range(l, r): 143 p[i] = i + 2 144 p[r] = l + 1 145 l = r + 1 146 print("YES") 147 for i in range(n): 148 print(p[i], end=" ") 149 print() 150 return 151 152 t = int(input()) 153 for _ in range(t): 154 solve() 155 ``` 156 157 [2146D1 - Max Sum OR (Easy Version)](/contest/2146/problem/D1 "Codeforces Round 1052 (Div. 2)") 158 159 **Hint 1** 160 161 Try a few cases by hand or guess by the samples, what's the maximized answer for $l=0,r=n$? 162 163 **Answer** 164 165 The answer is $n(n+1)$. Actually, as $x\mid y\le x+y$, so the upper bound for the answer is $\sum (a_i+b_i)=n(n+1)$. And we are going to reach the upper bound. 166 167 **Hint 2** 168 169 We need to make the bitwise AND of $a_i$ and $b_i$ all equal to $0$. Let's remind you that the bitwise AND of $x$ and $2^k-1-x$ is $0$ for $0\le x \lt 2^k$. We can try to pair integers $x$ and $y$ by letting $a_x=y,a_y=x$. 170 171 **Hint 3** 172 173 Construct from the back. 174 175 **Tutorial** 176 177 Tutorial is loading... 178 179 **Implementation** 180 181 By [Caylex](/profile/Caylex "Master Caylex"). 182 183 ``` 184 def solve(): 185 l, r = map(int, input().split()) 186 pw = 1 187 ans = 0 188 while pw < r: 189 pw = pw << 1 | 1 190 s = set() 191 for i in range(l, r + 1): 192 s.add(i) 193 a = [0] * (r + 1) 194 for i in range(r, l - 1, -1): 195 while pw - i not in s: 196 pw >>= 1 197 a[i] = pw - i 198 ans += i | a[i] 199 s.remove(pw - i) 200 print(ans) 201 print(*a[l : r + 1]) 202 return 203 204 t = int(input()) 205 for _ in range(t): 206 solve() 207 ``` 208 209 [2146D2 - Max Sum OR (Hard Version)](/contest/2146/problem/D2 "Codeforces Round 1052 (Div. 2)") 210 211 **Hint 1** 212 213 Let's consider from the highest bits to the lowest bits. If the highest bits of $l$ and $r$ are the same, we can just ignore this bit and go on to a lower bit. We can still try to pair integers $x$ and $y$ by letting $a_x=y,a_y=x$. 214 215 **Hint 2** 216 217 Consider the highest bit that $l$ and $r$ differs. There exist an integer $t$ that this bit of $l\ldots t-1$ are $0$ and this bit of $t\ldots r$ are $1$. We need to pair a $0$ with a $1$ as more as possible while keeping the bitwise AND of lower bits small. Can we turn it into a smaller subproblem? 218 219 **Hint 3** 220 221 In D1, it is optimal to pair $x$ with $2^k-1-x$. Here, for interval $[l,r]$ and integer $t$ defined in Hint2, it is optimal to pair $x$ with $2t-1-x$. 222 223 **Tutorial** 224 225 Tutorial is loading... 226 227 **Implementation** 228 229 By [Caylex](/profile/Caylex "Master Caylex"). 230 231 ``` 232 def g(x, j): 233 return x >> j & 1 234 235 def solve(): 236 L, R = map(int, input().split()) 237 a = [0] * (R - L + 1) 238 239 def solve(l, r, j): 240 if l > r: 241 return 242 if l == r: 243 a[l - L] = r 244 return 245 mid = l 246 while mid + 1 <= r and g(mid + 1, j) == g(l, j): 247 mid += 1 248 if mid == r: 249 solve(l, r, j - 1) 250 return 251 tl = mid + 1 252 tr = mid 253 while tl - 1 >= l and tr + 1 <= r: 254 tl -= 1 255 tr += 1 256 a[tl - L] = tr 257 a[tr - L] = tl 258 solve(l, tl - 1, j - 1) 259 solve(tr + 1, r, j - 1) 260 return 261 262 solve(L, R, 29) 263 ans = 0 264 for i in range(L, R + 1): 265 ans += a[i - L] | i 266 print(ans) 267 print(*a) 268 return 269 270 t = int(input()) 271 for _ in range(t): 272 solve() 273 ``` 274 275 **Another solution using greedy on trie** 276 277 It turns out that we can solve it greedily from the lowest bit to the highest bit. For each element in $[l,r]$, let's reverse its binary representation and insert it into a 01-trie. Then for each index $i$, we can do `dfs` on the trie while trying to keep every bit different with $i$. Formally, each step we try to go to the opposite side of each bit of $i$, and go on the other side if that subtree is empty. 278 279 We can prove that this gives the same construction with the other method constructing from the higher bits. You can read the implementation for better understanding. 280 281 **Implementation** 282 283 ``` 284 #include<bits/stdc++.h> 285 using namespace std; 286 #define int long long 287 #define pb push_back 288 #define REP(i,b,e) for(int i=(b);i<(int)(e);++i) 289 int l,r; 290 int tot; 291 int son[6000005][2],cnt[6000005]; 292 void Main() { 293 cin>>l>>r; 294 tot=1; 295 son[0][0]=son[0][1]=-1; 296 REP(i,l,r+1){ 297 int x=0; 298 REP(j,0,30){ 299 int &p=son[x][(i>>j)&1]; 300 if(p==-1)p=tot++,cnt[p]=0,son[p][0]=son[p][1]=-1; 301 x=p;++cnt[x]; 302 } 303 } 304 int ans=0; 305 vector<int>res; 306 REP(i,l,r+1){ 307 int x=0,t=0; 308 REP(j,0,30){ 309 int o=!((i>>j)&1); 310 if(son[x][o]==-1||!cnt[son[x][o]])o=!o; 311 t|=o<<j; 312 x=son[x][o];--cnt[x]; 313 } 314 res.pb(t);ans+=i|t; 315 } 316 cout<<ans<<'\n'; 317 for(auto i:res)cout<<i<<' '; 318 cout<<'\n'; 319 } 320 void TC() { 321 int tc=1; 322 cin>>tc; 323 while(tc--){ 324 Main(); 325 } 326 } 327 signed main() { 328 return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0; 329 } 330 /* 331 1. CLEAR the arrays (ESPECIALLY multitests) 332 2. DELETE useless output 333 */ 334 ``` 335 336 [2146E - Yet Another MEX Problem](/contest/2146/problem/E "Codeforces Round 1052 (Div. 2)") 337 338 **Hint 1** 339 340 For an array $b$ and an integer $x$ that **does not appear in** $b$, let $g(b,x)$ be the number of elements in $b$ that is greater than $x$. Then the weight of $b$ equals to $g(b,\rm{mex}(b))$. However, when $x\neq \rm{mex}(b)$, what will happen to $g(b,x)$? 341 342 **Answer** 343 344 The value of $g(b,x)$ is always smaller than or equal to $g(b,\rm{mex}(b))$, because when $x$ **does not appear in** $b$, letting $x=\rm{mex}(b)$ is optimal to maximize $g(b,x)$. 345 346 **Hint 2** 347 348 For a fixed right endpoint $r$, let's enumerate over all the $x$ and maximize $g(a[l\dots r],x)$ while keeping $x$ no occurred in $a[l\dots r]$. It's clear that the value is maximized for $x$ if $l$ equals the last occurrence of $x$ plus $1$. 349 350 **Hint 3** 351 352 Use a segment tree to maintain the answer for each $x$. 353 354 **Tutorial** 355 356 Tutorial is loading... 357 358 **Implementation** 359 360 By [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225"). 361 362 ``` 363 #include<bits/stdc++.h> 364 using namespace std; 365 #define all(v) v.begin(),v.end() 366 #define pb push_back 367 #define REP(i,b,e) for(int i=(b);i<(int)(e);++i) 368 int n; 369 int a[300005]; 370 struct ds{ 371 int seg[1200005],tag[1200005]; 372 void build(int l,int r,int p){ 373 seg[p]=tag[p]=0; 374 if(l==r)return; 375 int m=(l+r)>>1; 376 build(l,m,p*2+1);build(m+1,r,p*2+2); 377 } 378 void update(int l,int r,int s,int t,int p){ 379 if(l<=s&&t<=r){ 380 ++seg[p];++tag[p]; 381 return; 382 } 383 int m=(s+t)>>1; 384 if(m>=l)update(l,r,s,m,p*2+1); 385 if(m<r)update(l,r,m+1,t,p*2+2); 386 seg[p]=max(seg[p*2+1],seg[p*2+2])+tag[p]; 387 } 388 void point(int pos,int l,int r,int p,int val=0){ 389 if(l==r)return seg[p]=-val,void(); 390 int m=(l+r)>>1; 391 val+=tag[p]; 392 if(m>=pos)point(pos,l,m,p*2+1,val); 393 else point(pos,m+1,r,p*2+2,val); 394 seg[p]=max(seg[p*2+1],seg[p*2+2])+tag[p]; 395 } 396 }seg; 397 void Main() { 398 cin>>n; 399 REP(i,0,n)cin>>a[i]; 400 seg.build(0,n,0); 401 REP(i,0,n){ 402 seg.update(0,a[i],0,n,0); 403 seg.point(a[i],0,n,0); 404 cout<<seg.seg[0]<<' '; 405 } 406 cout<<'\n'; 407 } 408 void TC() { 409 int tc=1; 410 cin>>tc; 411 while(tc--){ 412 Main(); 413 cout.flush(); 414 } 415 } 416 signed main() { 417 return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0; 418 } 419 /* 420 1. CLEAR the arrays (ESPECIALLY multitests) 421 2. DELETE useless output 422 */ 423 ``` 424 425 **Bonus** 426 427 There's a harder version of the problem. Can you solve it? 428 429 There're $q$ queries: $x,y$. Find $\max_{x\le l\le r\le y}w(l,r)$. $n,q\le 3\cdot 10^5$. 430 431 [2146F - Bubble Sort](/contest/2146/problem/F "Codeforces Round 1052 (Div. 2)") 432 433 **Hint 1** 434 435 Let's focus on bubble sort first. For an element $p_x$, how many rounds does it take to make all the numbers before the position small than $p_x$? 436 437 **Answer** 438 439 Count the number of integers $i$ such that $i \lt x$ and $p_i \gt p_x$. In one round of bubble sort, exactly one of that sort of element will be moved to the right of $p_x$. 440 441 **Hint 2** 442 443 Try to count something else instead of permutations $p$. Can you come up with an $O(n^2)$ dynamic programming method? 444 445 **Hint 3** 446 447 The number of restrictions is small ($m\le 1000$). Can we decrease the number of states from $O(n^2)$ to $O(nm)$ and $O(m^2)$? How to calculate the coefficients then? 448 449 **Tutorial** 450 451 Tutorial is loading... 452 453 **Implementation** 454 455 By [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225"). 456 457 ``` 458 #include<bits/stdc++.h> 459 using namespace std; 460 #define MOD 998244353 461 #define speMOD 2933256077ll 462 #define int long long 463 #define pii pair<int,int> 464 #define all(v) v.begin(),v.end() 465 #define pb push_back 466 #define REP(i,b,e) for(int i=(b);i<(int)(e);++i) 467 #define over(x) {cout<<(x)<<endl;return;} 468 #define lowbit(x) ((x)&(-(x))) 469 #define cntbit(x) __builtin_popcount(x) 470 #define rf(v) shuffle(all(v),sd); 471 #define deal(v) sort(all(v));v.erase(unique(v.begin(),v.end()),v.end()) 472 #define lbound(v,x) lower_bound(all(v),x)-v.begin() 473 int qpow(int a,int b,int m=MOD,int res=1){ 474 a%=m; 475 while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1; 476 return res; 477 } 478 int fac[2000005],inv[2000005]; 479 void init(int n){ 480 fac[0]=inv[0]=1; 481 REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD; 482 inv[n]=qpow(fac[n],MOD-2); 483 for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD; 484 } 485 int binom(int x,int y){ 486 return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD; 487 } 488 struct restr{ 489 int l,r,k; 490 }; 491 int n,m; 492 int r1[1000005],r2[1000005]; 493 int dp[10005],sum[10005]; 494 int qry1(int l,int r,int k){ 495 if(k<l)return qpow(k+1,r-l+1); 496 if(k>r)return fac[r+1]*inv[l]%MOD; 497 return fac[k+1]*inv[l]%MOD*qpow(k+1,r-k)%MOD; 498 } 499 int qry2(int l,int r,int k,int x){ 500 return (qry1(l,r,k)+MOD-qry1(l,r,x))%MOD; 501 } 502 void Main() { 503 cin>>n>>m; 504 vector<int>v;vector<restr>a; 505 vector<int>t; 506 REP(i,0,m){ 507 int k,l,r; 508 cin>>k>>l>>r; 509 --l; 510 if(l>=0)v.pb(l); 511 if(r<n)v.pb(r); 512 t.pb(k); 513 a.pb({l,r,k}); 514 } 515 v.pb(n-1);t.pb(-1);t.pb(n-1); 516 deal(v);deal(t); 517 for(auto i:v)r1[i]=t.size()-1,r2[i]=0; 518 for(auto i:a){ 519 if(i.k==n-1&&i.r<n-1)over(0) 520 if(i.l>=0)r1[i.l]=min(r1[i.l],lbound(t,i.k)); 521 if(i.r<n)r2[i.r]=max(r2[i.r],lbound(t,i.k)); 522 } 523 int lst=0,m=t.size();dp[1]=1;REP(i,2,m+1)dp[i]=0; 524 for(auto i:v){ 525 REP(j,1,m)sum[j]=dp[j]; 526 REP(j,2,m)(sum[j]+=sum[j-1])%=MOD; 527 REP(j,1,m)if(j>r2[i]&&j<=r1[i]){ 528 dp[j]=(dp[j]*qry1(lst,i,t[j])+sum[j-1]*qry2(lst,i,t[j],t[j-1]))%MOD; 529 }else dp[j]=0; 530 lst=i+1; 531 } 532 int res=0; 533 REP(j,1,m+1)(res+=dp[j])%=MOD; 534 cout<<res<<endl; 535 } 536 void TC() { 537 init(1000000); 538 int tc=1; 539 cin>>tc; 540 while(tc--){ 541 Main(); 542 cout.flush(); 543 } 544 } 545 signed main() { 546 return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0; 547 } 548 /* 549 1. CLEAR the arrays (ESPECIALLY multitests) 550 2. DELETE useless output 551 */ 552 ```