A - Irreversible operation
对于某个 W 的位置，它的贡献即为前面 B 的个数，直接搞就完事了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200005;
int n;
char s[N];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
int cnt=0;
long long ans=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='B') cnt++;
else if(s[i]=='W') ans+=cnt;
}
printf("%lld",ans);
return 0;
}
B - Powers of two
对于每个数，加上一个小于等于它的数使得它等于 \(2\) 的幂次的数是唯一确定的。那么就可以将每个数向这个小于等于它的数连边，然后从叶子开始贪心匹配即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=200005;
int n;
int a[N];
unordered_map<int,int>cnt;
int b[N],tot;
vector<int>G[N];
int fa[N];
int ret[N];
int ans;
void dfs(int u,int father)
{
for(int v:G[u])
{
if(v==father) continue;
dfs(v,u);
if(ret[v]>0&&ret[u]>0)
{
int del=min(ret[v],ret[u]);
ret[v]-=del,ret[u]-=del,ans+=del;
}
}
if(__builtin_popcount(b[u]+b[u])==1) ans+=ret[u]/2,ret[u]%=2;
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
cnt[a[i]]++,b[++tot]=a[i];
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
for(int i=1;i<=tot;i++)
{
int t=log2(b[i])+1;
int val=(1<<t)-b[i];
if(!cnt[val]) continue;
int v=lower_bound(b+1,b+tot+1,val)-b;
if(i==v) continue;
G[i].emplace_back(v);
G[v].emplace_back(i);
fa[i]=v;
}
for(int i=1;i<=tot;i++)
ret[i]=cnt[b[i]];
for(int i=1;i<=n;i++)
if(!fa[i]) dfs(i,0);
printf("%d",ans);
return 0;
}
C - Lexicographic constraints
考虑二分答案，问题变成判断是否能用 \(k\) 个字符表示出所有的 \(S_i\)。
如果 \(A_{i-1} \lt A_i\)，\(S_i\) 只要在 \(S_{i-1}\) 的基础上加上 \(A_i-A_{i-1}\) 个 a 即可。
如果 \(A_{i-1}\ge A_{i}\)，\(S_i\) 只要在 \(S_{i-1}\) 的基础上去掉最后 \(A_{i-1}-A_i\) 个字符，然后将最后一个字符变成下一个字符。
那么就可以用一个栈来维护不是 a 的位置，最后只要判断下 \(1\) 有没有进位就好了。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=200005;
int n;
int a[N];
bool check(int x)
{
vector<pair<int,int>>S;
for(int i=1;i<=n;i++)
if(a[i]<=a[i-1])
{
while(!S.empty()&&S.back().second>a[i]) S.pop_back();
if(S.empty()) S.emplace_back(2,a[i]);
else if(S.back().second==a[i]) S.back().first++;
else S.emplace_back(2,a[i]);
while(!S.empty()&&S.back().first>x)
{
int c=S.back().second;
if(c==1) return false;
S.pop_back();
if(S.empty()) S.emplace_back(2,c-1);
else if(S.back().second==c-1) S.back().first++;
else S.emplace_back(2,c-1);
}
}
return true;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
bool flag=true;
for(int i=1;i<=n;i++)
if(a[i]<=a[i-1])
{
flag=false;
break;
}
if(flag)
{
printf("1");
return 0;
}
int l=2,r=n,ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
return 0;
}
D - Grid game
可以发现，第一个人是不会停下来的，否则第二个人也停下来游戏就结束了。
那么只需要算下到步数最少的那个障碍物的步数就行了（边界也算）。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005;
int h,w,n;
pair<int,int>a[N];
pair<int,int>c[N];
int cnt;
int main()
{
scanf("%d%d%d",&h,&w,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].first,&a[i].second);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
if(a[i].first!=1&&a[i].first!=c[cnt].first) c[++cnt]=a[i];
int x=1,y=1;
for(int i=1;i<=cnt;i++)
{
auto [dx,dy]=c[i];
if(dy<y+(dx-x))
{
printf("%d",dx-1);
return 0;
}
else if(dy==y+(dx-x)) y=dy-1;
else y+=(dx-x);
x=dx;
}
printf("%d",h);
return 0;
}
E - Wandering TKHS
设点 \(u\) 到根的路径上分别是 \(u_1,u_2,u_3,\cdots ,u_{k−1},u_k\)，考虑向上走的过程，从 \(u_i\to fa_{u_i}\) 就是 \(u\) 的子树中小于 \(fa_{u_i}\) 的点都走一遍。可以发现对于一个 \(i\in [1,n)\) 来说若存在 \(j\gt i\) 且 \(u_{j+1}>u_{i+1}\)，那么后者的作用会包含前者，我们只要考虑每个点到根路径上的后缀最大值，也就是根到每个点路径上的前缀最大值。
那么就可以由父亲向儿子递推了，分成几种情况讨论下即可。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=200005;
int n;
vector<int>G[N];
int calc(int u,int father,int x)
{
int res=0;
for(int v:G[u])
{
if(v==father) continue;
if(v<x) res+=calc(v,u,x)+1;
}
return res;
}
int mx[N];
int ans[N];
void dfs(int u,int father)
{
mx[u]=max(mx[father],u);
for(int v:G[u])
{
if(v==father) continue;
ans[v]=ans[u];
if(u>mx[father])
{
if(v>mx[father]) ans[v]+=calc(v,u,u)+1;
else ans[v]+=calc(v,u,u)-calc(v,u,mx[father]);
}
else
{
if(v>mx[father]) ans[v]+=calc(v,u,mx[father])+1;
}
dfs(v,u);
}
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x].emplace_back(y);
G[y].emplace_back(x);
}
dfs(1,0);
for(int i=2;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}
F - Construction of a tree
我们考虑以某个点为根，对于每条边，看做是儿子和包含它的某个集合匹配。不妨把每个数看做左部点，每个集合看做右部点，一个集合和这个集合中的数连边，那么我们就会得到一个去掉根之后的完美匹配。可以发现这是一个二分图，用 dinic 跑二分图匹配构造方案即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=200005;
const int INF=1061109567;
int n;
struct Edge
{
int to,next,flow;
}edge[N*2+N*4];
int head[N<<1],cnt=1;
void add_edge(int u,int v,int f)
{
cnt++;
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].flow=f;
head[u]=cnt;
return;
}
void add(int u,int v,int f)
{
add_edge(u,v,f);
add_edge(v,u,0);
return;
}
int s,t;
int dep[N<<1];
bool bfs()
{
memset(dep,-1,sizeof(dep));
queue<int>q;
q.push(s);
dep[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(dep[v]!=-1||edge[i].flow<=0) continue;
dep[v]=dep[u]+1;
q.push(v);
}
}
return dep[t]!=-1;
}
int cur[N<<1];
int dfs(int u,int flow)
{
if(u==t||flow==0) return flow;
int used=0;
for(int &i=cur[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(dep[v]!=dep[u]+1||edge[i].flow<=0) continue;
int now=dfs(v,min(flow,edge[i].flow));
flow-=now;
edge[i].flow-=now;
edge[i^1].flow+=now;
used+=now;
if(flow==0) break;
}
return used;
}
int dinic()
{
int res=0;
while(bfs())
{
memcpy(cur,head,sizeof(head));
res+=dfs(s,INF);
}
return res;
}
vector<int>G[N];
int match[N];
bool vis[N];
pair<int,int>res[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
int c;
scanf("%d",&c);
for(int j=1;j<=c;j++)
{
int x;
scanf("%d",&x);
if(x!=1) add(x,i+n,1);
G[x].emplace_back(i);
}
}
s=0,t=n+n-1+1;
for(int i=2;i<=n;i++)
add(s,i,1);
for(int i=1;i<=n-1;i++)
add(i+n,t,1);
int ans=dinic();
if(ans!=n-1)
{
printf("-1");
return 0;
}
for(int u=2;u<=n;u++)
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==s) continue;
if(edge[i].flow==0) match[v-n]=u;
}
queue<int>q;
q.emplace(1);
int tot=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int c:G[u])
if(!vis[c])
{
int v=match[c];
res[c]={u,v};
tot++;
q.emplace(v);
vis[c]=true;
}
}
if(tot!=n-1)
{
printf("-1");
return 0;
}
for(int i=1;i<=n-1;i++)
printf("%d %d\n",res[i].first,res[i].second);
return 0;
}
- AtCoder Contest Grand 029atcoder contest grand 029 authentic atcoder contest grand negative atcoder contest grand atcoder contest grand 022 atcoder contest grand 001 histogram atcoder contest grand atcoder contest radius grand atcoder contest descent grand atcoder contest grand 019 atcoder contest grand 017