第十四届蓝桥杯大赛软件赛省赛
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;
}
