codeforces-scrape

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

1395.md (9538B)


      1 Source: https://codeforces.com/blog/entry/81355
      2 
      3 Thank you for participating, and I hope you enjoyed the problems!
      4 
      5 ### [1395A - Boboniu Likes to Color Balls](/contest/1395/problem/A "Codeforces Round 664 (Div. 2)")
      6 
      7 Idea: [dqa2021](/profile/dqa2021 "Master dqa2021")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 def check(r,g,b,w):
     17     return False if r%2 + g%2 + b%2 + w%2 > 1 else True
     18 
     19 if __name__ == '__main__':
     20     T = int(input())
     21     for ttt in range(T):
     22         r,g,b,w = map(int,input().split())
     23         if check(r,g,b,w):
     24             print("Yes")
     25         elif r>0 and g>0 and b>0 and check(r-1,g-1,b-1,w+1):
     26             print("Yes")
     27         else :
     28             print("No")
     29 ```
     30 
     31 ### [1395B - Boboniu Plays Chess](/contest/1395/problem/B "Codeforces Round 664 (Div. 2)")
     32 
     33 Idea: [Xiejiadong](/profile/Xiejiadong "International Master Xiejiadong")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution**
     40 
     41 ```
     42 #include<bits/stdc++.h>
     43 using namespace std;
     44 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
     45 #define ROF(i,a,b) for(int i=(a);i>=(b);--i)
     46 
     47 int n,m,sx,sy;
     48 
     49 void f(int i,int j){
     50     printf("%d %d\n",(i+sx-2)%n+1,(j+sy-2)%m+1);
     51 }
     52 int main(){
     53     scanf("%d%d%d%d",&n,&m,&sx,&sy);
     54     FOR(i,1,n){
     55         if(i&1)FOR(j,1,m)f(i,j);
     56         else ROF(j,m,1)f(i,j);
     57     }
     58     return 0;
     59 }	
     60 ```
     61 
     62 ### [1395C - Boboniu and Bit Operations](/contest/1395/problem/C "Codeforces Round 664 (Div. 2)")
     63 
     64 Idea: [Retired_xryjr233](/profile/Retired_xryjr233 "Master Retired_xryjr233")
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution**
     71 
     72 ```
     73 #include<bits/stdc++.h>
     74 #define ci const int&
     75 using namespace std;
     76 int n,m,p[210],d[210],ans;
     77 bool Check(ci x){
     78 	for(int i=1;i<=n;++i){
     79 		for(int j=1;j<=m;++j)if(((p[i]&d[j])|x)==x)goto Next;
     80 		return 0;
     81 		Next:;
     82 	}
     83 	return 1;
     84 }
     85 int main(){
     86 	scanf("%d%d",&n,&m);
     87 	for(int i=1;i<=n;++i)scanf("%d",&p[i]);
     88 	for(int i=1;i<=m;++i)scanf("%d",&d[i]);
     89 	ans=(1<<9)-1;
     90 	for(int i=8;i>=0;--i)Check(ans^(1<<i))?ans^=(1<<i):0;
     91 	printf("%d",ans);
     92 	return 0;
     93 }
     94 ```
     95 
     96 ### [1394A - Boboniu Chats with Du](/contest/1394/problem/A "Codeforces Round 664 (Div. 1)")
     97 
     98 Idea: [sshwyR](/profile/sshwyR "International Master sshwyR")
     99 
    100 **Tutorial**
    101 
    102 Tutorial is loading...
    103 
    104 **Solution**
    105 
    106 ```
    107 #include <bits/stdc++.h>
    108 #define rep(i, a, b) for (int i = (a); i <= int(b); i++)
    109 using namespace std;
    110 
    111 typedef long long ll;
    112 const int maxn = 1e5;
    113 int n, d, m, k, l;
    114 ll a[maxn + 5], b[maxn + 5];
    115 
    116 void solve(ll a[], int n) {
    117 	sort(a + 1, a + n + 1);
    118 	reverse(a + 1, a + n + 1);
    119 	rep(i, 1, n) a[i] += a[i - 1];
    120 }
    121 
    122 int main() {
    123 	scanf("%d %d %d", &n, &d, &m);
    124 	for (int i = 0, x; i < n; i++) {
    125 		scanf("%d", &x);
    126 		if (x > m) a[++k] = x;
    127 		else b[++l] = x;
    128 	}
    129 	if (k == 0) {
    130 		ll s = 0;
    131 		rep(i, 1, n) s += b[i];
    132 		printf("%lld\n", s);
    133 		exit(0);
    134 	}
    135 	solve(a, k);
    136 	solve(b, l);
    137 	fill(b + l + 1, b + n + 1, b[l]);
    138 	ll res = 0;
    139 	rep(i, (k + d) / (1 + d), k) if (1ll * (i - 1) * (d + 1) + 1 <= n) {
    140 		res = max(res, a[i] + b[n - 1ll * (i - 1) * (d + 1) - 1]);
    141 	}
    142 	printf("%lld\n", res);
    143 	return 0;
    144 }	
    145 ```
    146 
    147 ### [1394B - Boboniu Walks on Graph](/contest/1394/problem/B "Codeforces Round 664 (Div. 1)")
    148 
    149 Idea: [sshwyR](/profile/sshwyR "International Master sshwyR")
    150 
    151 **Tutorial**
    152 
    153 Tutorial is loading...
    154 
    155 **Solution**
    156 
    157 ```
    158 //by Sshwy
    159 #include<bits/stdc++.h>
    160 using namespace std;
    161 #define pb push_back
    162 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
    163 #define ROF(i,a,b) for(int i=(a);i>=(b);--i)
    164 
    165 mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
    166 const int N=2e5+5,HS=3,K=10;
    167 int n,m,k;
    168 vector< pair<int,int> > g[N];
    169 
    170 int mod[HS];
    171 
    172 struct hash_number{
    173     int a[HS];
    174     hash_number(){ fill(a,a+HS,0); }
    175     hash_number(long long x){
    176         FOR(i,0,HS-1)a[i]=(x%mod[i]+mod[i])%mod[i];
    177     }
    178     hash_number operator+(hash_number x){
    179         hash_number res;
    180         res.a[0]=(a[0]+x.a[0])%mod[0];
    181         res.a[1]=(a[1]*1ll*x.a[1])%mod[1];
    182         res.a[2]=(a[2]+x.a[2])%mod[2];
    183         return res;
    184     }
    185     bool operator==(const hash_number& x)const {
    186         FOR(i,0,HS-1)if(a[i]!=x.a[i])return 0;
    187         return 1;
    188     }
    189 }val[N],c[K][K],s;
    190 int ans;
    191 int status[K];
    192 void dfs(int x,hash_number hsh){
    193     if(x==k){
    194         if(hsh == s) ++ans;
    195         return;
    196     }
    197     FOR(i,1,x+1){
    198         status[x+1]=i;
    199         dfs(x+1,hsh+c[x+1][i]);
    200     }
    201 }
    202 int main(){
    203     mod[0]=998244353;
    204     mod[1]=1e9+7;
    205     mod[2]=std::uniform_int_distribution<int>(1e8,1e9)(mt_rand);
    206 
    207     fprintf(stderr,"%d %d %d\n",mod[0],mod[1],mod[2]);
    208 
    209     scanf("%d%d%d",&n,&m,&k);
    210     FOR(i,1,m){
    211         int u,v,w;
    212         scanf("%d%d%d",&u,&v,&w);
    213         g[u].pb({w,v});
    214     }
    215     std::uniform_int_distribution<long long> rg(1,1e18);
    216     FOR(i,1,n)val[i]=hash_number(rg(mt_rand));
    217     FOR(i,1,n)s=s+val[i];
    218     FOR(u,1,n){
    219         int d=g[u].size();
    220         sort(g[u].begin(),g[u].end());
    221         for(int i=1;i<=g[u].size();++i){
    222             int v=g[u][i-1].second;
    223             c[d][i]=c[d][i]+val[v];
    224         }
    225     }
    226     dfs(0,hash_number());
    227     printf("%d\n",ans);
    228     return 0;
    229 }
    230 ```
    231 
    232 ### [1394C - Boboniu and String](/contest/1394/problem/C "Codeforces Round 664 (Div. 1)")
    233 
    234 Idea: [sshwyR](/profile/sshwyR "International Master sshwyR")
    235 
    236 **Tutorial**
    237 
    238 Tutorial is loading...
    239 
    240 **Solution**
    241 
    242 ```
    243 //by Sshwy
    244 #include<bits/stdc++.h>
    245 using namespace std;
    246 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
    247 #define ROF(i,a,b) for(int i=(a);i>=(b);--i)
    248 const int INF=1e9;
    249 
    250 int n;
    251 
    252 int main(){
    253     cin>>n;
    254     int lx=INF,rx=-INF,ly=INF,ry=-INF,lz=INF,rz=-INF;
    255     FOR(i,1,n){
    256         string s;
    257         cin>>s;
    258         int x=0,y=0;
    259         for(char c:s){
    260             if(c=='B')++x;
    261             else ++y;
    262         }
    263         //printf("%d %d\n",x,y);
    264         lx=min(lx,x), rx=max(rx,x);
    265         ly=min(ly,y), ry=max(ry,y);
    266         lz=min(lz,x-y), rz=max(rz,x-y);
    267     }
    268 
    269     int ans=INF,ax=0,ay=0,az=0;
    270     auto calc = [&](){
    271         int l=0,r=lz-(lx-ry),mid;
    272         auto check = [&](int a){
    273             return lx+a+a>=rx && lx-ry+a+a+a>=rz && ry-a-a<=ly;
    274         };
    275         if(check(r)==0)return INF;
    276         while(l<r)mid=(l+r)>>1, check(mid)?r=mid:l=mid+1;
    277         return l;
    278     };
    279     FOR(_,1,6){
    280         assert(lx<=rx && ly<=ry && lz<=rz);
    281         int v=calc();
    282         if(v<ans){
    283             ans=v;
    284             ax=lx+v, ay=ry-v, az=ax-ay;
    285         }
    286         int Lx=ly,Rx=ry,Ly=-rz,Ry=-lz,Lz=lx,Rz=rx;
    287         lx=Lx, rx=Rx, ly=Ly, ry=Ry, lz=Lz, rz=Rz;
    288         int Ax=ay,Ay=-az,Az=ax;
    289         ax=Ax,ay=Ay,az=Az;
    290     }
    291     cout<<ans<<endl;
    292     FOR(i,1,ax)cout<<'B';
    293     FOR(i,1,ay)cout<<'N';
    294     cout<<endl;
    295     return 0;
    296 }
    297 ```
    298 
    299 ### [1394D - Boboniu and Jianghu](/contest/1394/problem/D "Codeforces Round 664 (Div. 1)")
    300 
    301 Idea: [Z18](/profile/Z18 "Grandmaster Z18")
    302 
    303 **Tutorial**
    304 
    305 Tutorial is loading...
    306 
    307 **Solution**
    308 
    309 ```
    310 #include <bits/stdc++.h>
    311 using namespace std;
    312 
    313 typedef long long ll;
    314 const int maxn = 2e5;
    315 int n, h[maxn + 3], t[maxn + 3], in[maxn + 3], out[maxn + 3];
    316 vector<int> G[maxn + 3];
    317 bool vis[maxn + 3];
    318 ll ans, f[maxn + 3], g[maxn + 3], a[maxn + 3];
    319 
    320 void dfs(int u, int fa = 0) {
    321 	vis[u] = true;
    322 	for (int i = 0, v; i < G[u].size(); i++) {
    323 		if ((v = G[u][i]) == fa) continue;
    324 		dfs(v, u);
    325 	}
    326 	int s = 0;
    327 	ll cur = 0;
    328 	for (int i = 0, v; i < G[u].size(); i++) {
    329 		if ((v = G[u][i]) == fa) continue;
    330 		cur += g[v], a[++s] = f[v] - g[v];
    331 	}
    332 	sort(a + 1, a + s + 1);
    333 	reverse(a + 1, a + s + 1);
    334 	for (int i = 0; i <= s; i++) {
    335 		cur += a[i];
    336 		if (fa) {
    337 			f[u] = max(f[u], 1ll * min(in[u] + 1 + s - i, out[u] + i) * t[u] + cur);
    338 			g[u] = max(g[u], 1ll * min(in[u] + s - i, out[u] + 1 + i) * t[u] + cur);
    339 		} else {
    340 			f[u] = max(f[u], 1ll * min(in[u] + s - i, out[u] + i) * t[u] + cur);
    341 		}
    342 	}
    343 }
    344 
    345 int main() {
    346 	scanf("%d", &n);
    347 	for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
    348 	for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    349 	for (int i = 1, u, v; i < n; i++) {
    350 		scanf("%d %d", &u, &v);
    351 		ans += t[u] + t[v];
    352 		if (h[u] == h[v]) {
    353 			G[u].push_back(v), G[v].push_back(u);
    354 		} else {
    355 			if (h[u] > h[v]) swap(u, v);
    356 			in[u]++, out[v]++;
    357 		}
    358 	}
    359 	for (int i = 1; i <= n; i++) if (!vis[i]) {
    360 		dfs(i), ans -= f[i];
    361 	}
    362 	printf("%lld\n", ans);
    363 	return 0;
    364 }
    365 ```
    366 
    367 ### [1394E - Boboniu and Banknote Collection](/contest/1394/problem/E "Codeforces Round 664 (Div. 1)")
    368 
    369 Idea: [sshwyR](/profile/sshwyR "International Master sshwyR")
    370 
    371 **Tutorial**
    372 
    373 Tutorial is loading...
    374 
    375 **Solution**
    376 
    377 ```
    378 //by Sshwy
    379 #include<bits/stdc++.h>
    380 using namespace std;
    381 #define pb push_back
    382 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
    383 #define ROF(i,a,b) for(int i=(a);i>=(b);--i)
    384 
    385 const int N=1e5+5;
    386 int n,a[N],xyx,q[N],c[N],p[N];
    387 vector<int> v[N];
    388 
    389 int pos;
    390 
    391 void get_v(int pos){
    392     v[pos].clear();
    393     if(pos==1)return;
    394     if(a[pos]==a[pos-1])v[pos].pb(2);
    395     for(auto x:v[pos-1])if(a[pos]==a[pos-x-1])v[pos].pb(x+2);
    396 }
    397 bool check_even_pal(int L,int R){
    398     assert(R<=pos);
    399     for(auto x:v[R])if(x==R-L+1)return 1;
    400     return 0;
    401 }
    402 
    403 int qry(){
    404     int res=xyx+c[pos];
    405     int cur=pos;
    406     while(p[cur] && q[pos]<=cur-p[cur]/2){
    407         cur-=p[cur]/2;
    408         ++res;
    409     }
    410     return res;
    411 }
    412 
    413 int main(){
    414     scanf("%d",&n);
    415     q[0]=1;
    416     FOR(i,1,n){
    417         ++pos;
    418         scanf("%d",&a[pos]);
    419         get_v(pos);
    420         int x;
    421         if(v[pos].size() && (x=v[pos][0], check_even_pal(pos-x/2-x+1,pos-x/2))){
    422             pos-=x;
    423             xyx+=2;
    424         }else {
    425             p[pos]=v[pos].size()? v[pos][0]:0;
    426             q[pos]=q[pos-1],c[pos]=c[pos-1];
    427             if(check_even_pal(q[pos],pos)){
    428                 q[pos]+=(pos-q[pos]+1)/2;
    429                 c[pos]++;
    430             }
    431         }
    432         printf("%d%c",qry()," \n"[i==n]);
    433     }
    434     return 0;
    435 }
    436 ```