Thank you for participating, and I hope you enjoyed the problems!
1395A - Boboniu Likes to Color Balls
Idea: dqa2021
Tutorial
Tutorial is loading...
Solution
def check(r,g,b,w):
return False if r%2 + g%2 + b%2 + w%2 > 1 else True
if __name__ == '__main__':
T = int(input())
for ttt in range(T):
r,g,b,w = map(int,input().split())
if check(r,g,b,w):
print("Yes")
elif r>0 and g>0 and b>0 and check(r-1,g-1,b-1,w+1):
print("Yes")
else :
print("No")
1395B - Boboniu Plays Chess
Idea: Xiejiadong
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
int n,m,sx,sy;
void f(int i,int j){
printf("%d %d\n",(i+sx-2)%n+1,(j+sy-2)%m+1);
}
int main(){
scanf("%d%d%d%d",&n,&m,&sx,&sy);
FOR(i,1,n){
if(i&1)FOR(j,1,m)f(i,j);
else ROF(j,m,1)f(i,j);
}
return 0;
}
1395C - Boboniu and Bit Operations
Idea: Retired_xryjr233
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
#define ci const int&
using namespace std;
int n,m,p[210],d[210],ans;
bool Check(ci x){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)if(((p[i]&d[j])|x)==x)goto Next;
return 0;
Next:;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&p[i]);
for(int i=1;i<=m;++i)scanf("%d",&d[i]);
ans=(1<<9)-1;
for(int i=8;i>=0;--i)Check(ans^(1<<i))?ans^=(1<<i):0;
printf("%d",ans);
return 0;
}
1394A - Boboniu Chats with Du
Idea: sshwyR
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= int(b); i++)
using namespace std;
typedef long long ll;
const int maxn = 1e5;
int n, d, m, k, l;
ll a[maxn + 5], b[maxn + 5];
void solve(ll a[], int n) {
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
rep(i, 1, n) a[i] += a[i - 1];
}
int main() {
scanf("%d %d %d", &n, &d, &m);
for (int i = 0, x; i < n; i++) {
scanf("%d", &x);
if (x > m) a[++k] = x;
else b[++l] = x;
}
if (k == 0) {
ll s = 0;
rep(i, 1, n) s += b[i];
printf("%lld\n", s);
exit(0);
}
solve(a, k);
solve(b, l);
fill(b + l + 1, b + n + 1, b[l]);
ll res = 0;
rep(i, (k + d) / (1 + d), k) if (1ll * (i - 1) * (d + 1) + 1 <= n) {
res = max(res, a[i] + b[n - 1ll * (i - 1) * (d + 1) - 1]);
}
printf("%lld\n", res);
return 0;
}
1394B - Boboniu Walks on Graph
Idea: sshwyR
Tutorial
Tutorial is loading...
Solution
//by Sshwy
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5+5,HS=3,K=10;
int n,m,k;
vector< pair<int,int> > g[N];
int mod[HS];
struct hash_number{
int a[HS];
hash_number(){ fill(a,a+HS,0); }
hash_number(long long x){
FOR(i,0,HS-1)a[i]=(x%mod[i]+mod[i])%mod[i];
}
hash_number operator+(hash_number x){
hash_number res;
res.a[0]=(a[0]+x.a[0])%mod[0];
res.a[1]=(a[1]*1ll*x.a[1])%mod[1];
res.a[2]=(a[2]+x.a[2])%mod[2];
return res;
}
bool operator==(const hash_number& x)const {
FOR(i,0,HS-1)if(a[i]!=x.a[i])return 0;
return 1;
}
}val[N],c[K][K],s;
int ans;
int status[K];
void dfs(int x,hash_number hsh){
if(x==k){
if(hsh == s) ++ans;
return;
}
FOR(i,1,x+1){
status[x+1]=i;
dfs(x+1,hsh+c[x+1][i]);
}
}
int main(){
mod[0]=998244353;
mod[1]=1e9+7;
mod[2]=std::uniform_int_distribution<int>(1e8,1e9)(mt_rand);
fprintf(stderr,"%d %d %d\n",mod[0],mod[1],mod[2]);
scanf("%d%d%d",&n,&m,&k);
FOR(i,1,m){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].pb({w,v});
}
std::uniform_int_distribution<long long> rg(1,1e18);
FOR(i,1,n)val[i]=hash_number(rg(mt_rand));
FOR(i,1,n)s=s+val[i];
FOR(u,1,n){
int d=g[u].size();
sort(g[u].begin(),g[u].end());
for(int i=1;i<=g[u].size();++i){
int v=g[u][i-1].second;
c[d][i]=c[d][i]+val[v];
}
}
dfs(0,hash_number());
printf("%d\n",ans);
return 0;
}
1394C - Boboniu and String
Idea: sshwyR
Tutorial
Tutorial is loading...
Solution
//by Sshwy
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
const int INF=1e9;
int n;
int main(){
cin>>n;
int lx=INF,rx=-INF,ly=INF,ry=-INF,lz=INF,rz=-INF;
FOR(i,1,n){
string s;
cin>>s;
int x=0,y=0;
for(char c:s){
if(c=='B')++x;
else ++y;
}
//printf("%d %d\n",x,y);
lx=min(lx,x), rx=max(rx,x);
ly=min(ly,y), ry=max(ry,y);
lz=min(lz,x-y), rz=max(rz,x-y);
}
int ans=INF,ax=0,ay=0,az=0;
auto calc = [&](){
int l=0,r=lz-(lx-ry),mid;
auto check = [&](int a){
return lx+a+a>=rx && lx-ry+a+a+a>=rz && ry-a-a<=ly;
};
if(check(r)==0)return INF;
while(l<r)mid=(l+r)>>1, check(mid)?r=mid:l=mid+1;
return l;
};
FOR(_,1,6){
assert(lx<=rx && ly<=ry && lz<=rz);
int v=calc();
if(v<ans){
ans=v;
ax=lx+v, ay=ry-v, az=ax-ay;
}
int Lx=ly,Rx=ry,Ly=-rz,Ry=-lz,Lz=lx,Rz=rx;
lx=Lx, rx=Rx, ly=Ly, ry=Ry, lz=Lz, rz=Rz;
int Ax=ay,Ay=-az,Az=ax;
ax=Ax,ay=Ay,az=Az;
}
cout<<ans<<endl;
FOR(i,1,ax)cout<<'B';
FOR(i,1,ay)cout<<'N';
cout<<endl;
return 0;
}
1394D - Boboniu and Jianghu
Idea: Z18
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5;
int n, h[maxn + 3], t[maxn + 3], in[maxn + 3], out[maxn + 3];
vector<int> G[maxn + 3];
bool vis[maxn + 3];
ll ans, f[maxn + 3], g[maxn + 3], a[maxn + 3];
void dfs(int u, int fa = 0) {
vis[u] = true;
for (int i = 0, v; i < G[u].size(); i++) {
if ((v = G[u][i]) == fa) continue;
dfs(v, u);
}
int s = 0;
ll cur = 0;
for (int i = 0, v; i < G[u].size(); i++) {
if ((v = G[u][i]) == fa) continue;
cur += g[v], a[++s] = f[v] - g[v];
}
sort(a + 1, a + s + 1);
reverse(a + 1, a + s + 1);
for (int i = 0; i <= s; i++) {
cur += a[i];
if (fa) {
f[u] = max(f[u], 1ll * min(in[u] + 1 + s - i, out[u] + i) * t[u] + cur);
g[u] = max(g[u], 1ll * min(in[u] + s - i, out[u] + 1 + i) * t[u] + cur);
} else {
f[u] = max(f[u], 1ll * min(in[u] + s - i, out[u] + i) * t[u] + cur);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
ans += t[u] + t[v];
if (h[u] == h[v]) {
G[u].push_back(v), G[v].push_back(u);
} else {
if (h[u] > h[v]) swap(u, v);
in[u]++, out[v]++;
}
}
for (int i = 1; i <= n; i++) if (!vis[i]) {
dfs(i), ans -= f[i];
}
printf("%lld\n", ans);
return 0;
}
1394E - Boboniu and Banknote Collection
Idea: sshwyR
Tutorial
Tutorial is loading...
Solution
//by Sshwy
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
const int N=1e5+5;
int n,a[N],xyx,q[N],c[N],p[N];
vector<int> v[N];
int pos;
void get_v(int pos){
v[pos].clear();
if(pos==1)return;
if(a[pos]==a[pos-1])v[pos].pb(2);
for(auto x:v[pos-1])if(a[pos]==a[pos-x-1])v[pos].pb(x+2);
}
bool check_even_pal(int L,int R){
assert(R<=pos);
for(auto x:v[R])if(x==R-L+1)return 1;
return 0;
}
int qry(){
int res=xyx+c[pos];
int cur=pos;
while(p[cur] && q[pos]<=cur-p[cur]/2){
cur-=p[cur]/2;
++res;
}
return res;
}
int main(){
scanf("%d",&n);
q[0]=1;
FOR(i,1,n){
++pos;
scanf("%d",&a[pos]);
get_v(pos);
int x;
if(v[pos].size() && (x=v[pos][0], check_even_pal(pos-x/2-x+1,pos-x/2))){
pos-=x;
xyx+=2;
}else {
p[pos]=v[pos].size()? v[pos][0]:0;
q[pos]=q[pos-1],c[pos]=c[pos-1];
if(check_even_pal(q[pos],pos)){
q[pos]+=(pos-q[pos]+1)/2;
c[pos]++;
}
}
printf("%d%c",qry()," \n"[i==n]);
}
return 0;
}