2023年第十四届蓝桥杯大赛软件类省赛C&C++大学C 组真题（代码&完整题解）_2023年蓝桥杯c组省赛题目及答案

C题-三国游戏⭐

标签：贪心

简述：三个国家初始人数都为0，n个事件，第i个事件若发生每个国家分别加Ai，Bi，Ci人，求最多发生几个事件使得两个国家人数之和小于第三国

链接：三国游戏

思路：分别求个事件第三国与另两国人数和之差后排序，求前k项差值和为正，比较三个k

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051976

D题-填充⭐⭐

标签：贪心

简述：填充01串中的？使得互不重叠的 00 和 11 子串最多，输出子串个数

链接：填充

思路：遍历默认i之前的为最优，对于i，与i+1相同 或 与i+1中有一个？都认为是一组子串

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051976

E题-翻转⭐

标签：贪心

简述：如果 S 中存在子串 101 或者 010，就可以将其分别变为 111 和 000，操作可以无限重复。最少翻转多少次可以把 S 变成和 T 一样。

链接： 翻转

思路：要求步骤最少->S每个位置最多修改一次->从头开始遍历不匹配就翻转->翻转不了就-1

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051976

F题-子矩阵⭐⭐⭐

标签：STL-set

简述：求一个nm矩阵中每一ab子矩阵的最大最小值之积的和

链接：子矩阵

思路：multiset维护区间最值 注意：multimap用迭代器只删除重复元素中的一个

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051976

G题- 互质数的个数⭐⭐⭐

标签：数论-欧拉函数,数论-快速幂

简述：求小于a^b与ab互质的数的个数

链接：互质数的个数

思路：利用欧拉函数φ(a^b)=φ(a)*a(b-1)

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051976

H题- 异或和之差⭐⭐⭐⭐

标签：数论-位运算,字符串-字典树

简述：n 个元素的数组 Ai。求出不相交的子段内的数的异或和的差值的最大值。

链接：异或和之差

思路：01字典树，里面存前缀异或和，然后查询[1,i][i,n]的最值，做个dp最后枚举答案。

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051976

I题- 公因数匹配⭐⭐⭐

标签：数论-质因数

简述：找出最早出现两次质因数的位置

链接：公因数匹配

思路：考虑到 $a_i$ 很小，所以首先预处理出1 ~ 1000000 所有素数，然后对于每个素数枚举其倍数，算出每个数的质因子，这里时间和空间复杂度大概是 $O(loglogn)$，然后对于每个 $a_i$ 枚举其质因子，然后看之前是否有数有相同质因子即可。最后排序输出答案

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051976

J题-子树的大小⭐⭐⭐

标签：数据结构-m叉树

简述：n个节点的m叉树第k个节点有几个子树

链接：子树的大小

思路：运用m叉树的性质,第i层的结点个数是$m^i$,找到n和k所在的层，计算k往下直到n所在层每层节点数,注意:ll t和max(oLL, )

ACcode：

完整代码：https://download.csdn.net/download/weixin_45741872/89051976