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