第十四届蓝桥杯大赛软件赛省赛

对于一个长度为 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 可能的最小值和最大值，中间用空格分开。

输入样例复制

输出样例复制

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;
}