这新生赛质量也太差了吧，不打了。

D 一道看上去就很链表的模拟题。vim 使用者对此题有些莫名的感慨…… 在 Normal Mode 下  按下 i ：进入 Insert Mode 。 按下 f ：紧接着一个小写字母 char，若当前光标后（右）方有至少一个 char ，将光标移动到其所在位置，否则不移动。 按下 x ：删除当前光标所在位的字符，后面的字符均会前移一格。 按下 h ：将光标向左（前）移动一格，若无法移动就不移动。 按下 l ：将光标向右（后）移动一格，若无法移动就不移动。 若按下了其他字符：无任何效果。  在 Insert Mode 下  按下非 e 小写字母 char ：在光标当前位置前插入这个字母 char...

E 看上去就很水的题目，然而给的限制是 导致必须使用 vector 存图，于是频繁出锅，卡了我很久。一开始使用并查集做法，具体思路如下：使用维护 的并查集，将边界放在同一集合中，将 # 点看做障碍，每个 . 点四方向合并集合，最后统计非边界集合的大小和，加上 # 点数量即为答案。由于不明原因锅了，改写搜索。 搜索的思路就更加简单了，从每个未访问过的点开始搜索，同时维护当前搜索到的联通块的大小，若遇到边界则打一个标记，代表该联通块大小不计入答案中。复杂度为 。 #include <cstdio> #include <algorithm> #include <vect...

本文亦发表于笔者博客：https://www.codein.icu/nowcoderweekly19/ C 第 次长出来的花瓣数记为 ，可以得到 ，进而推知 ，而记录所有 的和即为答案。构造 的初始矩阵，分别代表 和 ，，构造一个 的转移矩阵矩阵，用矩阵快速幂即可。建议自己手写个表感受一下数据，方便初始构造。当然，具体构造方法各位按自己顺手的来吧。 #include <cstdio> #include <algorithm> #include <ctype.h> const int bufSize = 1e6; #define DEBUG inline ch...

本文亦发表于笔者博客：https://www.codein.icu/nowcoderweekly19/ B 赛上看错题，导致一直不知道如何下手。解说一下题意，给出若干个三元组 ，要求满足对于 ，找出第一个三元组，在添加该三元组前可满足条件，在添加该三元组后无法满足。 这种最值问题，很容易联想到二分。若前 个三元组时不满足条件，则前 个三元组时一定也不满足，二分找出分界点即为答案。 接下来考虑如何有效地判断是否有满足条件的解。 对三元组按 分类，同 下的若干线段 ，由于数字两两不相同，也就是 有唯一确定的 ，因此线段一定有交集，否则无解。 此外，还需要保证在 中，最小值为 ，因此若有 的线段 位...

本文亦发表于笔者博客：https://www.codein.icu/nowcoderweekly19/ A 考虑选出每个人当队长时，被选数组的方案数为多少。每个人状态有2种：选与不选，而选定队长必须选，因此有 种包含该人且为队长的选人方案。总方案数即为 ，注意取模即可。 #include <cstdio> #include <algorithm> #include <ctype.h> const int bufSize = 1e6; inline char nc() { #ifdef DEBUG return getchar(); #endif static...

Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：https://www.codein.icu/nowcoderweekly16/ 似乎网上没这道题题解，于是全场……一开始看错题了，以为黑白球必须分别扎堆，其实不需要。可以使用动态规划来解决，由于要求顺序，那么：设前 个球中，有 个白球， 个黑球，那么对应的黑白球编号一定是 和 。此时决定第 个球，选择白球或者黑球进行转移，即满足了最优子结构。设 为前 个球， 个白球， 个黑球的状态。如果决定第 个球为白球，，其中 为编号为 的球移到 的代价。黑球同理。考虑如何计算这个代价，显然可以记录 代...

Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：https://www.codein.icu/nowcoderweekly16/显然变动函数是一个周期函数，相信大家都做过类似的数学题。  设经过边数为 ，边权为 ，将 代入即可求得当时边权。随后就是经典的分层图、图上dp问题。设计状态为，到达 点，经过边数模三结果为 ，跑个最短路就行了。 代表上述状态的最小距离。 #include <cstdio> #include <queue> #include <algorithm> #include <ct...

Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：https://www.codein.icu/nowcoderweekly16/ 每层黑色节点数都为偶数时，先手必败。假设先手选择一个黑点，不翻转祖先，则后手选择同层黑点，不翻转祖先，状态不变。假设先手翻转祖先，则后手翻转对应层的祖先，状态不变。这样逐层消去，末状态为与根节点相连的黑点为偶数个，此时翻转祖先不改变结果，依次取黑，后手胜。 否则，若有一层为奇数，则先手可以一步将所有层设为偶数，随后将后手代入上述推导，便是先手胜局。 #include <cstdio> #includ...

Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：https://www.codein.icu/nowcoderweekly16/ 按题意模拟即可。至于那两个特殊情况，其实就是超出值域时拉回来。 #include <cstdio> #include <algorithm> #include <ctype.h> const int maxn = 20; int a[maxn]; int main() { while(scanf("%d %d %d %d %d %d %d %d %d %d",a + 1,a ...

Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：https://www.codein.icu/nowcoderweekly16/ 这题真是令人难以理解……根据直觉，我们知道期望为 ，其他的描述都是无用的。这期望居然是个整数，用浮点会WA。 #include <cstdio> #include <algorithm> #include <ctype.h> #define DEBUG const int bufSize = 1e6; #define int long long int n,m,T; sign...

首先推几个结论：  原编号为 的点新编号为 ，可使字典序最小。 距离新编号为 的点，最短距离为 的点，新编号中有 个 。考虑从 号点开始走，每次增加一个 ，最少 步后才能走出 个 ，且该距离为最小距离，若不如此走，分两种情况：将新编号中 位走成 或将新编号中 位走成 ，则都需要走回头路，因此距离更长。 新编号含有 个 的点，仅与若干个含有 个 的点与含有 个 的点联通，且若干个含有 个 的点新编号的或和即为该点新编号。考虑含有 个 的点，根据第二条结论发现它们离 的距离为 ，则其直接与含有 个 的点联通的路径即为其最短路。因此可以推出，这些点与含有 个 的点仅相差一个包含在 个 中的 ，且每个...

E 算式子 数论题。 显然左半边右半边可以分开计算。 Update:修正了描述……之前写反了。 定义：  为值 的元素的数量。  为 时， 的值。 考虑 与 如何计算。 对于 ，枚举每个 ，可以用整除分块的思想发现：  设 ，那么：  ，对于 ，产生的贡献都为 。 可以通过处理 数组来计算该贡献。 对于 ，用类似的思想，考虑对被除数 进行分块计算对每个 值的贡献。 设 ，那么：  ，对于 ，产生的贡献都为 。 区间修改可以通过差分实现，最后做前缀和处理 数组。  如果枚举每个 的话复杂度是不对的，例如全为 的数组就可以卡掉。但可以借助 数组，枚举值域进行计算，复杂度就正确了。 复杂度分析：不考...

其实这是我打的第二道题……一眼可以用树剖做，于是就是树链剖分的板子题。但其实似乎只求子树用dfs序就可以……？是我蠢了。线段树维护平方和也是老套路了：  #include <cstdio> #include <ctype.h> #define DEBUG #define int long long const int bufSize = 1e6; inline char nc() { #ifdef DEBUG return getchar(); #endif static char buf[bufSize],*p1 = buf,*p2 = buf; return p1=...