发表更新ICPC/CCPC / Contests / 其他11 分钟读完 (大约1699个字)

2020牛客暑期多校训练营（第五场）

比赛链接

收获

  • 比赛要把所有题都看一遍——即便是那些很少人过的题（队友最后 10min 才发现会做 $A$ 题……）
  • 学会了一个求 $\text{MST}$ 的新姿势——$\textbf{Boruvka}$ 算法

A Portal

先鸽一会儿……

B Graph

设 $dis[i]$ 表示 $i$ 号节点到根的路径上所有权值的异或，那么连上的边 $(u,v)$ 的权值等于形成的环中其它边的异或值，也就等于 $dis[u]\text{ XOR }dis[v]$，所以问题转化为：$n$ 个值，两两连边的权值为 $dis[a]\text{ XOR }dis[b]$，求最小生成树。

这就和 $\text{CF888G}$ 一毛一样啊……采用 $\textbf{Boruvka}$ 算法的思想，在 $\text{Trie}$ 树上进行合并。

B.cpp
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int INF = 2e9;
const int N = 100005;

int n, dis[N];
LL ans;

vector<pii> edge[N];
void dfs(int x, int f, int xorval){
	dis[x] = xorval;
	for(auto &to : edge[x]){
		if(to.first == f)	continue;
		dfs(to.first, x, xorval ^ to.second);
	}
}

inline int get(int val, int k){ return (val >> k) & 1; }

struct Trie{
	int son[2], val;
	Trie(){ son[0] = son[1] = 0, val = -1; }
}tr[N*20];
int tot;
void insert(int val){
	int now = 0;
	for(int i = 30; i >= 0; i--){
		if(!tr[now].son[get(val, i)])
			tr[now].son[get(val, i)] = ++tot;
		now = tr[now].son[get(val, i)];
	}
	tr[now].val = val;
}
int getMin(int now, int val, int k){
	if(k == -1)	return tr[now].val ^ val;
	if(!tr[now].son[get(val, k)])
		return	getMin(tr[now].son[!get(val, k)], val, k-1);
	else	return getMin(tr[now].son[get(val, k)], val, k-1);
}

void dfs(int now, vi &v){
	if(tr[now].val != -1){
		v.pb(tr[now].val);
		return;
	}
	if(tr[now].son[0])	dfs(tr[now].son[0], v);
	if(tr[now].son[1])	dfs(tr[now].son[1], v);
}

void getAns(int x, int dep){
	if(tr[x].son[0])	getAns(tr[x].son[0], dep - 1);
	if(tr[x].son[1])	getAns(tr[x].son[1], dep - 1);
	if(tr[x].son[0] && tr[x].son[1]){
		vi v; dfs(tr[x].son[0], v);
		int mn = 2e9;
		for(auto &val : v){
			int res = getMin(tr[x].son[1], val, dep - 1);
			mn = min(mn, res | (1 << dep));
		}
		ans += mn;
	}
}

int main(){
	read(n);
	for(int i = 1; i < n; i++){
		int u, v, w; read(u, v, w); u++, v++;
		edge[u].pb(mp(v, w)), edge[v].pb(mp(u, w));
	}
	dfs(1, 0, 0);
	for(int i = 1; i <= n; i++)	insert(dis[i]);
	getAns(0, 30);
	printf("%lld\n", ans);
	return 0;
}

C Easy

队友做的，生成函数。

D Drop Voicing

题目可以转换成：一次操作为任意选一个数插入到任意一个位置，求最少多少次操作使序列有序（可以是转动后有序）。

可以预想到，把最长上升子序列求出来，其他数插入到该在的位置是最好的方案，操作数为 $n$ 减去 $\text{LIS}$ 的长度。由于可以转动，我们需要求转出来的 $n$ 个序列的 $\text{LIS}$。

复杂度：$O(n^2\lg n)$

D.cpp >folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 505;

int dp[N];
int LIS(int n, vector<int> &a){
	memset(dp, 0, sizeof dp); // dp[i]: a substring whose length is i ends at dp[i]
	int len = 0;
	for(int i = 1; i <= n; i++){
		if(a[i] >= dp[len])	dp[++len] = a[i];
		else{
			int p = upper_bound(dp+1, dp+len+1, a[i]) - dp;
			dp[p] = a[i];
		}
	}
	return len;
}

int n, p[N];

int main(){
	read(n);
	for(int i = 1; i <= n; i++)	read(p[i]);
	int ans = 1e9;
	for(int i = 1; i <= n; i++){
		vi t(n+5);
		int tid = 0;
		for(int j = i; j <= n; j++)	t[++tid] = p[j];
		for(int j = 1; j < i; j++)	t[++tid] = p[j];
		ans = min(ans, n - LIS(n, t));
	}
	printf("%d\n", ans);
	return 0;
}

E Bogo Sort

根据 $p$ 序列可以得到若干个环，答案就是所有环的长度的 $\text{lcm}$。需要高精度。

E.cpp >folded
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
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

const int N = 100005;

int n, p[N], a[N], mx;
bool vis[N];

struct BigNum{
	vector<int> a; // a[n-1]...a[1]a[0]
	int neg;

	BigNum(){ a.clear(); neg = 1; }
	explicit BigNum(const string &s){
		a.clear();
		int len = s.length();
		for(int i = 0; i < len; i++)
			a.pb(s[len-i-1] - '0');
	}
	explicit BigNum(LL num){
		a.clear();
		do{
			a.pb(num % 10);
			num /= 10;
		}while(num);
	}

	BigNum operator = (const string &s){ return *this = BigNum(s); }
	BigNum operator = (LL num){ return *this = BigNum(num); }

	bool operator < (const BigNum &b) const{
		if(a.size() != b.a.size())	return a.size() < b.a.size();
		for(int i = a.size() - 1; i >= 0; i--)
			if(a[i] != b.a[i])
				return a[i] < b.a[i];
		return false;
	}
	bool operator > (const BigNum &b) const{ return b < *this; }
	bool operator <= (const BigNum &b) const{ return !(*this > b); }
	bool operator >= (const BigNum &b) const{ return !(*this < b); }
	bool operator != (const BigNum &b) const{ return (*this > b) || (*this < b); }
	bool operator == (const BigNum &b) const{ return !(*this < b) && !(*this > b); }

	BigNum operator + (const BigNum &b) const{
		BigNum C;
		int x = 0;
		for(int i = 0, g = 0; ; i++){
			if(g == 0 && i >= a.size() && i >= b.a.size())	break;
			x = g;
			if(i < a.size())	x += a[i];
			if(i < b.a.size())	x += b.a[i];
			C.a.pb(x % 10);
			g = x / 10;
		}

		if(C.a.size() > n)	C.a.resize(n);
		
		return C;
	}
	BigNum operator * (const BigNum &b) const{
		BigNum C;
		C.a.resize(a.size() + b.a.size());
		for(int i = 0; i < a.size(); i++){
			int g = 0;
			for(int j = 0; j < b.a.size(); j++){

				if(i + j >= n)	break;

				C.a[i+j] += a[i] * b.a[j] + g;
				g = C.a[i+j] / 10;
				C.a[i+j] %= 10;
			}
			if(i + b.a.size() < n)
				C.a[i+b.a.size()] = g;
		}
		while(C.a.size() > 1 && C.a.back() == 0)	C.a.pop_back();

		if(C.a.size() > n)	C.a.resize(n);
		
		return C;
	}
	BigNum operator += (const BigNum &b){ *this = *this + b; return *this; }
	BigNum operator *= (const BigNum &b){ *this = *this * b; return *this; }

};

ostream& operator << (ostream &out, const BigNum &b){
	string res;
	if(b.neg == -1)	res += '-';
	for(int i = b.a.size() - 1; i >= 0; i--)
		res += b.a[i] + '0';
	return out << res;
}
istream& operator >> (istream &in, BigNum &b){
	string str;
	if(in >> str)   b = str;
	return in;
}

int main(){
	// freopen("E_data.in", "r", stdin);
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++)	cin >> p[i], mx = max(mx, p[i]);
	for(int i = 1; i <= n; i++){
		int now = i, len = 0;
		if(vis[now])	continue;
		while(!vis[now]){
			vis[now] = true;
			len++;
			now = p[now];
		}
		for(int i = 2; 1ll * i * i <= len; i++){
			if(len % i)	continue;
			int cnt = 0;
			while(len % i == 0)	len /= i, cnt++;
			a[i] = max(a[i], cnt);
		}
		if(len > 1)	a[len] = max(a[len], 1);
	}
	BigNum ans(1ll);
	for(int i = 1; i <= mx; i++)
		for(int j = 1; j <= a[i]; j++)
			ans *= BigNum(i);
	cout << ans << '\n';
	return 0;
}

F DPS

签到题，注意开 long long（为此 WA 了两发，呜呜呜～）

F.cpp >folded
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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 105;

int n;
LL d[N], mxd = -1, s[N];

int main(){
	read(n);
	for(int i = 1; i <= n; i++){
		read(d[i]);
		mxd = max(mxd, d[i]);
	}
	for(int i = 1; i <= n; i++){
		s[i] = 50ll * d[i] / mxd;
		while(s[i] * mxd < 50ll * d[i])	s[i]++;

		putchar('+'); for(int k = 1; k <= s[i]; k++) putchar('-'); putchar('+'); puts("");

		putchar('|'); for(int k = 1; k < s[i]; k++)	putchar(' ');
		if(s[i] > 0)	putchar(d[i] == mxd ? '*' : ' ');
		putchar('|'); printf("%lld\n", d[i]);
		
		putchar('+'); for(int k = 1; k <= s[i]; k++) putchar('-'); putchar('+'); puts("");
	}
	return 0;
}

I Hard Math Problem

答案就是 $\frac{2}{3}$，构造如下：

I.py >folded
1
print(0.666667)

2020牛客暑期多校训练营（第五场）

http://xyfjason.github.io/blog-xcpc/2020/07/25/2020牛客暑期多校训练营（第五场）/

作者

xyfJASON

发布于

2020-07-25

更新于

2021-08-28

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×