[数据结构与算法]第23次CCF计算机软件能力认证 A B(思维题X2)

(还没找到题面，代码是靠记忆写出来的，也没地方交题不知道对没对，大体思路对了就行)
A题:
假设有一个数组a[N]，构造一个数组b[N]使得b[i]是a[1]到a[i]中的最大值，现给出b数组，让你构造a数组，a数组可能性有很多，只需要数组总和最大的a数组的值和总和最小的a数组的值
其实这题面向样例编程就能解出来了，但其实还是用的贪心思想
b数组就像是对a数组每一位上限的一个限制
想要构造出来的a最大，就是让a顶着b的上限去搞(说白了就是b)
想要构造出来a最小，只需要在每次上限发生变化时，在那个位置放一个上限值，其他位置全部放0就好(就是b数组去重后的值)
代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n;
int b[N];
set<int>s;

int calc() {
	cin >> n;
	int ans1 = 0, ans2 = 0;
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		ans1 += b[i];
		s.insert(b[i]);
	}
	for (auto i : s) { //吐槽一下机房的编译器之旧，遍历set用迭代器来搞的，巨麻烦
		ans2 += i;
	}
	cout << ans1 << " " << ans2 << endl;
}

void solve() {
	cin >> n;

}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

B题:
给定一个非负数组，你可以选择一个数值K，使得数组中小于K的值变成0，要让变化后的数组正数块最多
比如
1 2 3 0 0 2 0 0 1 1 2 8 0
中的整数块就有
1 2 3| 2 | 1 1 2 8 三个
数据很有个性，数组长度5e5，元素最大值1e4。
暴力做法:枚举K值，找最大正数块，但只能拿70分(挺群友说优化常数可以摸到80分，不知道是什么神仙优化)
这题坑点就在于以前csp的第二题一般考的都是些简单算法,惯性思维下就往着板子算法方面搞了，所以我就尝试了以下搞法:
二分/三分(结果打表出来发现没有单调性)
模拟退火(没有模拟退火的板子，随机数的有几个单词写不出来)
分治(写了一半发现复杂度反而提高了Orz)
然后写到后面才意识到是思维题
就以1 2 3 0 0 2 0 0 1 0 2 1 8 8 而言
初始情况下，有3个块
如果我们等于1的数变成0
最左边的那个1变成0，可以看到最左边那个1的左边没有数（或者可以当做是0），右边是一个非0数，将左边这个1变成0后依旧有4个块，将其变成0后对正数块数无贡献度
然后看中间那个1，它的左边是0，右边是0，把它变成0后就少了一个正数块，贡献度为-1(del=1)
看右边那个1，它的左边不为0，右边不为0，把它变成0后就多了一个正数块，贡献度为1(add=1)
所以，在将所有等于1的位置变成0后，还有4个块(原本块数+add-del)
现在将数组变成了0 2 3 0 0 2 0 0 0 0 2 0 8 8
现在将所有2变成0，第一个2左边为0，右边不为0，对块数无影响
中间的2左边为0，右边为0，del=1;
右边2左边为0，右边为0，del=2
所以将2变成0后现在答案是2(4+add-del)
变成了0 0 3 0 0 0 0 0 0 0 0 0 8 8
一直减下去，直到所有数变成0，取期间答案的最大值
代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10, M = 1e4 + 10;
int n;
int a[N];
vector<int>g[M];//g[i]表示数组中数值i的所有位置
set<int>s;

int calc() {
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] > 0) {
			res++;
			while (a[i] > 0 && i <= n)
				i++;
		}
	}
	return res;
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		g[a[i]].push_back(i);
		s.insert(a[i]);//去重排序
	}
	int ans = calc();//计算最开始有多少正数块
	int now = ans;
	for (auto i : s) {
		if (i == 0)
			continue;
		int add = 0, del = 0;
		for (auto j : g[i]) {
			if (a[j - 1] == 0 && a[j + 1] == 0)
				del++;
			if (a[j - 1] != 0 && a[j + 1] != 0)
				add++;
		}
		now += add - del;//当前答案
		ans = max(ans, now);//最优答案
	}
	cout << ans << endl;
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

以下开始口胡:
简单提一下其他题
C:要把随机数代码中的next改一下，否者本地能编译，交上去就CE QWQ
大模拟题，由于神经递质的传递有延时性。把神经递质的传递事件拿vector储存起来，在新的一轮时间里拿出来一个个加(在收获三个CE和一个RE时候考试结束QWQ)
D:暴搜拿了10分，暴搜的时候要注意特判一下n=1，听群友说正解要用数位DP(就算知道了也写不出来Orz)
E:感觉应该是主席树，手里没主席树板子写不出来QWQ，本来想的是把C题搞了再来暴力写E骗点分(然后就没有然后了)