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;
const int maxn = 100;
int n, m, a, b;
bool row[maxn + 3], vis[maxn + 3][maxn + 3];
int main() {
scanf("%d %d %d %d", &n, &m, &a, &b);
for (int i = 1; i <= n; i++) {
if (i > 1) for (int j = 1; j <= n; j++) if (!row[j]) { a = j; break; }
row[a] = true;
printf("%d %d\n", a, b);
vis[a][b] = true;
for (int j = 1; j < m; j++) {
for (int k = 1; k <= m; k++) if (!vis[a][k]) { b = k; break; }
printf("%d %d\n", a, b);
vis[a][b] = true;
}
}
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>
#define ci const int&
using namespace std;
const long long INF=1e18;
struct edge{
int t,nxt,dir;
}e[400010];
int n,h[200010],c[200010],u,v,be[200010],vis[200010],ar[200010],sz,cnt,t;
long long f[200010],g[200010];
priority_queue<long long>pq;
void add(ci x,ci y,ci d){
e[++cnt]=(edge){y,be[x],d},be[x]=cnt;
}
long long Calc(ci x,ci st){
//cout<<"CALC "<<x<<" "<<st<<"\n";
if(!sz)return (!!st)*c[x];
int tmp=st+sz;
long long a1,a2;
a1=1ll*((st>0)+sz)*c[x];
while(!pq.empty())pq.pop();
for(int i=1;i<=sz;++i)f[ar[i]]!=INF?pq.push(f[ar[i]]-g[ar[i]]+c[x]),a1+=f[ar[i]]:(a1+=g[ar[i]]-c[x],tmp-=2);
//cout<<"A1="<<a1<<",tmp="<<tmp<<"\n";
while(!pq.empty()&&tmp>1&&pq.top()>0)a1-=pq.top(),pq.pop(),tmp-=2;
if(tmp<0)a1=INF;
a2=1ll*((st<0)+sz)*c[x],tmp=st-sz;
while(!pq.empty())pq.pop();
for(int i=1;i<=sz;++i)g[ar[i]]!=INF?pq.push(g[ar[i]]-f[ar[i]]+c[x]),a2+=g[ar[i]]:(a2+=f[ar[i]]-c[x],tmp+=2);
//cout<<"A2="<<a2<<",tmp="<<tmp<<"\n";
while(!pq.empty()&&tmp<-1&&pq.top()>0)a2-=pq.top(),pq.pop(),tmp+=2;
if(tmp>0)a2=INF;
//cout<<"a1="<<a1<<",a2="<<a2<<"\n";
return min(a1,a2);
}
void TDP(ci x){
vis[x]=1;
int td=0;
for(int i=be[x];i;i=e[i].nxt)if(!vis[e[i].t])TDP(e[i].t);
else td=e[i].dir;
sz=0;
for(int i=be[x];i;i=e[i].nxt)if(!vis[e[i].t])ar[++sz]=e[i].t;
//cout<<"DP"<<x<<" sz="<<sz<<"\n";
if(x==1)f[x]=Calc(x,0);
else f[x]=(td!=1?Calc(x,-1):INF),g[x]=(td!=-1?Calc(x,1):INF);
//cout<<"F "<<x<<"="<<f[x]<<",g="<<g[x]<<"\n";
vis[x]=0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&c[i]);
for(int i=1;i<=n;++i)scanf("%d",&h[i]);
for(int i=1;i<n;++i)scanf("%d%d",&u,&v),t=(h[u]>=h[v]?(h[u]>h[v]):-1),add(u,v,t),add(v,u,-t);
TDP(1),printf("%lld",f[1]);
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;
}