2119.md (7722B)
1 Source: https://codeforces.com/blog/entry/144494 2 3 Sorry for misjudging the difficulty of problem D, but we still hope you enjoyed the problems! 4 5 [2119A - Add or XOR](/contest/2119/problem/A "Codeforces Round 1035 (Div. 2)") 6 7 Author: [CutieSmileHaruka](/profile/CutieSmileHaruka "Grandmaster CutieSmileHaruka") 8 9 **Hint 1** 10 11 $a \oplus 1$ is equivalent to $a - 1$ when $a$ is an odd number, otherwise it is equivalent to $a + 1$. 12 13 **Hint 2** 14 15 If you apply $a \gets a \oplus 1$ when $a$ is odd, then that operation should make $a = b$. 16 17 **Tutorial** 18 19 Tutorial is loading... 20 21 **Implementation** 22 23 ``` 24 #include <algorithm> 25 #include <cstring> 26 #include <cstdio> 27 #include <vector> 28 #include <queue> 29 using namespace std; 30 int t, a, b, x, y; 31 int main(){scanf("%d", &t); 32 while (t --){scanf("%d%d%d%d", &a, &b, &x, &y); 33 if (a > b) printf("%d\n", (a ^ 1) == b ? y : -1); 34 else {int c0 = b - a, c1 = (b + 1 >> 1) - (a + 1 >> 1); 35 printf("%lld\n", y > x ? 1ll * c0 * x : 1ll * (c0 - c1) * x + 1ll * c1 * y);} 36 } 37 } 38 ``` 39 40 [2119B - Line Segments](/contest/2119/problem/B "Codeforces Round 1035 (Div. 2)") 41 42 Author: [Lyz09](/profile/Lyz09 "Candidate Master Lyz09") 43 44 **Hint 1** 45 46 Transform $(p_x,p_y)$ to $(q_x,q_y)$ into an operation where $a_i$ is the distance between the two points. 47 48 **Hint 2** 49 50 When $n+1=3$, there is a solution if and only if the largest $a_i$ is less than or equal to the sum of the remaining $a_i$. 51 52 **Tutorial** 53 54 Tutorial is loading... 55 56 **Implementation 1** 57 58 ``` 59 #include<iostream> 60 #include<algorithm> 61 #include<cmath> 62 using namespace std; 63 #define N 100010 64 #define int long long 65 int t,n,sx,sy,tx,ty; 66 double a[N]; 67 signed main() 68 { 69 cin>>t; 70 while(t--) 71 { 72 cin>>n; 73 cin>>sx>>sy>>tx>>ty; 74 for(int i=1;i<=n;i++) 75 cin>>a[i]; 76 a[++n]=sqrt((sx-tx)*(sx-tx)+(sy-ty)*(sy-ty)); 77 sort(a+1,a+n+1); 78 double sum=a[n]; 79 for(int i=1;i<n;i++) 80 sum-=a[i]; 81 if(sum<=0) 82 puts("Yes"); 83 else 84 puts("No"); 85 } 86 } 87 ``` 88 89 **Implementation 2** 90 91 ``` 92 #include<iostream> 93 #include<algorithm> 94 using namespace std; 95 #define N 100010 96 #define int long long 97 int t,n,sx,sy,tx,ty,a[N]; 98 signed main() 99 { 100 cin>>t; 101 while(t--) 102 { 103 cin>>n; 104 cin>>sx>>sy>>tx>>ty; 105 for(int i=1;i<=n;i++) 106 cin>>a[i]; 107 sort(a+1,a+n+1); 108 int p=(sx-tx)*(sx-tx)+(sy-ty)*(sy-ty); 109 if(p>a[n]*a[n]) 110 { 111 int sum=0; 112 for(int i=1;i<=n;i++) 113 { 114 sum+=a[i]; 115 if(sum*sum>=p) 116 break; 117 } 118 if(sum*sum>=p) 119 puts("Yes"); 120 else 121 puts("No"); 122 } 123 else 124 { 125 int sum=a[n]; 126 for(int i=1;i<=n-1;i++) 127 sum-=a[i]; 128 if(sum<=0||sum*sum<=p) 129 puts("Yes"); 130 else 131 puts("No"); 132 } 133 } 134 } 135 ``` 136 137 [2119C - A Good Problem](/contest/2119/problem/C "Codeforces Round 1035 (Div. 2)") 138 139 Author: [lizhous](/profile/lizhous "Expert lizhous") Preparation: [Lyz09](/profile/Lyz09 "Candidate Master Lyz09") 140 141 **Hint 1** 142 143 For odd $n$, setting $a_i = l$ for all $i$ suffices. 144 145 **Hint 2** 146 147 For even $n$, there does not exist a valid array $a$ that satisfies $a_1=a_2=\dots=a_{n-1}=l$. 148 149 **Hint 3** 150 151 For even $n$, try to make $a_1=a_2=\dots=a_{n-2}=l$. 152 153 **Tutorial** 154 155 Tutorial is loading... 156 157 **Implementation** 158 159 ``` 160 #include<iostream> 161 using namespace std; 162 #define int long long 163 int t,n,l,r,k; 164 signed main() 165 { 166 cin>>t; 167 while(t--) 168 { 169 cin>>n>>l>>r>>k; 170 if(n%2==1) 171 { 172 cout<<l<<endl; 173 continue; 174 } 175 if(n==2) 176 { 177 cout<<-1<<endl; 178 continue; 179 } 180 int res=1; 181 bool fl=0; 182 while(res<=r) 183 { 184 if(res>l) 185 { 186 fl=1; 187 if(k<=n-2) 188 cout<<l<<endl; 189 else 190 cout<<res<<endl; 191 break; 192 } 193 res*=2; 194 } 195 if(!fl) 196 cout<<-1<<endl; 197 } 198 } 199 ``` 200 201 [2119D - Token Removing](/contest/2119/problem/D "Codeforces Round 1035 (Div. 2)") 202 203 Author: [CutieSmileHaruka](/profile/CutieSmileHaruka "Grandmaster CutieSmileHaruka") 204 205 **Hint 1** 206 207 Calculating the weight of a single valid sequence is difficult. Try another way? 208 209 **Tutorial** 210 211 Tutorial is loading... 212 213 **Implementation** 214 215 ``` 216 #include <algorithm> 217 #include <cstring> 218 #include <cstdio> 219 #include <vector> 220 #include <queue> 221 using namespace std; 222 const int N = 5005; 223 int t, n, mod, f[N][N], ans; 224 inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;} 225 int main(){scanf("%d", &t); 226 while (t --){scanf("%d%d", &n, &mod), f[0][0] = 1, ans = 0; 227 for (int i = 1;i <= n;i ++) for (int j = 0;j <= i;j ++) f[i][j] = 0; 228 for (int i = 1;i <= n;i ++) 229 for (int j = 0, now;j < i;j ++) 230 if (now = f[i - 1][j]) add(f[i][j + 1], now), 231 f[i][j] = (f[i][j] + (n - i + 1ll) * (j + 1) * now) % mod; 232 for (int j = 0;j <= n;j ++) add(ans, f[n][j]);printf("%d\n", ans); 233 } 234 } 235 ``` 236 237 [2119E - And Constraint](/contest/2119/problem/E "Codeforces Round 1035 (Div. 2)") 238 239 Author: [ma2021tyoi0037](/profile/ma2021tyoi0037 "Expert ma2021tyoi0037") 240 241 **Hint 1** 242 243 As same as the title, can you find a simple necessary constraint? 244 245 **Hint 2** 246 247 Consider $a_i = 0$ first. 248 249 **Tutorial** 250 251 Tutorial is loading... 252 253 **Implementation** 254 255 ``` 256 #include <bits/stdc++.h> 257 using namespace std; 258 259 typedef long long ll; 260 struct stu{ 261 int x; 262 ll dp; 263 }; 264 int n,a[100007],b[100007]; 265 vector<stu> f,g; 266 const ll inf=0x3f3f3f3f3f3f3f3f; 267 void Subt(){ 268 cin>>n; 269 for(int i=1;i<n;i++) cin>>a[i]; 270 for(int i=1;i<=n;i++) cin>>b[i]; 271 a[n]=0; 272 f.clear(); 273 f.push_back((stu){0,0}); 274 for(int i=1;i<=n;i++){ 275 int x=0; 276 g.clear(); 277 for(int j=30;j>=-1;j--){ 278 int y=x|a[i-1]|a[i]; 279 if(j!=-1) y|=(1<<j); 280 if(y>=b[i]){ 281 ll mn=inf; 282 for(stu l:f){ 283 if((l.x&y)!=a[i-1]) continue; 284 mn=min(mn,l.dp+y-b[i]); 285 } 286 if(mn<inf) g.push_back((stu){y,mn}); 287 } 288 x|=((1<<j)&b[i]); 289 } 290 swap(f,g); 291 } 292 ll mn=inf; 293 for(stu l:f) mn=min(mn,l.dp); 294 if(mn<inf) cout<<mn<<endl; 295 else cout<<-1<<endl; 296 return; 297 } 298 signed main(){ 299 ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 300 int T=1; 301 cin>>T; 302 while(T--) Subt(); 303 } 304 ``` 305 306 [2119F - Volcanic Eruptions](/contest/2119/problem/F "Codeforces Round 1035 (Div. 2)") 307 308 Author: [lizhous](/profile/lizhous "Expert lizhous") 309 310 **Hint 1** 311 312 Try to determine the vertex where you were before the last move. 313 314 **Hint 2** 315 316 I just need to calculate the earliest time I can reach the end vertex. 317 318 **Hint 3** 319 320 What form of moving path from the starting vertex to the end vertex is considered optimal? 321 322 **Tutorial** 323 324 Tutorial is loading... 325 326 **Implementation** 327 328 ``` 329 #include<iostream> 330 #include<cstdio> 331 #include<algorithm> 332 #include<cstring> 333 #include<vector> 334 #include<set> 335 #include<queue> 336 #include<unordered_map> 337 #include<map> 338 #define int long long 339 using namespace std; 340 int n,st,dist[1000002],w[1000001],tim[1000001],ans; 341 vector <int> g[1000001]; 342 int f[1000001]; 343 queue<int> q; 344 void getdis(int u,int fa) 345 { 346 for(int v:g[u]) 347 { 348 if(v==fa) continue; 349 dist[v]=dist[u]+1; 350 getdis(v,u); 351 } 352 } 353 void dfs(int u,int fa,int k,bool inn,int hei,int TIM,int dis) 354 { 355 if(hei<0) 356 { 357 TIM=max(TIM,(-hei+1)/2*2+k*2+dis); 358 } 359 if(TIM<=dist[u]) 360 { 361 ans=max(ans,dist[u]); 362 } 363 else 364 { 365 return; 366 } 367 for(int v:g[u]) 368 { 369 if(v==fa) continue; 370 if(inn&&w[u]!=w[v]) 371 { 372 dfs(v,u,min(k,tim[v]),inn,hei+w[v],TIM+1,dis+1); 373 } 374 else 375 { 376 dfs(v,u,k,0,hei+w[v],TIM+1,dis+1); 377 } 378 } 379 } 380 int T; 381 signed main() 382 { 383 ios::sync_with_stdio(false); 384 cin>>T; 385 int cnt=0; 386 while(T--) 387 { 388 cnt++; 389 cin>>n>>st; 390 for(int i=1;i<=n;i++) 391 { 392 dist[i]=0; 393 tim[i]=1000000000; 394 g[i].clear(); 395 f[i]=-10000000000000000; 396 } 397 ans=0; 398 for(int i=1;i<=n;i++) 399 { 400 cin>>w[i]; 401 } 402 for(int i=1,u,v;i<n;i++) 403 { 404 cin>>u>>v; 405 g[u].push_back(v); 406 g[v].push_back(u); 407 } 408 getdis(1,-1); 409 for(int i=1;i<=n;i++) 410 { 411 for(int v:g[i]) 412 { 413 if(w[i]==1&&w[v]==1) 414 { 415 tim[i]=0; 416 q.push(i); 417 break; 418 } 419 } 420 } 421 while(!q.empty()) 422 { 423 int u=q.front(); 424 q.pop(); 425 for(int v:g[u]) 426 { 427 if(tim[v]==1000000000&&w[v]!=w[u]) 428 { 429 tim[v]=tim[u]+1; 430 q.push(v); 431 } 432 } 433 } 434 dfs(st,-1,tim[st],1,w[st],1,1); 435 cout<<ans+(dist[st]&1)-1<<'\n'; 436 } 437 } 438 ```