当前位置：首页 > article >正文

2020年蓝桥杯第十一届CC++大学B组（第二次）真题及代码

article 2025/3/18 15:54:05

1A：门牌制作（填空5分_拆分数字）

2B：既约分数（填空5分_gcd）

3C：蛇形填数（填空10分_找规律）

4D：跑步锻炼（填空10分_模拟）

5E：七段码（填空15分_图论+并查集+dfs）

6F：成绩统计（编程题15分）

解析代码（格式化输出）

7G：回文日期（编程题20分）

解析代码（模拟）

8H：子串分值和（编程题20分）

解析代码1（暴力_过50%）

解析代码2（小优化_过60%）

解析代码3（乘法原理_过100%）

9I：平面切分（编程题25分）

解析代码（数学）

10J：字串排序（编程题25分）

解析代码（dp）

1A：门牌制作（填空5分_拆分数字）

题目解析：

简单模拟，答案624

#include<iostream>
using namespace std;
int main()
{
	int sum = 0;
	for (int i = 1; i <= 2020; ++i)
	{
		int tmp = i;
		while (tmp)
		{
			if (tmp % 10 == 2)
			{
				sum++;
			}
			tmp /= 10;
		}
	}
	cout << sum << endl; // 答案624
	return 0;
}

2B：既约分数（填空5分_gcd）

题目分析：

其实就是求分子，分母 [ 1,2020 ] 中的最大公约数为一的个数
可以考虑使用STL的__gcd()函数

答案2481215

#include<iostream>
using namespace std;
int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}
int main()
{
	int res = 0;

	for (int i = 1;i <= 2020;i++)
	{
		for (int j = 1;j <= 2020;j++)
		{
			//if (__gcd(i, j) == 1)
			//	res++;
			if (gcd(i, j) == 1)
				res++;
		}
	}
	cout << res << endl; // 答案2481215
	return 0;
}

3C：蛇形填数（填空10分_找规律）

题目解析：

这道题目可以观察，可以写代码。
观察发现每次对角线值的差是4的倍数，可以通过递推的方式计算。

答案761


#include<iostream>
using namespace std;
int a[100][100];
int main()
{
	int cnt = 1;
	int x, y;
	for (int i = 1;i <= 40;i++)
	{
		if (i % 2 == 1)
		{
			for (x = i, y = 1;x >= 1 && y <= i; --x, ++y)
			{
				a[x][y] = cnt++;
			}
		}
		else
		{
			for (x = 1, y = i;x <= i && y >= 1; ++x, --y)
			{
				a[x][y] = cnt++;
			}
		}
	}
	cout << a[20][20]; // 答案761
	return 0;
}

4D：跑步锻炼（填空10分_模拟）

题目解析：这个问题简单暴力的解决方法可以直接遍历每一天，算出每一天的日期，并使用一个计数器计数。

答案8879

#include<iostream>
using namespace std;
int	get_month_day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int main()
{
	int year, month, day, week = 6, sum = 0;
	for (year = 2000;year <= 2020;year++)
	{
		if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0))
		{
			get_month_day[2] = 29;
		}
		for (month = 1;month <= 12;month++)
		{
			for (day = 1;day <= get_month_day[month]; ++day)
			{
				if (day == 1 || week == 1)
					sum += 2;
				else
					sum += 1;
				week = (week + 1) % 7;
				if (year == 2020 && month == 10 && day == 1)
				{
					cout << sum << endl; // 到时间就退出来， 答案8879
					return 0;
				}
			}
		}
		get_month_day[2] = 28;
	}
	return 0;
}

5E：七段码（填空15分_图论+并查集+dfs）

题目解析：必须要相邻才能发光，也就是所有开着的灯必须是连通的，才能算是一种合法方案，求合法的方案数。

把每条边相连，建立一个无向图。如果在一个状态之后遍历这个图，用并查集的方式，看是否是一个父节点，如果是一个父节点的话，就是相连的
大佬解法是利用二进制。因为每一个灯仅仅对应着开或者关，正好对应二进制的0和1，用二进制优化，但是我这菜鸡只能理解到这里，还是建图能理解
实在不行，蓝桥杯比赛现场，用数学办法推理也行。暴力出奇迹

答案80

#include<iostream>
using namespace std;
int use[10];
int ans, e[10][10], father[10];
void init() // 连边建图
{
    // a b c d e f g
    // 1 2 3 4 5 6 7
    e[1][2] = e[1][6] = 1;
    e[2][1] = e[2][7] = e[2][3] = 1;
    e[3][2] = e[3][4] = e[3][7] = 1;
    e[4][3] = e[4][5] = 1;
    e[5][4] = e[5][6] = e[5][7] = 1;
    e[6][1] = e[6][5] = e[6][7] = 1;
}
int Find(int a) // 简易并查集
{
    return (a == father[a]) ? a : father[a] = Find(father[a]);

}
void dfs(int d)
{
    if (d > 7)//一个七段管的所有灯的状态已经列举完了
    {
        for (int i = 1; i <= 7; ++i)
        {
            father[i] = i;//初始化
        }
        for (int i = 1; i <= 7; ++i)
        {
            for (int j = 1; j <= 7; ++j)
            {//如果存在这条边 且 开i节点 且 开j节点
                if (e[i][j] && use[i] && use[j])
                {
                    int fa = Find(i), fb = Find(j);//寻找i，j对于的祖宗节点
                    if (fa != fb)//如果祖宗节点不同，证明未连通
                        father[fa] = fb;//连通 a b
                }
            }
        }
        int k = 0;
        for (int i = 1; i <= 7; ++i)
        {
            if (use[i] && i == father[i]) // 如果它被用过 且 它等于它的祖宗节点
                k++;
        }
        if (k == 1) // 只有一个父节点，就说明他们是相连的
            ans++;
        return;
    }
    use[d] = 0; // 不选
    dfs(d + 1);

    use[d] = 1; // 选
    dfs(d + 1);
    use[d] = 0; // 归位
}
int main()
{
    init();
    dfs(1);
    cout << ans << endl;
    return 0;
}

6F：成绩统计（编程题15分）

解析代码（格式化输出）

注意要输入%%才表示输出%

#include <iostream>
using namespace std;

int main()
{
	int n = 0;
	cin >> n;
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < n; ++i)
	{
		int x = 0;
		cin >> x;
		if (x >= 60)
			++cnt1;
		if (x >= 85)
			++cnt2;
	}
	printf("%.0f%%\n", cnt1 / (n / 100.0));
	printf("%.0f%%\n", cnt2 / (n / 100.0));
	return 0;
}

7G：回文日期（编程题20分）

题目解析：

遍历前四位数，然后进行回文构造，然后再判断构造出来的回文串是否满足日期的标准，即判断它是否是合法的日期即可。

输入是一个合法的八位数的日期。

第一个输出是，这个日期之后的第一个合法的回文日期

第二个输出是，这个日期之后的第一个符合ABABBABA的日期

#include<iostream>
#include<cstdio>
using namespace std;

int get_month_day[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

bool check(int date) // 判断是否位合法日期
{
	int year = date / 10000;
	int month = date % 10000 / 100;
	int day = date % 100;
	if (!month || month >= 13 || day == 0)
		return false;
	if (month != 2 && day > get_month_day[month])
		return false;
	if (month == 2)
	{
		bool leap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
		if (day > 28 + leap)
			return false; // 如果二月的天数>大于原本的二月天数+（可能的闰年+1的天数）
	}
	return true;
}

bool checkAB(int s) // 判断AB
{
	bool flag = false;
	int y = s / 10000; // 得到年份 
	int m = (s / 100) % 100; // 得到月份(BA)
	int d = s % 100; // 得到日(BA)

	int k = y / 100; // AB 
	int n = y % 100; // AB 
	if (k == n && m == d)  // 判断是否为ABABBABA 
		flag = true;
	return flag;
}

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

	int flag = 0;
	for (int i = (date / 10000) + 1; i <= 9999; i++) // 枚举四位数的年份
	{	// 举例 i=1234
		int left = i;
		int right = i; // 构造出来的回文串，构造出来的回文串即：12344321
		for (int j = 0; j < 4; ++j)
		{
			right = right * 10 + left % 10; // 1234*10+1234%10
			left = left / 10; // 得到left的下一位
		} // 因为是按顺序进行的枚举，所以先符合条件的第一个必然是顺序最小的那一个
		if (check(right))
		{
			++flag; // 保证第一个符合的回文串只有一个输出
			if (flag == 1)
				cout << right << endl;
			if (checkAB(right))
			{
				cout << right << endl;
				return 0;
			}
		}
	}
	return 0;
}

解析代码（模拟）

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int get_month_day[13] = { -1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 };//每个月的天数
bool checkLeapYear(int y) // 判断闰年
{
	if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0))
		return true;
	return false;
}
bool checkABABBABAstyle(string s) // 判断是否为ABABBABA型
{
	if (s[0] == s[2] && s[0] == s[5] && s[0] == s[7] 
	 && s[1] == s[3] && s[1] == s[4] && s[1] == s[6])
		return true;
	return false;
}
int main()
{
	string S, ans1, ans2;
	string s, t, year;
	int y, m, d, i;
	cin >> S;
	year = S.substr(0, 4);
	for (i = stoi(year); ans1 == "" || ans2 == ""; ++i) // i 初值为输入数据的年
	{
		// 找到了ans1和ans2，循环结束，有任何一个没有找到 就要继续循环寻找        
		s = to_string(i); // s为当前枚举的年
		t = to_string(i);
		reverse(t.begin(), t.end()); // 求i的逆
		s += t; // 构造拼接出 s+s'  年月日
		if (s <= S) // 构造出的s 小于起始日期，不计，
			continue; // 考察下一年，下面的语句不执行
		y = stoi(s.substr(0, 4));
		m = stoi(s.substr(4, 2)); // 从回文串中获得年月日：y、m、d。
		d = stoi(s.substr(6, 2));
		if (checkLeapYear(y)) // 如果是闰年，2月的天数为29，
			get_month_day[2] = 29;
		if (m < 1 || m > 12)
			continue;
		if (d < 1 || d > get_month_day[m])
			continue;
		if (ans1 == "") // s是合法日期的回文串，记录在ans1中
			ans1 = s;
		if (checkABABBABAstyle(s) && ans2 == "")
			ans2 = s; // s还符合ABABBABA型，记录在ans2中。
	}
	cout << ans1 << '\n' << ans2 << '\n';
	return 0;
}

8H：子串分值和（编程题20分）

解析代码1（暴力_过50%）

暴力思路解析：哈希表存储字母出现的次数，查看哈希表中是否有多个字母即可

最外层循环枚举一次走的步长
第二层循环枚举左端点
第三层循环将左端点~~~左端点+步长的这一段距离赋值
查找哈希表中是否存在元素，如果存在即 res++
memset：重新初始化哈希表
cout<<res<<endl;

时间O（N^3）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    int cnt[27] = { 0 };
    int res = 0;
    for (int len = 1; len <= n; ++len)//枚举长度
    {
        for (int i = 0; i + len <= n; ++i)//枚举左端点
        {
            for (int j = i; j < i + len; ++j)//将该段进行填充
            {
                cnt[s[j] - 'a']++;
            }
            for (int k = 0; k < 26; k++)//查找
            {
                if (cnt[k] != 0)
                    res++;
            }
            memset(cnt, 0, sizeof(cnt));//重新赋值为：0
        }
    }
    cout << res << endl;
    return 0;
}

解析代码2（小优化_过60%）

时间优化成O（N^2）

//}
#include <iostream>
#include <unordered_set>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int ans = 0;
	for (int l = 0; l < s.size(); l++)
	{
		unordered_set<char> S;
		for (int r = l; r < s.size(); r++)
		{
			S.insert(s[r]);
			ans += S.size();
		}
	}
	cout << ans << endl;
	return 0;
}

解析代码3（乘法原理_过100%）

乘法原理，时间O ( N ) ：解题思路：

每个字母只有在第一次出现时才有贡献度，因此可以统计每个字母在第一次出现的情况下，能被多少子串所包含；
用 last[s[i]] 记录字母 s[i] 上一次出现的位置；
那么往左最多能延伸到 last[s[i]] + 1，其到第 i 个字母一共有 i - last[s[i]] 个字母；
同理往右最多能延伸到 n，其到第 i 个字母一共有 n - i + 1 个字母；
二者相乘，就是该字母被不同子串所包含的总次数；

样例解释的排列就是这个思路，5 + 8 + 6 + 4 + 5 = 28

#include <iostream>
using namespace std;
typedef long long LL;
int last[200];
int main()
{
	string s;
	cin >> s;
	int n = s.size();
	s = ' ' + s;
	LL ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans += (LL)(i - last[s[i]]) * (n - i + 1);
		last[s[i]] = i;
	}
	cout << ans << endl;
	return 0;
}

9I：平面切分（编程题25分）

解析代码（数学）

题目解析：在同一个平面内，如果添加的每一条直线互不相交，则每添加一条直线，就会增加一个平面；当添加一条直线时，这条直线与当前平面内已有直线每产生一个不同位置的交点时，这条直线对平面总数量的贡献会额外增多一个。

结合图理解一下：

需要注意的是给的边可能会有重复。

如果用两个set集合，一个存边，一个存点，因为set集合会自动去重，所以不用再一个一个判断是否重边，但是set没有下标，不方便与之前的边进行比较。所以采取边输入边计算的方式，一旦获取一条边的信息后就存储到数组中，再和之前已经加入的边进行匹配，判断不重边后再计算交点个数。

#include <iostream>
#include <set>
using namespace std;
const int N = 1010;
long double L[N][2]; // 存储A，B 
long long ans = 1;
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> L[i][0] >> L[i][1];
		bool flag = false;
		for (int j = 0 ;j < i; ++j) // 判断是否重边
		{
			if ((L[j][0] == L[i][0]) && (L[j][1] == L[i][1]))
			{
				flag = true;
				break;
			}
		}
		if (!flag) // 若不重边,再判断交点数
		{
			// 记录每一条边加进来后与已有直线相交的不同位置的点 
			set<pair<long double, long double>> points;
			for (int k = 0;k < i;k++)
			{
				if (L[k][0] == L[i][0])
					continue;
				long double x = (L[i][1] - L[k][1]) / (L[k][0] - L[i][0]);
				long double y = L[i][0] * x + L[i][1];
				points.insert(make_pair(x, y)); // set自动去重 
			}
			ans += points.size() + 1;
		}
	}
	cout << ans;
	return 0;
}

10J：字串排序（编程题25分）

解析代码（dp）

蓝桥云课的思路：

蓝桥杯真题：字串排序_蓝桥杯字串排序-CSDN博客

//#include <bits/stdc++.h> // 字串切分
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int V, len, now, cnt[27], sum[27];
int get_max(int len)
{
    return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
bool check(int x, int n)
{
    memset(cnt, 0, sizeof(cnt)); // cnt记录后面n个位置放置的对应字符数量
    int add1 = 0, add2 = 0;
    for (int j = 26; j >= x + 1; --j)
    {
        add1 += sum[j]; // 1~pos-1里边比当前插入字符大的字符数量
    }
    sum[x]++; // 当前字符数量增加1
    for (int L = 1; L <= n; L++)
    {
        // ma保存最大逆序对个数 L-1-cnt[j]+num
        // L-1-cnt[j]是当前字符之后的比当前字符小的字符数量的最大值
        // num是1~pos+L-1前的比当前放置字符字典序大的字符数量
        int ma = -1, pos = 0, num = 0;
        for (int j = 26; j >= 1; j--)
        {
            if (L - 1 - cnt[j] + num > ma)
            {
                ma = L - 1 - cnt[j] + num;
                pos = j;
            }
            num += sum[j];
        }
        add2 += ma, cnt[pos]++;
    }
    if (now + add1 + add2 >= V)
    {
        now += add1;
        return true;
    }
    else
    {
        sum[x]--;
        return false;
    }
}
signed main()
{
    string ans = "";
    cin >> V;
    for (int i = 1; ; i++)
    {
        if (get_max(i) >= V)
        {
            len = i;
            break;
        }
    }
    for (int i = 1; i <= len; i++)
    {
        for (int j = 1; j <= 26; j++)
        {
            if (check(j, len - i))
            {
                ans += char(j + 'a' - 1);
                break;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

查看全文

http://www.kler.cn/a/589940.html