本文主要是介绍2024蓝桥杯省赛C++软件算法研究生组题解+游记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A题
给你一个音游的游戏记录log.txt，判断玩家的最高连击数
题解
水题，但是要小心，miss的键需要重置k=0，超时但正确的键重置k=1
个人答案是9
B题
计算1~2024041331404202中有多少个数x满足x! - x*(x+1)/2能被100整除
题解
首先x=10时，x！就会被100整除，所以只需要后面x*(x+1)/2能被100整除即可
可以数论分类讨论，x*(x+1)的因子需要包含3个2和2个5，然后通过x和x+1的奇偶性来删除一些讨论的情况
但是我选择打表，发现x每1000构成一个循环，1~1000只有20个x满足条件
然后再暴力判断一下1~10是否有满足原条件的，发现只有1满足
所以最后答案就是1+2024041331404202/1000 * 20 + 4（24、175、199、200<=202）
40480826628089
C题
一个长度为n的数组a[i]
给出数字的封闭图形数的定义
12357没有封闭图形，0469有一个封闭图形，8有两个封闭图形
要求以封闭图形数为第一关键字，数字值为第二关键字给数组排序。
n<=10^5,a[i]<=10^9
题解
结构体排序基础题
每个数字先算出它的封闭图形数作为第一关键字，再把它本身的值作为第二关键字。
结构体排序即可。
D题
给出n个长度为m的环形字符串，设每两个字符串的边权为LCS（最长公共子串）
求连接这n个字符串的最大生成树的代价
n<=200,m<=50
题解
显然瓶颈在建图，后面随便上一个生成树算法都能过。
看题的时候呆住了，想了一下自己SA和SAM都不会，这下咋办
突然发现不需要高级的算法
先O(n^2)枚举所有字符串对
再O（logm）二分答案最长公共子串的长度
最后O(mlogm)哈希检查LCS是否存在
对每个字符串先预处理出各个长度下的哈希值，保存到map里面
总时间复杂度O(n^2*m*(logm)^2)，空间复杂度O(n*m^2)
E题
数轴上有n个点，第i个点在ai，从0开始，走一步将坐标-1 或者 +1，一共可以走m步，问最多可以经过多少个点，重复经过一个点只算做一次。
n<=10^5, ai<=10^6,m<=2*10^6
题解
简单贪心
显然不可能反复横跳找点，这样会浪费步数
所以要么向左走到头，然后向右走用完步数；要么反过来。（路径只会有一个拐点）
发现m实际上很小，甚至可以直接暴力前缀和，直接统计m范围内的点。
直接枚举向左、向右走到的位置（拐点），然后前缀和O(1)查询即可。
时间复杂度O(m)
O（nlogn）做法也差不多，把点正负分类之后，用lower_bound查询回到0后剩余步数可以覆盖多少点即可。
F题
一个矩阵，每行有一个权值ri，每列有一个权值ci
一个点（x，y）能走到另一个点（z，y），当且仅当，rx<rz且不存在u使得rx<ru<rz
一个点（x，y）能走到另一个点（x，w），当且仅当，cy<cw且不存在v使得cy<cv<cw
现给出T个询问，每次询问从点(x,y)到点(z,w)的路径条数，答案mod 1e9 +7
n,m,T<=10^5，Ri<=10^8
题解
当时一看就不想做了，看了一下道题发现有50%的白送分，就稍微推了一下式子
首先，行列的顺序在这道题中不重要，所以直接进行一个离散化（排序+去重）
题目要求的答案就直接变成了一个网格图路径计数问题，显然组合数
然后预处理一下组合数，搞定了（虽然期间还把题目读错了一次，以为是从大到小走。。）
但是！！！还没完
这个题坑点就在于，有重复的ri和ci值，在路径中也会贡献方案数
而这一点在出题人精心构造的样例下被完美回避了，稍有不慎就是0分和满分的区别
我们按行来看一下，发现如果从（1，1）走到（4，4），实际上就是给答案乘上了当前2的这一行可以选择的方案数，同理列也一样。
但是如果我们从（1，1）走到（3，3），情况就不一样了，由于我们无法在相同ri和ci的地方进行跳跃，只能走严格大于的路，我们就需要提前决策好哪些点是不能走的。
所以此时的答案就不应该乘上当前阶段的行列重复数
最终答案就是
Rcnt[i]表示Ri值第i小的有多少行（也就是重复的ri的数量）
另外还有一些坑点，例如在ri相同时，还需要判断原始的行数是否相同，才能确定是否有答案。列同理。在ri和ci都相同时，就需要判断原始坐标是否一致。
G题
给出一个n个点的树，每个点有权值ai，求树上不相邻两点的权值异或的最大值。
n<=10^5，ai<=2^31-1
题解
先写了个暴力，就去看最后一题了，最后才来想的正解
发现很简单
直接把所有点插入01Trie树里面
然后枚举1~n的所有点，在Trie树中删除其相邻点，利用贪心遍历01Trie树查询最大异或值
然后再恢复所有相邻点即可
每个点u会被删除d[u]次（u的度数），均摊下来就是边数次，O（n）级别
查询和插入修改都是O（logn）
总复杂度O(nlogn)
不过我比较fw，最后没有调出来，只交了一个暴力。
H题
给出一个n个点的树，根为root，每个点有权值ai。
求每个点u的子树中有多少个节点v，满足av<au且av不整除au
你只需要输出每个子树答案的和。
n<=10^5，ai为1~n的一个排列。
题解
当时一看，觉得这题是啥玩意啊
然后看了看性质，发现非常可做
首先，按照子树一个一个算肯定是不可能的，肯定需要一大堆高级数据结构
我们换个思路，既然它求整体的答案，我们可以把枚举子树改为枚举链
因为一个节点v给u做贡献，u必定会在v到root的路径上，而一个点v也只会对v到root路径上的点做贡献。
于是我们就从上到下dfs，维护一个树状数组，里面装当前点u到root的路径上点的权值，
这样就可以直接查询到这条路径上 有多少点权大于当前点权
那剩下一个不整除的条件应该怎么办
暴力扫描即可！！！
维护一个桶，来看路径上是否存在点权为x的点
然后对一个点a[u]，暴力枚举a[u]的所有倍数，有一个存在的点，就让答案减一掉即可。（倍数肯定比a[u]大，所以不会多减）
这样做的均摊时间复杂度O（n*ln(n)）
总的时间复杂度也是O（nlogn）（树状数组logn，暴力枚举均摊nlnn）
代码？之后发
游记
Day0
忙碌的一天，上午早八上课，听不进去，开始看莫比乌斯反演，心想着，这次考研究生组是不是题会很难啊，估计有什么字符串网络流主席树平衡树CDQ分治之类的东西，反正全都看看。
课上就劈里啪啦的默写模板。
下午又是满课，看了点计数，晚上吃个饭，回来又是排练
回寝本来打算再复习一下，结果看了一晚上下象棋
好一个准备充足
Day1
早上8点醒，有点困。
然后开始比赛了。
先看了前两道填空，发现A题挺好做的，freopen一下，读个文件，小统计一下
然后B题打个表找了下规律，就过去30分钟了
10分钟写完C题结构体排序，开始看D题，开始后悔自己没有看SAM，毕竟n*m是10000，说大不大，说小不小，时限还给的一秒，九年编程，字符串题还是只会哈希。
大概过了20几分钟，发现直接二分求LCS就搞定了，呆
好久没写哈希了，又写了20几分钟，调完就10：27了
看E题，这个数轴游走取值勾起了我不好的回忆，想当年做了一道180多行的分类讨论贪心也是长这样。原题重测背了我好几个个小时才背下来。
结果发现只有一个拐点，是个简单贪心，10分钟过了，10：47。
看F题，开始还有点懵逼，然后发现就是一个离散化+网格路径计数，正兴高采烈地写完准备下一题的时候，发现有点不对劲，ri和ci会重复，瞬间就汗流浃背了（汗流浃背了吧~小老弟），但是又发现了一个很好的性质，可以直接把重复的贡献单独拿出来算，就结束了。一看时间11：20，人麻了。
看G题，先想到是01Trie树合并，感觉研究生组目前还没有题上强度，到G题应该开始加码了吧，然后一看，发现一共就只有8道题，瞬间就轻松了。但是我不想些01Trie树合并，50%的O(n^2)暴力它不香吗，那肯定香啊，十分钟暴力走人。
最后到了H题，看了5分钟，转换一下枚举方式之后，发现直接暴力可以均摊复杂度O（nln(n)），直接过了，有点难以置信，这居然能让我给做出来了？！但是时间已经不多了，还有个01Trie合并没写，就直接开写了，12：00过了样例，感觉没毛病。
回来写G题的01Trie树合并，各种细节处理、空间优化，写了半个小时，发现不对劲啊，有更简单的做法，直接一个01Trie树插入加删除不就搞定了，此时只剩下30分钟了，然后删了重新开写，写了15分钟就写完了，然后开始调，调到最后都没有调出来，有点难受。
有生之年能不能AK一次啊。
这篇关于2024蓝桥杯省赛C++软件算法研究生组题解+游记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
