M. 龙卷风摧毁停车场 笔者出的题，观察到我们只需要记录招式  的使用次数 ，以及是否使用招式  招式  一定是最后使用的，招式  的顺序无所谓 对于给定的出招序列 ，我们在已知  的情况下，可以比较  的优劣性 若 ，招数  更优，直接一次大招做完 反之，计算  可分成多少块 ，还余下多少，即  对于  份 ，我们使用更优的招数 ；对于余下的 ，我们比较  和  取最小值即可 该过程的时间复杂度为  #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fType int #defi...

L. 爆破鸭科夫 我们定义 √ 为可以到达终点，× 为不可到达终点 随着炸弹的依次爆炸，状态分布为 "√√√√...××××" 也就是必定从连续的一段 √ 变化为连续的一段 ×，中间存在一个分界点 题目其实就是让我们求这个分界点对应的爆炸时间 ，输出  怎么找呢？如果我们二分，外层是 ，这里  为  上界， 内层的  需要判一次当前图连通性，是  的 事实上由于本题维护的是连通性，而连通性在 只加不删 的时候可以 并查集 直接维护 所以我们应该直接时光倒流，从炸完的状态往回跑，找到第一个连通的时间点，此时对应的就是那个恰好炸掉最后一条逃生路径的炸弹 这样时间复杂度就变成了  其中  指的是 并...

K. 走地鸡学飞 注意到收益和限制都是常数，不随时间变化 我们定义走地鸡当前活动区间为 ，初始取  每次尝试往  和  的地方扩展升级，一直扩展到两边都不能扩展为止即可 由于 ，可将坐标离散化一下，方便后续扩展 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fType ll #define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++) #define foreach_sub(x, a, b) ...

J. 破译密码 题面故意整的很长，且题号靠后的签到题 我们发现三种不同加密规则得到的结果，其具备的特征也是唯一的：  同行规则： 是同行的，加密后也是同行 同列规则： 是同列的，加密后也是同列 矩阵规则： 是不同行不同列的，加密后也是不同行不同列  所以我们可以直接对每一组密文  逆向解密回去 对于  的情况，同时满足规则 ，但是题目只要求我们的明文可以合法，所以两种逆向选一种即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fType int #define foreach...

I. 走地鸡地走 模拟题，注意到 ，并且几个条件都只需要判断前几步 坑点在于，转向 的定义是不同时才视为转向，所以 UURRDDLLUU 其实也发生了连续四次转向都为顺时针的情况 可以在  的时间复杂度内完成，其中  是一个小常数 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fType int #define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++) #define foreach_su...

H. 回文王国 经典的计数题目，题目问的是  可以转换为  我们可先算出不修改字符下的答案，枚举比较  的右端点  然后计算  的总比较次数，以及多少次是  的，作差就能计算出  的贡献 对于修改字符的方案，记  表示第  个位置修改为  的变化量，也可以用类似的思路算出来 然后再枚举修改方案即可，细节看代码，有详细注释 事实上本题还存在不挂  的更精细写法，笔者这里的代码并不是最优实现 主要是一下子就想出来了，直接力大砖飞懒得优化了 #include <bits/stdc++.h> using namespace std; typedef long long ll; #defin...

G. 因数分解 博弈论，伪装成 nim 游戏的贪心题 注意到本题强调了，每次拿石子 必须从最左堆取，所以这不是一个 nim 游戏 博弈论下任何局面 必定为必胜/必败，我们设当前最左堆石子个数为   当  时，只能拿光，换成对手拿 当  时，我们一定可以拿  或者  个石子，使得石子个数变成  或者 ：  如果拿完后，对方必败，我们直接拿  个，从而必胜 如果拿完后，对方必胜，我们直接拿  个，让对方再拿  个，从而必胜  因此只需要知道第一个  轮到谁玩，就能知道谁是胜者了 #include <bits/stdc++.h> using namespace std; typedef ...

F. 除数链 和因子有关，直接质因数分解  我们定义  表示 ，则  表示  题目要求找到最长的除数链，我们发现对于  ， 代表的  和  代表的  满足  且  说人话：除数链往右扫的过程中，这个  元组中，至少有一个元素增加恰好  要最长，肯定是从  变到  我们需要加  次，定义  表示加到第  个位置 问题变成给你一个  的字符串，有多少种排列方案 显然根据高中数学常识，这就是  预处理 阶乘 和 阶乘逆元 即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fType...

E. 代号 N 笔者出的题，我们设第  条分支对应分配了  个脉冲设备 只需要在  的前提下，使得  最小即可 这个问题结构本身就是一个经典的二分答案，假设  的上界后看看所需要的  够不够即可 也可以贪心+指针去做，在  排序并前缀和预处理后，两者都可以高效解决 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fType int #define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++) #...

D. 水群 如图所示，我们需要从  走到  （图中 ） 两种不同的边对应不同代价，由于这个图不是 DAG，不能直接  可以直接套最短路 Dijkstra 解决           1  2  3  4  5            代码如下 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fType int #define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++) #define foreac...

C. 终会再相见 初中数学题，我们将  个人画在数轴上，重新排序    1  2  3  4  假设我们的相遇点为 ，将  这些人配对，记第  个人所处位置为  某一对  到  点相遇的代价为（假设 ）  其中  指  到距离较近的  或者  的距离的两倍，有  显然我们希望尽可能取第一种情况，不引入这个  容易发现此时不引入  的区间存在一个公共部分    1  2  3  4  区间 1-4  区间 2-3  我们只需要令  位于这个公共部分，就可以让所有情况下的  都不被引入了 当  为奇数时， 位于最中间点上 当  为偶数时， 位于最中间的两个点之间任意一个位置 笔者这里巧用了 0-i...

B. 找数 题意让我们找到出现次数最多的，数值最小的数，这是一个双关键字视角下求最值的问题 注意到值域取 ，我们可以用  存储  的出现次数，再扫一遍即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fType int #define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++) #define foreach_sub(x, a, b) for (fType x = a, _end_ = b...

A. 爆零什么的千万不要啊 总链接：https://blog.nowcoder.net/n/621ba39d00774b9c89afbe3c1e8935fa 本场比赛最难的题，属于构造题 构造题的证明往往比较复杂，需要投机取巧 但是本题不经过严谨证明很难 AC，所以还是老老实实证明吧 首先手玩一会找特殊情况， 是比较特殊的 当不为零的数字少于  时，我们的两个端点必定出现 ，无解 反之  直接往中间塞就行，没有影响，此时只需要考虑非零数 对于非零数，如果全为正或者全为负，必定有解 反之正，负都同时存在，此时如果总和 ，必定无解 反之我们不妨令 ，此时将正负分到两边 正数加完再加入负数的过程中，...