A 牛牛的方程式 更好的阅读体验 Statement 牛牛最近对三元一次方程非常感兴趣。众所周知，三元一次方程至少需要三个方程组成一个方程组，才有可能得出一组解。 牛牛现在想要知道对于方程 中有没有至少存在一组 的解，且 都为整数，使得方程式成立。 裴蜀定理 对于方程 ，当且仅当 时方程有整数解。 题解 容易将上述定理拓展到多元情况。 当 时，有整数解。 但是当 时，方程存在两种情况： 对于 式，，对于 式， 无解。 如果不对 进行特判，会因为浮点错误 RE 掉 50 分。 代码 #include<bits/stdc++.h> using namespace...

又双叒叕能暴力AC？？？？？ C题

稍微复杂的换根 DP，我能一发 A 掉的还是不多的... 题目大意 给出一棵有 个结点的树，其中 个结点 作特殊标记，令 代表结点 到 简单路径上边数，求有多少个点 ，满足 题解 不妨令 为根。 考虑结点 的最远标记点，可以在 的子树 内，也可以在 的子树外。 对这两种情况分别讨论。 在 的子树内情况比较简单，可以通过一次 dfs 求出。 记 为 内最远标记点到 的距离，如果 内没有标记点，则 但在这个 dfs 过程中，还要维护 内第二远标记点到 的距离 ，原因将在 解释。 在 的子树外情况比较复杂，但可以自然地想到是一个换根 DP：根 号点...

D 的数据强度是认真的吗？？？ 我对面的 $O(n^2)$ 过了，我左边的爆搜过了 就欺负我这种没大胆乱搞的老实人……

A 设三个数分别为 发现三个数在模 意义下构成了整个剩余系 所以只有当 为质数时有答案，也就是满足题目要求的数对只有 #include<bits/stdc++.h> using namespace std; template < typename Tp > inline void read(Tp &x) { x = 0; int fh = 1; char ch = 1; while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if(ch =...

本题解同步发布于[本场总题解](https://www.luogu.org/blog/expect2004/CF530Div2)，欢迎来踩。 F - Cookies 这题在考试时间内有了正确的思路但没有写完。。。 的策略 题目的表述中，是可以随便剪断当前标记所在结点到任意一棵子树的。 但是题目要求我们求的是最坏情况下的最小值，我们可以只考虑创造了最坏的条件，即剪掉了本来可以取到最优解的子树。 树形 首先做一次，求出不剪时的最优解，同时记录取到最优解的位置。 接下来标记不得进入之前最优解的位置，再做一次。 这两次等价于维护了每个结点的最优解和次优解。 在的过程中使用了贪心的思想，显然从根到的路径...

好像是2019年上海市高三数学竞赛第12题原题？

题意简述 给出一个数 ，你需要将 写成若干个数的和，其中每个数的十进制表示中仅包含 和 。 问最少需要多少个数 题解 考虑一个整数 ，设 容易发现，第 位上的数字就是 。 因为我们分解出来的数里面只能是 ，那么想要得到第 位则需要 个数在该为上有 因此，输出的第一行就是 下面考虑构造方案，设 为构造出的第 个数，如果 ，则 的第 位为 ， 否则为零。 代码 #include<bits/stdc++.h> using namespace std; template < typename Tp > inline void read(Tp &...

华华给月月准备礼物 题解 显然可以二分答案解决。 二分答案证明 令 表示裁剪为长度 的根数， 因此 具有单调性，可以二分答案解决。 Code #include<bits/stdc++.h> using namespace std; const int maxn = 200000 + 7; int n, k, L = 1, R = 1000000000; int mid , ans; int a[maxn]; bool check(int x) { int res = 0; for(int i = 1; i <= n; i++) { ...

引言 对于树上的题目，一般都是在搜的过程中 解决。 其中 为搜索函数的复杂度。 题解 暴力 这道题有一个显然的 的暴力思路：就是枚举每一个点作为根，扫一遍。 换根DP 分析暴力做法的时间复杂度瓶颈，发现主要在于每次都要遍历整棵树。 考虑是否能够每次 地转移两个根之间的信息。 显然，想要 转移这两个根 的信息，他们必定在树上相邻。 观察上面的这张图 假设当前 为根，向 换根时，有 的点距离增加一，有 个点距离减少一。 先钦定 为根，把 dep 都跑出来，然后再次遍历的过程中取 max 就行了。 关于本题的特殊做法 这个题好像是牛客OI周赛14普及的第三题 由于点权的特...

牛客算法周周练1题解 A Maximize The Beautiful Value 题意翻译 给出一个单调不减的数列 ，选择一个数 ，将其放置至 至 的任意一个位置 中，并将 到 依次向后移动一位。 求 题解 因为单调不减，所以越往前越吃亏，显然选择的这个数只会移动 位。 设 为移动前的 ，如果移动的位置为 ，则有移动后的 发现等式右边的 可以前缀和处理。 所以从 到 扫一遍就行了。 时间复杂度 Code #include<bits/stdc++.h> using namespace std; typedef long long LL;...

20200409 Running Median 题意翻译 输入 个数，每次到奇数个数的时候输出中位数。 多测， 组数据。 题解 使用对顶堆。 一个小根堆，存放比中位数大的数。 一个大根堆，存放比中位数小的数。 动态调整堆的大小。 参考了神仙的 std 写法，细节处理比我之前的写法好的多。 priority_queue 的坑点 priority_queue < int, vector < int >, greater < int > > 可以直接定义小根堆 priority_queue 的成员函数 size 返回类型为 unsigned int 型...

20200408 黑白树 题意转化 在 个点中选择若干个点，将这些点的 级父亲以内全部染成黑色，求要把所有点染成黑色至少选多少点。 题解 考虑下面的这样一种情况 傻子才会选红色的点——绿色的点可以完全替代掉红色的点。 这样一来，可以等价为红色点 。 由此可以得到，一个点的 可以更换为自己子树中点 。 同时维护 代表覆盖 子树后还可以向上覆盖的最大距离，当 时需要选择点 。 实际上，这是一个贪心的过程。 Code #include<bits/stdc++.h> using namespace std; typedef long long LL; temp...