A. Portal ↬\looparrowright

题目描述

You are now in a big factory. The factory could be recognized as a graph with n vertices and m edges. Every edge has its length. You have kk missions to do. The ii-th mission is going to vertex aia_i, picking a block and then sending it to vertex bib_i. You should complete the missions in the order from 11-st to kk-th. Initially you are standing at vertex 11.
You have a gun in your hand. When you are at some vertex uu, you could shoot the gun at the ground, and then a portal will be built at vertex uu. When there are two portals in the factory, assuming they are at uu and vv, you could transfer between uu and vv with no cost (just like an edge connecting uu and vv with length 00).
You also have a remote controller in your hand. It allows you to close a portal whenever you want and wherever you are (closing one portal at a time, not all portals at the same time). What’s more, there could be at most two existing portals. So if you want to create another portal when there exists two, you must use your controller to close one before you create.
You need to find the minimum distance you have to walk in order to complete all kk missions.

输入描述

First line contains three positive integers n,m,kn, m, k separated by spaces.
Next mm lines, each contains three integers ui,vi,wiu_i, v_i, w_i, indicating a bidirectional edge connecting vertex uiu_i and viv_i with length wiw_i.
Next kk lines, each contains two intergers ai,bia_i, b_i, indicating the begin and the end of the ii-th mission.
1⩽n⩽3001 \leqslant n \leqslant 300, 1⩽m⩽400001 \leqslant m \leqslant 40000, 1⩽k⩽3001 \leqslant k \leqslant 300.
1⩽ui,vi⩽n1 \leqslant u_i, v_i \leqslant n, 0⩽wi⩽1090 \leqslant w_i \leqslant 10^9.
1⩽ai,bi⩽n1 \leqslant a_i, b_i \leqslant n.
The graph is guaranteed to be connected.

输出描述

Output one integer indicating the minimum distance.

示例1

输入

1
2
3
4
5
6
7
5 4 2
1 2 1
2 3 1
3 4 1
4 5 1
1 5
2 4

输出

1
5

说明

Solution for sample 11: walk from 11 to 55, create portals at 22 and 44 when passing by, and then walk from 55 to 44, then you could use portals to complete the second mission.

示例2

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
6 10 3
1 1 6
5 6 9
3 5 8
1 4 1
2 4 7
6 6 10
1 4 2
6 5 10
3 5 2
3 1 9
1 5
2 5
4 3

输出

1
28

示例3

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
6 10 3
1 1 3
3 1 1
6 2 3
1 6 10
4 1 1
3 1 2
5 6 9
5 4 10
6 3 4
3 4 4
3 5
3 6
6 5

输出

1
16

分析

用动态规划求解。
f(i,u,x,y)f(i,u,x,y) 表示已经完成了第 ii 个任务，当前人在节点 uu，传送门在节点 xx 和 yy 时，行走的最短距离。状态过多，显然会 MLE\text{MLE} 和 TLE\text{TLE}。
贪心地思考，一直创建两个传送门是没有必要的：若要从 xx 传送到 yy，当前节点为 uu，那么必须要从 uu 走到 xx 再传送到 yy；不妨只在 yy 创建一个传送门，走到 xx 后再设置传送门；也就是说，我们可以随时在当前节点创建传送门。因此，只需要在状态中记录一个传送门的位置即可。f(i,u,p)f(i,u,p) 表示已经完成了第 ii 个任务，当前人在节点 uu，传送门在节点 pp 时，行走的最短距离。需要继续精简状态。
不妨将 kk 个任务看作一条路径：1→a1→b1→⋯→an→bn1\to a_1\to b_1\to\cdots\to a_n\to b_n。一共有 t=2k+1t=2k+1 个节点，cic_i 表示第 ii 个节点，其中 1⩽i⩽t1\leqslant i\leqslant t。f(i,p)f(i,p) 表示当前人位于节点 cic_i，传送门位于节点 pp 时，行走的最短距离。
可以证明，只需要三种转移，即可覆盖所有状态：① 直接从 ci−1c_{i-1}走到 cic_i，不更改传送门位置；② 枚举 qq，将传送门的位置更改到 qq，从 ci−1c_{i-1} 传送到 pp，再从 pp 走到 qq，将传送门放在 qq，再从 qq 走到 cic_i；③ 枚举 qq，将传送门的位置更改到 qq，从 ci−1c_{i-1} 走到 qq，将传送门放在 qq，再从 qq 传送到 pp，从 pp 走到 cic_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
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
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem A
Date: 8/24/2020
Description: Dynamic Programming
*******************************************************************/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=705;
//====================
//f[i][j]表示：
// 当前在c[i]，传送门在j时；
// 行走的最小路程。
ll f[N][N];
ll dis[N][N];
int c[N];
int n,m;
int t;
int main(){
	int i,j,k;
	cin>>n>>m>>k;
	memset(f,inf,sizeof(f));
	memset(dis,inf,sizeof(dis));
	for(i=1;i<=n;i++) dis[i][i]=0;
	for(i=1;i<=m;i++){
		int u,v;
		ll w;
		scanf("%d%d%lld",&u,&v,&w);
		dis[u][v]=min(dis[u][v],w);
		dis[v][u]=min(dis[v][u],w);
	}
	c[++t]=1;
	for(i=1;i<=k;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		c[++t]=a;
		c[++t]=b;
	}
	//Floyed算法求(x,y)之间的最短路
	for(k=1;k<=n;k++){
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
			}
		}
	}
	for(i=1;i<=n;i++){
		//初始化
		//当前在c[1]
		//传送门设置在i
		f[1][i]=dis[1][i];
	}
	int p,q;
	for(i=2;i<=t;i++){
		//当前在c[i-1]，要走向c[i]
		for(p=1;p<=n;p++){
			//当前传送门在p
			//不改变传送门位置，直接走到 c[i]
			f[i][p]=min(f[i][p],f[i-1][p]+dis[c[i-1]][c[i]]);
			for(q=1;q<=n;q++){
				//从c[i-1]传送到p，路程0
				//从p走到q，路程dis[p][q]
				//从q走到a[i]，路程dis[q][c[i]]
				f[i][q]=min(f[i][q],f[i-1][p]+dis[p][q]+dis[q][c[i]]);
				//从c[i-1]走到q，路程dis[c[i-1]][q]
				//从q传送到p，路程为0
				//从p走到c[i]，路程dis[q][c[i]]
				f[i][q]=min(f[i][q],f[i-1][p]+dis[c[i-1]][q]+dis[p][c[i]]);
			}
		}
	}
	ll ans=inf;
	for(i=1;i<=n;i++){
		ans=min(f[t][i],ans);
	}
	cout<<ans<<endl;
	return 0;
}

B. Graph ↬\looparrowright

题目描述

Mr. W got a new graph with nn vertices and n−1n- 1 edges. It’s a connected graph without cycles. Each edge should have an ugly value. To make the graph more beautiful, Mr. W hope you can help him modify it. You can delete or add one edge with an ugly value at a time and you can do it as many times as you want. But the following conditions should be satisfied at any time. The graph is connected. For each cycles in the graph, the XOR sum of all ugly values in the cycle is 00.
Mr. W wants to know the minimum sum of ugly values of all edges in the graph.

输入描述

The first line contains one integer n (2⩽n⩽100000)n\ (2 \leqslant n \leqslant 100000).
Next n−1n - 1 lines each contains three integers u,v,wu,v,w (0⩽u,v<n,0⩽w<230)(0 \leqslant u,v < n, 0 \leqslant w < 2^{30}), denoting an edge between vertex uu and vv with ugly value ww.

输出描述

One integer, the minimum sum of ugly values of all edges in the graph.

示例1

输入

1
2
3
4
5
6
6
0 1 1
1 2 4
1 3 3
0 4 5
0 5 2

输出

1
7

分析

可以发现任意两个点之间连边的权值都是固定的。由于图始终连通，所以两点间始终存在至少一条路径，如果存在多条，根据环的异或和为 00，两点间的路径的异或和应该相等，且始终是固定的。在初始状态，设根节点（设为 11）到节点 ii 路径的异或和为 disidis_i，那么若要在 x,yx,y 之间添加一条边，为满足环的异或和为 00，其边权必须为 disx⊕disydis_x\oplus dis_y。
可以视为：nn 个节点的完全图中，节点 ii 的点权为 disidis_i，两点间的边权为两点权的异或值接下来。如此一来，预处理点权 disidis_i 后，就转化为求解异或最小生成树的问题，可以参考异或最小生成树模板题：CF888G。

代码

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem B
Date: 8/20/2020
Description: Minimum XOR Spanning Tree
*******************************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200004;
struct E
{
	int to;
	int w;
	int Next=-1;
}edge[N<<1];
ll ans=0;
int n;
bool vis[N];
int trie[N*30][2];
int head[N];
int dis[N];
int tot;
int num;
void bfs();//预处理dis
inline void add_edge(int,int,int);
//=================================
//异或最小生成树模板
void insert(int);
void dfs(int,int);
ll f(int,int,int);
//=================================
int main(){
	int i;
	cin>>n;
	memset(head,-1,sizeof(head));
	for(i=1;i<=n-1;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		u++;
		v++;
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	bfs();
	//init(1,0);
	for(i=1;i<=n;i++){
		insert(dis[i]);
	}
	dfs(0,30);
	cout<<ans<<endl;
	return 0;
}
void bfs(){
	queue<int>q;
	q.push(1);
	vis[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(register int i=head[x];~i;i=edge[i].Next){
			int y=edge[i].to;
			if(vis[y]){
				continue;
			}
			vis[y]=1;
			q.push(y);
			dis[y]=dis[x]^edge[i].w;
		}
	}
}
void insert(int x){
	int p=0;
	for(register int i=30;i>=0;i--){
		int ch=(x>>i)&1;
		if(!trie[p][ch]){
			trie[p][ch]=++tot;
		}
		p=trie[p][ch];
	}
}
void dfs(int p,int bit){
	if(bit<0){
		return;
	}
	if(trie[p][0]&&trie[p][1]){
		ans+=f(trie[p][0],trie[p][1],bit-1)+(1<<bit);
	}
	if(trie[p][0]){
		dfs(trie[p][0],bit-1);
	}
	if(trie[p][1]){
		dfs(trie[p][1],bit-1);
	}
}
ll f(int p1,int p2,int bit){
	if(bit<0){
		return 0;
	}
	ll res1=-1,res2=-1;
	if(trie[p1][0]&&trie[p2][0]){
		res1=f(trie[p1][0],trie[p2][0],bit-1);
	}
	if(trie[p1][1]&&trie[p2][1]){
		res2=f(trie[p1][1],trie[p2][1],bit-1);
	}
	if(res1>=0&&res2>=0){
		return min(res1,res2);
	}
	if(res1>=0){
		return res1;
	}
	if(res2>=0){
		return res2;
	}
	if(trie[p1][0]&&trie[p2][1]){
		res1=f(trie[p1][0],trie[p2][1],bit-1)+(1<<bit);
	}
	if(trie[p1][1]&&trie[p2][0]){
		res2=f(trie[p1][1],trie[p2][0],bit-1)+(1<<bit);
	}
	if(res1>=0&&res2>=0){
		return min(res1,res2);
	}
	if(res1>=0){
		return res1;
	}
	if(res2>=0){
		return res2;
	}
}
inline void add_edge(int u,int v,int w){
	num++;
	edge[num].to=v;
	edge[num].w=w;
	edge[num].Next=head[u];
	head[u]=num;
}

D. Drop Voicing ↬\looparrowright

题目描述

Inaka composes music. Today’s arrangement includes a chord of nn notes that are pairwise distinct, represented by a permutation p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n of integers from 11 to nn (inclusive) denoting the notes from the lowest to the highest.
Her friend, Miyako, sneaks in and plays a trick by altering the chord with the following two operations. Drop-2\text{Drop-2}: Take out the second highest note and move it to the lowest position, i.e. change the permutation to pn−1,p1,p2,⋯ ,pn−3,pn−2,pnp_{n-1}, p_1, p_2, \cdots, p_{n-3}, p_{n-2}, p_n. Invert: Take out the lowest note and move it to the highest position, i.e. change the permutation to p2,p3,…,pn−1,pn,p1p_2, p_3, \dots, p_{n-1}, p_n, p_1.
Any number of consecutive Drop-2\text{Drop-2} operations is considered a multi-drop. Miyako would like to change the permutation to an ordered permutation, 1,2,⋯ ,n1, 2, \cdots, n, in the fewest number of multi-drops\text{multi-drops} possible. Please help her find the number of multi-drops\text{multi-drops} needed.

输入描述

The first line contains an integer nn (2⩽n⩽500)(2 \leqslant n \leqslant 500) — the number of notes.
The second line contains n space-separated integers p1,p2,⋯ ,pnp_1, p_2, \cdots, p_n — the original permutation of notes.
The input guarantees each integer from 11 to nn (inclusive) appears in the permutation exactly once.

输出描述

Output one integer — the number of multi-drops\text{multi-drops} required to change the permutation to an ordered one.

示例1

输入

1
2
6
2 4 5 1 3 6

输出

1
2

说明

An optimal solution with two multi-drops is:
Invert\text{Invert}, 55 times, changing the permutation to 6,2,4,5,1,36,2,4,5,1,3;
Drop-2\text{Drop-2}, 33 times, changing the permutation to 4,5,1,6,2,34,5,1,6,2,3;
Invert\text{Invert}, 44 times, changing the permutation to 2,3,4,5,1,62,3,4,5,1,6;
Drop-2\text{Drop-2}, 11 time, changing the permutation to 1,2,3,4,5,61,2,3,4,5,6.

示例2

输入

1
2
8
8 4 7 3 6 2 5 1

输出

1
5

分析

对于操作 Drop-2\text{Drop-2}，可以将 p1∼pn−1p_1\sim p_{n-1} 看作一个环，环的长度为 n−1n-1，即进行 n−1n-1 次操作 Drop-2\text{Drop-2}，排列还原；对于操作 Invert\text{Invert}，可以将 p1∼pnp_1\sim p_n 看作一个环，环的长度为 nn，即进行 nn 次操作 Invert\text{Invert}，排列还原。形成的两个环如图所示，√\color{red}\surd 代表当前排列 pp 的第一个数，×\color{red}\times 代表位于大环（长度为 nn 的环）上，而在小环（长度为 n−1n-1 的环）外的数。
2020牛客暑期多校训练营（第五场）D1.png
小环和大环可以独立顺时针转动，两个指针 ×\color{red}\times 和 √\color{red}\surd 的位置是固定不动的；当转动小环，视为进行了一次 multi-drops\text{multi-drops}，当转动大环，视为进行多次 Invert\text{Invert}。可以发现，当转动小环，可以将位于小环外的数字，插入任意两个数字之间。在图中，当前 66 位于 33 和 22 之间，转动一次小环，66 就在 11 和 33 之间了；显然，进行一次 multi-drops\text{multi-drops}，可以将 66 放入任何你想要的位置。更一般的，若要该边数字 xx 在大环中的相对其他数字位置，应该首先用多次 Invert\text{Invert} 将 xx 放入 ×\color{red}\times 标记的位置，然后进行一次 multi-drops\text{multi-drops}。我们要对大环上的数字进行排序，那么只需要通过若干次操作，利用小环调整一些数字的相对位置，令大环上形成 1→2→⋯→n→1→⋯1\to2\to\cdots\to n\to 1\to\cdots 这样的环，再进行几次 Invert\text{Invert} 即可将原序列 pp 完成排序。
那么问题就变得简单：每次调整一个数的位置就要进行一次 multi-drops\text{multi-drops}，因此要调整尽可能少的数字。不妨找出大环上的一个 LIS\text{LIS}（最长上升子序列），其长度为 lenlen；对于在 LIS\text{LIS} 上的 lenlen 个数字不作调整，只需要调整 n−lenn-len 个数字的相对位置；显然，这样的方案使得需要调整的数字个数最小。对于不在 LIS\text{LIS} 上的 n−lenn-len 个数字，用 n−lenn-len 次 multi-drops\text{multi-drops} 和若干次 Invert\text{Invert}，即可将这 n−lenn-len 个数字一一放入正确的位置，完成排序。
计算环上的 LIS\text{LIS} 长度时，可以枚举环的起点，对 nn 个起点各求一次 LIS\text{LIS}，取长度最大的即可。时间复杂度为 O(n2log⁡n)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
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem D
Date: 8/20/2020
Description: Circle, LIS
*******************************************************************/
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=504;
int n;
int p[N];
int a[N];
int dp[N];
int main(){
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++){
		scanf("%d",p+i);
	}
	int ans=0x3f3f3f3f;
	//枚举环的起点
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			//环确定了起点为i
			//于是可以环拉成链
			a[j]=p[i+j-1-n*(i+j-1>n)];
		}
		//求LIS
		int len=1;
		dp[1]=a[1];
		for(j=2;j<=n;j++){
			if(a[j]>dp[len]){
				dp[++len]=a[j];
			}else{
				*lower_bound(dp+1,dp+1+len,a[j])=a[j];
			}
		}
		ans=min(n-len,ans);//最小调整次数
	}
	cout<<ans<<endl;
	return 0;
}

E. Bogo Sort ↬\looparrowright

题目描述

Today Tonnnny the monkey learned a new algorithm called Bogo Sort. The teacher gave Tonnnny the code of Bogo sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
bool is_sorted(int a[], int n) {
	for (int i = 1; i < n; i++) {
		if (a[i] < a[i - 1]) {
			return false;
		}
	}
	return true;
}
void bogo_sort(int a[], int n){
	while (!is_sorted(a, n)){
		shuffle(a, a + n);
	}
}

The teacher said the shuffle function is to uniformly randomly permute the array with length , and the algorithm’s expectation complexity is O(n⋅n!)O(n \cdot n!).
However, Tonnnny is a determined boy — he doesn’t like randomness at all! So Tonnnny improved Bogo Sort. He had chosen one favorite permutation with length , and he replaced the random shuffle with shuffle of , so the improved algorithm, Tonnnny Sort, can solve sorting problems for length array — at least Tonnnny thinks so.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int p[N]={....};// Tonnnny's favorite permutation of n
void shuffle(int a[],int n){
	int b[n];
	for (int i=0;i<n;i++){
		b[i]=a[i]
	}
	for (int i=0;i<n;i++) {
		a[i]=b[p[i]];
	}
}
void tonnnny_sort(int a[], int n){
	assert (n == N); // Tonnnny appointed!
	while (!is_sorted(a, n)){
		shuffle(a, a + n);
	}
}

Tonnnny was satsified with the new algorithm, and decided to let you give him a different array of length every day to sort it with Tonnnny Sort.
You are the best friend of Tonnnny. Even though you had found the algorithm is somehow wrong, you want to make Tonnnny happy as long as possible. You’re given N,pN,p, and you need to calculate the maximum number of days that Tonnnny will be happy, since after that you can’t give Tonnnny an array that can be sorted with Tonnnny Sort and didn’t appeared before.
The answer may be very large. Tonnnny only like numbers with at most digits, so please output answer mod 10N10^N instead.

输入描述

The first line contains one integer N (1⩽N⩽105)N\ (1 \leqslant N \leqslant 10^5).
The second line contains integer indicating , which forms a permutation of 1,2,⋯ ,N1, 2, \cdots, N.

输出描述

The maximum number of days that Tonnnny will be happy, module 10N10 ^ N.

示例1

输入

1
2
5
1 2 3 4 5

输出

1
1

示例2

输入

1
2
6
2 3 4 5 6 1

输出

1
6

分析

在 Tonnnny Sort\text{Tonnnny Sort} 的 shuffle function\text{shuffle function} 中，有操作 ai=bpia_i=b_{p_i}，实际上是用置换 pp 将原序列 aa 映射到当前的序列 aa。如 p=[3,5,4,1,2]p=[3,5,4,1,2]，那么就有：a1=b3a_1=b_3，a3=b4a_3=b_4，a4=b1a_4=b_1，形成了 3→1→4→3→⋯3\to 1\to4\to3\to\cdots 的闭环，即 a1,a3,a4a_1,a_3,a_4 三者的值进行了交换；同理，有 5→2→5→⋯5\to2\to5\to\cdots 这样的闭环。
问题转化为：给定置换 pp，求多少种排列可以通过置换 pp 完成排序。不妨考虑将排序后的序列 aa 用置换 pp 打乱会产生多少种不同序列。设排序后的序列为 a=[a1,a2,⋯ ,an]a=[a_1,a_2,\cdots,a_n]，pp 有 mm 个环，且各个环的长度为 c1,c2,⋯ ,cmc_1,c_2,\cdots,c_m，显然，利用置换 pp 进行 lcm(c1,c2,⋯ ,cm)\mathrm{lcm}(c_1,c_2,\cdots,c_m) 次 shuffle function\text{shuffle function}，aa 回到最初排完序的状态，而每次操作后得到的序列都是不同的。因此，只要找出置换 pp 所有的环，所有环长的最小公倍数即为答案。
值得注意的是，数据范围较大，可以使用 Java\text{Java} 的 BigInteger\text{BigInteger} 类。并且，所有环的长度总和为 nn，所以所有环的长度的最小公倍数不可能超过 10n10^n，因此最后不必煞费苦心地将答案对 10n10^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
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem E
Date: 8/20/2020
Description: Group Theory, BigInteger
*******************************************************************/
import java.math.BigInteger;
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		final int N=100005;
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		BigInteger[] cycle=new BigInteger[N];//环长度
		boolean[] vis=new boolean[N];
		int[] p=new int[N];
		int m=0;
		int i;
		for(i=1;i<=n;i++){
			p[i]=in.nextInt();
		}
		for(i=1;i<=n;i++){
			int len=0;
			int pos=i;
			while(!vis[pos]){
				//遍历环
				//记录访问
				len++;
				vis[pos]=true;
				pos=p[pos];
			}
			if(len>0) cycle[++m]=BigInteger.valueOf(len);
		}
		BigInteger ans=cycle[1];
		//求环长度的最大公约数
		for(i=2;i<=m;i++){
			ans=cycle[i].multiply(ans).divide(cycle[i].gcd(ans));
		}
		System.out.println(ans);
	}
}

F. DPS ↬\looparrowright

题目描述

When you are playing multiplayer games, you may want to show that you are the MVP of your team or blame the one always wandering and watching away from the storm center. Well, there’re statistics that show you preformance, but sometimes numbers speak softer than charts. Now, you’re hired to write a program that output ASCII art histograms showing damage dealt to enemies.
There are nn players in the game. Given that the ii-th player dealt did_i damage to enemies where max⁡1⩽i⩽ndi>0\max\limits_{1\leqslant i\leqslant n} d_i > 0 is granted, you need to calculate the number sis_i of spaces in the bar by the following foluma: si=⌈50dimax⁡1⩽i⩽ndi⌉s_i = \left\lceil 50 \frac {d_i} {\max\limits_{1\leqslant i\leqslant n} d_i} \right\rceil. Instead of formal definition of bar description, we will give an example. For some player i whose si=7s_i = 7 and di=777d_i = 777, the bar is shown as:

1
2
3
+-------+
|       |777
+-------+

Moreover, you have to mark the player with maximal damage dealt to enemies by replacing the last space into *. If there’re multiple maximum, mark all of them.
See samples for more ideas.

输入描述

The first line contains one integer n (1⩽n⩽100)n\ (1 \leqslant n \leqslant 100).
The next nn line each contains one integer, the ii-th line contains did_i (0⩽di⩽43962200)(0 \leqslant d_i \leqslant 43962200).
It’s granted that max⁡1⩽i⩽ndi>0\max\limits_{1\leqslant i\leqslant n}d_i>0.

输出描述

3n3n lines, each 33 lines denote a bar in the correct format.

示例1

输入

1
2
3
4
5
4
50
40
50
0

输出

1
2
3
4
5
6
7
8
9
10
11
12
+--------------------------------------------------+
|                                                 *|50
+--------------------------------------------------+
+----------------------------------------+
|                                        |40
+----------------------------------------+
+--------------------------------------------------+
|                                                 *|50
+--------------------------------------------------+
++
||0
++

示例2

输入

1
2
3
4
5
6
5
1676
4396
2200
443
556

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
+--------------------+
|                    |1676
+--------------------+
+--------------------------------------------------+
|                                                 *|4396
+--------------------------------------------------+
+--------------------------+
|                          |2200
+--------------------------+
+------+
|      |443
+------+
+-------+
|       |556
+-------+

分析

按照题意模拟即可。
需要注意细节：计算 sis_i 时会爆 int\text{int}；最大值在直方图中要作出标记；did_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
44
45
46
47
48
49
50
51
52
53
54
55
56
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem F
Date: 8/16/2020
Description: Simulation
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=105;
int n;
ll d[N];
bool is[N];
int s[N];
int main(){
	ll MAX=-1;
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++){
		scanf("%lld",&d[i]);
		MAX=max(d[i],MAX);
	}
	for(i=1;i<=n;i++){
		is[i]=d[i]==MAX;//是最大值
		s[i]=ceil(50.0/MAX*d[i]);
	}
	for(i=1;i<=n;i++){
		//第一行
		putchar('+');
		for(j=1;j<=s[i];j++){
			putchar('-');
		}
		putchar('+');
		putchar('\n');
		//第二行
		putchar('|');
		for(j=1;j<=s[i]-is[i];j++){
			putchar(' ');
		}
		if(is[i]) putchar('*');
		putchar('|');
		printf("%lld\n",d[i]);
		//第三行
		putchar('+');
		for(j=1;j<=s[i];j++){
			putchar('-');
		}
		putchar('+');
		putchar('\n');
	}
	return 0;
}

I. Hard Math Problem ↬\looparrowright

题目描述

You are a player of the game Mine Craft. As a lawful goo?d player, instead of dropping TNT everywhere you want to build your village on a vast plain.
The game map could be recognized as a rectangle grid. In one grid, you can set up a gold miner, or an elixir collector, or a headquarter. You also can leave some grids green and vibrant.
However, one restriction for some good reasons is that a headquarter must be next to at least one gold miner and at least one elixir collector. Next to means that their grids share one side, every grid is next to up, down, left, and right grids.
“Efficiency!” A good old man said to you. You, the vast plain holder, want to be the most efficient player in the server. You want to maximize the number of headquarters in your village. Formally, If the village is a grid of size n×mn \times m, we define the max number of headquarters can be built as . For example, since there should be at least 33 grids for setting up a headquarter; and one possible solution is (G,H,E,G,H,E)(G,H,E,G,H,E).
To prove that you really understand the problem very well, print the efficiency on the infinite plain. Formally, you need to calculate lim⁡n→∞m→∞f(n,m)nm\lim\limits_{n\to\infty\atop m\to\infty} \frac{f(n,m)}{nm}.

输入描述

No input.

输出描述

A real number denoting the answer to the question. Round the answer to 66 decimal places. For example, if your answer is 0.1234567890.123456789, print 0.1234570.123457.

分析

用 △\triangle 代表总部，√\surd 代表黄金矿工，×\times 代表圣水收集器，如图的结构能够使总部的数量尽量多。
牛客第五场签到.jpg
对于一个无穷网络，一个单元已经用虚线框出。一个总部分到 12\frac{1}{2} 个黄金矿工和 12\frac{1}{2} 个圣水收集器。一个单元所占格子数量为 32\frac{3}{2}，一个总部占整个单元的 23≈0.666667\frac{2}{3}\approx0.666667。

代码

PHP是世界上最好的语言!

1
0.666667