补题计划-牛客周赛Round66

牛客周赛Round66

A 题

很简单，其实就是求三个数的最大值和其他两个数之和那个打，输出最大的就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
	int x,y,z;
	cin>>x>>y>>z;
	int sum = x + y + z;
	int t = max(x,max(y,z));
	cout<<max(sum - t,t);
	return 0;
}

B 题

构造题，构造一个\(p_i\)使得\(a_i = p_i + p_{p_{i}}\)，使得重新构造的数组 \(a_i\) 为一个单调不增的数列。

可以想到最简单的构造就是每一个 \(a_i\) 都是相等。很简单可以想到构造\(1 \dotsc n\) 使得 \(a_i\) 成立。

注意最后一个的输出没有空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
#include<iostream>

using namespace std;

int main()
{
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		for(int i=n;i>=1;i--)	cout<<i<<(i== 1 ? "" : " ");
		cout<<endl;
	}
	return 0;
}

C 题

可以观察到 \(n\) 非常小，只有 \(10\) 位，所以可以直接暴力枚举断点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;string s;
	cin>>T;
	while(T--){
		cin>>s;
		string ans = s;
		for(int i=1;i<s.length();i++){
			string s1 = s.substr(i) + s.substr(0,i);
			ans = min(s1,ans);
		}
		cout<<ans<<endl;
	}
	return 0;
}

D、E 题

E 题为 D 题的加强版，没有想出来。这题可以用并查集，每次操作都会使两个区间合并，就相当于并查集里的合并。

对于区间，并查集可以维护每个区间的总长度以及水量，父亲为区间的最右点。剩下的就是并查集的部分了。

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

using namespace std;
const int maxn = 200010;
long long a[maxn];
long long pa[maxn],cnt[maxn];
int n,q;

int Find(int x){return pa[x] == x ? x : Find(pa[x]);}

void unite(int x,int y){
	int fx = Find(x),fy = Find(y);
	if(fx == fy)	return;
	if(fx < fy)		swap(fx,fy);
	cnt[fx] += cnt[fy];
	a[fx] += a[fy];
	pa[fy] = fx;
}

int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
	
	for(int i=1;i<=n;i++)	pa[i] = i,cnt[i] = 1; 
	
	int opt,l,r;
	for(int i=1;i<=q;i++){
		cin>>opt;
		if(opt == 1){
			cin>>l>>r;
			for(int j=l;j<r;j++){
				unite(j,j+1);
				j = Find(j) - 1;
			}
		}
		else if(opt == 2){
			int x;
			cin>>x;
			int f = Find(x);
			printf("%.10lf\n",1.0*a[f]/cnt[f]);
		}
	}
	return 0;
}

F 题

这道题其实挺可惜的，当时补题时，想出来思路了，就是不会实现，看了题解才发现，题解实现的特别妙。

显然可以发现 \(Move(a)\) 是字典序最小的，因为 \(a\) 提到了最前面了，字典序当然最小，其他的依次变大。

如果存在两个相同的字母，那字典序的排名该怎么算呢？

如果将一个字母放到前面来，相对顺序变化的只有移到前面来的字符以及原来后面的一个字符，其他的相对顺序不变，不会影响到字典序的排名。

假定 \(s_i = a\)，a 为重复的字符。

  1. 如果 \(s_i > s_{i+1}\) : 那么是排名较小的字典序。（为什么？）因为在移动了他之后\(s_{i+1}\)的相对顺序变小了（通俗来讲就是\(s_i\)原本所在的位置被\(s_{i+1}\)替换），让其他字典序无法比它更小。
  2. 如果 \(s_i < s_{i+1}\) : 那么是排名较大的字典序。与上面的同理。
  3. 如果 \(s_i = s_{i+1}\) : 不用排名，显然与后一个相同，因为无论是移动 \(s_i\) 还是 \(s_{i+1}\)，字符串没有变化。

然后把所有排名排序，找到我们想要的那个排名字符串即可。

代码实现的非常妙，时间复杂度为 \(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
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
#include<bits/stdc++.h>
#define arank pair<int,int>

using namespace std;
int T;
const int maxn = 1000010;
int a[28],vv[maxn];

bool cmp(arank x,arank y){
	return x.second < y.second;
}

int main()
{
	cin>>T;
	while(T--){
		int n,k;string s;
		memset(a,0,sizeof(a));
		memset(vv,-1,sizeof(vv));
		cin>>n>>k>>s;
		for(int i=0;i<n;i++)
			a[s[i] - 'a'] ++;
		// cout<<s<<endl;
		int tar;
		for(int i=0;i<26;i++){
			if(k <= a[i]){
				tar = i;
				break;
			}
			k -= a[i];
		}
		
		int l = 1,r = 1e6;
		for(int i=0;i<n;i++){
			if(s[i] == tar + 'a'){
				if(i == n-1)	vv[i] = r;
				else{
					if(s[i] < s[i+1])
						vv[i] = r --;
					else if(s[i] > s[i+1])
						vv[i] = l ++;
					else
						continue;
				}
			}
		}
		
		for(int i=n-1;i>=0;i--)
			if(s[i] == tar + 'a' && vv[i] == -1)
				vv[i] = vv[i+1];
		
		vector<arank> vec;
		for(int i=0;i<n;i++){
			if(s[i] == tar + 'a')
				vec.push_back(make_pair(i,vv[i]));
		}
		sort(vec.begin(),vec.end(),cmp);
		
		for(auto it : vec){
			k --;
			if(k <= 0){
				cout<<(char)(tar + 'a');
				for(int i=0;i<it.first;i++) cout<<s[i];
				for(int i=it.first+1;i<n;i++) cout<<s[i];
				break;
			}
		}
		cout<<endl;
	}
	return 0;
}