牛客挑战赛35

发表于 分类于

牛客挑战赛35

A

签到题，用最大的匹配最小的，次大的匹配次小的…

但是手速还是过于慢了…花了 $2\min$ 才AC此题。

B

题意

给一个图 $G_1$，$G_i=L(G_{i-1})$，$L(G)$ 表示 $G$ 的线图。

当 $n$ 无穷大时，求 $|G_n|$ 的值。发散时输出 $-1$。

$n\leq 10^5,m\leq 2\times 10^5$

题解

显然我们可以只考虑一个连通块的情况。

下面证明几个性质：

性质1

如果存在两个环有共同的点，那么 $|G_n|$ 发散。

证明

因为共享点，因此必然存在某个点的度数至少为3，求一次线图就至少多一个环，因此环数会一直变多，因此发散。

性质2

若连通块是一个环，就不能再往里加边加点形成连通块。否组答案发散。

证明

对该图求一次线图，变成性质1的情况。

因此边数大于点数的连通块都不可行。

边数等于点数的连通块只能是环。

下面考虑树的情况：

性质3

除了一个4个点菊花图，所有出现度数大于等于3的点都会使得答案发散。

证明

求一次线图，变成性质2的情况或者更坏。

因此只需判断每个连通块是否为4个点的菊花，一条链，一个环的情况即可。

时间复杂度 $O(n)$

C

题意

现在给出长度为 $n$ 的置换 $F$，求所有长度为 $n$ 且字典序严格大于 $F$ 的置换的循环节个数之和模 $998244353$。

$n\leq 2\times 10^5$

题解

很显然地，我们考虑固定前 $i-1$ 位，第 $i$ 位可以选和第 $p_i$ 位以后的点相连。

一条还没有成环的链可以看成一个点。

设 $p_i$ 后面一共有 $w$ 个可连的点/链，有 $p$ 个在之前已经成环的环，那么大概就会有三种情况对答案产生贡献：

第一种是直接已经成环的，此时产生 $wp\times (n-i)!$ 的贡献。

第二种是未成环的，此时产生 $w\times f(n-i)$ 的贡献，其中 $f(i)$ 表示所有长度为 $i$ 的置换的循环节个数之和，这个可以 $O(n)$ 算出来。

第三种是自环，产生 $(n-i)!$ 的贡献。

那么用树状数组维护 $w$ ，并查集维护链即可。

时间复杂度$O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define N 200010
int n;
ll f[N],ans;
ll fac[N],inv[N];
void init(int n)
{
	fac[0]=1;
	fo(i,1,n) fac[i]=fac[i-1]*i%mod;
	inv[n]=Pow(fac[n],mod-2);
	fd(i,n,1) inv[i-1]=inv[i]*i%mod;
}
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int Bit[N];
inline void add(int x){for(;x;x-=lowbit(x)) Bit[x]++;}
inline int ask(int x,int ans=0){for(;x<=n;x+=lowbit(x)) ans+=Bit[x]; return ans;}
int main()
{
	n=read();
	init(n);
	fo(i,1,n) f[i]=(fac[i-1]+f[i-1]*i)%mod;
	fo(i,1,n) fa[i]=i;
	int p=0,s=0,w=0,x,y;
	fo(i,1,n)
	{
		x=read();
		y=find(i);
		w=n-x-ask(x);
		if(y>x) ans=Add(ans,fac[n-i]);
		ans=Add(ans,Mul(Mul(w,p),fac[n-i]));//已成环的
		ans=Add(ans,Mul(f[n-i],w));//未成环的
		add(x);
		if(find(i)==x) p++;
		else fa[x]=i;
	}
	printf("%d",ans);
	return 0;
}

D

题意

懒得写了…

题解

将S串01反转后，去掉前导0的集合记为 $A$，将集合 $A$ 里01反转后不去掉前导0的集合记为 $B$。可以发现，当且仅当字符串 $t$ 由这两个集合里的字符串拼接而成才合法。

也就是说，从 $t$ 的后缀开始匹配，需要满足 $s,t$ 的某后缀相匹配，要么全相等，要不全不相等，且 $s$ 的这个后缀的第一个字符和前面一个字符不相等。

$O(n^2)$ DP一下就好了。

E

感觉是全场第2简单的题…

题意

$n$ 个点的树复制 $k$ 遍，变成一个森林。在这个森林里加 $m$ 条边变成一个图。只有一次询问，问某两个点间最短路，边权为 $1$。

$n\leq 2\times 10^5,m,k\leq 50000$

题解

虚树+Dijkstra即可。