J题 | 终于再见 解题思路： 对于所有繁荣度为a的城市，以它们为起点bfs遍历所有繁荣度小于它们的城市，可以得到那些城市到繁荣度为a的城市的距离，这可能会是答案，但也许存在更短的路径。 假设有所有城市的繁荣度去重后有k种，那进行k次bfs遍历，在更新路径的时候和原答案比较，最后可以得到所有正确答案，时间复杂度为O(k×(n+m))，会不会太大了点。但对于本题，可以证明繁荣度的种数最多为√m种，因此时间复杂度为O(√m×(n+m))。 示例代码： #include <bits/stdc++.h> #define int long long #define pii pair<i...

C题 | Inverted World 解题思路： 当处理完毕时，s要么是形如101010...的字符串，要么是形如010101...的字符串。以一种为例（另一种处理方法完全copy这一种），若s原来是1110011，处理完毕后是1010101，会发现需要反置原字符串第2，5，6位，对应字符为101，我们只需要处理它们，其他不需要考虑，相当于是把101的所有字符反置，我们要求最小化的操作次数。 string need_reverse(int mode, string s) {//通过输入的字符串得到需要反置的字符串 string ret; for (int i = 0; i < s.si...

E题 | 01矩阵 解题思路： 如图所示，n为7时可以这么构造，白色表示填充0，蓝色表示填充1，拓展一下，欸？是不是觉得n为任何值时都可以这么构造？对的！这是一种解法！这道题一下子就变得过于简单了。  示例代码： #include <bits/stdc++.h> #define int long long using namespace std; signed main() { int n; cin >> n; //啊，还要看示例代码吗 //已经很简单了喵 for (int i = 1; i <= n; i++) { int zero_or_one = 0; fo...

G题 | Digital Folding 解题思路： 分类讨论：   1.l=r:显然结果是l或r的折叠数。   2.l!=r:    若r是形如100...0这样最高位是1,其余全为0的数： 最优结果应该是r-1的折叠数，位数比r少1，全部由9构成。     否则： 此时可以保证最终的答案的位数和r一致，若此时r是k位数，l的位数比r小，可以把l改成首位末位均为1，中间有k-2个0的数，把问题转化成l和r位数一致的情况。此时可以贪心，尽可能多的让最低位为9构造折叠前的数字。为了保证构造数字的合法性，从最高位开始前往后遍历l，r，若l，r当前位相等，则待折叠数字当前位和l，r当前位一致，若出现...

A题 | A+B Problem 解题思路： 题目给出表示每个灯管点亮概率的整数pi，则每个灯管点亮概率是pi%，故障概率是(100-pi)%，这时如果要显示器显示某个合法数字，那要保证参与显示这个数字的所有灯管都点亮，而其他灯管全部故障，这时显示对应数字的概率就是需要点亮的灯管对应的概率的乘积再乘上所有故障灯管故障概率的乘积。 我用on数组存取每个灯管点亮的概率，off数组存取它们故障的概率，number数组存显示每个数字的概率，它们存的是整数，实际上第i根灯管的点亮概率是on[i]÷100，下面的几乎所有运算也像这样省略除号及之后的内容，需要作除法的操作统一留到最后处理。 根据on和off...