Thank you for participating, and I hope you enjoyed the problems!
Solutions will be updated after system testing...
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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<vector>
#define pb push_back
#define nd second
#define st first
using namespace std;
#define G getchar()
int read()
{
int x=0; bool flg=false; char ch=G;
for (;!isdigit(ch);ch=G) if (ch=='-') flg=true;
for (;isdigit(ch);ch=G) x=(x<<3)+(x<<1)+(ch^48);
return flg?-x:x;
}
#undef G
typedef long long ll;
int n,m,k;
struct Edge{
int to,nxt;
}edge[200010];
int cnt,last[200010],deg[200010];
inline void addedge(int x,int y){
edge[++cnt]=(Edge){y,last[x]},last[x]=cnt;
}
typedef pair<int,int> P;
vector<P> d[200010];
ll S[15][15];
int id[15][15],idtot;
int ans;
int c[15];
void dfs(int x){
if (x>k){
ll T=0;
for (int i=1;i<=k;i++) T|=1LL<<id[i][c[i]];
for (int i=1;i<=k;i++) if (T&S[i][c[i]]) return;
// puts("===========");
// for (int i=1;i<=k;i++) printf("%d ",c[i]); puts("");
// for (int i=1;i<=n;i++) printf("%d -> %d %d (%d)\n",i,deg[i],c[deg[i]],d[i][c[deg[i]]-1].nd);
ans++;
return;
}
for (int i=1;i<=x;i++) c[x]=i,dfs(x+1);
}
int main()
{
n=read(),m=read(),k=read();
for (int i=1;i<=k;i++)
for (int j=1;j<=i;j++)
id[i][j]=++idtot;
for (int i=1;i<=m;i++){
int x=read(),y=read(),v=read();
addedge(y,x); deg[x]++;
d[x].pb((P){v,y});
}
for (int i=1;i<=n;i++) sort(d[i].begin(),d[i].end());
for (int i=1;i<=n;i++){
static int bin[15][15];
for (int u=1;u<=k;u++)
for (int v=1;v<=u;v++)
bin[u][v]=0;
// printf("invalid set of %d\n",i);
ll T=0;
for (int j=last[i],v;j;j=edge[j].nxt){
v=edge[j].to;
int p=0; while (d[v][p].nd^i) p++; p++;
T|=1LL<<id[deg[v]][p];
bin[deg[v]][p]++;
// printf("ins %d %d\n",deg[v],p);
}
for (int j=last[i],v;j;j=edge[j].nxt){
v=edge[j].to;
int p=0; while (d[v][p].nd^i) p++; p++;
if (bin[deg[v]][p]==1) S[deg[v]][p]|=T^(1LL<<id[deg[v]][p]);
else S[deg[v]][p]|=T;
}
}
dfs(1);
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;
}