笨蛋也能看懂（就是啰嗦） 知识点：线段树 树状数组 我们来一步步推出做法。 1、首先思考 ，即长度大于等于2的回文串。 2、为了不出现如 或 这样的回文串，我们要保证连续三个字符都不一样。 3、即整个字符串 都是按照一个顺序重复排列的，例如 “” 或 “” 。而 的不同排序一共有 种：、、、、、。 4、那么对于操作 询问区间 ~ 的子串是否是字串，我们只要看该子串需要修改几个字符就可以形成上述排序的重复排列。 例如： s = r e d e d r e r r 变为 r e d r e d r e d 需要修改 个字符。但要变为 e d r e d r e d r ...

2023顺丰全球高校菁英挑战赛——编程方向个人题解 A： 遍历所给字符串，按照小写字母、大写字母、数字三种类型分别把字符加到三个字符串上。然后输出。 AC代码 void solve() { string s; cin >> s; string a, b, c; for (auto& i : s) { if (i >= 'a' && i <= 'z')a += i; else if (i >= 'A' && i <= 'Z')b += i; else c += i; } if (a.size()...

2023年福建农林大学程序设计校赛个人题解（无D解析) A-这是一道原题 问题解析 从绿色材料合成到金色材料。 用 whilewhilewhile 循环判断材料数是否能合成，能就合，合成后下一级材料数增加，原料数加上合成出的材料数。 AC代码 #include<iostream> using namespace std; #include<vector> #include<algorithm> #include<iostream> using namespace std; #include<vector> #include<al...

L、字符串 前置知识：字符串哈希 我们判断两个十进制的数是否相等，可以如下来拆分操作： 先判断个位数是否一样，再判断十位数是否一样……最后判断最高位是否一样，如果全部一样那么这两个十进制数就是一样大的。设个位数是a，十位数是b……最后一位数是z，那么这个数的大小就是：(a* 10^0)+(b * 10^1)+……+(z * 10^n).只要这个数相等，那么这两个十进制数也是相等的。 这个其实就是字符串哈希的原理。我们可以把字符串转化成一个base进制的数，只要两个字符串转化成的数相同，那我们就认为这两个字符串是相等的。但base必须是一个质数，才能保证正确性。 问题解析 记录下s的长度为len...

D、树上祖先询问题解 前置知识：dfs序，倍增法求lca OI wiki上的倍增LCA模板， 看文字嫌累还有b站的讲解视频（个人觉得不错） 题目主要是让我们求A集合内全部点的公共祖先，对于求多个点的最近公共祖先，我们并不真的要对所有点两两都求一次。我们只用取这些点中dfs序最小和最大的两个点来求最近公共祖先就行。 证明可以看看去如何在 DAG 中找多个点的 LCA ? 看，这里不多做补充。 问题解析 知道了这两个前置知识后，这题就变的很简单了。 我们可以先对所有的点来一遍前序遍历，求得他们的dfs序。 用A集合中dfs序中最小的点和最大的点来求得A集合的最近公共祖先z 看A集合中是否有z，...

A、Sum 吐槽 再经过"YE5"和"N0"后又一次被牛客恶心到辣，为什么是对1e7+7取模啊喂！ 前置知识：排序+贪心 问题解析 每次我们可以合并至少两个数，并获得等同于他们之和的分数总和。 那么对于贪心来说，我们可以先对所有数进行降序排序（大的在前面，小的在后面）。 每次合并最大的两个数即可，而因为每次合并后数组最大的两个数肯定是原数组最大的数和当前合并产生的数。 我们可以用一个变量sum记录每次合并后的值，下一次合并只要把数组剩下的最大的值加到sum上，就算完成合并了，每次合并后把sum加到我们的结果上（我这里用一个变量res来存储结果）。 我们就持续合并，直到数组只剩下一个数，或者合并...

D、Word 前置知识：BFS（广度优先搜索） 问题解析 看到数据后我们发现，一共最多只有2000个字符串，字符串的最大长度才20，而且只有一个询问而已。那就可以先想暴力了，加上这里要求的是把s变成t的最少操作数，我们可以采用BFS的方法。 初始队列中存入字符串s。 在每一步的bfs中，我们可以枚举当前字符串的每一个位置，再在每个位置枚举a到z共26个字母，看修改过后的字符串是否有在那n个字符串出现即可，如果出现了，我们不妨把它变成这一个字符串，再把这个字符串存入队列中。直到这个字符串变成t为止。 根据BFS的性质，第一个变成字符串t的一定是最少次数。 题目还要求我们输出变化的路径，那我们可以...

C、School 前置知识：区间合并+二分查找 区间合并：对于多个区间来说，如果其中有区间的范围有重合，那便可以把他们合并成一个区间，这样做对于某些对区间的处理就能方便简洁很多。 问题解析 为了方便处理，我们可以直接把所有时间改成分钟的形式，比如1小时10分，对于我们正常的时间来说，这就是70分，那么1小时10分到2小时20分，就是70分中到140分钟。 我们直接把所有的不能打电话的时间段转化成分钟形式的区间，对于样例来说： 输入 3 24 60 2 7 0 11 15 14 20 17 35 18 50 21 10 7 1 21 11 输出 No Yes 不能打电话的时间段就为： 42...

B、Gaming 前置知识：线段树（区间修改+单点查询） 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 logn 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 具体可以移步https://oi-wiki.org/ds/seg/ 学习 问题解析 题目说，只要有一个debuff我们没有拿到，那么我们就可以战胜boss。那么我们可以去枚举每个debuff，看哪个debuff我们不要它后，得到的分数依然是最大的。（这里指的debuff是1~m中某个具体的数） 而我们不要哪个数，说明只要包含这个数的房间我们都不能进。 拿样例来说...

前言 不会倍增不会树刨不会树上差分，然后自己想了个On的解法过了（虽然事后有佬说我这个和树上差分差不多）但没有什么前置知识，只要会dfs就行。然后赛时debug了两小时都是wa，正当崩溃的时候才发现题目没有保证给的边（u,v)一定是u到v的单向边，遂改成双向边，就AC了（哭）。 题意 有一个以1为根节点的树，树有n个节点，每个节点有一个最大移动距离di，表示他们只能向上移动di个点，走到根节点为止（只能往上走，不能转方向去往别的子树），问对于每个点，有多少点能够到达它（包括自己）。 样例解释 输入 10 1 2 2 3 2 4 3 5 4 6 4 7 1 8 8 9 8 10 0 0 1 2 ...

PS：之前图有误，已更新 D、Jobs (Easy Version) 前置知识：二维前缀min，快速幂 题意 题目是说给你n个公司的求职岗位，每个岗位有三个要求：EQ、IQ、AQ，当你的这三项质数都大于等于这个职位的标准时，这个公司就会邀请你入职。现在你有q个朋友，你要算出他们分别会被多少个公司邀请，再根据公司的数量算出： 其中ans是第i个朋友收到公司邀请的数目，seed是题目给我们的随机数种子。 问题解析 先说一下题目给的这一段代码： #include <random> std::mt19937 rng(seed); std::uniform_int_distribution...

A、Ancestor题解 前置知识：dfs序，倍增法求lca OI wiki上的倍增LCA模板， 看文字嫌累还有b站的讲解视频（个人觉得不错） 题目主要是让我们求长度为k-1的点集的最近公共祖先（一个点被删了），对于求多个点的最近公共祖先，我们并不真的要对所有点两两都求一次。我们只用取这些点中dfs序最小和最大的两个点来求最近公共祖先就行。 证明可以看看去如何在 DAG 中找多个点的 LCA ? 看，这里不多做补充。 问题解析 知道了这两个前置知识后，这题就变的很简单了。 我们可以先对所有的点来一遍前序遍历，求得他们的dfs序。 根据dfs序对k集合的点进行升序排序（两个树的dfs序...

北华大学计算机程序设计算法提高训练营个人赛（无L） 题面相当有意思了，题目感觉出的也挺好，L防ak题吧这也太难了 A-洛姐打题日记 AC代码 #include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterato...