AtCoder Regular Contest 162

【题解】AtCoder Regular Contest 162

A.Ekiden Race

题目描述：

有 $n$ 个人参加了往返赛跑，每个人有一个编号 $1$ 到 $n$。已知以下信息：

• 如果按照往路的成绩排序，那么任何两个人的成绩都不相同。同时第 $i$ 个人在往路中排名第 $i$。
• 如果按照往返的成绩排序，那么任何两个人的成绩都不相同。同时第 $i$ 个人在往返中排名第 $p_i$。
• 如果復路的成绩最快，那么获得復路奖的人是復路成绩最快的人。

请计算有多少人可能得到了復路奖项。

有 $T$ 个测试用例，请对于每个测试用例输出答案。

(翻译者注：往路指来回的第一段路程，復路指来回的第二段路程。)

$2 \le n \le 10^3$

题目分析：

如果 $a$ 在第一段路快于 $b$，而经过了第二段路之后 $a$ 慢于 $b$，则必然有 $a$ 第二段路慢于 $b$。
否则无法确定 $a,b$ 的第二段路的快慢，也就是可以直接认为 $a,b$ 都有可能。
直接这样判就可以了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		int n;scanf("%d",&n);
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		int ans = n+1;
		int tot = 0;
		for(int i=n; i>=1; i--){
			if(a[i] < ans)	++tot;
			ans = min(ans,a[i]);
		}
		printf("%d\n",tot);
	}
	return 0;
}

B.Insertion Sort 2

题目描述：

给定 $1,2,...,N$ 的排列 $P=(P_1,P_2,...,P_N)$。

最多进行 $2\times 10^3$ 次操作，每次操作满足 $1\le i\le N-1, 0\le j\le N-2$，选取整数 $i,j$，从 $P$ 中取出 $(P_i,P_{i+1})$ 得到序列 $Q=(Q_1,Q_2,...,Q_{N-2})$，则将 $P$ 中 $(P_i,P_{i+1})$ 替换成序列 $Q$ 的 $j$ 与 $j+1$ 位置上的数，得到新的排列 $P'$。

判断是否能够通过这样的操作使 $P$ 变成升序排列，如果可以，给出操作步骤。
$2\ \leq\ N\ \leq\ 10^3$

题目分析：

一个显然的想法就是一个个数地确定，也就是先把 $1$ 通过操作放到第一个，然后 $2$ 放到第二个然后依次类推。
但是现在的有的一个问题就是如果我们现在要放 $x$，但是 $x$ 是序列中的最后一个数就做不了这个操作了，可是我们可以做类似如下的操作：$(n-2,n-1,n)$ $\to$ $(n-1,n,n-2)$ 这样 $P_n$ 就不在最后了，我们就可以操作它了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
vector<pair<int,int> > v;
int n,a[N],b[N];
void solve(int pos1,int pos2){
	if(!(1 <= pos1 && pos1 <= n-1))	return;
	if(!(0 <= pos2 && pos2 <= n-2))	return;
	v.push_back({pos1,pos2});
	int tot = 0;
	if(tot == pos2)	b[++tot] = a[pos1],b[++tot] = a[pos1+1];
	for(int i=1; i<=n; i++){
		if(i == pos1 || i == pos1 + 1)	continue;
		b[++tot] = a[i];
		if(tot == pos2)	b[++tot] = a[pos1],b[++tot] = a[pos1+1];
	}
	for(int i=1; i<=n; i++)	a[i] = b[i];
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
	for(int i=1; i<=n; i++){
		if(a[i] == i)	continue;
		if(a[n] == i)	solve(n-1,n-3);
		int pos = i;
		for(int j=i+1; j<=n; j++){
			if(a[j] == i)	pos = j;
		}
		if(pos > i)	solve(pos,i-1);
	}
	if(a[n] != n)	printf("No\n");
	else{
		printf("Yes\n");
		printf("%d\n",(int)v.size());
		for(auto i : v)	printf("%d %d\n",i.first,i.second);
	}
	return 0;
}

C.Mex Game on Tree

题目描述：

有一棵 $n$ 个节点且以 $1$ 为根的数。

每个节点上有一个数表示颜色。

• 如果为 $-1$，表示没有填颜色。
• 否则，表示填的颜色。

$\text{Alice}$ 和 $\text{Bob}$ 轮流对没填颜色的节点填上 $0$ 到 $n$（$\text{Alice}$ 先手）。

填完后，如果某个点和它的子树颜色的 $\mathrm{mex}$ 为 $k$，$\text{Alice}$ 胜，否则为 $\text{Bob}$。

$2\ \leq\ N\ \leq\ 10^3$

题目分析：

BoB 的策略十分显然，就是填 $k$，所以只要让 Bob 走一步，那么 Alice 之前的所有布局就全没用了。
因为是考虑某一个子树，所以不妨对每一棵子树都求一下是不是可以使得它的 $\mathrm{mex}$ 为 $k$。
因为我们对每一棵子树都考虑了，所以若 Alice 走两步可以让某个子树变成合法，要么就是那棵子树走一步就可以合法，要么就是受到前一步的影响，而第二种情况显然 Bob 可以直接堵掉 Alice 的第二步，就结束了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
int n,k,cnt,head[N],a[N];
bool vis[N],ans;
vector<int> v;
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void get_val(int now,int fath){
	v.push_back(a[now]);
	for(int i=head[now]; i; i=e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		get_val(to,now);
	}
}
void dfs(int now,int fath){
	for(int i=head[now]; i; i=e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs(to,now);
	}
	
	get_val(now,fath);
	int flag = 0;
	for(auto i : v){
		if(i == -1){
			flag++;
			continue;
		}
		vis[i] = true;
	}
	int tmp = 0;
	while(vis[tmp])	++tmp;
	if(flag && tmp < k){
		++tmp;
		while(vis[tmp])	++tmp;
	}
	if(tmp == k && flag <= 1)	ans = true;
	for(auto i : v){
		if(i != -1)	vis[i] = false; 
	}
	v.clear();
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		for(int i=2; i<=n; i++){
			int fa;scanf("%d",&fa);
			add_edge(fa,i);add_edge(i,fa);
		}
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		dfs(1,0);
		if(ans)	printf("Alice\n");
		else	printf("Bob\n");
		cnt = 0;
		for(int i=1; i<=n; i++)	head[i] = 0;
		ans = false;
	}
	return 0;
}

D.Smallest Vertices

题目描述：

在本问题中，当我们提到有根有向树时，我们指的是所有边都指向从根到叶子的有根树。

给定一个使得其总和为 $N-1$ 的非负整数序列 $d=(d_1,d_2,\ldots,d_N)$。

对于带编号从 $1$ 到 $N$ 的顶点，假设 $1$ 是根，我们将其点度数定义为 $d_i$。

我们称满足以下条件的根付有向树为好树：

• 点 $i$ 的出度是 $d_i$。

此外，对于好树的顶点 $v$，定义 $f(v)$ 为“包含顶点 $v$ 的子树中的顶点（包括 $v$）的顶点编号的最小值”。我们将满足 $f(v)=v$ 的顶点称为好顶点。

求好树中所有好顶点的总数，将其对 $998244353$ 取模后的余数。

• $2\ \leq\ N\ \leq\ 500$
• $0\ \leq\ d_i\ \leq\ N-1$
• $d_1\ \geq\ 1$
• $\sum_{i=1}^N\ d_i\ =\ N-1$

题目分析：

显然可以考虑对于每一个点作为好节点的方案数求和就是答案。

若 $v = 1$ 或 $d_v = 0$，则任意一个好树都是合法的，这个时候根据 $prufer$ 序列，显然方案数就是：

$$\dfrac{(n-2)!}{\prod_{u} (d_{1,u}-1)!}$$

其中 $d_{i,j}$ 表示以 $i$ 为根的时候 $j$ 的度数。
否则的话，考虑以 $v$ 为根的子树只能包含 $[v,n]$ 这些点，但是好像除了这个就发现不了什么式子了，就不大能做。
所以不妨设 $S$ 为 $v$ 子树内的点的点集，看看这个时候的方案数是什么：

$$\dfrac{(|S|-2)!}{\prod\limits_{u\in S} (d_{v,u}-1)!} \times \dfrac{(n-|S|+1-2)!}{\prod\limits_{u\not\in S}(d_{1,u}-1)!} = \dfrac{(|S|-2)!(n-|S|-1)!d_1d_v}{\prod\limits_u (d_u!)}$$

第一个式子就是考虑 $v$ 的子树的方案数，乘以其余点构成一棵树的方案数，其中在其余点构成的树中 $v$ 所在子树充当一个叶子。
第二个式子就是考虑如下的事实：

$$d_{i,j} = \begin{cases} d_j & i = j \\ d_j+1 & i \not= j \end{cases}$$

所以带入就得到了第二个式子。
注意为了可以组成一棵树，一个隐形的限制就是：$\sum\limits_{u \in S} d_u = |S| - 1$。
所以此时 $dp$ 状态就相当显然了，$dp[i][j][k]$ 表示大于等于 $i$ 的点，选择了 $j$ 个点，$d_u$ 之和为 $k$ 的方案数。
这样就可以直接统计方案数，然后乘以上面的系数就可以得到答案。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505;
const int MOD = 998244353;
int f[N][N][N],d[N],fac[N],inv[N];
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
void add(int &a,int b){
	a = (a + b) % MOD;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%lld",&n);
	fac[0] = 1;
	for(int i=1; i<=n; i++)	fac[i] = fac[i-1] * i % MOD;
	inv[n] = power(fac[n],MOD-2);
	for(int i=n-1; i>=0; i--)	inv[i] = inv[i+1] * (i+1) % MOD;
	for(int i=1; i<=n; i++)	scanf("%lld",&d[i]);
	f[n+1][0][0] = 1;
	for(int i=n; i>=1; i--){
		for(int j=0; j<=n; j++){
			for(int k=0; k<=n; k++){
				add(f[i][j][k],f[i+1][j][k]);
				if(j-d[i]>=0&&k-1>=0)	add(f[i][j][k],f[i+1][j-d[i]][k-1]);
			}
		}
	}
	int tmp = fac[n-2];
	for(int i=1; i<=n; i++){
		if(i == 1)	tmp = tmp * inv[d[i]-1] % MOD;
		else tmp = tmp * inv[d[i]] % MOD;
	}
	int mul = 1,ans = 0;
	for(int i=1; i<=n; i++)	mul = mul * inv[d[i]] % MOD;
	for(int i=1; i<=n; i++){  //统计 i 为好节点的贡献 
		if(i == 1 || d[i] == 0){
			add(ans,tmp);
//			printf("%lld %lld\n",i,tmp);
			continue;
		}
		for(int j=1; j<=n; j++){  //枚举 [i,n] 选择了多少个节点 
			int sum_d = j - 1;
			if(sum_d-d[i]>=0 && j-1>=0 && j-2>=0 && n-j-1>=0)
				add(ans,f[i+1][sum_d-d[i]][j-1] * d[1] %MOD* d[i] %MOD* fac[j-2] %MOD* fac[n-j-1]%MOD * mul%MOD);
		}
//		printf("%lld %lld\n",i,ans);
//		ans = 0;
	}
	printf("%lld\n",ans);
	return 0;
}

E.Strange Constraints

题目描述：

给定长度为 $n$ 的序列 $A$，求序列 $B$ 的个数模 $998244353$，满足以下条件：

• 值域 $[1, n]$。
• $i$ 的个数不超过 $A_i$。
• $B_i$ 的个数不超过 $A_i$。

$1 \le n \le 500$。

题目分析：

考虑设 $d_i$ 表示数 $i$ 出现的次数，则题目条件可以转化为：

• $d_i \le A_i$
• 若 $i$ 可以放在位置 $j$，则必然满足 $d_i \le A_j$

设 $c_i = \sum_{j=1}^n [i \le A_j]$，则 $c_i$ 就代表出现次数为 $i$ 的数可选的种类数，以及出现次数为 $i$ 的数在 $B$ 中可以放的位置数。
所以这个东西直接 $dp$ 去做就很简单了，也就是设 $dp[i][j][k]$ 表示考虑了出现次数大于等于 $i$ 的数，总共选择了 $j$ 种数，放在 $B$ 的 $k$ 个位置上。
转移就是枚举出现次数等于 $i$ 的数有 $x$ 个：

$$dp[i+1][j][k] \times \binom{c_i-j}{x} \times \dfrac{(c_i-k)!}{(i!)^x(c_i-k-ix)!} \to dp[i][j+x][k+ix]$$

转移的两个系数：第一个就是选择哪些数，第二个就是这些数放在哪些位置。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505;
const int MOD = 998244353;
int f[N][N][N],fac[N],inv[N],a[N],c[N];
int binom(int n,int m){
	if(n < m || n < 0 || m < 0)	return 0;
	return fac[n] * inv[m] % MOD * inv[n-m]%MOD;	
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
void add(int &a,int b){
	a = (a + b)%MOD;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%lld",&n);
	fac[0] = 1;
	for(int i=1; i<=n; i++)	fac[i] = fac[i-1] * i % MOD;
	inv[n] = power(fac[n],MOD-2);
	for(int i=n-1; i>=0; i--)	inv[i] = inv[i+1] * (i+1) % MOD;
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	for(int i=0; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(a[j] >= i)	c[i]++;
		}
	}
	f[n+1][0][0] = 1;
	for(int i=n; i>=1; i--){
		for(int j=0; j*i<=n; j++){
			if(j > c[i])	break;
			for(int k=0; k<=n; k++){
				if(k > c[i])	break;
				for(int x=0; x*i<=n; x++){
					if(k + i * x > c[i])	break;
					if(j+x<=n && k+i*x<=n && c[i]-j>=0 && c[i]-k>=0 && c[i]-k-i*x>=0)
						add(f[i][j+x][k+i*x],f[i+1][j][k] * binom(c[i]-j,x) %MOD* fac[c[i]-k] %MOD* power(inv[i],x) %MOD* inv[c[i]-k-i*x]%MOD);
				}
			}
		}
	}
	int ans = 0;
	for(int i=1; i<=n; i++)	add(ans,f[1][i][n]);
	printf("%lld\n",ans);
	return 0;
}