9.23 %你赛

比赛数据

分数 $\color{#D0FF00}221/400$。
各题分数（赛时/总分）：
T1 $\color{#00FF00}100/100$
T2 $\color{#F02000}9/100$
T3 $\color{#00FF00}100/100$
T4 $\color{#F04000}12/100$
排名 $\color{#b8c0d0}2/7$（符合预期）。

这破比赛怎么每题都有多测呢？

膜拜未来 AKIOIer @Benny。/bx

T1 link $\color{#50F000}(3.25)$

某几个神人赛时问我怎么做。

先考虑 $k=0$ 的部分分，发现点 $x$ 可行当且仅当 $x$ 在点 $1$ 到任意 $d_i$ 的某条最短路上。
由于边权均为 $1$，可以BFS处理到源点的距离后，从目标点反推可行点。 如果 $k>0$，还要考虑是最短路的情况下，最多经过多少已有的花田。

注意，有多种可能路径时要对所有可转移的点取可经过花田的最大值而不是一锤定音，否则亲测会 $\color{#FFC000}-8$。
有多测，记得按需清空，不然就会和我的首次提交一样 $\color{#FF3020}-79$。

时间复杂度 $O(n+m+k+l)$（单组数据）。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000007;
int t,n,m,k,l,x,y,p[N],d[N],f[N],g[N],h[N],q[N],mx,hd,tl;
vector<int>v[N];
vector<int>w[N];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&n,&m,&k,&l);
		for(int i=1;i<=n;i++){
			v[i].clear();
			v[i].shrink_to_fit();
			f[i]=0;
			g[i]=0;
			h[i]=0;
			d[i]=998244353;
		}
		for(int i=1;i<=k;i++){
			scanf("%d",&x);
			f[x]=1;
		}
		for(int i=1;i<=l;i++) scanf("%d",&p[i]);
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			v[x].push_back(y);
			v[y].push_back(x);
		}
		mx=0;
		hd=0;
		tl=1;
		q[tl]=1;
		d[1]=0;
		while(hd<tl){
			hd++;
			x=q[hd];
			for(int i=0;i<v[x].size();i++){
				y=v[x][i];
				if(d[x]+1<=d[y]){
					if(d[y]>d[x]+1){
						tl++;
						q[tl]=y;
						d[y]=d[x]+1;
						if(d[y]>mx){
							mx=d[y];
							w[mx].clear();
							w[mx].shrink_to_fit();
						}
						w[d[y]].push_back(y);
					}
					g[y]=max(g[y],g[x]+f[y]);
				}
			}
		}
		for(int i=1;i<=l;i++) if(g[p[i]]==k) h[p[i]]=1;
		for(int i=mx;i>=1;i--){
			if(w[i].empty()) continue;
			for(int j=0;j<w[i].size();j++){
				x=w[i][j];
				if(!h[x]) continue;
				for(int o=0;o<v[x].size();o++){
					y=v[x][o];
					if(d[y]==i-1&&g[y]>=g[x]-f[x]) h[y]=1;
				}
			}
		}
		for(int i=2;i<=n;i++) printf("%d",h[i]);
		printf("\n");
	}
	return 0;
}

T2 link $\color{#00D8C0}(4.25)$

注意到所有必要的性质结果没切，我是废物。

很明显 $f(p)\leq p$ 的逆序对数。
本题有两种写法，一种是直接维护 $f(p)$ 和 $p$ 的逆序对数（@qinkaiwen做法）；
在这里嘲讽一下某个维护逆序对数不开 long long 的神人。（逆序对数最高可达 $O\left(n^2\right)$）
另一种是发现排列（或排列的循环移位）是好的当且仅当其不存在长度为 $3$ 的递减子序列。

注：这段引用了他人题解。（毕竟我没场切）
由于需要处理所有循环移位，我们将原排列复制两遍，形成一个长度为 $2n$ 的数组 $a$。
对于每一个位置 $a_i$，计算其左侧排列的最大值的位置 $l_i$ 与其右侧排列的最小值位置 $r_i$，
如果存在 $a_{l_i}>a_i>a_{r_i}$ 且 $r_i-l_i \le N$，那么就可以知道：
若一个长度为 $n$ 的排列包含了区间 $[l_i,r_i]$，则此排列必不合法。
设该排列的起始点为 $s$，则 $s \le l_i$ 且 $s+n-1\ge r_i$，即 $r_i - n + 1 \le s \le l_i$。
使用差分数组记录所有使排列变“坏”的起始位置 $s$。
注意处理窗口在 $[1,2n]$ 序列上循环映射回 $[1,n]$ 的逻辑。
最终差分数组中值为 $0$ 的位置即为好的起始点。

PS：这 $10^6$ 的数据范围显然不是给 $O\left(n\log(n)^2\right)$ 的东西乱草的。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000007;
int t,n,x,y,a[N],s[2*N],d[N],l[2*N],r[2*N],tp;
vector<int>ans;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			d[i]=0;
			a[i+n]=a[i];
			l[i]=l[i+n]=r[i]=r[i+n]=-1;
		}
		for(int i=1;i<=2*n;i++){
			while(tp&&a[s[tp]]<=a[i]) tp--;
			if(tp&&i-s[tp]<n) l[i]=s[tp];
			tp++;
			s[tp]=i;
		}
		tp=0;
		for(int i=2*n;i>=1;i--){
			while(tp&&a[s[tp]]>=a[i]) tp--;
			if(tp&&i-s[tp]<n) r[i]=s[tp];
			tp++;
			s[tp]=i;
		}
		tp=0;
		for(int i=1;i<=2*n;i++){
			if(l[i]==-1||r[i]==-1||r[i]-n+1>l[i]) continue;
			x=((r[i]-n+1)%n+n-1)%n+1;
			y=(l[i]%n+n-1)%n+1;
			if(x>y){
				d[n+1]--;
				d[1]++;
			}
			d[x]++;
			d[y+1]--;
		}
		for(int i=1;i<=n;i++){
			d[i]+=d[i-1];
			if(d[i]==0) ans.push_back((n-i+1)%n);
		}
		sort(ans.begin(),ans.end());
		cout<<ans.size()<<endl;
		for(int i=0;i<ans.size();i++) cout<<ans[i]<<' ';
		cout<<endl;
		ans.clear();
		ans.shrink_to_fit();
	}
    return 0;
}

T3 link $\color{#00E0A0}(4.00)$

这就是个套着组合数学外衣的换根DP板子。

首先，看到求概率就要优先考虑计算 $\frac{\text{有效方案数}}{\text{总方案数}}$。
而本题中的总方案数 $=n!\times(n-1)!$，易于计算，所以只需计算有效方案数即可。

设以 $x$ 为根的子树大小为 $s_x$，$x$ 的儿子集合为 $son_x$，生成以 $x$ 为根的子树的方案数为 $dp_x$，则

$$dp_x=(s_x-1)!\prod_{y\in son_x}\frac{dp_y}{s_y!}$$

现在通过预处理阶乘及其逆元再枚举根进行树形DP就得到了 $O\left(n^2\right)$ 做法。

等等，枚举根？这完全没必要好吗？
用上换根DP的方法，就可以做到单组数据 $O(n\log(n))$（$\log(n)$ 来自求逆元）。
于是就做完了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000007;
const ll mod=1000000007;
int t,n,x,y,siz[N];
ll f[N],invf[N],dpa[N],dpb[N],ans;
vector<int>v[N];
int QP(ll b,ll e){
	ll ret=1;
	while(e){
		if(e&1) ret=(ret*b)%mod;
		b=(b*b)%mod;
		e>>=1;
	}
	return ret;
}
void DFSx(int p,int fa){
	siz[p]=1;
	dpa[p]=1;
	for(int i=0;i<v[p].size();i++){
		int y=v[p][i];
		if(y==fa) continue;
		DFSx(y,p);
		dpa[p]=(dpa[p]*dpa[y]%mod*invf[siz[y]])%mod;
		siz[p]+=siz[y];
	}
	dpa[p]=(dpa[p]*f[siz[p]-1])%mod;
	return;
}
void DFSy(int p,int fa,int dpr){
	int rs=n-siz[p];
	dpb[p]=dpr*invf[rs]%mod;
	for(int i=0;i<v[p].size();i++){
		int y=v[p][i];
		if(y==fa) continue;
		dpb[p]=(dpb[p]*dpa[y]%mod*invf[siz[y]])%mod;
	}
	dpb[p]=(dpb[p]*f[n-1])%mod;
	for(int i=0;i<v[p].size();i++){
		int y=v[p][i];
		if(y==fa) continue;
		DFSy(y,p,dpb[p]*QP(dpa[y],mod-2)%mod*invf[n-1]%mod*f[n-siz[y]-1]%mod*f[siz[y]]%mod);
	}
	return;
}
int main(){
	f[0]=1;
	for(int i=1;i<=N-3;i++) f[i]=(f[i-1]*i)%mod;
	invf[N-3]=QP(f[N-3],mod-2);
	for(int i=N-3;i>=1;i--) invf[i-1]=(invf[i]*i)%mod;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		ans=0;
		for(int i=1;i<=n;i++){
			v[i].clear();
			v[i].shrink_to_fit();
		}
		for(int i=1;i<n;i++){
			scanf("%d%d",&x,&y);
			v[x].push_back(y);
			v[y].push_back(x);
		}
		DFSx(1,0);
		DFSy(1,0,1);
		for(int i=1;i<=n;i++) ans=(ans+dpb[i])%mod;
		ans=(ans*QP(f[n-1]*f[n]%mod,mod-2))%mod;
		printf("%lld\n",ans);
	}
	return 0;
}

T4 link $\color{#CCCCCC}(-)$

赛时用链性质+输出样例直接骗 $\color{#F04000}12$ 分跑路了。
一场比赛 $2$ 个树形DP？教练，你有多喜欢树啊……

总结与反思

wyh你必须恶补DS了，要不然同级OIer觉得简单的维护都搞不定。

彩蛋

$$998244353$$