1806.md (5746B)
1 Source: https://codeforces.com/blog/entry/114048 2 3 We are really sorry that C is tough and E is easier than D. But anyway hope you can enjoy the problems themselves and learn something from them. 4 5 [1806A - Walking Master](/contest/1806/problem/A "Codeforces Round 858 (Div. 2)") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include<bits/stdc++.h> 15 #define ll long long 16 #define fir first 17 #define sec second 18 #define pii pair<int,int> 19 using namespace std; 20 21 const int maxn=500005; 22 const int inf=0x3f3f3f3f; 23 24 signed main() { 25 ios::sync_with_stdio(false); 26 cin.tie(0),cout.tie(0); 27 int T; 28 cin>>T; 29 while(T--) { 30 int a,b,c,d; 31 cin>>a>>b>>c>>d; 32 if(b<=d&&c<=a+d-b) { 33 cout<<(d-b)+(a+d-b-c)<<"\n"; 34 } else { 35 cout<<"-1\n"; 36 } 37 } 38 } 39 ``` 40 41 [1806B - Mex Master](/contest/1806/problem/B "Codeforces Round 858 (Div. 2)") 42 43 **Solution** 44 45 Tutorial is loading... 46 47 **Code** 48 49 ``` 50 #include<bits/stdc++.h> 51 #define ll long long 52 #define fir first 53 #define sec second 54 #define pii pair<int,int> 55 using namespace std; 56 57 const int maxn=200005; 58 const int inf=0x3f3f3f3f; 59 60 signed main() { 61 ios::sync_with_stdio(false); 62 cin.tie(0),cout.tie(0); 63 int T; 64 cin>>T; 65 while(T--) { 66 int n; 67 cin>>n; 68 int sum0=0; 69 bool f=false; 70 for(int i=1;i<=n;i++) { 71 int x; 72 cin>>x; 73 if(x==0) { 74 sum0++; 75 } else if(x>=2) { 76 f=true; 77 } 78 } 79 if(sum0<=(n+1)/2) { 80 cout<<"0\n"; 81 } else if(f||sum0==n) { 82 cout<<"1\n"; 83 } else { 84 cout<<"2\n"; 85 } 86 } 87 } 88 ``` 89 90 [1806C - Sequence Master](/contest/1806/problem/C "Codeforces Round 858 (Div. 2)") 91 92 **Solution** 93 94 Tutorial is loading... 95 96 **Code** 97 98 ``` 99 #include<bits/stdc++.h> 100 #define ll long long 101 #define fir first 102 #define sec second 103 #define pii pair<int,int> 104 using namespace std; 105 106 const int maxn=400005; 107 const ll inf=0x3f3f3f3f3f3f3f3f; 108 109 ll a[maxn]; 110 111 signed main() { 112 ios::sync_with_stdio(false); 113 cin.tie(0),cout.tie(0); 114 int T; 115 cin>>T; 116 while(T--) { 117 int n; 118 cin>>n; 119 ll ans=0,sum=0; 120 for(int i=1;i<=n*2;i++) { 121 cin>>a[i]; 122 ans+=abs(a[i]); 123 sum+=abs(a[i]-(-1)); 124 } 125 if(n==1) { 126 ans=min(ans,abs(a[1]-a[2])); 127 } 128 if(n==2) { 129 ans=min(ans,abs(a[1]-2)+abs(a[2]-2)+abs(a[3]-2)+abs(a[4]-2)); 130 } 131 if(n%2==0) { 132 for(int i=1;i<=n*2;i++) { 133 ans=min(ans,sum-abs(a[i]-(-1))+abs(a[i]-n)); 134 } 135 } 136 cout<<ans<<"\n"; 137 } 138 } 139 ``` 140 141 [1806D - DSU Master](/contest/1806/problem/D "Codeforces Round 858 (Div. 2)") 142 143 **Solution** 144 145 Tutorial is loading... 146 147 **Code** 148 149 ``` 150 #include<bits/stdc++.h> 151 #define ll long long 152 #define fir first 153 #define sec second 154 #define pii pair<int,int> 155 using namespace std; 156 157 const int maxn=500005; 158 const int inf=0x3f3f3f3f; 159 const int mod=998244353; 160 161 int a[maxn]; 162 int f[maxn]; 163 164 signed main() { 165 ios::sync_with_stdio(false); 166 cin.tie(0),cout.tie(0); 167 int T; 168 cin>>T; 169 while(T--) { 170 int n; 171 cin>>n; 172 for(int i=1;i<=n-1;i++) { 173 cin>>a[i]; 174 } 175 f[1]=1; 176 for(int i=1;i<=n-1;i++) { 177 f[i+1]=1ll*f[i]*(i-a[i])%mod; 178 } 179 int ans=0; 180 for(int i=1;i<=n-1;i++) { 181 ans=(1ll*ans*i+(!a[i])*f[i])%mod; 182 cout<<ans<<" "; 183 } 184 cout<<"\n"; 185 } 186 } 187 ``` 188 189 [1806E - Tree Master](/contest/1806/problem/E "Codeforces Round 858 (Div. 2)") 190 191 **Solution** 192 193 Tutorial is loading... 194 195 **Code** 196 197 ``` 198 #include<bits/stdc++.h> 199 #define ll long long 200 #define fir first 201 #define sec second 202 #define pii pair<int,int> 203 using namespace std; 204 205 const int maxn=100005; 206 const int sqrtn=325; 207 const int B=320; 208 const int inf=0x3f3f3f3f; 209 210 int n,q; 211 int a[maxn]; 212 int h[maxn]; 213 int fa[maxn]; 214 int cnt[maxn]; 215 int depth[maxn]; 216 ll f[maxn][sqrtn]; 217 vector<int> tree[maxn]; 218 219 void dfs(int x,int d) { 220 h[x]=++cnt[d],depth[x]=d; 221 for(int to:tree[x]) { 222 dfs(to,d+1); 223 } 224 } 225 226 ll ask(int x,int y) { 227 if(!x&&!y) { 228 return 0; 229 } 230 if(cnt[depth[y]]<=B&&f[x][h[y]]) { 231 return f[x][h[y]]; 232 } 233 ll ans=ask(fa[x],fa[y])+1ll*a[x]*a[y]; 234 if(cnt[depth[y]]<=B) { 235 f[x][h[y]]=ans; 236 } 237 return ans; 238 } 239 240 signed main() { 241 ios::sync_with_stdio(false); 242 cin.tie(0),cout.tie(0); 243 cin>>n>>q; 244 for(int i=1;i<=n;i++) { 245 cin>>a[i]; 246 } 247 for(int i=2;i<=n;i++) { 248 cin>>fa[i]; 249 tree[fa[i]].push_back(i); 250 } 251 dfs(1,0); 252 while(q--) { 253 int x,y; 254 cin>>x>>y; 255 cout<<ask(x,y)<<"\n"; 256 } 257 } 258 ``` 259 260 [1806F2 - GCD Master (hard version)](/contest/1806/problem/F2 "Codeforces Round 858 (Div. 2)") 261 262 **Solution** 263 264 Tutorial is loading... 265 266 **Code** 267 268 ``` 269 #include<bits/stdc++.h> 270 #define ll long long 271 #define int128 __int128 272 #define fir first 273 #define sec second 274 #define pii pair<int,int> 275 using namespace std; 276 277 const int maxn=1000005; 278 const ll inf=9e18; 279 const int128 inf128=(int128)(inf)*(int128)(inf); 280 281 ll a[maxn]; 282 ll b[maxn]; 283 ll g[maxn]; 284 ll ra[maxn]; 285 int128 suma[maxn]; 286 int128 sumb[maxn]; 287 int128 ans[maxn]; 288 289 ll gcd(ll x,ll y) { 290 return !y?x:gcd(y,x%y); 291 } 292 293 void print(int128 x) { 294 if(!x) { 295 return ; 296 } 297 print(x/10); 298 cout<<(int)(x%10); 299 } 300 301 signed main() { 302 ios::sync_with_stdio(false); 303 cin.tie(0),cout.tie(0); 304 int T; 305 cin>>T; 306 while(T--) { 307 int n,k; 308 ll m; 309 cin>>n>>m>>k; 310 for(int i=1;i<=n;i++) { 311 cin>>a[i]; 312 } 313 sort(a+1,a+n+1); 314 int t=0,r=0; 315 for(int i=1;i<=n;i++) { 316 if(i>1&&a[i]==a[i-1]) { 317 b[++r]=a[i]; 318 } else { 319 ra[++t]=a[i]; 320 } 321 } 322 n=t; 323 for(int i=1;i<=n;i++) { 324 a[i]=ra[i]; 325 g[i]=gcd(g[i-1],a[i]); 326 suma[i]=suma[i-1]+a[i]; 327 } 328 for(int i=0;i<=k;i++) { 329 ans[i]=-inf128; 330 } 331 for(int l=1;l<=n;) { 332 int r=l; 333 while(r<=n&&g[r]==g[l]) { 334 r++; 335 } 336 r--; 337 ll Max=-inf; 338 for(int i=r+1;i<=n;i++) { 339 a[i]=gcd(a[i],g[l]); 340 Max=max(Max,a[i]-ra[i]); 341 } 342 for(int i=r;i>=l;i--) { 343 ans[i]=suma[n]-suma[i]+Max; 344 a[i]=gcd(a[i],g[l]); 345 Max=max(Max,a[i]-ra[i]); 346 } 347 l=r+1; 348 } 349 for(int i=1;i<=r;i++) { 350 sumb[i]=sumb[i-1]+b[i]; 351 } 352 int128 final=-inf128; 353 if(k<=r) { 354 final=suma[n]+sumb[r]-sumb[k]; 355 } 356 for(int i=0;i<=r&&i<=k;i++) { 357 final=max(final,sumb[r]-sumb[i]+ans[k-i]); 358 } 359 print(final); 360 cout<<"\n"; 361 } 362 } 363 ```