介绍一个简短的 G 题构造方案。 先特判无解的情况，， 或 。 注意到一个同色的环中必然存在一条边 ，使得它与 或 同色。 如图：   所以我们只需要保证同行 / 列没有两条相邻的边，且相邻两行 / 列同一列 / 行的边颜色不相同。 这是很好构造的，对于 ，直接按 顺序依次分配边权；对于 ，在偶数行 / 列上循环移 1 位即可。 时间复杂度是 。 代码： #include <algorithm> #include <cstdio> #include <cstring> int main() { int te; scanf("%d", &te); wh...

这题是一个 01 背包的形式，唯一可能的解法是动态规划。 但在本题未经处理的情况下，动态规划是不能使用的。因为原图上的转移不是有向无环图，带来了后效性，使得动态规划出错。 于是我们需要安排一种转移顺序，使得原图的转移变成 DAG，从而应用动态规划解决问题。 结论是，一定存在一种最优方案 ，使得对于任意 ，都有 。 证明如下：若不满足该条件，则必然存在一个位置 ，满足 。 我们把 和 两道菜肴拎出来，单独计算它们对答案的贡献。 设这种方案中开始制作 的时间为 。 若按照 的顺序制作菜肴，则对答案的贡献为 。 如果我们交换 和 的顺序，变成按照 的顺序制作菜肴，则对答案的贡献为 。 作差法比较两贡...

题目传送门 算法：min-max 容斥、树上背包、NTT。 题意简述 有一棵 个点的树。一开始所有点都是白色，每次操作会随机选择 条路径中的一条，将路径上所有点染黑。求所有点都被染黑的期望操作数。 。多组数据。对 取模。 题解 套路性地，我们使用 min-max 容斥。 如果我们把树画出来，并将 内的点标记，可以发现，这些点把原树分成了若干个连通块，而每个连通块内部可以任意选取路径，能够保证该路径不经过 内的点。而一旦路径跨越连通块，那么一定经过 内的点。 记共分成了 个连通块 ，则不经过 的路径数为 那么概率为  继续化简原式，得 对于最终情况，一个划分方案给答案带来的贡献仅仅是 和 两块。...

我简直是咸鱼，一只彻头彻尾的咸鱼。 慵懒，成为了我本次比赛的主调。 10 月 27 日晚上——也有可能是 10 月 28 日的凌晨，睡眼惺忪的我坐在书桌前，照常奋笔疾书着。作业本放回一本又拿出一本，练习材料做完一张又掏出一张，我就这样机械着循环反复着，完全看不到尽头。 在这种困倦又疲劳的情形下，我申请了停课，开始为 CSP-S2 做准备。 写完停课申请的我仿佛如释重负，用最后一点气力把作业扔到一旁，然后摊到床上，不久就睡熟了。  为期三周的训练，是缓和而有趣的。每天早上七点钟起床，慢条斯理地吃完早饭后悠闲走到学校，参加校内举行的提高模拟赛。在三个半小时里，我只愿意思考每题的满分做法，对部分分置...

A. 集合统计 出题人：henry_y 题意 定义一个集合 的 函数为 。给定一个集合 ，求该集合所有非空子集的 函数之和。 题解 解法一（） 直接枚举所有子集判断即可。复杂度 。 解法二（题解做法） 考虑每个数作为答案的贡献。 设小于 的数共有 个，那么 作为最大值的子集共有 个，对答案累加上 即可。 作为最小值同理。 找到小于 的数和大于 的数可以直接排序。 复杂度  标程 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41720323  B. 下雨天 出题人：Trote 题意 有 个池塘，第 个池塘容量为...

A. 服务器需求   出题人：Trote   题意  有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \cdots, a_n$。每次操作可以选择最多 $m$ 个正整数，将它们的值减少 $1$。$q$ 次询问，每次询问会修改一个位置的值，问最少多少次操作后序列可以变为全零。询问对后面的询问有影响，操作对后面的询问没影响。  题解   解法一（$m = 1$）  注意到 $m=1$ 时，$\sum a_i$ 即为答案。 每次询问维护差值即可。  解法二（$n, q \le 100$）  我们可以考虑如何利用贪心策略。 注意到如果在一开始准备了很多服务器，我们总会优先选择当前使用天数最少...

T1: 最短路 对于第一档部分分，构造一朵菊花，直接从 向其他节点连对应权值的边即可。期望得分 分。 对于第二档部分分，我们希望每一个点都从最近的那个点连过来。也就是说，对于某个点 ，我们可以找到一个 ，满足 并且 尽可能大，然后从 向 连一条权值为 的边。可以证明这样构造出的图一定是最优的（最大边边权最小的），因此若找不到点 （即 ）或 ，则一定无解。暴力找前驱 可以做到 的复杂度。结合上一档部分分可以拿到 分。 对于所有数据，可以优化这个找点的过程。我们不妨将所有节点按照权值先排序，然后我们发现，随着 的增大，点 一定不会减小，因此用双指针扫描法即可找到这个 。当然用二分查找也是可以的。复...

T1: 最短路 对于第一档部分分，构造一朵菊花，直接从 向其他节点连对应权值的边即可。期望得分 分。 对于第二档部分分，我们希望每一个点都从最近的那个点连过来。也就是说，对于某个点 ，我们可以找到一个 ，满足 并且 尽可能大，然后从 向 连一条权值为 的边。可以证明这样构造出的图一定是最优的（最大边边权最小的），因此若找不到点 （即 ）或 ，则一定无解。暴力找前驱 可以做到 的复杂度。结合上一档部分分可以拿到 分。 对于所有数据，可以优化这个找点的过程。我们不妨将所有节点按照权值先排序，然后我们发现，随着 的增大，点 一定不会减小，因此用双指针扫描法即可找到这个 。当然用二分查找也是可以的。复...

牛客OI周赛9-提高组题目记录 昨天晚上做了这一套比赛，觉得题目质量挺高，而且有一些非常有趣而且非常清奇的脑回路在里边，于是记录在此。  T1: 扫雷 题目链接 设 \(f_i\) 表示扫到第 \(i\) 个雷的期望用时，那么我们要求的答案就是 \(f_n\)。 我们不难写出一个递推式： \[ f_{i +1} = \left((f_i +1) \cdot \dfrac{a_i}{b_i}\right) + \left(2(f_i + 1) \cdot \dfrac{b_i - a_i}{b_i} \cdot \dfrac{a_i}{b_i} \right) + \left(3(f_i + 1...

目录   拆点和拆边  一、总述 二、常见的有针对性的算法  针对点权 针对边权  三、拆点  过程 实例  四、拆边  过程 实例  五、总结     拆点和拆边 一、总述 在图论中，一张图由点和边构成。而点和边都可以作为信息的载体，比如说点权和边权。尽管点和边看似如此接近，但是它们的性质确实截然不同的。点表示的是一种实质上的状态，而边表示的是一种虚拟的状态间的转移。 因此，有一些图论算法只能处理点上的信息，而另一些图论算法只能处理边上的信息。怎样使得这些针对性的算法通用化呢？某些情况下，我们可以通过拆点和拆边的方式来解决。 二、常见的有针对性的算法 针对点权  树链剖分（套线段树或树状数组...

不得不承认，去年提高组 D2T3 对动态 DP 起到了良好的普及效果。 动态 DP 主要用于解决一类问题。这类问题一般原本都是较为简单的树上 DP 问题，但是被套上了丧心病狂的修改点权的操作。举个例子，我们来看一道例题。 【模板】动态 DP  给定一棵 \(n\) 个点的树。\(i\) 号点的点权为 \(a_i\)。有 \(m\) 次操作，每次操作给定 \(u, w\)，表示修改点 \(u\) 的权值为 \(w\)。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。  我们首先考虑没有修改的情况下怎么做。首先先选取 \(1\) 号点作为全树的根。然后我们设 \(f_{i, 0}\) 表示...

目录   树杂谈（上）  1. 树的基本概念和一些有关定义  树的基本概念 树相关的定义  2. 生成树  Kruskal 算法 Prim 算法 Borůvka 算法 Kruskal 重构树  3. 最近公共祖先  最近公共祖先的定义与性质 倍增算法 应用 总结  4. 树链剖分  引入 原理 代码实现      树杂谈（上） 研究问题的道路，一般都是从特殊到一般，从简单到复杂。在数学中，三角形是一种特殊的多边形，因此在三角形的基础上，又有了有关全等三角形、相似三角形、三角函数等令学生们头疼的数学题。同样的道理，在信息学竞赛的道路上，树——作为一种最特殊的图，在许多题目中都能见到它的身影。 1...

前几天在洛谷日报征文中看到了这样一篇文章：C++不止能做题。作为原来校管弦乐队的一名成员，而后因为信息完全放弃了管弦乐队，我看完是又激动又怀念。于是我自行去研究了一下：C++ 如何让蜂鸣器叫出乐曲。 由于本人乐理只有五线谱D2-2级，数学成绩中游，信息也只有普及组水平。如果有哪里写错了，望大家指正、轻 D。  首先需要知道两个函数： #include <windows.h> Beep( f, t ); Sleep( t ); Beep() 函数可以让蜂鸣器发出频率为 \(f\) 赫兹，音长大约为 \(2t\) 毫秒的音。（注意是 \(2t\)） Sleep() 函数可以当做休止符用...

题意：  给定两个数列 \(A\) 、 \(B\) ，元素个数分别为 \(n\) ， \(m\) \((2 \le n,m \le 50)\) 。数列中所有元素大小均在 \(-10^{9}\) 到 \(10^{9}\) 之间。 现要求在 \(A\) 数列中删掉一个元素，使得 \(A\) 中任一元素和 \(B\) 中任一元素相乘的共 \((n-1) \times m\) 种可能的值中的最大值最小。输出该最大值。  题解： 其实这题的 \(n, m\) 都可以开大到 \(10^6\)。 我的做法是 \(O(n+m)\) 的贪心。 先考虑不拿走元素的情况。那么对答案有贡献的元素只有可能是 \(A,B...