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

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

0%

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

发表于 更新于 分类于 Valine：

今天A了5题，还算不错，但是AK的队伍好像有点多啊（

B.Boundary

题目描述

Given ${n}$ points in 2D plane. Considering all circles that the origin point ${(0, 0)}$ is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

题目分析

这道题首先可以想到使用$O(n^2)$的时间代价枚举圆（计算三点成圆的时间是$O(1)$的）
但是我们似乎只能用$O(n)$的时间去枚举圆上的点。

与题解不同的是，我们可以想到用map做所有圆的hash，自定义类记录下圆心和半径，重载一下小于符号即可。
但是map的常数过大，于是改成排序指针即可。

代码

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
106
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>

using namespace std;

const int maxn=2005;

const double eps=1e-3;

struct Point {
	double x,y;
	Point(double _x=0,double _y=0):x(_x),y(_y) {}
} a[maxn];

Point tcircle(Point pt1, Point pt2, Point pt3, double &radius) {
	double x1 = pt1.x, x2 = pt2.x, x3 = pt3.x;
	double y1 = pt1.y, y2 = pt2.y, y3 = pt3.y;
	double a = x1 - x2;
	double b = y1 - y2;
	double c = x1 - x3;
	double d = y1 - y3;
	double e = ((x1 * x1 - x2 * x2) + (y1 * y1 - y2 * y2)) / 2.0;
	double f = ((x1 * x1 - x3 * x3) + (y1 * y1 - y3 * y3)) / 2.0;
	double det = b * c - a * d;
	if( fabs(det) < eps) {
		radius = -1;
		return Point(0,0);
	}

	double x0 = -(d * e - b * f) / det;
	double y0 = -(a * f - c * e) / det;
	radius = hypot(x1 - x0, y1 - y0);
	return Point(x0, y0);
}

int dcmp(double x,double y) {
	if(fabs(x-y)<eps)return 0;
	return x<y?-1:1;
}
 
struct node {
	double x,y,r;
	node(double _x=0,double _y=0,double _r=0):x(_x),y(_y),r(_r) {}
	bool operator < (const node &b) const {
		if (fabs(r-b.r) < eps && fabs(x-b.x) < eps && fabs(y-b.y) < eps) return false;//equal
		return dcmp(r,b.r)<0||(dcmp(r,b.r)==0&&dcmp(x,b.x)<0)||(dcmp(r,b.r)==0&&dcmp(x,b.x)==0&&dcmp(y,b.y)<0);
	}
};

//map<node,int> M;
int n;
node mem[4000000];
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%lf%lf",&a[i].x,&a[i].y);
	if(n==1) {
		puts("1");
		return 0;
	}
	int memcnt = 0;
	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++) {
			double r=0;
			Point tmp=tcircle(a[i],a[j],Point(0,0),r);
			if(r==-1)continue;
			node tmpp=node(tmp.x,tmp.y,r);
			mem[memcnt++] = tmpp;
			//M[tmpp]++;
		}
	sort(mem,mem+memcnt);
	int curcnt = 0;
	int st = 0;
	int ans = 1;
	node x;
	for (int i=0;i<memcnt;i++) {
		if (i == 0) {
			curcnt = 1;
		}
		else {
			bool eq = !(mem[i] < mem[i-1]) && !(mem[i-1] < mem[i]);
			if (eq) {
				curcnt ++;
			}
			else {
				if (curcnt > ans) {
					ans = curcnt;
					x = mem[st];
				}
				curcnt = 1;
				st = i;
			}
		}
	}
	if (curcnt > ans) {
		ans = curcnt;
		x = mem[st];
	}
	if(ans==1)printf("%d\n",ans);
	else {
		int cnt=0;
		for(int i=1; i<=n; i++)if(dcmp((a[i].x-x.x)*(a[i].x-x.x)+(a[i].y-x.y)*(a[i].y-x.y),x.r*x.r)==0)cnt++;
		printf("%d\n",cnt);
	}
	return 0;
}

C.Cover the Tree

题目描述

Given an unrooted tree, you should choose the minimum number of chains that all edges in the tree are covered by at least one chain. Print the minimum number and one solution. If there are multiple solutions, print any of them.

题目分析

根据结论答案是$\lceil\frac n2\rceil$，但是题目要我们输出方案。
这里采取了和题解不同的方法。

我们从叶子结点开始处理，在每个结点处做向上传递叶子结点的操作：

  • 若本结点有奇数个子结点，随便留下一个子结点所对应的叶子结点向上传递，剩下的结点两两匹配
  • 若本结点有偶数个子结点，随便留下两个子结点所对应的叶子结点向上传递，剩下的结点两两匹配

注意，向上传递的结点尽量保证不来自同一子结点，同时匹配的时候也不能匹配来自同一子结点的两个结点

最终在根结点时把剩下的结点两两匹配完（如果剩下了一个结点，该结点与根结点匹配）
为了保证处理时不会匹配来自同一子结点的两个结点，我们边匹配边加入队列，在判断时优先匹配后加入队列，同时挑选一个度数大于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
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
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
#define mp make_pair

const int maxn=200005;

vector<pii> ans;
vector<int> edges[maxn];
int n;

pii TreeDp(int Now,int fa) {
	if(edges[Now].size()==1&&fa!=-1)return mp(Now,-1);
	vector<int> tmp;
	for(int Next:edges[Now]) {
		if(Next==fa)continue;
		pii tmpp=TreeDp(Next,Now);
		if(tmp.size()>=2) {
			ans.push_back(mp(tmp.back(),tmpp.first));
			tmp.pop_back();
		} else tmp.push_back(tmpp.first);
		if(tmp.size()>=2&&tmpp.second!=-1) {
			swap(tmp.back(),tmp[0]);
			ans.push_back(mp(tmp.back(),tmpp.second));
			tmp.pop_back();
		} else if(tmp.size()<2&&tmpp.second!=-1)tmp.push_back(tmpp.second);
	}
	if(fa==-1) {
		if(tmp.size()==2)ans.push_back(mp(tmp[0],tmp[1]));
		else ans.push_back(mp(tmp[0],Now));
	}
	if(tmp.size()==2)return mp(tmp[0],tmp[1]);
	else return mp(tmp[0],-1);
}

int main() {
	scanf("%d",&n);
	if(n==1) {
		puts("0");
		return 0;
	} else if(n==2) {
		int x,y;
		scanf("%d%d",&x,&y);
		printf("1\n%d %d\n",x,y);
		return 0;
	}
	for(int i=1; i<n; i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	for(int i=1; i<=n; i++)if(edges[i].size()>1) {
		TreeDp(i,-1);
		break;
	}
	printf("%d\n",ans.size());
	for(pii x:ans)printf("%d %d\n",x.first,x.second);
	return 0;
}

D.Duration

题目描述

Given two moments on the same day in the form of HH:MM:SS, print the number of seconds between the two moments.

题目分析

签到题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int read() {
	int res = 0;
	char c = getchar();
	while (!(c >= '0' && c <= '9')) c = getchar();
	while (c >= '0' && c <= '9') {
		res = res*10 + c - '0';
		c = getchar();
	}
	return res;
}
int gettime() {
	int h = read();
	int m = read();
	int s = read();
	m += h * 60;
	s += m * 60;
	return s;
}
int main() {
	printf("%d\n",abs(gettime() - gettime()));
	return 0;
}

F.Fake Maxpooling

题目描述

Given a matrix of size $n\times m$ and an integer ${k}$, where $A_{i,j} = lcm(i, j)$, the least common multiple of ${i}$ and ${j}$. You should determine the sum of the maximums among all $k\times k$ submatrices.

题目分析

预处理矩阵，两次滑动窗口即可。
如果$\gcd$写成线性时间复杂度的话，最终时间就是$O(nm)$。
不过带$\log$也过了

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
const int N = 5e3 + 5;
int t[N][N];
int ans[N][N];
deque<int> win(N);

// 标准的滑动窗口
void solve1(int n, int len, int *arr, int *ans) {
	win.clear();
	for(int i = 0; i < n; i ++) {
		while(!win.empty() && arr[win.back()] < arr[i])
			win.pop_back();
		while(!win.empty() && win.front() < i - len + 1)
			win.pop_front();
		win.push_back(i);
		if(i + 1 >= len)
			ans[i - len + 1] = arr[win.front()];
	}
}


int main() {
	ios::sync_with_stdio(false);
	int m, n, a, b, k;
	cin >> n >> m >> k;
	a=k;b=k;
	for(int i = 0; i < m; i ++)
		for(int j = 0; j < n; j ++)
			t[i][j]=(i+1)/__gcd(i+1,j+1)*(j+1);
	for(int i = 0; i < m; i ++)
		solve1(n, b, t[i], ans[i]);

	// 遍历每列
	// 第二次用作滑动窗口的数组是经过第一次处理后的
	int len = a;
	for(int i = 0; i < n; i ++) {
		win.clear();
		for(int j = 0; j < m; j ++) {
			while(!win.empty() && ans[win.back()][i] < ans[j][i])
				win.pop_back();
			while(!win.empty() && win.front() < j - len + 1)
				win.pop_front();
			win.push_back(j);
			if(j + 1 >= len)
				ans[j - len + 1][i] = ans[win.front()][i];
		}
	}

	long long sum=0;

	for(int i = 0; i < m - a + 1; i ++)
		for(int j = 0; j < n - b + 1; j ++)sum+=ans[i][j];
		
	printf("%lld\n",sum);
	return 0;
}

I.Interval

题目描述

There is an interval ${[1, n]}$ initially. For an interval ${[l, r]}$, if ${l < r}$, there will be two possible changes:

  • Shrinking, ${[l, r]}$ changes to ${[l + 1, r]}$ or ${[l, r - 1]}$
  • Expanding, ${[l, r]}$ changes to ${[l - 1, r]~(l > 1)}$ or ${[l, r + 1]~(r < n)}$

So, when ${l = r}$, the interval will be unable to be changed. You don’t want to see this, so you may need to ban some changing manners.
Specifically, we use tuple ${(l, r, dir, c)}$ to describe banning. If ${dir = L}$, you can ban the bidirectional changing between ${[l, r]}$ and ${[l + 1, r]}$ with cost ${c}$ while you can ban the bidirectional changing between ${[l, r]}$ and ${[l, r - 1]}$ with cost ${c}$ if ${dir = R}$.
Determine the minimum total cost to guarantee that ${l = r}$ will never happen. Print “-1” if it’s impossible to make it.

题目分析

参见官方题解：
这个题的本质就是一个网格图网络流，把每个区间$[l,r]$定到$(l,r)$的位置，其中原点就是$(1,n)$，汇点是$(n,1)$，并把所有$(i,i)$的点跟汇点连一条流量为正无穷的边即可，除此之外没有被限制的两点间也要连流量正无穷的边。
这种题一般是转对偶图然后变成最短路，具体请参考题目“狼抓兔子”。
时间复杂度$O(n^2\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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define mp make_pair
#define sqr(x) (x)*(x)
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=4000007;
const ll inf=0x3f3f3f3f3f3f3f3f;
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;
}
ll d[maxn];
int N,e1,head[maxn],to[maxn<<1],nex[maxn<<1],vis[maxn],w[maxn<<1];
void addedge(int u,int v,int x){
	++e1;nex[e1]=head[u];head[u]=e1;to[e1]=v;w[e1]=x;
}
inline void dijkstra(int s){
	for(int i=1;i<=N;++i) d[i]=inf,vis[i]=0;
	priority_queue<pair<ll,int>> q;d[s]=0;q.push(mp(0,s));
	while(!q.empty()){
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			int v=to[i];
			if(d[v]>d[u]+w[i]){
				d[v]=d[u]+w[i];
				q.push(mp(-d[v],v));
			}
		}
	}
}
int n,m;
int id(int a,int b){
	if(a==0||a==n) return n*n+1;
	else if(b==0||b==n) return n*n+2;
	return (a-1)*n+b;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		char s[4];scanf("%s",s+1);
		int x=read();
		if(s[1]=='L'){
			addedge(id(l,r-1),id(l,r),x),addedge(id(l,r),id(l,r-1),x);
		}
		else{
			addedge(id(l-1,r-1),id(l,r-1),x),addedge(id(l,r-1),id(l-1,r-1),x);
		}
	}
	N=n*n+2;
	dijkstra(n*n+1);
	printf("%lld",d[n*n+2]==inf?-1:d[n*n+2]);
	return 0;
}

J.Just Shuffle

题目描述

Given a permutation with size ${n}$ and an integer ${k}$, you should find a permutation substitution ${P}$ that $\{1, 2, \cdots, n\}$ will become ${A}$ after performing substitution ${P}$ for exactly ${k}$ times. Print the permutation after performing ${P}$ for once on $\{1, 2, \cdots, n\}$. If there are multiple solutions, print any of them. If there is no solution, print “-1” in one line.

题目分析

总之就是求置换的$-k$次幂。
$k$是质数，不可能有无解情况。
先把置换$A$拆成若干个轮换/循环/环。
假设环$i$的长度是$r_i$，因此这个环需要运算$inv_i = k−1 \pmod {r_i}$次才能还原成$P$里的环。
为了避免求逆，我们可以逆向使用计算循环$k$次幂的公式。
循环的第$j$个位置在进行$k$次幂后会出现在循环的$j\times k\bmod r_i$的位置，故可以逆向计算原来$P$中的环。
时间复杂度$O(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
#include<bits/stdc++.h>

using namespace std;

const int maxn=100005;

int n,k,cnt=0,a[maxn],pos[maxn],ans[maxn],ori[maxn],pre[maxn];
bool vst[maxn];
vector<int> vec[maxn];

void Dfs(int x) {
	vec[cnt].push_back(x);
	vst[x]=1;
	if(!vst[a[x]])Dfs(a[x]);
}

int main() {
	scanf("%d%d",&n,&k);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
		pos[a[i]]=i;
	}
	for(int i=1; i<=n; i++)if(!vst[i]) {
		cnt++;
		Dfs(i);
		int size=vec[cnt].size();
		int x=k%size;
		for(int j=0; j<size; j++)ori[j*x%size]=j;
		for(int j=0; j<size; j++)ans[vec[cnt][ori[j]]]=vec[cnt][ori[(j+1)%size]];
	}
	for(int i=1; i<=n; i++)printf("%d ",ans[i]);
	return 0;
}
相关文章
姥爷们赏瓶冰阔落吧~