D1T1 火车站
为什么省选会考这种题？
不妨考虑一直往右走的情况，如果某一段轨道的左端点是可以到达的，就说明这一段都是可以到达的。
对所有轨道按左端点排序，同时维护能够到达的最右点 \(lim\)，对于新加入的轨道 \([l,r]\)，如果 \(l\leqslant lim\) 就说明这段轨道是可以到达的，同时将 \(lim\) 更新为 \(\max(lim,r)\)，将 \(r\) 记入答案。
初始时 \(lim=x\)，左边同理，对于 \(l<x<r\) 的区间，拆成 \([l,x]\) 和 \([x,r]\) 即可。
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
typedef pair<int,int> pr;
int n,m,x,l,r,fl;
vector<pr> solL,solR;
bool abl[200010];
int main()
{
n=Qread(),m=Qread(),x=Qread();
for(int i=1;i<=m;i++)
{
l=Qread(),r=Qread();
if(r<=x) solL.push_back(make_pair(r,l));
else if(x<=l) solR.push_back(make_pair(l,r));
else solL.push_back(make_pair(x,l)),solR.push_back(make_pair(x,r));
}
sort(solL.begin(),solL.end());
reverse(solL.begin(),solL.end());
sort(solR.begin(),solR.end());
fl=x;
for(pr &g:solL)
{
if(g.first<fl) break;
fl=min(fl,g.second);
abl[g.second]=true;
}
fl=x;
for(pr &g:solR)
{
if(g.first>fl) break;
fl=max(fl,g.second);
abl[g.second]=true;
}
for(int i=1;i<=n;i++)
if(abl[i])
printf("%d ",i);
printf("\n");
return 0;
}
D1T2 城市建造
题目要求大概是能不能将原图分成若干个连通块，连通块大小差 \(\leqslant k\)，同时每个连通块内与其他连通块连边的点有且仅有一个。
不难发现这种与外面连边的点必然是割点，同时，如果一个点双连通分量不全在一个连通块中，这些点一定两两不在同一连通块内。这些又可以用反证法证明。
考虑建出圆方树，那么一个点双被分割开就相当于是直接删除圆方树中对应的方点。
由于原图中 \(t\) 个点联通，所以对于圆方树中删除的两个方点的路径上所有的方点都会被删掉，或者，可以说，删除的方点是“联通”的。
考虑DP维护答案，同时每一种删除方式的贡献在所有删除方点的LCA处统计贡献。
由于只有圆点对应原图中实实在在的点，所以我们的子树大小记录的是子树内圆点的数量。
考虑对于每一个特定的连通块大小 \(g\) 和 \(g+k\) 进行DP（其实有解的 \(g\) 只有 \(O(\sqrt{n})\) 种）。
我们设计一个DP数组 \(f\)，表示：
- 如果这个点为圆点，表示它的父亲被删除的情况下，子树内合法的删除方案数。
- 如果这个点是方点，表示在它被删除的情况下，子树内合法的删除方案数。
对于 \(k=0\)。
子树大小 \(siz_v\geqslant g\) 的，必然是它自己成为一个块。如果这个点是圆点，如果 \(\sum\limits_{siz_v<g}siz_v+1=g\)，说明可以把所有\(<g\) 的拼成一个连通块，方案数为 \(\prod\limits{siz_v\geqslant g}f_v\)；如果这个点是方点，它必须被删除，所以如果出现 \(siz_v<g\) 的子树 \(f_u\) 就是 \(0\)，否则是 \(\prod f_v\)。
对于 \(k=1\)。
和 \(k=0\) 唯一的区别就是：在这个点是圆点的情况下，如果不存在 \(siz_v<g\)，那么我们可以选择一个 \(siz_v=g\) 的子树和这个节点拼成一个大小为 \(g+1\) 的连通块，此时方案数为 \(\prod\limits_{siz_v\geqslant g}f_v\times(1+\prod\limits_{siz_v=g}\dfrac{1}{siz_v})\)。
考虑答案统计，如果所有删除方点的LCA是方点，只需要判断这个子树内节点数是否是 \(n-g\) 或者 \(n-g-k\) 即可。如果所有删除方点的LCA是圆点，这是就只能选择至少删除了2个儿子方点的所有方案了，然后在判断和方点一样的条件。
考虑剪枝优化，如果 \(siz<g\) 则 \(f=0\)。复杂度优化到 \(O(n\log n)\)。
细节有点多，注意实现：
#include <bits/stdc++.h>
#define Mod 998244353
using namespace std;
int Qread()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
bool k;
int gl;
long long ans;
vector<int> ed[200010];
int cnt,lim;
int siz[200010];
long long f[200010];
bool cmp(int A,int B){return siz[A]<siz[B];}
void init(int n){lim=cnt=n;}
void add_edge(int u,int v)
{
ed[u].push_back(v);
ed[v].push_back(u);
}
int get_node(){return ++cnt;}
void dfs(int a,int fa)
{
for(int v:ed[a])
{
if(v==fa) continue;
dfs(v,a);
siz[a]+=siz[v];
}
siz[a]+=(a<=lim);
sort(ed[a].begin(),ed[a].end(),cmp);
return;
}
void solve(int a,int fa)
{
long long rem=1,mul=1,ls=0;
int cnt=(a<=lim),tot=0,ctt=0;
f[a]=0;
if(siz[a]<gl) return;
for(int v:ed[a])
{
if(v==fa) continue;
solve(v,a);
if(siz[v]<gl) cnt+=siz[v];
else if(siz[v]>=gl+k) rem=rem*f[v]%Mod,tot+=siz[v],ctt++;
else if(siz[v]==gl)
{
ls=(mul+ls*f[v])%Mod;
mul=mul*f[v]%Mod;
tot+=siz[v];ctt++;
}
}
if(a>lim)
{
if(cnt) f[a]=0;
else
{
f[a]=rem*mul%Mod;
if(lim-tot==gl||lim-tot==gl+k)
ans=(ans+mul*rem)%Mod;
}
}
else
{
if(cnt==gl||cnt==gl+k) f[a]=rem*mul;
if(cnt==1)
{
f[a]=(f[a]+rem*ls)%Mod;
if(ctt>2&&(lim-tot==1&&k))
ans=(ans+ls*rem)%Mod;
}
if(ctt>1&&(lim-tot==gl||lim-tot==gl+k))
ans=(ans+mul*rem)%Mod;
}
return;
}
struct Graph{
vector<int> ed[100010];
int zhan[100010],top;
int low[100010],dfn[100010],ind;
bool vis[100010];
void add_ed(int u,int v)
{
ed[u].push_back(v);
ed[v].push_back(u);
}
void build_CS_Tree(int a)
{
vis[a]=true;
low[a]=dfn[a]=++ind;
zhan[++top]=a;
for(int v:ed[a])
{
if(vis[v]) low[a]=min(low[a],dfn[v]);
else
{
build_CS_Tree(v);
low[a]=min(low[a],low[v]);
if(low[v]==dfn[a])
{
int rem=get_node();
add_edge(rem,a);
while(top&&zhan[top+1]!=v)
{
add_edge(zhan[top],rem);
top--;
}
}
}
}
return;
}
}G;
int n,m,B;
vector<int> typ;
int main()
{
n=Qread(),m=Qread(),k=Qread();
cnt=lim=n;
for(int i=1;i<=m;i++)
G.add_ed(Qread(),Qread());
G.build_CS_Tree(1);
B=sqrt(n);
dfs(1,0);
for(int i=1;i<=B;i++) typ.push_back(i);
for(int i=2;i<=B;i++) typ.push_back(n/i);
sort(typ.begin(),typ.end());
typ.erase(unique(typ.begin(),typ.end()),typ.end());
for(int zsh:typ)
{
gl=zsh;
solve(1,0);
}
ans%=Mod;
if(k)
{
ans=(Mod-ans)%Mod;
k=false;
for(int i=0,lim=typ.size()-1;i<lim;i++)
{
gl=typ[i+1];
if(typ[i]==typ[i+1]-1)
solve(1,0);
}
ans=(Mod-ans)%Mod;
}
printf("%lld\n",ans);
return 0;
}
D1T3 人员调度
考虑 \(m=0\) 的情况，就是一个类似最大权匹配问题。
在解决这类问题时，每次都是选择最长路增广，我们考虑将所有的人员进行排序，从大到小加入，对于每一个数看加入之后是否有完美匹配，有就加入，没有就删除。而根据hall定理，如果每一个子树内选择的节点数量小于子树大小，就一定存在完美匹配。
具体实现时，每一个节点的初始值时子树大小 \(siz_u\)，考虑加入一个节点时，如果它到根的路径上每一个点的值都 \(>0\)，则加入这个点，并将到根的路径上每个点权值减 \(1\)，使用树剖实现复杂度为 \(O(k\log^2n)\)。
考虑存在加入怎么办，由于我们不能进行排序。所以在无法形成完美匹配的时候存在某一个点替代掉另一个点的情况，如果这个点到根路径上值的最小值为 \(0\)，则找到深度最深的 \(=0\) 的节点，在它的子树内找到一个权值最小的点，如果将其删掉更优，就将其删掉然后加入当前员工。
可以使用树剖+小根堆维护子树内权值最小的点，实现复杂度为 \(O((k+m)\log^2n)\)。
考虑带删除怎么办，发现我们维护的东西不好用删除实现，所以考虑对时间进行分治，将加入删除变成 \(O(\log m)\) 次加入和撤销。
使用树剖时间复杂度为 \(O((k+m)\log^2n\log m)\)，\(10^5\) 有点小卡，但是能过。
考虑将树剖换成全局平衡二叉树，复杂度变为 \(O((k+m)\log n\log m)\)。
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
struct cz{
int x,v,sta,en;
}peo[200010];
vector<int> ed[100010];
void add_edge(int u,int v)
{
ed[u].push_back(v),ed[v].push_back(u);
}
struct Poi{
int fa,siz,bigson;
int top,ind,sonnum;
int dep;
}p[100010];
int dfn;
int RR[100010];
int bk[100010];
int qzh[100010];
void dfs1(int a,int fa)
{
p[a].fa=fa;
p[a].dep=p[fa].dep+1;
p[a].siz=p[a].sonnum=1;
for(int v:ed[a])
{
if(v==fa) continue;
dfs1(v,a);
p[a].siz+=p[v].siz;
if(p[v].siz>p[p[a].bigson].siz) p[a].bigson=v;
}
for(int v:ed[a])
{
if(v==fa||v==p[a].bigson) continue;
p[a].sonnum+=p[v].siz;
}
return;
}
#define ls s[pos].lson
#define rs s[pos].rson
typedef pair<int,int> pr;
struct GBT{
struct Node{
int fa,lson,rson,laz;
pr num,minn;
}s[100010];
void giv_laz(int pos,int num)
{
s[pos].laz+=num;
s[pos].num.first+=num;
s[pos].minn.first+=num;
}
void update(int pos)
{
s[pos].minn=min(s[pos].num,min(s[ls].minn,s[rs].minn));
}
void pushdown(int pos)
{
if(s[pos].laz)
{
if(ls) giv_laz(ls,s[pos].laz);
if(rs) giv_laz(rs,s[pos].laz);
s[pos].laz=0;
}
}
void poi_change(int pos,int num)
{
s[pos].num.first+=num;
s[pos].minn=min(s[ls].minn,s[rs].minn);
s[pos].minn.first+=s[pos].laz;
s[pos].minn=min(s[pos].num,s[pos].minn);
}
void push_all_down(int x)
{
if(s[x].fa) push_all_down(s[x].fa);
pushdown(x);
}
void lian_add(int x,int num)
{
int las=x;
push_all_down(x);
giv_laz(s[x].lson,num),poi_change(x,num);
x=s[x].fa;
while(x)
{
update(x);
if(las!=s[x].lson||!s[x].lson) giv_laz(s[x].lson,num),poi_change(x,num);
las=x;
x=s[x].fa;
}
}
pr get_minn(int x)
{
int las=x;
push_all_down(x);
pr ret=min(s[x].num,s[s[x].lson].minn);
x=s[x].fa;
while(x)
{
if(las!=s[x].lson||!s[x].lson) ret=min(ret,s[x].num),ret=min(ret,s[s[x].lson].minn);
las=x;
x=s[x].fa;
}
return ret;
}
int build_GBT(int l,int r)
{
if(r<l) return 0;
if(l==r)
{
s[l].num=make_pair(p[bk[l]].siz,-l);
update(l);
return l;
}
int sum=(qzh[r]+qzh[l-1])/2,mid=0,las=0;
mid=lower_bound(qzh+l,qzh+r+1,sum)-qzh;
s[mid].num=make_pair(p[bk[mid]].siz,-mid);
s[s[mid].lson=build_GBT(l,mid-1)].fa=mid;
s[s[mid].rson=build_GBT(mid+1,r)].fa=mid;
update(mid);
return mid;
}
}G;
#undef ls
#undef rs
void dfs2(int a,int top)
{
bk[p[a].ind=++dfn]=a;
qzh[dfn]=qzh[dfn-1]+p[a].sonnum;
p[a].top=top;
if(p[a].bigson) dfs2(p[a].bigson,top);
else G.s[G.build_GBT(p[top].ind,p[a].ind)].fa=p[p[top].fa].ind;
for(int v:ed[a])
{
if(v==p[a].fa||v==p[a].bigson) continue;
dfs2(v,v);
}
RR[p[a].ind]=dfn;
return;
}
int n,m;
#define ls (pos<<1)
#define rs (pos<<1|1)
#define mid (l+r>>1)
struct Sege{
pr s[400010];
int ind[100010];
priority_queue<int,vector<int>,greater<int> > q[100010],q_[100010];
void update(int pos){s[pos]=min(s[ls],s[rs]);}
void init(int pos=1,int l=1,int r=n)
{
s[pos]=make_pair(100010,l);
if(l==r) return ind[l]=pos,q[l].push(100010),void();
return init(ls,l,mid),init(rs,mid+1,r);
}
void add_num(int loc,int num)
{
int pos=ind[loc];
q[loc].push(num);
s[pos]=make_pair(q[loc].top(),loc);
for(pos>>=1;pos;pos>>=1)
update(pos);
}
void del_num(int loc,int num)
{
int pos=ind[loc];
q_[loc].push(num);
while(!q_[loc].empty()&&!q[loc].empty()&&q_[loc].top()==q[loc].top())
q_[loc].pop(),q[loc].pop();
s[pos]=make_pair(q[loc].top(),loc);
for(pos>>=1;pos;pos>>=1)
update(pos);
}
pr get_minn(int L,int R,int pos=1,int l=1,int r=n)
{
if(L<=l&&r<=R) return s[pos];
if(R<=mid) return get_minn(L,R,ls,l,mid);
if(mid<L) return get_minn(L,R,rs,mid+1,r);
return min(get_minn(L,R,ls,l,mid),get_minn(L,R,rs,mid+1,r));
}
}T;
vector<pr> cz[400010];
void add_cz(int L,int R,pr yg,int pos=1,int l=0,int r=m)
{
if(L<=l&&r<=R) return cz[pos].push_back(yg),void();
if(R<=mid) return add_cz(L,R,yg,ls,l,mid);
if(mid<L) return add_cz(L,R,yg,rs,mid+1,r);
return add_cz(L,R,yg,ls,l,mid),add_cz(L,R,yg,rs,mid+1,r);
}
long long ans;
typedef tuple<int,int,int> zsh;
void solve(int pos=1,int l=0,int r=m)
{
vector<zsh> Rem_cz;
pr rem,rem_;
for(pr &g:cz[pos])
{
rem=G.get_minn(g.first);
rem.second=-rem.second;
if(rem.first>0)
{
Rem_cz.push_back(make_tuple(1,g.first,g.second));
G.lian_add(g.first,-1);
T.add_num(g.first,g.second);
ans+=g.second;
}
else
{
rem_=T.get_minn(rem.second,RR[rem.second]);
if(rem_.first<g.second)
{
Rem_cz.push_back(make_tuple(2,rem_.second,rem_.first));
Rem_cz.push_back(make_tuple(1,g.first,g.second));
ans+=g.second-rem_.first;
G.lian_add(g.first,-1);
T.add_num(g.first,g.second);
G.lian_add(rem_.second,1);
T.del_num(rem_.second,rem_.first);
}
}
}
if(l==r) printf("%lld ",ans);
else solve(ls,l,mid),solve(rs,mid+1,r);
reverse(Rem_cz.begin(),Rem_cz.end());
for(zsh &g:Rem_cz)
{
if(get<0>(g)==1)
{
G.lian_add(get<1>(g),1);
T.del_num(get<1>(g),get<2>(g));
ans-=get<2>(g);
}
else
{
G.lian_add(get<1>(g),-1);
T.add_num(get<1>(g),get<2>(g));
ans+=get<2>(g);
}
}
return;
}
#undef ls
#undef rs
#undef mid
int sid,k,op;
int main()
{
sid=Qread();
G.s[0].minn=G.s[0].num=make_pair(100000000,-1);
n=Qread(),k=Qread(),m=Qread();
for(int i=2;i<=n;i++)
add_edge(i,Qread());
for(int i=1;i<=k;i++)
{
peo[i].x=Qread();
peo[i].v=Qread();
peo[i].en=m;
}
for(int i=1;i<=m;i++)
{
op=Qread();
if(op==1)
{
peo[++k].x=Qread();
peo[k].v=Qread();
peo[k].sta=i,peo[k].en=m;
}
else peo[Qread()].en=i-1;
}
dfs1(1,0);
dfs2(1,1);
T.init();
for(int i=1;i<=k;i++)
add_cz(peo[i].sta,peo[i].en,make_pair(p[peo[i].x].ind,peo[i].v));
solve();
return 0;
}
D2T1 过河卒
博弈论问题，发现状态数只有 \(n^3m^3\leqslant 10^6\) 个，转移方式只有 \(\leqslant 5.5\times 10^6\) 条，考虑直接建图。
考虑某一个点的胜负态确定方式：
- 如果转移中存在胜态，选择其中最短的。
- 如果所有状态都是负态，选择其中最长的。
- 如果无法使用上面两种确定方式确定，就说明存在平局方式（因为如果所有可以转移的胜负态都能用上述方法确定，则这个点就可以确定）。
发现上述所有性质均符合广搜，所以直接反向广搜即可，复杂度 \(O(n^3m^3)\)。
可以通过钦定红方棋子顺序来将状态数优化成原来的 \(\dfrac{1}{2}\)，这样常数会小些，但是这道题好像没有卡。
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
typedef pair<int,int> pr;
int n,m;
char mp[20][20];
vector<int> ed[1000010];
int dis[1000010],ind[1000010];
bool abl[1000010];
int typ[1000010];
pr sol[1000010],emp;
int sta,sta_,Rx1,Ry1,Rx2,Ry2,Bx,By,rem;
queue<int> Q;
int rt(int a,int b,int c,int d,int e,int f){return a*100000+b*10000+c*1000+d*100+e*10+f;}
void solve()
{
n=Qread(),m=Qread();
sta=sta_=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
do mp[i][j]=getchar();
while(mp[i][j]!='.'&&mp[i][j]!='#'&&mp[i][j]!='O'&&mp[i][j]!='X');
if(mp[i][j]=='O') sta=(sta*100+i*10+j);
if(mp[i][j]=='X') sta_=10*i+j;
}
sta=sta*100+sta_;
for(Rx1=0;Rx1<n;Rx1++)
for(Ry1=0;Ry1<m;Ry1++)
for(Rx2=0;Rx2<n;Rx2++)
for(Ry2=0;Ry2<m;Ry2++)
for(Bx=0;Bx<n;Bx++)
for(By=0;By<m;By++)
{
rem=Rx1*100000+Ry1*10000+Rx2*1000+Ry2*100+Bx*10+By;
abl[rem]=(mp[Rx1][Ry1]!='#'&&mp[Rx2][Ry2]!='#'&&mp[Bx][By]!='#'&&(Rx1!=Rx2||Ry1!=Ry2));
if(abl[rem]) ed[rem].clear();
}
for(Rx1=0;Rx1<n;Rx1++)
for(Ry1=0;Ry1<m;Ry1++)
{
if(mp[Rx1][Ry1]=='#') continue;
for(Rx2=0;Rx2<n;Rx2++)
for(Ry2=0;Ry2<m;Ry2++)
{
if(mp[Rx2][Ry2]=='#'||Rx2*m+Ry2<Rx1*m+Ry1) continue;
for(Bx=0;Bx<n;Bx++)
for(By=0;By<m;By++)
{
rem=Rx1*100000+Ry1*10000+Rx2*1000+Ry2*100+Bx*10+By;
if(abl[rem])
{
ind[rem]=0;
int sd=0;
for(int i=1;i<1000000;i*=10)
sd+=(sta/i%10-rem/i%10);
typ[rem]=(sd%2==0);
if(typ[rem])
{
if(Rx1&&abl[rem-100000]) ed[rem-100000].push_back(rem),ind[rem]++;
if(Rx1!=n-1)
{
int sd=0;
if(Rx2*m+Ry2<(Rx1+1)*m+Ry1) sd=rt(Rx2,Ry2,Rx1+1,Ry1,Bx,By);
else sd=rem+100000;
if(abl[sd]) ed[sd].push_back(rem),ind[rem]++;
}
if(Ry1&&abl[rem-10000]) ed[rem-10000].push_back(rem),ind[rem]++;
if(Ry1!=m-1&&abl[rem+10000]) ed[rem+10000].push_back(rem),ind[rem]++;
if(Rx2)
{
int sd=0;
if((Rx2-1)*m+Ry2<Rx1*m+Ry1) sd=rt(Rx2-1,Ry2,Rx1,Ry1,Bx,By);
else sd=rem-1000;
if(abl[sd]) ed[sd].push_back(rem),ind[rem]++;
}
if(Rx2!=n-1&&abl[rem+1000]) ed[rem+1000].push_back(rem),ind[rem]++;
if(Ry2&&abl[rem-100]) ed[rem-100].push_back(rem),ind[rem]++;
if(Ry2!=m-1&&abl[rem+100]) ed[rem+100].push_back(rem),ind[rem]++;
}
else
{
if(Bx&&abl[rem-10]) ed[rem-10].push_back(rem),ind[rem]++;
if(By&&abl[rem-1]) ed[rem-1].push_back(rem),ind[rem]++;
if(By!=m-1&&abl[rem+1]) ed[rem+1].push_back(rem),ind[rem]++;
}
if(Bx==0) sol[rem]=make_pair(0,0),Q.push(rem);
else if((Rx1==Bx&&Ry1==By)||(Rx2==Bx&&Ry2==By)) sol[rem]=make_pair(!typ[rem],0),Q.push(rem);
else if(ind[rem]==0) sol[rem]=make_pair(!typ[rem],0),Q.push(rem);
else sol[rem]=emp;
}
}
}
}
while(!Q.empty())
{
int rea=Q.front();Q.pop();
for(int &g:ed[rea])
{
if(sol[g]!=emp) continue;
ind[g]--;
if(sol[rea].first==typ[g])
{
sol[g]=make_pair(typ[g],sol[rea].second+1);
Q.push(g);
}
else if(ind[g]==0)
{
sol[g]=make_pair(!typ[g],sol[rea].second+1);
Q.push(g);
}
}
}
if(sol[sta]==emp) printf("Tie\n");
else if(sol[sta].first) printf("Red %d\n",sol[sta].second);
else printf("Black %d\n",sol[sta].second);
}
int op;
int main()
{
op=Qread();
emp=make_pair(-1,-1);
int T=Qread();
while(T--) solve();
return 0;
}