蓝桥杯2023年国A

蓝桥杯2023年国A真题

C切割:

  • 思路：找两个数的最小公因数，从小暴力遍历即可
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define int long long
using namespace std;
int w, h, ans;
signed main()
{
	cin>>w>>h;
	int minn = min(w, h);
	int maxn = max(w, h);
	int flag = 0;
	for(int i = 2; i <= minn; i++){
		if(minn % i==0 && maxn %i ==0){
			ans = (minn/i)*(maxn/i);
			cout<<ans<<endl;
			flag = 1;
			break;
		}
	}
	if(!flag){
		cout<<"0"<<endl;
	}
	return 0;
}

DXYZ：

  • 思路：先思考1-R的个数，是有规律的，再逐步减去L前面的数,最终可以总结出一个公式。注意，当R<2L,应直接返回，不能使用公式会出错。所以还是要多多考虑特殊情况，多想一些测试用例。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
int l, r, sum, res; 
signed main()
{
	cin>>T;
	while(T--){
		cin>>l>>r;
		if(r<2*l) cout<<"0"<<endl;
		else{
			sum = r*(r-1)/2;
			//cout<<"sum:"<<sum<<endl;
			res = (2*r-2*l+1)*(l-1);
			//cout<<"res:"<<res<<endl;
			cout<<sum-res<<endl;
		}
	}
	return 0;
}
  • 总结：仔细思考是可以做出来的，并不是很难。要多想几组测试用例。

E第K小的数：

暴力：
  • 思路：直接模拟，用vector来装5000*5000个数据， vector的sort写法sort(c.begin(), c.end());
  • 代码：
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;
const int N = 1e5 + 10;
int n, m, k;
int a[N], b[N];
vector <int> c; 
signed main()
{
	cin>>n>>m>>k;
	for(int i = 1; i <= n; i++) cin>>a[i];
	for(int i = 1; i <= m; i++) cin>>b[i];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			c.push_back(a[i]+b[j]);
		}
	} 
	sort(c.begin(), c.end());
    cout<<c[k-1]<<endl;
	
	return 0;
}
  • 总结：可以拿30%分数，注意vector下标从0开始
正解：二分
  • 思路：先二分值，来逼近k，然后再套一层二分，固定数组a,二分数组b，找到当前值排第几。两个二分主要要注意边界情况的考虑，l和r的更新
  • 代码：
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
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10;
int n, m, k;
int a[N], b[N];
int get(int x){
	int res = 0;
	for(int i = 1; i <= n; i++){
		int l = 1, r = m;
		while(l<r){
			int mid = l + r + 1>>1;
			if(a[i] + b[mid] > x)  r = mid-1;
			else l = mid;
		}
		if(a[i] + b[l] <= x)res += l;
	}
	return res;
}
signed main()
{
	cin>>n>>m>>k;
	for(int i = 1; i <= n; i++) cin>>a[i];
	for(int i = 1; i <= m; i++) cin>>b[i];
	sort(a+1, a+1+n);
	sort(b+1, b+1+m);
	int l = 1, r = 1e18;
	while(l<r){
		int mid = l + r>>1;
		if(get(mid)>=k) r = mid;
		else l = mid + 1;
	} 
	cout<<l<<endl;
	
	return 0;
}
  • 去思考暴力手法为什么复杂度高，如何简化，像这道题，存在很明显的递增性，两次二分就可以解决，不要局限于一次的情况，学习了。

F相连的边：

  • 思路：取边长和最大的连在一起的三条边有两种可能性，一是三条边有一个共同端点，二是三条边依次相连。对于一的话，可以遍历所有点，把它所在的边按边长进行倒叙排序，取前三条即可；对于二的话，遍历所有边，对于它的两个端点找最大的边长，但不能和当前这条边重复，可以给每条边一个id来区分。使用vector来存储每个点对应的边，手写自定义排序。
  • 代码：
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>
#define int long long
using namespace std;
const int N = 2e5+10;
struct edge{
	int x, y, l, id;
}e[N];
vector<edge> node[N];
int n, ans;
bool cmp(edge a, edge b){
	return a.l>b.l;
}
signed main()
{
	cin>>n;
	for(int i = 1; i < n; i++){
		int x, l;
		cin>>x>>l;
		e[i] = {x, i+1, l, i};
		node[x].push_back(e[i]);
		node[i+1].push_back(e[i]); 
	}
	for(int i = 1; i <= n; i++){
		sort(node[i].begin(), node[i].end(), cmp);
	}
	for(int i = 1; i <= n; i++){
		if(node[i].size()>=3){
			ans = max(ans, node[i][0].l+node[i][1].l+node[i][2].l);
		}
	}
	for(int i = 1; i < n; i++){
		int x = e[i].x, y = e[i].y, l = e[i].l, id = e[i].id;
		int tmp = l;
		if(node[x].size()>1){
			tmp += node[x][0].id == id? node[x][1].l : node[x][0].l;
		}
		if(node[y].size()>1){
			tmp += node[y][0].id == id? node[y][1].l : node[y][0].l;
		}
		ans = max(ans, tmp);
	}
	cout<<ans<<endl; 
	
	return 0;
}
  • 总结：首先对问题进行分类，涉及到树的存储，使用vector，实际上并不难，只是需要经验。尤其是这种树上的问题，多做多积累经验。

G01游戏：

  • 思路：使用dfs+剪枝，有两种情况0或1，再往下深入，直到所有都遍历过了，验证矩阵是否合法：所有行和列不能相同，使用状压数组来记录，不能有连续三个相同。合法的话就直接在dfs里输出，并将flag置为1，后续的dfs陆续return。剪枝：在遍历过程中验证是否和前两个（行，列）相同，0，1个数是否<=n/2。
  • 代码：
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
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 12;
string s[N];
int n, flag =0;
int fr[N][2], fc[N][2];
int A[1050], B[1050];
bool chk(int x, int y){
	if(x>2&&s[x-1][y]==s[x][y]&&s[x-2][y]==s[x][y]) return false;
	if(y>2&&s[x][y-1]==s[x][y]&&s[x][y-2]==s[x][y]) return false;
	return true;
}
void bfs(int x, int y){
	if(flag == 1) return;
	if(x == n+1 && y == 1){
		int res = 1;
		for(int i = 1; i <= n; i++){
			for(int j = 2; j < n; j++) if(s[i][j] == s[i][j-1] && s[i][j] == s[i][j+1]) res = 0;
			for(int j = 2; j < n; j++) if(s[j][i] == s[j-1][i] && s[j][i] == s[j+1][i]) res = 0;
		}
		if(res == 0) return;
		memset(A,0,sizeof(A));
		memset(B,0,sizeof(B)); 
		for(int i = 1; i <= n; i++){
			int tmp = 0;
			for(int j = 1; j <= n; j++){
				tmp = tmp*2 + s[i][j]-'0';
			}
			if(A[tmp]) res = 0;
			A[tmp]++;
		}
		for(int i = 1; i <= n; i++){
			int tmp = 0;
			for(int j = 1; j <= n; j++){
				tmp = tmp*2 + s[j][i]-'0';
			}
			if(B[tmp]) res = 0;
			B[tmp]++;
		}
		if(!res) return;
		flag = 1;
		for(int i = 1; i<=n; i++){
			for(int j = 1; j <= n ;j++){
				cout<<s[i][j];
			}
			cout<<endl;
		}
		return;
	}
	int a = x, b = y;
	b++;
	if(b==n+1) a++, b=1;
	if(s[x][y]!='_'){
		bfs(a, b);
		return;
	}
	s[x][y] = '0';
	fr[x][0]++;
	fc[y][0]++;
	if(fr[x][0]<=n/2&&fc[y][0]<=n/2&&chk(x,y)) bfs(a, b);
	fr[x][0]--;
	fc[y][0]--;
	
	s[x][y] = '1';
	fr[x][1]++;
	fc[y][1]++;
	if(fr[x][1]<=n/2&&fc[y][1]<=n/2&&chk(x,y)) bfs(a, b);
	fr[x][1]--;
	fc[y][1]--;
	s[x][y]='_';  //记得回复现场
	return;
}
signed main()
{
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>s[i];
		s[i] = ' '+s[i];
		for(int j = 1; j <= n; j++){
			if(s[i][j] == '0'){
				fr[i][0]++;
				fc[j][0]++;
			}else if(s[i][j] == '1'){
				fr[i][1]++;
				fc[j][1]++;
			}
		}
	}
	bfs(1, 1);
	
	return 0;
}
  • 要先理清思路再开始写，尤其是dfs（bfs），主要是截止判断，下一个dfs的写法，还是要多多练习。并没有想象的那么复杂。

H子串暴力：

  • 思路： 统计出现次数为1-n的子串个数，可以采用map统计所有子串的出现次数，再遍历所有map来对出现次数进行一个计数即可。可以过25%。
  • 代码：
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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10;
string s; 
unordered_map<string, int> mp;
int cnt[N];
signed main()
{
	cin>>s;
	int n = s.size();
	for(int len = 1; len <= n; len++){
		for(int i = 0; i+len-1<n; i++){
			string t = s.substr(i, len); 
			mp[t]++;
		}
	}
	for(auto i:mp){
		int t = i.second;
		cnt[t]++;
	}
	for(int i = 1; i <= n; i++){
		cout<<cnt[i]<<endl;
	}
	return 0;
}
  • 需要掌握map的使用以及获取，还有字符串的处理。遍历所有字串可以先遍历长度再遍历起始点，使用substr来获取子串，遍历所有map可以采取auto，获取次数（map的映射值）可以使用i.second。

I树上的路径暴力：

  • 计算任意两个点的距离需要用到lca算法，再枚举所有两个点的组合，可以过65%，太牛了！是可以做到的。
  • 代码：
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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10;
typedef pair<int, int> PII;
int n, l, r, sum[N], ans;
vector<PII> e[N];
int siz[N], dep[N], top[N], fa[N], son[N];
void dfs1(int u ,int father){//(1,0)
	siz[u] = 1;
	dep[u] = dep[father] + 1;
	fa[u] = father;
	for(int i = 0; i < e[u].size(); i++){
		int s = e[u][i].first;
		if(s == fa[u]) continue;
		dfs1(s, u);
		siz[u] += siz[s];
		if(siz[son[u]] < siz[s]){
			son[u] = s;
		}
	}
}
void dfs2(int u ,int t){//(1,1)
	top[u] = t;
	if(son[u] == 0) return;
	dfs2(son[u], t);
	for(int i = 0; i < e[u].size(); i++){
		int s = e[u][i].first;
		if(s == fa[u] || s == son[u]) continue;
		dfs2(s, s);
	}
}
int lca(int x, int y){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]){
			swap(x, y);
		}
		x = fa[top[x]];
	}
	return dep[x] < dep[y]? x : y;
}
void cal_sum(int u){
	for(int i = 0; i < e[u].size(); i++){
		int x = e[u][i].first;
		if(x == fa[u]) continue;
		int y = e[u][i].second;
		sum[x] = sum[u] + y;
		cal_sum(x);
	}
}
signed main()
{
	cin>>n>>l>>r;
	
	for(int i = 1,x; i < n; i++){
		cin>>x;
		e[x].push_back({i + 1,1});
		e[i+1].push_back({x, 1});
	}
	dfs1(1, 0);
	dfs2(1, 1);
	cal_sum(1);
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <=n; j++){
			int dis = sum[i]+sum[j]-2*sum[lca(i,j)];
			//cout<<"i:"<<i<<" j:"<<j<<" dis:"<<dis<<endl;
			if(dis>=l&&dis<=r){
				ans+=dis;
			}
		}
	} 
	cout<<ans<<endl;
	
	return 0;
}
  • 总结：lca还是比较常用的算法，要熟练掌握，另外暴力计算树上两点的距离也要熟练才行。
#算法
蓝桥杯2023年国A
http://example.com/2024/05/03/蓝桥杯国赛备赛/蓝桥杯2023年国A/
作者
jhxxxxx
发布于
2024年5月3日
许可协议