第十三届蓝桥杯国赛真题训练

2022年蓝桥杯国赛真题

A小蓝于钥匙：

  • 思路：主要在于C14 28的求解以及错排的求解。错排是一种基于推导可以得出的dp,D[n] = (n-1)*(D[n-1]+D[n-2])
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define int long long
using namespace std;
int ans = 1;
int d[20];
signed main() {
    int cnt = 2;
    for(int i = 15; i <= 28; i++){
    	ans = ans * i;
    	while(ans % cnt == 0 && cnt <= 14){
    		ans /= cnt;
    		cnt++;
		}
	}
	d[2] = 1;
	d[3] = 2;
	for(int i = 3; i <= 14; i++){
		d[i] = 1ll*(i-1) *(d[i-1] + d[i-2]);
	}
	cout<<ans*d[14]<<endl;
    return 0;
}
  • 总结：要理解清楚题意，搞清概念，学习了错排这一算法

B排列距离：

  • 思路：康托展开，从0开始编号，全排列的字符串中某一个的编号是ai*f[len-1-i],ai表示后面小于当前数字的个数，f数组表示阶乘。注意最终比较大小时的边界问题。
  • 代码：
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
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 20;
int f[21];
void jie_cheng(int n){
	f[0] = f[1] = 1;
	for(int i = 2; i <= n; i++){
		f[i] = i * f[i-1];
	}
	return;
}
int kangtuo(string str){
	int len = str.length();
	int ans = 1;
	for(int i = 0; i < len; i++){
		int tmp = 0;
		for(int j = i + 1; j < len; j++){
			if(str[i] > str[j]) tmp++;
		}
		ans += tmp * f[len-1-i];
	}
	return ans;
}
signed main()
{
	jie_cheng(N);
	int s1 = kangtuo("aejcldbhpiogfqnkr");
	int s2 = kangtuo("ncfjboqiealhkrpgd");
	int ans = min(s2-s1,f[17]-(s2-s1));
	cout<<ans<<endl;

	
	return 0;
}

C内存空间：

  • 思路：模拟题，主要考验字符串的处理，逐行输入，采用getline(cin, s)。另外，cin>>t之后要getchar()取走一个换行符。先分好类，再逐个实现，并不难。
  • 代码：
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
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int t, ans, a[4];
string s, mp[4] = {"GB", "MB", "KB", "B"};

void solve1(){
	int m, num = 0;
	if(s[0] == 'i') m = 4;
	else m = 8;
	for(int i = 0; i < s.length(); i++){
		if(s[i] == '='){
			num ++;
		}
	}
	ans += num*m;
	return;
}
void solve2(){
	int m;
	if(s[0] == 'i') m = 4;
	else m = 8;
	for(int i = 0; i < s.length(); i++){
		if(s[i] == '['){
			int num = 0;
			for(int j = i + 1; s[j] != ']'; j++){
				num = num * 10 + (s[j]-'0');
			}
			ans += m*num;
		}
	}
	return;
}
void solve3(){
	for(int i = 0; i < s.length(); i++){
		if(s[i] == '"' && s[i-1] == '='){
			for(int j = i + 1; s[j] != '"'; j++){
				ans++;
			}
		}
	}
}
signed main()
{
	cin>>t;
	getchar();
	while(t--){
		getline(cin, s);
		if((s[0] == 'i' && s[3] == '[')|| (s[0] == 'l' && s[4] == '[')){
			solve2();
		}else if (s[0] == 'S'){
			solve3();
		}else{
			solve1();
		}
	}
	int cur = 4;
	while(ans){
		a[--cur] = ans % 1024;
		ans /= 1024;
	}
	for(int i = 0; i <= 3; i++){
		if(a[i]){
			cout<<a[i]<<mp[i];
		}
	}
	return 0;
}

D最大公约数：

暴力：
  • 思路：有一个1就好办了，所以没有1的话就找最短的一个范围[a,b]内的数的gcd为1，需要进行b-a次出现一个1，然后就是加上n-1次，所有数都会变为1。可以过75%的点。
  • 代码：
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
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int ans = 1e9;
signed main()
{
    cin>>n;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        if(a[i]==1) cnt++;
    } 
    if(cnt){
        cout<<n-cnt<<endl;
        return 0;
    }

    for(int i = 1; i < n; i++){
        int x = a[i], sum = 0;
        for(int j = i + 1; j <= n; j++){
            sum++;
            x=__gcd(x,a[j]);
            if(x==1){
                ans = min(ans, sum);
                break;
            }
        }
    }
    
    if(ans == 1e9){
        cout<<"-1"<<endl;
    }else{
        cout<<n-1+ans<<endl;
    }
    return 0;
}
  • 总结：暴力的思路并不难，抓住1这个题眼即可
正解：线段树+双指针：
  • 思路：目标是求最短区间满足其gcd为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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;
int n, a[N]; 
struct node{
	int l,r,g;
}tr[N*4];
void build(int k, int l, int r){
	tr[k].l = l, tr[k].r = r;
	if(l == r){
		tr[k].g = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(k*2, l, mid);
	build(k*2+1, mid+1, r);
	tr[k].g = __gcd(tr[k*2].g, tr[k*2+1].g);
}
int search(int k, int l, int r){
	if(tr[k].l>=l && tr[k].r<=r) return tr[k].g;
	int ans = 0;
	int mid = tr[k].l+tr[k].r>>1;
	if(l <= mid) ans = __gcd(ans, search(2*k, l, r));
	if(r > mid) ans = __gcd(ans, search(2*k+1, l, r));
	return ans;
}
signed main()
{
	cin>>n;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		if(a[i] == 1) cnt++;
	}
	if(cnt){
		cout<<n-cnt<<endl;
		return 0;
	}
	build(1,1,n);
	int i = 1;
	int ans = 1e9;
	for(int j = 1; j <=n; j++){
		while(i<j && search(1, i+1, j) == 1) i++;
		if(search(1,i,j) == 1) ans = min(ans, j-i);
	}
	if(ans == 1e9) cout<<"-1"<<endl;
	else cout<<n-1+ans<<endl; 
	return 0;
}
  • 总结：线段树这部分熟悉一下还是比较好理解的，结合双指针这里还是不是特别清楚，好像是把很多不必要的情况跳过了，从而降低了时间复杂度。
线段树：二分：
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
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N=100010;
int n;
int a[N];
struct node
{
    int l, r;
    int g;
}tr[N * 4];

void pushup(int u)
{
    tr[u].g =__gcd(tr[u<<1].g,tr[u<<1|1].g);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, a[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].g;
    int mid = tr[u].l + tr[u].r >> 1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else return __gcd(query(u<<1,l,r),query(u<<1|1,l,r));
}

int main()
{
    cin>>n;
    int f=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(a[i]==1) f++;
    }
    if(f){
        printf("%d\n",n-f);
        return 0;
    } 
    build(1,1,n);
    if(query(1,1,n)!=1){
        puts("-1");
        return 0;
    }
    int ans=inf;
    for(int i=1;i<=n;++i){
        int l=i+1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(query(1,i,mid)==1) r=mid;
            else l=mid+1;
        }
        if(query(1,i,r)==1) ans=min(ans,r-i);
    }
    printf("%d\n",n-1+ans);
    return 0;
}

Eowo:

  • 思路：采取一种很特别的手法，随机，以最大的可能去测出结果，与字符串的操作很密切，包括find函数，random_shuffle函数
  • 代码：
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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10;
int n, ans;
string st[N]; 
int main()
{
	cin>>n;
	for(int i = 0; i < n; i++){
		cin>>st[i];
		for(int j = 0; j < 5e3; j++ ){
			random_shuffle(st, st+i+1);
			string t;
			for(int k = 0; k <= i; k++){
				t = t + st[k];
			}
			int res = 0;
			int p = t.find("owo");
			while(p != -1){
				res++;
				p = t.find("owo", p+1);
			}
			ans = max(ans, res);
		}	
		cout<<ans<<endl;
	}
	
	return 0;
}
  • 总结：拓展的题目，正常暴力情况太多太复杂了

F环境治理：

  • 思路：存在明显的二分性，对于最终的值的求解基于Floyed算法，算出每两点之间最近的距离。
  • 代码：
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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
int n,q;
int d[N][N], limit[N][N], tmp[N][N]; 
int cal(int day){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			tmp[i][j] = d[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		int val = day/n + (day%n-1>=i?1:0);
		for(int j = 0; j < n; j++){
			tmp[i][j] = max(limit[i][j], tmp[i][j]-val);
			tmp[j][i] = max(limit[j][i], tmp[j][i]-val);
		}
	}
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				tmp[i][j] = min(tmp[i][k]+tmp[k][j], tmp[i][j]);
			}
		}
	}
	int res = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			res += tmp[i][j];
		}
	}
	return res;
}
signed main()
{
	cin>>n>>q;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin>>d[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin>>limit[i][j];
		}
	}
	int l = 0, r = 1e5*n, ans = -1;
	while(l < r){
		int mid = l + r >>1;
		if(cal(mid)<=q){
			r = mid;
			ans = r;
		}else{
			l = mid + 1;
		}
	}
	cout<<ans<<endl;

	return 0;
}
  • 总结：二分+Floyed,Floyed中k在最外层，注意细节。

G选素数：

  • 思路：一共两步，第一步是找m-pmax+1,设为函数f(m),在f[m]到n的范围内找到一个数i使得f[i]最小。pmax是一个数的最大质因子，可以与线性筛算法相结合，**p[prime[j]*i] = max[p[i], prime[j]]**。能与求最大质因子结合也非常的巧妙。
  • 代码：
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
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000001;
int n,t;
bool isprime[MAXN];
int prime[MAXN];
int p[MAXN];
int ans=1e9;
int f(int m)
{
	if(isprime[m]==true)
	{
		return 1e9;
	}
	return (m-p[m]+1);
}
void Linear_sieve()
{
	for(int i = 2; i <= n; i++){
		isprime[i] = true;
	}
	for(int i = 2; i <= n; i++){
		if(isprime[i]){
			t++;
			prime[t] = i;
			p[i] = i;
		}
		for(int j = 1; j <= t&&prime[j]*i<=n; j++){
			p[prime[j]*i] = max(p[i], prime[j]);
			isprime[prime[j]*i] = false;
			if(i % prime[j] == 0){
				break;
			}
		}
	}
}
int main()
{
	cin>>n;
	Linear_sieve();
	for(int i=f(n);i<=n;i++)
	{
		ans=min(ans,f(i));
	}
	if(ans!=1e9)
	{
		cout<<ans<<endl;
	}
	else
	{
		cout<<"-1"<<endl;
	}
	return 0;
}
  • 总结：需要对线性筛算法较为熟悉，算是一道数论题，倒推。或者基于所给的样例也可窥见端倪。

H替换字符：

暴力：
  • 思路：直接模拟即可，洛谷可过60%
  • 代码：
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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
string s;
int m;
int l, r;
char x,y;

int main()
{
	cin>>s;
	cin>>m;
	while(m--){
		cin>>l>>r>>x>>y;
		l--;r--;
		for(int i = l; i <= r; i++){
			if(s[i] == x){
				s[i] = y;
			}
		}
	}
	cout<<s<<endl;
	
	return 0;
}

I三角序列暴力60%：

  • 思路：第一反应就是二分，对于每个三角序列，进行pre操作确定它的左右边界，然后check函数先找到L,R所在的三角形的右端点，分类讨论，先基于cal,再基于cal2计算，逐步解决问题。很棒的一道模拟题。
  • 代码：
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
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 20;
int n,m;
struct node{
	int len, type, l, r;
}a[N];
int pre[N];
int cal2(int len, int h){
	int sum = len*(len+1)/2;
	int tmp = max(len-h,0LL);
	int res = tmp*(tmp+1)/2;
	return sum-res;
}
int cal(int idx, int col, int h){
	if(col > a[idx].r) return 0;
	if(a[idx].type == 0){
		return cal2(a[idx].len, h)-cal2(col - a[idx].l, h);
	}else{
		return cal2(a[idx].r-col+1, h);
	}
}
int check(int l, int r, int h){
	int idx_l = lower_bound(pre+1,pre+1+n,l)-pre;
	int idx_r = lower_bound(pre+1,pre+1+n,r)-pre;
	if(idx_l == idx_r){
		return cal(idx_l, l, h)-cal(idx_l, r+1, h);
	}
	int ans = cal(idx_l, l, h) + cal(idx_r, a[idx_r].l, h) - cal(idx_r, r+1, h);
	for(int i = idx_l + 1; i < idx_r; i++){
		ans += cal(i, a[i].l, h);
	}
	return ans;
}
signed main()
{
	cin>>n>>m;
	int max_h = 0;
	for(int i = 1; i <= n; i++){
		cin>>a[i].len>>a[i].type;
		max_h = max(max_h, a[i].len);
		pre[i] = pre[i-1] + a[i].len;
		a[i].l = pre[i-1] + 1;
		a[i].r = pre[i];
	}	
	int L,R,v;
	for(int i = 1; i <= m; i++){
		cin>>L>>R>>v; 
		int l = 1, r = max_h + 1, h = -1;
		while(l < r){
			int mid = l + r >>1;
			if(check(L, R, mid) >= v){
				h = mid;
				r = mid;
			}else{
				l = mid + 1;
			}
		} 
		cout<<h<<endl;
	}
	return 0;
}
  • 总结:遇到这种大模拟题，思路一定要清晰，划分问题然后逐步增加函数来解决。
#算法
第十三届蓝桥杯国赛真题训练
http://example.com/2024/04/20/蓝桥杯国赛备赛/第十三届蓝桥杯国赛真题训练/
作者
jhxxxxx
发布于
2024年4月20日
许可协议