隐藏
2020牛客暑期多校训练营（第一场）解题报告 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

2020牛客暑期多校训练营（第一场）解题报告

发表于 更新于 分类于 Valine：

今天复健赛，只过了三题，太菜了。

A. B-Suffix Array

题目描述

The BB-function $B(t_1 t_2 \dots t_k) = b_1 b_2 \dots b_k$ of a string $t_1 t_2 \dots t_k$ is defined as follows.

  • If there is an index $j < i$ where $t_j = t_i, b_i = \min_{1 \leq j < i, t_j = t_i}\{i - j\}$,
  • Otherwise, $b_i = 0$.

Given a string $s_1 s_2 \dots s_n$ , sort its $n$ suffixes into increasing lexicographically order of the BB-function.

Formally, the task is to find a permutaion $p_1, p_2, \dots, p_n$ of $\{1, 2, \dots, n\}$ such that $B(s_{p_{i - 1}} \dots s_n) < B(s_{p_{i}} \dots s_n)$ holds for $i = 2, \dots, n$.

题目分析

大概就是让你对B生成的字符串进行排序，这里有一份写的很好的题解。

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>

using namespace std;

const int maxn=200005;

namespace Suffix_Array {
	int sa[maxn],rk[maxn],fir[maxn],sec[maxn],buc[maxn],tmp[maxn],height[maxn];

	void fill_buc(int n,int *a) {
		fill(buc,buc+n+1,0);
		for(int i=1; i<=n; i++)buc[a[i]]++;
		for(int i=1; i<=n; i++)buc[i]+=buc[i-1];
	}

	void build(int n,int *a) {
		fill_buc(n,a);
		for(int i=1; i<=n; i++)rk[i]=buc[a[i]-1]+1; //calculate single alpha rank
		for(int t=1; t<=n; t<<=1) {
			for(int i=1; i<=n; i++) {
				fir[i]=rk[i]; //first key
				sec[i]=(i+t)>n?0:rk[i+t]; //second key
			}
			fill_buc(n,sec); //second key
			for(int i=1; i<=n; i++)tmp[n-(--buc[sec[i]])]=i; //tmp[i] record ith second key's position
			fill_buc(n,fir); //first key
			for(int i=1; i<=n; i++)sa[buc[fir[tmp[i]]]--]=tmp[i];
			bool unique=1;
			for(int j=1,last=0; j<=n; j++) {
				int i=sa[j];
				if(!last)rk[i]=1;
				else if(fir[i]==fir[last]&&sec[i]==sec[last])rk[i]=rk[last],unique=0;
				else rk[i]=rk[last]+1;
				last=i;
			}
			if(unique)break; //already unique
		}
	}
}

using namespace Suffix_Array;

int n,b[maxn];
string s;

struct node {
	int x,y;
	node(int _x=0,int _y=0):x(_x),y(_y) {}
	bool operator < (const node& b) const {
		if(y-x==b.y-b.x)return rk[y+1]<rk[b.y+1]; //前半部分长度相等
		else return y-x<b.y-b.x;
	}
} a[maxn];

int main() {
	while(cin>>n>>s) {
		s=' '+s;
		int x=0,y=0;
		for(int i=1; i<=n; i++)
			if(s[i]=='a') {
				if(x)b[i]=i-x;
				else b[i]=0;
				x=i;
			} else {
				if(y)b[i]=i-y;
				else b[i]=0;
				y=i;
			}
		for(int i=1; i<=n; i++)b[i]++; //腾出空位离散化
		build(n,b);
		x=y=n+1;
		for(int i=n; i>=1; i--)
			if(s[i]=='a') {
				a[i]=node(i,y);
				x=i;
			} else {
				a[i]=node(i,x);
				y=i;
			}
		rk[n+1]=-1,rk[n+2]=-2;
		sort(a+1,a+n+1);
		for(int i=1; i<=n; i++)printf("%d ",a[i].x);
		putchar('\n');
	}
	return 0;
}

D. Quadratic Form

题目描述

Bobo has a positive-definite $n \times n$ matrix $A$ and an $n$-dimension vector $b$. He would like to find $x_1, x_2, \dots, x_n$ where

  • $x_1, x_2, \dots, x_n \in \mathbb{R}$,
  • $\sum_{i = 1}^n \sum_{j = 1}^n A_{i, j} x_i x_j \leq 1$
  • $\sum_{i = 1}^n b_i x_i$ is maximum.

It can be shown that $\left(\sum_{i = 1}^n b_i x_i\right)^2 = \frac{P}{Q}$ , which is rational.

Find the value of $P \cdot Q^{-1} \bmod 998244353$.

题目分析

答案就是$b^T A^{-1} b$
用高斯约旦消元算矩阵的逆即可

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn=405,p=998244353;

int n;
LL A[maxn][maxn],tmp[maxn],B[maxn];

LL Quick_Pow(LL a,LL b) {
	LL sum=1;
	for(; b; b>>=1,a=a*a%p)if(b&1)sum=sum*a%p;
	return sum;
}

LL inv(LL x) {return Quick_Pow(x,p-2);}

LL Gauss_Jordan(int n,int m) {
	LL r=1;
	for(int i=1; i<=n; i++) {
		int row=i;
		for(; row<=n; row++)if(A[row][i])break;
		if(row>n)continue;
		if(row!=i) {
			for(int j=1; j<=m; j++)swap(A[i][j],A[row][j]);
			r=(p-r)%p;
		}
		r=r*A[i][i]%p;
		LL t=inv(A[i][i]);
		for(int j=1; j<=m; j++)A[i][j]=A[i][j]*t%p;
		for(int j=1; j<=n; j++)
			if(j!=i) {
				t=A[j][i];
				for(int k=1; k<=m; k++)A[j][k]=(A[j][k]-t*A[i][k]%p+p)%p;
			}
	}
	return r;
}

int main() {
	while(scanf("%d",&n)!=EOF) {
		memset(A,0,sizeof(A));
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++) {
				scanf("%lld",&A[i][j]);
				A[i][j]=(A[i][j]+p)%p;
			}
		for(int i=1; i<=n; i++)A[i][i+n]=1;
		Gauss_Jordan(n,n<<1);
		for(int i=1; i<=n; i++) {
			scanf("%lld",&B[i]);
			B[i]=(B[i]+p)%p;
		}
		LL ans=0;
		for(int i=1; i<=n; i++) {
			tmp[i]=0;
			for(int j=1; j<=n; j++)tmp[i]=(tmp[i]+B[j]*A[i][j+n]%p)%p;
			ans=(ans+tmp[i]*B[i]%p)%p;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

E. Counting Spanning Trees

题目描述

Bobo has a bipartite graph with $(n + m)$ vertices $x_1, x_2, \dots, x_n$ and $y_1, y_2, \dots, y_m$.

The vertex $x_i$ is connected to the first $a_i$ vertices in $Y$, namely $y_1, \dots, y_{a_i}$.

Given $n, m, a_1, \dots, a_n$ and $\mathrm{mod}$, find the number of spanning trees of the graph modulo $\mathrm{mod}$.

题目分析

将结点度数从大到小排序，生成数个数就是$\prod_{i >= 2}^n deg(x_i) \prod_{i >= 2}^m deg(y_i)$

代码

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
39
40
41
42
43
#include<bits/stdc++.h>

using namespace std;

const int maxn=100005;

long long da[maxn],db[maxn];
int n,m,mod;

struct BIT {
	int c[maxn];
#define lowbit(x) (x&(-x))
	void init() {
		fill(c,c+m+1,0);
	}
	void add(int x,int v) {
		for(int i=x; i>=1; i-=lowbit(i))c[i]+=v;
	}
	int query(int x) {
		int ans=0;
		for(int i=x; i<=m; i+=lowbit(i))ans+=c[i];
		return ans;
	}
} bit;

int main() {
	ios::sync_with_stdio(false);
	while(cin>>n>>m>>mod) {
		bit.init();
		for(int i=1; i<=n; i++) {
			cin>>da[i];
			bit.add(da[i],1);
		}
		for(int i=1; i<=m; i++)db[i]=bit.query(i);
		sort(da+1,da+n+1,greater<int>());
		sort(db+1,db+m+1,greater<int>());
		long long ans=1;
		for(int i=2; i<=n; i++)ans=ans*da[i]%mod;
		for(int i=2; i<=m; i++)ans=ans*db[i]%mod;
		printf("%lld\n",ans);
	}
	return 0;
}

F. Infinite String Comparision

题目描述

For a string $x$, Bobo defines $x^\infty = x x x \dots$, which is $x$ repeats for infinite times, resulting in a string of infinite length.

Bobo has two strings $a$ and $b$. Find out the result comparing $a^\infty$ and $b^\infty$ in lexicographical order.

You can refer the wiki page for further information of Lexicographical Order.

题目分析

两个串对应$\gcd$的位置必须相同，否则两个串就不同，如果不同暴力比较即可。

代码

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
#include<bits/stdc++.h>
  
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	string a,b;
	while(cin>>a>>b) {
		int lena=a.length(),lenb=b.length(),posa=0,posb=0;
		int gcd=__gcd(lena,lenb);
		long long lcm=1LL*lena/gcd*lenb;
		bool flag=0;
		for(int i=0; i<lena; i++) {
			if(a[i%gcd]!=a[i]) flag=1;
		}
		for(int i=0;i<lenb;i++){
			if(a[i%gcd]!=b[i]) flag=1;
		}
		if(flag==0) {
			puts("=");
		} else {
			for(int i=0; i<lcm; i++) {
				if(a[posa]<b[posb]) {
					puts("<");
					break;
				} else if(a[posa]>b[posb]) {
					puts(">");
					break;
				}
				posa++;
				posb++;
				if(posa==lena)posa=0;
				if(posb==lenb)posb=0;
			}
		}
	}
	return 0;
}

H. Minimum-cost Flow

题目描述

Bobo has a network of $n$ nodes and $m$ arcs. The $i$-th arc goes from the $a_i$-th node to the $b_i$-th node, with cost $c_i$.

Bobo also asks $q$ questions. The $i$-th question is specified by two integers $u_i$ and $v_i$, which is to ask the minimum cost to send one unit of flow from the $1$-th node to the $n$-th node, when all the edges have capacity $\frac{u_i}{v_i}$ (a fraction).

You can refer the wiki page for further information of Minimum-cost Flow.

题目分析

这道题非常机智，可惜我考试的时候没想到是队友想到的。
定义费用流$cost(c,f)$表示容量为$c$，流量为$f$时的费用流总费用。

这样我们就可以把分数容量转化为相对的分数流量，跑网络流就轻松多了。
我们用EK费用流，每次留一个单位的流量，记录下每个单位流量所花费的费用，即可根据不同的询问计算不同的费用，跑一次费用流即可。

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>

using namespace std;

const int maxn=405;

typedef long long LL;

struct Edge {
	LL from,to,cap,flow,cost;
	Edge(LL x=0,LL y=0,LL c=0,LL f=0,LL co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

LL per[maxn];

struct MinimumCost_MaximumFlow { //EK Edition
	int n,m;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool inque[maxn];
	LL a[maxn],dist[maxn];
	int path[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,LL v,LL f) {
		edges.push_back(Edge(x,y,v,0,f));
		edges.push_back(Edge(y,x,0,0,-f));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bellmanford(int s,int t,LL& flow,LL& cost) {
		for(int i=1; i<=n; i++)dist[i]=LLONG_MAX/2;
		queue<int> Q;
		Q.push(s);
		dist[s]=path[s]=0;
		a[s]=LLONG_MAX/2;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			inque[Now]=0;
			for(int id:G[Now]) {
				Edge& e=edges[id];
				int Next=e.to;
				if(e.cap>e.flow&&dist[Next]>dist[Now]+e.cost) {
					dist[Next]=dist[Now]+e.cost;
					path[Next]=id;
					a[Next]=min(a[Now],e.cap-e.flow);
					if(!inque[Next]) {
						Q.push(Next);
						inque[Next]=1;
					}
				}
			}
		}
		if(dist[t]==LLONG_MAX/2)return false;
		flow+=a[t];
		cost+=dist[t]*a[t];
		for(int Now=t; Now!=s; Now=edges[path[Now]].from) {
			edges[path[Now]].flow+=a[t];
			edges[path[Now]^1].flow-=a[t];
		}
		return true;
	}
	LL maxflow(int s,int t,LL& cost) {
		LL flow=0;
		cost=0;
		while(bellmanford(s,t,flow,cost))per[flow]=cost;
		return flow;
	}
} mcmf;

void printFrac(LL u,LL d) {
	printf("%lld/%lld\n",u/__gcd(u,d),d/__gcd(u,d));
}

int n,m,q;

int main() {
	while(scanf("%d%d",&n,&m)!=EOF) {
		mcmf.init(n);
		for(int i=1; i<=m; i++) {
			LL x,y,v;
			scanf("%lld%lld%lld",&x,&y,&v);
			mcmf.AddEdge(x,y,1,v);
		}
		LL cost=0;
		LL flow=mcmf.maxflow(1,n,cost);
		scanf("%d",&q);
		for(int i=1; i<=q; i++) {
			LL u,v;
			scanf("%lld%lld",&u,&v);
			if(flow*u<v) {
				puts("NaN");
				continue;
			}
			LL intt=v/u;
			printFrac(per[intt]*u+(intt==flow?0:(per[intt+1]-per[intt])*(v-intt*u)),v);
		}
	}
	return 0;
}

I. 1 or 2

题目描述

Bobo has a graph with $n$ vertices and $m$ edges where the $i$-th edge is between the vertices $a_i$ and $b_i$. Find out whether is possible for him to choose some of the edges such that the $i$-th vertex is incident with exactly $d_i$ edges.

题目分析

拆点拆边
对于两边度数都为2的边$e(x,y)$，拆成以下5条边：

  • $(x, e) (x’, e)$
  • $(y, e’) (y’, e’)$
  • $(e, e’)$

然后跑带花树即可

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100007;
int head[maxn],nex[maxn],to[maxn],n;
int mate[maxn],link[maxn],vis[maxn], fa[maxn];
int que[maxn],hd,tl,e1;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
void addedge(int u,int v) {
	++e1;nex[e1]=head[u];head[u]=e1;to[e1]=v;
}
int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int LCA(int x,int y){
	static int ss[maxn],tim;
	++tim;
	while(ss[x]!=tim){
		if(x) {ss[x]=tim;x=find(link[mate[x]]);}
		swap(x,y);
	}
	return x;
}
void Flower(int x,int y,int p){
	while(find(x)!=p){
		link[x]=y;
		fa[y=mate[x]]=(fa[x]=p);
		if(vis[y]==1) vis[que[++tl]=y]=2;
		x=link[y];
	}
}
bool match(int x) {
	hd=1;tl=0;
	for(int i=1;i<=n;i++) vis[fa[i]=i]=0;
	vis[que[++tl]=x]=2;
	while(hd<=tl){
		x=que[hd++];
		for(int i=head[x];i;i=nex[i]) {
			int u=to[i];
			if(!vis[u]){
				vis[u]=1;
				link[u]=x;
				if(!mate[u]){
					while(x){
						x=mate[link[u]];
						mate[mate[u]=link[u]]=u;
						u=x;
					}
					return true;
				}else vis[que[++tl]=mate[u]] = 2;
			}else if(vis[u]==2&&find(u)!=find(x)) {
				int p=LCA(x,u);
				Flower(x,u,p);
				Flower(u,x,p);
			}
		}
	}
	return false;
}
int d[maxn],ans;
void init(){
	for(int i=1;i<=n;i++) head[i]=mate[i]=0;
	e1=ans=0;
}
void add(int u,int v){
	addedge(u,v);addedge(v,u);
	if(!mate[u]&&!mate[v])
	mate[mate[u]=v]=u,++ans;
}
int main(){
	int nn,m;
	while(scanf("%d%d",&nn,&m)==2){
		n=nn*2+m*2;
		init();
		int tot=0;
		for(int i=1;i<=nn;i++) d[i]=read(),tot+=d[i];
		for(int i=1;i<=m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,nn*2+i);
			if(d[u]==2) add(nn*2+i,u+nn);
			add(v,nn*2+m+i);
			if(d[v]==2) add(nn*2+m+i,v+nn);
			add(nn*2+i,nn*2+m+i);
		}
		for(int i=1;i<=n;++i)
		if(!mate[i]&&match(i)) ++ans;
		if(tot%2==0&&ans==m+tot/2) printf("Yes\n");
		else printf("No\n");
	  //  for (int i = 1; i <= n; ++i)
	//	printf("%d ",mate[i]);
	}
	return 0;
}

J. Easy Integration

题目描述

Given $n$, find the value of $\int_{0}^1 (x - x^2)^n \mathrm{d} x$

It can be proved that the value is a rational number $\frac{p}{q}$.

Print the result as $(p \cdot q^{-1}) \bmod 998244353$.

题目分析

答案是$\frac{(n!)^2}{(2n+1)!}$

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
const long long mo = 998244353;
long long fac[maxn];
long long qpow(long long a,long long b) {
	long long res = 1;
	while (b) {
		if (b & 1) {
			res *= a;
			res %= mo;
		}
		a *= a;
		a %= mo;
		b >>= 1;
	}
	return res;
}
long long inv(long long x) {
	return qpow(x,mo-2);
}
int main() {
	fac[1] = 1;
	for (int i=2;i<maxn;i++) fac[i] = (fac[i-1] * i) % mo;
	long long n;
	while (scanf("%lld",&n) == 1) {
		long long ans = fac[2 * n + 1];
		ans = (ans * qpow(inv(fac[n]),2)) % mo;
		printf("%lld\n",inv(ans));
	}
	return 0;
}
相关文章
姥爷们赏瓶冰阔落吧~