第23次CCF计算机软件能力认证 A B(思维题X2)

2023-08-01 21:09| 来源: 网络整理| 查看: 265

(还没找到题面，代码是靠记忆写出来的，也没地方交题不知道对没对，大体思路对了就行) 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 #define int long long using namespace std; const int N = 5e5 + 10; int n; int b[N]; sets; int calc() { cin >> n; int ans1 = 0, ans2 = 0; for (int i = 1; i //吐槽一下机房的编译器之旧，遍历set用迭代器来搞的，巨麻烦 ans2 += i; } cout 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 #define int long long using namespace std; const int N = 5e5 + 10, M = 1e4 + 10; int n; int a[N]; vectorg[M];//g[i]表示数组中数值i的所有位置 sets; int calc() { int res = 0; for (int i = 1; i res++; while (a[i] > 0 && 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

【本文地址】

公司简介

联系我们