2024年的蓝桥杯省赛第一场已经圆满结束了，相信大家在蓝桥杯备赛和比赛的过程中都收获满满。现在快来检验一下这一阶段的学习成果，看看自己能取得多少分数吧

---

总分：100分    时间 9：00 - 1：00（4个小时）

填空题

试题A(5分)

解：开一个数组存储每个数字对应的值，然后遍历20000101到20240413之间的日期，注意月份，闰年判断，然后可以做一些优化：如：显然0的个数大于等于四个的日期，都是打篮球的（4*13=52>50）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<unordered_map>
#include<unordered_set>
#include<map>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N=100010;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;

int bi[]={13,1,2,3,5,4,4,2,2,2};
int month[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

int is_leap(int y){
    if((y%4==0&&y%100!=0)||y%400==0) return 1;
    return 0;
}

bool check(int x){
    int y=x/10000;
    int m=x%10000/100;
    int d=x%100;
    
    if(!m||m>12||!d) return false;
    if(m!=2&&d>month[m]) return false;
    if(m==2){
        if(d>month[m]+is_leap(y)) return false;
    }
    
    return true;
}

int main(){
    int ans=0;
    for(int i=20000101;i<=20240413;i++){
        if(check(i)){
            int t=i;
            int res=0;
            while(t){
                res+=bi[t%10];
                t/=10;
            }
            if(res>50){
                ans++; 
            }
        }
    }
    cout<<ans;
    return 0;
}

试题B(5分)

解：看成是一个25位的01串，12个1和13个0（表示黑白），1和0各可以分为12种获胜情况（5+5+2），遍历25位的可能情况，每次check1的个数以及是否在获胜情况中即可。（填空题挂着让代码跑~）

试题C(10分)

显然每次组团都会减少一个士兵（把这个士兵训练量练完）

所以要找到什么时候士兵单独训练划算比组团划算

#include<bits/stdc++.h>
using namespace std;
int N, S;
int main() {
	scanf("%d%d",&N,&S);
	int n = N;
	vector<int> p;		
	vector<int> c;		
	while (n--) {
		int pi, ci;
		scanf("%d%d",&pi,&ci);
		p.push_back(pi);
		c.push_back(ci);
	}
	int sum = 0;
	while (1) {
		int flag = 1;
		int consume = 0;
		for (int i = 0; i < c.size(); i++) {
			if (c[i] > 0)
			{
				consume += p[i];
				c[i]--;
				flag = 0;
			}
		}
		sum += min(consume, S);
		if (flag) break;
	}
	cout << sum;
	return 0;
}

试题D(10分)

#include<bits/stdc++.h>

using namespace std;

const int T = 200000;

vector<vector<int>> tree1(T);
vector<vector<int>> tree2(T);
vector<int> nums1(T);
vector<int> nums2(T);

int N, M;

int get() ;

int main() {
	cin >> N >> M;
	int n = N, m = M;
	int temp;
	while (n--) {
		cin >> temp;
		nums1[N - n] = temp;
	}
	while (m--) {
		cin >> temp;
		nums2[M - m] = temp;
	}
	n = N - 1; m = M - 1;
	int t1, t2;
	while (n--) {
		cin >> t1 >> t2;
		tree1[min(t1, t2)].push_back(max(t1, t2));
	}
	while (m--) {
		cin >> t1 >> t2;
		tree2[min(t1, t2)].push_back(max(t1, t2));       //存储每个节点的孩子
	}
	cout << get();
	return 0;
}
int get() {
	int sum = 0;	
	int t1 = 1, t2 = 1;
	if (nums1[1] == nums2[1]) sum++;
	else return 0;
	while (1) {
		int i, j;
		int flag = 1;
		if (tree1[t1].size() == 0 || tree2[t2].size() == 0) break;
		for (i = 0; i < tree1[t1].size(); i++) {
			for (j = 0; j < tree2[t2].size(); j++) {
				if (nums1[tree1[t1][i]] == nums2[tree2[t2][j]])   //寻找公共前缀
				{
					flag = 0;
					t1 = tree1[t1][i];
					t2 = tree2[t2][j];                            //选取下一层的父节点
					sum++;
					break;
				}
			}
		}
		if (flag) break;
	}
	return sum;
}

试题E(15分)

思路一：每次读入的数排序，连续的k个数是为方差最小，遍历n，排序nlogn，计算方差O(1)所以是O(n^2log(n))的复杂度。

思路二：每次加进去的数能不能用得上是看代换掉离方差最远的那个数之后，方差有没有变小来决定的

#include<bits/stdc++.h>

using namespace std;

vector<double> t;
vector<double> nums;
int N, k, T;

bool calculate0() ;

int main() {
	cin >> N >> k >> T;
	int n = N;
	while (n--) {
		double temp;
		cin >> temp;
		nums.push_back(temp);
	}
	if (N < k) { cout << -1; return 0; }
	double mean = 0;
	for (int i = 0; i < k; i++) {
		t.push_back(nums[i]);
		mean += nums[i];
	}
	mean /= k;
	if (calculate0()) { cout << k; return 0; }
	for (int length = k; length < nums.size(); length++) {
		double sub = 0;
		int x = -1;
		for (int i = 0; i < t.size(); i++) {
			if (abs(t[i] - mean) > sub) {
				sub = abs(t[i] - mean);
				x = i;
			}
		}
		if (x != -1 && sub > abs(nums[length] - mean))            
			t[x] = nums[length];
		if (calculate0()) { cout << length + 1; return 0; }
	}
	cout << -1;
	return 0;
}

bool calculate0() {            
	double e;
	double sum = 0;
	for (auto num : t) {
		sum += num;
	}
	e = sum / k;
	double val = 0;
	for (auto num : t) {
		val += (num - e) * (num - e);
	}
	val /= k;
	if (val < T) return true;
	else return false;
}

试题F(15分)

#include <iostream>
#include <vector>
#include <set>

using namespace std;

// 使用 set 存储 pair，其中 pair 的元素是整数
set<pair<int, int>> factorPairs;

int main() {
    int numCount;
    cin >> numCount;

    // 使用 vector 存储输入的数字
    vector<int> numbers;
    for (int i = 0; i < numCount; i++) {
        int tempNumber;
        cin >> tempNumber;
        numbers.push_back(tempNumber);
    }

    // 检查每对数字，如果一个数字是另一个数字的因数，就将它们的索引（索引从1开始）作为 pair 存入 set
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers[i] % numbers[j] == 0)
                factorPairs.insert({ j + 1, i + 1 });
            if (numbers[j] % numbers[i] == 0)
                factorPairs.insert({ i + 1, j + 1 });
        }
    }

    // 计算满足条件的 pair 的数量
    int pairCount = 0;
    for (const auto& pair1 : factorPairs) {
        for (const auto& pair2 : factorPairs) {
            if (pair1.first != pair2.first && pair1.first != pair2.second && pair1.second != pair2.first && pair1.second != pair2.second)
                pairCount++;
        }
    }

    cout << pairCount;
    return 0;
}

试题G(20分)

DFS做法：

#include<bits/stdc++.h>

using namespace std;

int N, q;

vector<int> type;
vector<int> temp;

void dfs(int b, int e,vector<vector<int>>& line,vector<vector<int>> matrix,int length)
 {
	if (b == e)
    {
        line.push_back(temp); 
        return; 
    }
	if (length > N) return;
	for (int i = 0; i < matrix[b].size();i++) 
    {
		if (matrix[b][i] == 1) {
			temp.push_back(i);						
			dfs(i, e, line, matrix,length+1);		
			temp.pop_back();
		}
	}

	return;
}


int main() {

	cin >> N >> q;

	vector<int> t(N, 0);
	vector<vector<int>> matrix(N, t);

	int n = N;
	while (n--) {
		int temp;
		cin >> temp;
		type.push_back(temp);
	}

	n = N - 1;
	while (n--) {
		int i, j;
		cin >> i >> j;
		matrix[i - 1][j - 1] = 1;
		matrix[j - 1][i - 1] = 1;			
	}

	while (q--) 
    {
		int Begin, End;
		cin >> Begin >> End;

		vector<vector<int>> line;
		dfs(Begin - 1, End - 1, line,matrix,0);
		int minlength = line[0].size();
		int f = 0;

		for (int i = 0; i < line.size(); i++)
		{
			if (line[i].size() < minlength) {
				f = i;
				minlength = line[i].size();			
			}
		}
		set<int> s;
		s.insert(type[begin0 - 1]);
		for (auto x : line[f]) {
			s.insert(type[x]);                    
		}

		cout << s.size();
	}

	return 0;
}

试题H(20分)