2023联合省选题解
火车站
签到题。
可以发现，一段被覆盖的区间上任意两点联通，因此用差分维护连续段即可。
int main(){
n=read(),m=read(),x=read();
for(int i=1;i<=m;i++){
int l=read(),r=read();
bl[l]=1;
br[r]=1;
c[l]++,c[r+1]--;
}
for(int i=1;i<=n;i++){
c[i]+=c[i-1];
if(c[i]){
if((c[i]==1&&bl[i])||!c[i-1])tot++,L[tot]=R[tot]=i;
else if(c[i-1])R[tot]=i;
}
else tot++,L[tot]=R[tot]=i;
id[i]=tot;
}
for(int i=1;i<=n;i++){
if(id[i]==id[x]&&((i<x&&bl[i])||(i>x&&br[i]))&&i!=x)write(i),putchar(' ');
}
return 0;
}
城市建造
首先有一些性质。如果两个点被选择，那么如果有一条简单路径连接这两个点，这条路上的所有点都要被选择。由此可以推出，如果一个点双里面选了两个点，那么整个点双都要被选择。因此，建出圆方树，钦定选一个方点表示选择了整个点双，那么我们最终选出的一定是方点的连通块，且删掉这些方点后每个连通块的大小之差不大于\(k\)。
接着可以想到枚举连通块大小\(d\)来计数，而可以证明合法的d是\(\left\lfloor\frac{n}{i}\right\rfloor\)或\(\left\lfloor\frac{n}{i}\right\rfloor-1\)，因此只有\(n\sqrt n\)种。
然后我们考虑如何计数。
设\(f_i\)表示：如果\(i\)是圆点，删掉它的父亲方点的方案数；如果是方点，删掉它自己的方案数。
当\(k=0\)时，可以证明答案一定是0/1，因此对于一个点\(x\)的儿子\(y\)，有：如果\(x\)时方点，\(f_x=\prod f_y\)；如果\(x\)是圆点，只有\(siz_y<d\)的\(siz_y\)之和为\(d-1\)，且所有\(siz>=d\)的\(f_y\)都为1时，\(f_x=1\)，否则为0。
当\(k=1\)时，多的情况是如果没有\(siz_y<d\)的点，那么每一个\(siz_y=d\)的\(y\)都可以和\(x\)在同意连通块内，会多产生一种情况，直接加上即可。
namespace RST{
int cnt,ver[N<<1],nxt[N<<1],h[N],d,dfn[N];
bool isd[N];
inline void add_edge(int x,int y){
cnt++;ver[cnt]=y;nxt[cnt]=h[x];h[x]=cnt;
cnt++;ver[cnt]=x;nxt[cnt]=h[y];h[y]=cnt;
}
int siz[N],maxn,rt,cntdfn,id[N];
inline void getrt(int x,int fa){
siz[x]=(x<=n);
int maxsiz=1;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa)continue;
getrt(y,x);
siz[x]+=siz[y];
maxsiz=max(maxsiz,siz[y]);
}
maxsiz=max(maxsiz,n-siz[x]);
if(maxsiz<maxn&&x<=n)rt=x,maxn=maxsiz;
}
inline void dfs(int x,int fa){
cntdfn++;
dfn[x]=cntdfn;
id[cntdfn]=x;
siz[x]=(x<=n);
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa)continue;
dfs(y,x);
siz[x]+=siz[y];
}
}
int f[N];
inline void dfs1(){
for(int i=tot;i>=1;i--){
int x=id[i];
f[x]=0;
if(siz[x]<d)continue;
bool flag1=0,flag2=1;
int sum=1;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(dfn[y]<dfn[x])continue;
if(x<=n){
if(siz[y]>=d)flag1|=(f[y]==0);
else sum+=siz[y];
}
else flag2&=f[y];
}
if(x<=n){
if(!flag1&&sum==d)f[x]=1;
else f[x]=0;
}
else f[x]=flag2;
if(siz[x]>d+1&&f[x]==0){
f[rt]=0;
break;
}
}
}
inline void dfs2(){
for(int i=tot;i>=1;i--){
int x=id[i];
f[x]=0;
if(siz[x]<d)continue;
int prod=1,sum=1,cnt=0;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(dfn[y]<dfn[x])continue;
if(x<=n){
if(siz[y]<d)sum+=siz[y];
else if(siz[y]>d)prod=1ll*prod*f[y]%mod;
else{
if(f[y]==0)sum+=siz[y];
else cnt++;
}
}
else{
prod=1ll*prod*f[y]%mod;
}
}
if(x<=n){
if(d<=sum&&sum<=d+1)f[x]=prod;
if(sum==1)f[x]=(f[x]+1ll*cnt*prod%mod)%mod;
}
else f[x]=prod;
if(siz[x]>d+1&&f[x]==0){
f[rt]=0;
break;
}
}
}
inline void solve(){
maxn=tot;
getrt(1,0);
dfs(rt,0);
int ans=0;
for(int i=2;i<=n;i++){
isd[n/i]=1;
if(n%i==0)isd[n/i-1]=1;
}
for(d=1;d<=n/2;d++){
if(!isd[d])continue;
if(k==0&&(n%d!=0))continue;
int res=0;
if(k==0)dfs1(),res=f[rt];
else{
dfs2();
res=f[rt];
if(n%(d+1)==0){
d++;
dfs1();
res=(res-f[rt]+mod)%mod;
d--;
}
}
ans=(ans+res)%mod;
}
cout<<ans<<endl;
}
}
人员调度
GBT跑的还没别人树剖快，我写它干嘛
把原来的操作改成：树上每个点先有\(siz_x\)的容量，每加一个工厂就把\(x\)到根路径上的容量减1，如果加入后有-1了就把深度最大的为-1的点的子树里贡献最小的工厂的贡献减掉，这样就可以很好用树剖维护。我们发现不好处理删除操作，于是考虑按时间轴分治，这样就可以很好解决删除的问题。
瓶颈在于复杂度是\(O(n\log^3n)\)的，于是就考虑使用全局平衡二叉树把树剖降成单log，这样就是\(O(n\log^2n)\)的。
inline void dfs(int x){
siz[x]=1;
be[x]=cntk+1;
for(auto i:v[x])id[i]=++cntk;
for(auto y:e[x]){
dfs(y);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
en[x]=cntk;
}
namespace splay{
int ch[N][2],minn[N],lz[N],fa[N];
inline void pt(){
for(int i=1;i<=n;i++)cout<<i<<" "<<fa[i]<<" "<<ch[i][0]<<" "<<ch[i][1]<<" "<<lz[i]<<" "<<minn[i]<<endl;
cout<<endl;
}
inline void init(){minn[0]=lz[0]=1e9;}
inline void link(int x,int y,int op){
fa[x]=y;
if(op!=-1&&y)ch[y][op]=x;
}
inline void upd(int rt){minn[rt]=min(0,min(minn[ch[rt][0]],minn[ch[rt][1]]))+lz[rt];}
inline bool isroot(int rt){return ch[fa[rt]][0]!=rt&&ch[fa[rt]][1]!=rt;}
inline void modify(int rt,int x){
while(rt){
lz[rt]+=x;
if(ch[rt][1]){
lz[ch[rt][1]]-=x;upd(ch[rt][1]);
}
while(!isroot(rt)){
if(ch[fa[rt]][1]==rt)lz[fa[rt]]+=x,lz[rt]-=x;
upd(rt),rt=fa[rt];
}
upd(rt);
rt=fa[rt];
}
}
inline int calc(int rt){
int ans=lz[rt];
while(!isroot(rt))rt=fa[rt],ans+=lz[rt];
return ans;
}
inline int query(int rt){
while(rt){
int cur=calc(rt);
if(cur==-1)return rt;
else if(minn[ch[rt][0]]+cur==-1){
rt=ch[rt][0];cur+=lz[rt];
while(207){
if(minn[ch[rt][1]]+cur==-1)rt=ch[rt][1];
else if(cur==-1)return rt;
else rt=ch[rt][0];
cur+=lz[rt];
}
}
while(!isroot(rt)){
cur-=lz[rt];
if(ch[fa[rt]][1]==rt){
if(cur==-1)return fa[rt];
else if(minn[ch[fa[rt]][0]]+cur==-1){
rt=ch[fa[rt]][0],cur+=lz[rt];
while(207){
if(minn[ch[rt][1]]+cur==-1)rt=ch[rt][1];
else if(cur==-1)return rt;
else rt=ch[rt][0];
cur+=lz[rt];
}
}
}
rt=fa[rt];
}
rt=fa[rt];
}
return 0;
}
}
inline void build(int l,int r,int fa,int op){
ll sum=0,cur=0,maxn=0;
for(int i=l;i<=r;i++)sum+=lsiz[qu[i]];
int ans=l;
maxn=sum-lsiz[qu[l]];
for(int i=l;i<=r;i++){
ll tmp=sum-cur-lsiz[qu[i]];
if(max(tmp,cur)<maxn)maxn=max(tmp,cur),ans=i;
cur+=lsiz[qu[i]];
}
if(op==-1)splay::link(qu[ans],fa,-1);
else splay::link(qu[ans],fa,op);
if(l<ans)build(l,ans-1,qu[ans],0);
if(ans<r)build(ans+1,r,qu[ans],1);
}
inline void dfs1(int x,int topp){
for(auto y:e[x]){
if(y!=son[x])dfs1(y,y);
}
lsiz[x]=siz[x]-siz[son[x]];
if(son[x])dfs1(son[x],topp);
if(x==topp){
cntson=0;
for(int i=x;i;i=son[i])qu[++cntson]=i;
build(1,cntson,fa[x],-1);
}
}
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
namespace seg{
int minn[M<<2];
inline int chkmin(int x,int y){
if(!x||!y)return x+y;
return q[x].val<=q[y].val?x:y;
}
inline void upd(int rt){minn[rt]=chkmin(minn[ls],minn[rs]);}
inline void modify(int rt,int l,int r,int x,int k){
if(!x)return;
if(l==r){
minn[rt]=k;return;
}
if(x<=mid)modify(ls,l,mid,x,k);
else modify(rs,mid+1,r,x,k);
upd(rt);
}
inline int query(int rt,int l,int r,int L,int R){
if(L>R)return 0;
if(L<=l&&r<=R)return minn[rt];
if(R<=mid)return query(ls,l,mid,L,R);
else if(mid<L)return query(rs,mid+1,r,L,R);
else return chkmin(query(ls,l,mid,L,mid),query(rs,mid+1,r,mid+1,R));
}
}
#undef ls
#undef rs
#undef mid
struct option{
int op,x,y;
}st[N*5];
int tp;
inline void ins(int x){
res+=q[x].val;
splay::modify(q[x].x,-1),st[++tp]=(option){1,q[x].x,1};
seg::modify(1,1,tot,id[x],x),st[++tp]=(option){2,x,0};
int cur=splay::query(q[x].x);
if(cur){
int y=seg::query(1,1,tot,be[cur],en[cur]);
res-=q[y].val;
splay::modify(q[y].x,1),st[++tp]=(option){1,q[y].x,-1};
seg::modify(1,1,tot,id[y],0),st[++tp]=(option){2,y,y};
}
}
inline void init(int x){
while(tp!=x){
if(st[tp].op==1){
splay::modify(st[tp].x,st[tp].y);
}
else{
if(st[tp].y==0)res-=q[st[tp].x].val;
else res+=q[st[tp].x].val;
seg::modify(1,1,tot,id[st[tp].x],st[tp].y);
}
tp--;
}
}
inline void solve(int l,int r,vector<int>cur){
int mid=(l+r)>>1,tmp=tp;
vector<int>ql,qr;
for(auto i:cur){
if(q[i].l<=l&&r<=q[i].r)ins(i);
else if(l!=r){
if(q[i].l<=mid&&q[i].r>=l)ql.push_back(i);
if(q[i].l<=r&&q[i].r>mid)qr.push_back(i);
}
}
if(l==r)ans[l]=res;
else solve(l,mid,ql),solve(mid+1,r,qr);
init(tmp);
}
int main(){
sid=read();
n=read(),k=read(),m=read();
for(int i=2;i<=n;i++)fa[i]=read(),add_edge(fa[i],i);
tot=k;
for(int i=1;i<=k;i++){
q[i].l=1;q[i].x=read(),q[i].val=read();q[i].r=m+1;
}
for(int i=1;i<=m;i++){
int op=read();
if(op==1){
tot++;
q[tot].x=read(),q[tot].val=read();q[tot].l=i+1;q[tot].r=m+1;
}
else{
int x=read();
q[x].r=i;
}
}
for(int i=1;i<=tot;i++)v[q[i].x].push_back(i);
dfs(1);dfs1(1,1);
splay::init();
for(int i=1;i<=n;i++)splay::modify(i,1);
vector<int>cur;
for(int i=1;i<=tot;i++)cur.push_back(i);
solve(1,tot,cur);
for(int i=1;i<=m+1;i++)write(ans[i]),putchar(' ');
return 0;
}
过河卒
发现\(n,m\leqslant10\)，总状态数\((nm)^3\leqslant10^6\)，于是可以考虑把状态记录下来，用广搜解决。
具体地，先从初始状态开始广搜，标记所有胜负确定的状态，然后倒着连边，跑一遍类拓扑（只要胜负态确定就入队）就可以求出答案。
struct node{
int a,b,c,d,e,f;bool flag;
inline void pt(){cout<<a<<b<<c<<d<<e<<f<<flag<<endl;}
node(){}
node(int i,int j,int k,int l,int m,int n,bool fl):a(i),b(j),c(k),d(l),e(m),f(n),flag(fl){}
}ori;
inline void work(node &x){
if(x.c*n+x.d>x.e*n+x.f)swap(x.c,x.e),swap(x.d,x.f);
}
inline int getid(node x){return x.a*100000+x.b*10000+x.c*1000+x.d*100+x.e*10+x.f-111111;}
inline bool checkb(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!='#';}
inline bool checkr(int x,int y,int a,int b){return x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!='#'&&(x!=a||y!=b);}
struct Queue{
int l,r;
int q[M<<1];
inline void clear(){l=1,r=0;}
inline void push(int x){r++;q[r]=x;}
inline void pop(){l++;}
inline int front(){return q[l];}
inline bool empty(){return l>r;}
}Q;
struct Queue1{
int l,r;
node q[M<<1];
inline void clear(){l=1,r=0;}
inline void push(node x){r++;q[r]=x;}
inline void pop(){l++;}
inline node front(){return q[l];}
inline bool empty(){return l>r;}
}q;
inline void init(){
q.clear(),Q.clear();
memset(vis,0,sizeof(vis));memset(win,0,sizeof(win)),memset(in,0,sizeof(in));memset(hav,0,sizeof(hav));memset(ans,0,sizeof(ans));
posx1=posy1=0;
for(int i=1;i<=1000005;i++)edge[i].clear();
}
inline void bfs(){
q.push(ori);
vis[getid(ori)]=1;
while(!q.empty()){
node x=q.front();
q.pop();
int a=x.a,b=x.b,c=x.c,d=x.d,e=x.e,f=x.f,id=getid(x);bool flag=x.flag;
if(flag){
if((a==c&&b==d)||(a==e&&b==f)){
Q.push(id),hav[id]=1;
continue;
}
bool flag1=0;
for(int i=0;i<3;i++){
int xx=a+dir[i][0],yy=b+dir[i][1];
if(checkb(xx,yy)){
node cur=x;cur.a=xx,cur.b=yy,cur.flag=flag^1;
edge[getid(cur)].push_back(id);in[id]++;
if(!vis[getid(cur)]){
vis[getid(cur)]=1;
q.push(cur);
}
flag1=1;
}
}
if(!flag1)Q.push(id),hav[id]=1;
}
else{
if((a==c&&b==d)||(a==e&&b==f)||a==1){
Q.push(id),hav[id]=1;
continue;
}
bool flag1=0;
for(int i=0;i<4;i++){
int xx=c+dir[i][0],yy=d+dir[i][1];
if(checkr(xx,yy,e,f)){
node cur=x;cur.c=xx,cur.d=yy,cur.flag=flag^1;
work(cur);
edge[getid(cur)].push_back(id);in[id]++;
if(!vis[getid(cur)]){
vis[getid(cur)]=1;
q.push(cur);
}
flag1=1;
}
}
for(int i=0;i<4;i++){
int xx=e+dir[i][0],yy=f+dir[i][1];
if(checkr(xx,yy,c,d)){
node cur=x;cur.e=xx,cur.f=yy,cur.flag=flag^1;
work(cur);
edge[getid(cur)].push_back(id);in[id]++;
if(!vis[getid(cur)]){
vis[getid(cur)]=1;
q.push(cur);
}
flag1=1;
}
}
if(!flag1)Q.push(id),hav[id]=1;
}
}
int oriid=getid(ori);
while(!Q.empty()){
int x=Q.front();
Q.pop();
if(oriid==x)break;
for(auto y:edge[x]){
if(!win[x]){
if(!win[y]){
win[y]=1;
ans[y]=ans[x]+1;
hav[y]=1;
Q.push(y);
}
else{
ans[y]=min(ans[y],ans[x]+1);
in[y]--;
}
}
else{
if(!win[y]){
ans[y]=max(ans[y],ans[x]+1);
in[y]--;
if(!in[y])hav[y]=1,Q.push(y);
}else{
in[y]--;
}
}
}
}
if(!hav[oriid])printf("Tie\n");
else if(win[oriid])printf("Red %d\n",ans[oriid]);
else printf("Black %d\n",ans[oriid]);
}
inline void solve(){
init();
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cin>>mp[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='X')posxx=i,posxy=j;
else if(mp[i][j]=='O'){
if(!posx1)posx1=i,posy1=j;
else posx2=i,posy2=j;
}
}
}
ori=node(posxx,posxy,posx1,posy1,posx2,posy2,0);
bfs();
}
填数游戏
题意转化为：每个\(T_{i,0}\)与\(T_{i,1}\)之间连边，根据\(|S_i\cap T_i|\)的大小每条边有定向的代价和能否定某种方向，每个点最多被一条边指定，Alice要选择一种方案使得Bob的所有合法定向方案中代价最小值最大。
因为每个点最多被一条边指定，所以有\(|V|\geqslant|E|\)，因此每个连通块只能是基环树或者树。
先考虑基环树，对于不在环上的边，只能是叶向的，而且环上的边的方向必须一致，所以只有两种情况，很容易计算。
再考虑树的情况，Bob的选择一定是形如钦定一个点为根，所有边都是相对这个点叶向的，这样一共有\(|V|\)种方案。考虑从一个点到儿子时子树外的最小值-1，子树内加1，可以使用换根DP实现。
总复杂度\(O(n+m)\)。
namespace circle{
inline int solve(){
queue<int>q;
int pos=0,ans=0;
for(auto i:cir){
deg[i]=in[i];
if(deg[i]==1)q.push(i);
else pos=i;
}
while(!q.empty()){
int x=q.front();
q.pop();cntv--;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(deg[y]>1){
ans+=(w[i]==0||w[i]==2);
if(--deg[y]==1)q.push(y);
else pos=y;
}
}
}
if(cntv==1){
for(int i=h[pos];i;i=nxt[i]){
int y=ver[i];
if(y==pos){
ans+=w[i]>=0;
break;
}
}
}
else{
int cnt[3],cur=pos,lst=0;
cnt[0]=cnt[1]=cnt[2]=0;
while(cntv--){
for(int i=h[cur];i;i=nxt[i]){
int y=ver[i];
if(deg[y]==1||id[i]==lst)continue;
if(w[i]>=0)cnt[w[i]]++;
cur=y;lst=id[i];
break;
}
}
if(cnt[0]>cnt[1])swap(cnt[0],cnt[1]);
if(cnt[0]+cnt[2]<=cnt[1])ans+=cnt[0]+cnt[2];
else ans+=(cnt[0]+cnt[1]+cnt[2])/2;
}
return ans;
}
}
namespace tree{
int f[N],g[N],mn[N],mnn[N],ming[N];
inline void dfs1(int x,int fa){
f[x]=g[x]=mn[x]=mnn[x]=ming[x]=0;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa)continue;
dfs1(y,x);
f[x]+=f[y];
if(w[i]>0)f[x]++;
int cur=mn[y];
if(w[i]==0)cur++;
if(w[i]>0)cur--;
if(cur<mn[x])mnn[x]=mn[x],mn[x]=cur;
else if(cur<mnn[x])mnn[x]=cur;
}
}
inline void dfs2(int x,int fa){
ming[x]=min(ming[x],0);
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa)continue;
g[y]=g[x]+f[x]-f[y]-(w[i]>0);
if(w[i]==0||w[i]==2)g[y]++;
int cur=mn[y];
if(w[i]==0)cur++;
if(w[i]>0)cur--;
ming[y]=min(ming[x],cur==mn[x]?mnn[x]:mn[x]);
if(w[i]==0||w[i]==2)ming[y]--;
if(w[i]==1)ming[y]++;
dfs2(y,x);
}
}
inline int solve(){
dfs1(cir[0],0);dfs2(cir[0],0);
int ans=0;
for(auto i:cir)ans=max(ans,f[i]+g[i]+min(mn[i],ming[i]));
return ans;
}
}