2024_4_13十五届蓝桥杯_研究生c++组

因为在外面实习，考场在学校，早上6点多起床往学校赶，真的顶。整个考试过程还可，没啥大问题，赛题难度和往届比中等偏下一些。我们学校应该会报销国赛，希望可以北京一日游。。。

T1

求劲舞团的连击次数。答案好像是8。

我直接寄，考试时候10秒钟就知道代码怎么写，然后研究复制文本到命令行，就是不知道怎么粘贴进去，然后读文件的也忘了，考前还看对拍，真是鱼的记忆。其实最后还有半个多小时，这个题目看着操作手册完全能写出来的。

可以读文件或者while(cin >> t, t)的方式，最后输入一个0。

T2

找规律，1000个里面有20个可以的，1和3是额外的两个，最后在判断n%1000这种有四个。

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ll ans = 40480826628080; 
	cout << (ans + 6) << endl;
	return 0;
}

T3

排序

#include<iostream>
#include<bits/stdc++.h>
#include<vector>
using namespace std;
typedef long long ll;

int n, t;
vector<int> a; 
//             0 ,1, 2, 3, 4, 5, 6, 7, 8, 9
int b[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};

bool cmp(int x, int y){
	int t1 = 0;
	int t2 = 0;
	
	int x1 = x, y1 = y;
	while(x1 != 0) {
		t1 += b[x1 % 10];
		x1 /= 10;
	}
	while(y1 != 0) {
		t2 += b[y1 % 10];
		y1 /= 10;
	}

	return t1 == t2 ? (x < y) : (t1 < t2);
}

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> t;
		a.push_back(t);
	}
	sort(a.begin(), a.end(), cmp);		
	for(int i = 0; i < n; i++) cout << a[i] << " ";
	cout << endl;
	return 0;
} 

T4

最大生成树，P赛法和K算法都可以。这里暴力求的公共串，算了一下1e7，不知道会不会TLE，没敢开O3，官方好像默认开O2。

#include<iostream>
#include<bits/stdc++.h>
#include<vector>

using namespace std;
typedef long long ll;
const int N = 40005;

int n, m;
string st;
vector<string> sts;

int gets(int x, int y){
	int res = 0;
	for(int i = 0; i < m; i++){//枚举x的开头 
		int cur = 0;
		for(int j = 0; j < 2 * m; j++){
			if(sts[x][(int)((i+j)%m)] == sts[y][j % m]){
				cur++;
				res = max(res, cur);
			}else{
				cur = 0;
			}
		}
	}
	return min(m, res);
}

typedef pair<int,int> PII;

struct node{
    int x,y,z;
    bool operator<(node &t)const{
        return z > t.z;
    }
}edge[N];

int fa[N];

int Find(int x){
    if(x == fa[x])return x;
    return fa[x] = Find(fa[x]);
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> st;
		sts.push_back(st);
	}
	int en = 0;
    for(int i = 0; i < n; i++){
    	for(int j = i+1; j < n; j++){
    		edge[en].x = i;
    		edge[en].y = j;
    		edge[en].z = gets(i, j);
    		en++;
		}
	}
	
    
    sort(edge, edge + en);
    

    for(int i = 0; i < en; i++)
    fa[i] = i;
    ll res = 0;
    for(int i = 0; i < en; i++){
        int x = Find(edge[i].x);
        int y = Find(edge[i].y);
        if(x == y)continue;
        fa[x] = y;
        res += edge[i].z;
    }
    cout << res << endl;
	return 0;
}

T5

挖矿，就四种情况（本质是两种）,①一直右走②一直左走③先右走又折回来④先左走又折回来

其实代码可以写的很简洁，为了保证各种情况都能独立判分，我分开写了四种情况：

#include<iostream>
#include<bits/stdc++.h>
#include<vector>
using namespace std;
typedef long long ll;

int n, m;
int a[100005];

int main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a+n);
	int res = 0;
	if(a[0] >= 0){//向右 
		for(int i = 0; i < n; i++){
			if(a[i] <= m) res = max(res, i+1);
		}
		cout << res << endl;
		return 0;
	}
	if(a[n-1] <= 0){//向左 
		for(int i = n-1; i >= 0; i--){
			if(-a[i] <= m) res = max(res, n - i);
		}
		cout << res << endl;
		return 0;
	}
	//    / 
	//    \
	//    类型
	// 特判0 
	int l = 0, r = n-1;
	while(((-2*a[l]) + a[r]) > m){
		r--;
	} 
	res = max(res, r-l+1);
	while(l < n && a[l] < 0){
		l++;
		while(r < n && ((-2*a[l]) + a[r]) <= m){
			r++;
		}
		res = max(res, r-l);
	}
	l++;
	while(r < n && a[r] <= m){
		r++;
	}
	res = max(res, r-l);

	//    \
	//    /
	//    类型
	l = 0, r = n-1;
	while(((2*a[r]) - a[l]) > m){
		l++;
	} 
	res = max(res, r-l+1);
	while(r >= 0 && a[r] > 0){
		r--;
		while(l >= 0 && ((2*a[r]) - a[l]) <= m){
			l--;
		}
		res = max(res, r-l);
	}
	r--;
	while(l >= 0 && -a[l] <= m){
		l--;
	}
	res = max(res, r-l);
	cout << res << endl;
	return 0;
}

T6

题目是智力测试，没看懂题目，那个E打印错了，然后监考老师念正确的题目，一个字也听不清。感觉是一个图，用BFS能过一部分的，哎可惜了，属于非智力因素失分。

T7

没想出来怎么用n²以下复杂度找出全部异或值，直接50%写法了

#include<iostream>
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;

unordered_map<int, int> mp;
int a[100005], f[100005];
int n;

int main(){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) cin >> f[i];
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			mp[a[i] ^ a[j]]++;
		}
	}

	for(int i = 0; i < n; i++){
		if(f[i] == -1) continue;
		int sub = a[i] ^ a[f[i]];
		mp[sub]--;
		if(mp[sub] == 0) mp.erase(mp.find(sub));
	}
	int res = 0;
	for(auto it = mp.begin(); it != mp.end(); it++){
		res = max(res, it->first);
	}
	cout << res << endl;
	return 0;
}

T8

30%写法：

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

int n, s, x, y;
int a[100005];
vector<int> g[100005];

int res = 0;

void bfs(int i, int k){
	for(int j = 0; j < g[i].size(); j++){
		int node = g[i][j];
		if(a[node] < k && (k % a[node]) != 0){
			res++;
		}
		bfs(node, k);
	}
}

int main(){
	cin >> n >> s;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 0; i < n-1; i++){
		cin >> x >> y;
		g[x].push_back(y);
	} 
	for(int i = 1; i <= n; i++){
		bfs(i, a[i]);
	}
	cout << res << endl;
	return 0;
}