codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```