Thank you for participating, and I hope you enjoyed the problems!↵
↵
Solutions will be updated after system testing...↵
↵
## [problem:1395A]↵
↵
Idea: [user:dqa2020,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1395A]↵
</spoiler>↵
↵
<spoiler summary="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")↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1395B]↵
↵
Idea: [user:Xiejiadong,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1395B]↵
</spoiler>↵
↵
<spoiler summary="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;↵
} ↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1395C]↵
↵
Idea: [user:xryjr233,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1395C]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394A]↵
↵
Idea: [user:sshwyR,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394A]↵
</spoiler>↵
↵
<spoiler summary="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;↵
} ↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394B]↵
↵
Idea: [user:sshwyR,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394B]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394C]↵
↵
Idea: [user:sshwyR,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394C]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394D]↵
↵
Idea: [user:ZZZZZZZZZZZZZZZZZZ,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394D]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394E]↵
↵
Idea: [user:sshwyR,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394E]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
Idea: [user:dqa2020,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1395A]↵
</spoiler>↵
↵
<spoiler summary="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")↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1395B]↵
↵
Idea: [user:Xiejiadong,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1395B]↵
</spoiler>↵
↵
<spoiler summary="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;↵
} ↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1395C]↵
↵
Idea: [user:xryjr233,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1395C]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394A]↵
↵
Idea: [user:sshwyR,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394A]↵
</spoiler>↵
↵
<spoiler summary="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;↵
} ↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394B]↵
↵
Idea: [user:sshwyR,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394B]↵
</spoiler>↵
↵
<spoiler summary="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;↵
// 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);↵
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;↵
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]++;↵
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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394C]↵
↵
Idea: [user:sshwyR,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394C]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394D]↵
↵
Idea: [user:ZZZZZZZZZZZZZZZZZZ,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394D]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1394E]↵
↵
Idea: [user:sshwyR,2020-08-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1394E]↵
</spoiler>↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
