本文主要是介绍第十四届蓝桥杯大赛软件赛省赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
第十四届蓝桥杯大赛软件赛省赛
2.日期统计
小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的范围之内。
数组中的元素从左至右如下所示:
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
现在他想要从这个数组中寻找一些满足以下条件的子序列:
- 子序列的长度为 8;
- 这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期,并且
要求这个日期是 2023 年中的某一天的日期,例如 20230902,20231223。
yyyy 表示年份,mm 表示月份,dd 表示天数,当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。
对于相同的日期你只需要统计一次即可。
本题的结果为一个整数,在提交答案时只输出这个整数,输出多余的内容将无法得分。
枚举2023年的每一个日期,去字符串中判断是否合法
#include <bits/stdc++.h>
using namespace std;
int months[] =
{0,31,28,31,30,31,30,31,31,30,31,30,31
};
int cnt;string s = "5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3";bool check_date(string date)
{int idx = 0;for(int i = 0; i < s.size(); i ++){if(s[i] == date[idx]){idx ++;if(idx >= 8)return true;}}return false;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);for(int month = 1; month <= 12; month ++){for(int day = 1; day <= months[month]; day ++){string date = to_string(20230000 + month * 100 + day);
// cout << date << endl;if(check_date(date))cnt ++;}}cout << cnt << endl;return 0;
}
答案:235
2.01串的熵
对于一个长度为 n 的 01 串 S = x1x2x3…xn.
香农信息熵的定义为:
。
其中 p(0), p(1) 表示在这个 01 串中 0 和 1 出现的占比。
比如,对于S = 100 来说,信息熵 H(S ) = - 1/3 log2(1/3) - 2/3 log2(2/3) - 2/3 log2(2/3) = 1.3083。
对于一个长度为23333333 的 01 串,如果其信息熵为 11625907.5798,且 0 出现次数比 1 少,那么这个01 串中 0 出现了多少次?
本题的结果为一个整数,在提交答案时只输出这个整数,输出多余的内容将无法得分。
#include <bits/stdc++.h>
using namespace std;
const int m = 23333333;
double p0, p1;
double hs = 11625907.5798;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);double hs_cal = 0;//存储计算出来的串熵for(int i = 0; i < m / 2; i ++)//0出现次数比1少只要枚举一半{p0 = i * 1.0 / m;p1 = (m - i) * 1.0 / m;
// cout << p0 << " " << p1 << endl;hs_cal = i * 1.0 * p0 * (log(p0)/log(2)) + (m - i) * 1.0 * p1 * (log(p1)/log(2));if(fabs(hs_cal + hs) < 1e-4){cout << i << endl;return 0;}}
}
答案:11027421
1.冶炼金属
题目描述
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。
这个炉子有一个称作转换率的属性 V,V 是一个正整数,
这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X。
当普通金属 O 的数目不足 V 时,无法继续冶炼。
现在给出了 N 条冶炼记录,每条记录中包含两个整数 A 和 B,
这表示本次投入了 A 个普通金属O,最终冶炼出了 B 个特殊金属X。
每条记录都是独立的,这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
根据这 N 条冶炼记录,请你推测出转换率 V 的最小值和最大值分别可能是多少。
题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数 N,表示冶炼记录的数目。
接下来输入 N 行,每行两个整数 A、B,含义如题目所述。
对于 30% 的评测用例,1 ≤ N ≤ 100。
对于 60% 的评测用例,1 ≤ N ≤ 1000。
对于 100% 的评测用例,1 ≤ N ≤ 10000,1 ≤ B ≤ A ≤ 1,000,000,000。
输出格式
输出两个整数,分别表示 V 可能的最小值和最大值,中间用空格分开。
输入样例 复制
3
75 3
53 2
59 2
输出样例 复制
20 25
数据范围与提示
当 V = 20 时,有:⌊75 / 20⌋ = 3,⌊53 / 20⌋ = 2,⌊59 / 20⌋ = 2,可以看到符合所有冶炼记录。
当 V = 25 时,有:⌊75 / 25⌋ = 3,⌊53 / 25⌋ = 2,⌊59 / 25⌋ = 2,可以看到符合所有冶炼记录。
且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。
#include <bits/stdc++.h>
using namespace std;
int Vmax = 0x3f3f3f3f, Vmin = 0;
int n;
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;while(n --){int a, b;cin >> a >> b;Vmax = min(Vmax, a / b);Vmin = max(Vmin, (a / (b + 1) + 1));}cout << Vmin << " " << Vmax << endl;return 0;
}
1.整数删除
题目描述
给定一个长度为 N 的整数数列:A1, A2, … , AN。你要重复以下操作 K 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。
并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。
输入格式
第一行包含两个整数 N 和 K。
第二行包含 N 个整数,A1, A2, … , AN。
对于 20% 的数据,1 ≤ K < N ≤ 10000。
对于 100% 的数据,1 ≤ K < N ≤ 5 × 105,0 ≤ Ai ≤ 108。
输出格式
输出 N − K 个整数,中间用一个空格隔开,代表 K 次操作后的序列。
输入样例 复制
5 3
1 4 2 8 7
输出样例 复制
17 7
数据范围与提示
数列变化如下,中括号里的数是当次操作中被选择的数:
[1] 4 2 8 7
5 [2] 8 7
[7] 10 7
17 7
纯模拟可过30%
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> k;vector<int> a;for(int i = 1; i <= n; i ++){int x;cin >> x;a.push_back(x);}while(k --){//寻找最小值int x = *min_element(a.begin(), a.end());for(int i = 0; i <= (int)a.size() - 1; i ++){if(a[i] == x){if(i - 1 >= 0) a[i - 1] += x;if(i + 1 <= (int)a.size() - 1) a[i + 1] += x;a.erase(a.begin() + i, a.begin() + i + 1);break;}}}for(int i = 0; i < (int)a.size(); i ++)cout << a[i] << " \n"[i == a.size() - 1];return 0;
}
正解:优先队列+双链表
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL;
typedef pair<LL, LL> PLL;
priority_queue<PLL, vector<PLL>,greater<PLL>> q;
LL a[N], l[N], r[N];
int n, k;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> k;for(int i = 1; i <= n; i ++){cin >> a[i];l[i] = i - 1, r[i] = i + 1;q.push({a[i], i});}while(k && !q.empty()){auto t = q.top();q.pop();LL val = t.first, id = t.second;if(a[id] == val){//可以删除a[l[id]] += a[id], a[r[id]] += a[id], k --;l[r[id]] = l[id], r[l[id]] = r[id], a[id] = 0;}else{q.push({a[id], id});}}for(int i = 1; i <= n; i ++)if(a[i])cout << a[i] << " ";return 0;
}
这篇关于第十四届蓝桥杯大赛软件赛省赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!