查看原题请戳这里 一开始以为需要用线性筛（当然我不会），后来才知道原来容斥一下就可以通过这道题目…… 首先，有一个奇怪的结论：横纵坐标gcd为$k$的点前面共有$k-1$个（它们的gcd分别为$1,2…k-1$）。 我们可以发现，对于一个$n\times m$的图，横纵坐标的公因数含有$k$的点共有 ...

查看原题请戳这里 状态设计一开始我设计$f[i][j]$表示在以$i$为根节点的子树上保留$j$个节点需要断掉的最少的边数，但是这样设计状态虽然思考起来比较直观，但是状态转移貌似比较麻烦，所以我们直接用$f[i][j]$表示在以$i$为根的子树上删去$j$个节点需要去掉的最少的边数，$ans=\mi ...

查看原题请戳这里 我们通过在树上跑分组背包的方式来完成这道题。 状态设计我们设计状态$f[i][j]$表示在以$i$为根的子树上选取$j$个叶子节点（用户）共给信号能够获得的最大价值（当然，这个最大价值可能是负的，这都没有关系）。 状态转移我们考虑泛化物品。 泛化物品的背包:这种背包，没有固定的费 ...

查看原题请戳这里 导入我们先来看一个看似正确的分组背包的方法： 我们将每一列拆分为n个物品，第$m$行第$k$个物品的价值是$\sum_{i=k}^na[i][m]$，其代价为$\sum_{i=k}^n[pd[i][m]=1]$。 简单的说，第$m$行第$k$个物品的价值是第$m$行$k-n$个砖块 ...

查看原题请戳这里 因为在每个城市小A和小B下一个要去的城市是一定的，所以在这道题目中不存在决策的问题。 预处理最近点和次近点双向链表流程： 先把城市按高度排序，然后建立双向链表（每一个城市都指向第一个比它低的城市和第一个比它高的城市）。 按照从左到右的顺序去预处理每一个城市的最近点和次近点。 我 ...

题目下载链接：https://pan.baidu.com/s/124va3buX3cNITjDDXDFVKw提取码：nvt5 字符串考虑如何判断一个字符串 $S$ 是不是另一个字符串 $T$ 的子序列。 一个自然的想法是贪心：我们按照从前往后的顺序考虑 $S$ 的每个字母，然后维护一个 $j$，表 ...

查看例题请戳这里 这里我们从易到难来介绍三种求逆序对数的方法。 top1:暴力枚举时间复杂度：$O(n^2)$ emmmmm…… 这好像真的没什么可说的…… code: 123for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; ...

查看原题请戳这里 看到这道题，最直观的就是对于每一种情况都跑一遍多重背包，然而这样做的话时间复杂度会变得非常奇妙…… 首先，我们可以考虑每种钱的个数没有限制的方案数。很显然，我们可以直接跑一个完全背包。 那么，如果只有一种钱存在个数限制呢？ 我们用$f[i]$表示支付金额$i$的方案数，那么$f[s ...

题目链接：https://pan.baidu.com/s/1nXgVYuGv-aavPk7vzkcjaw提取码：hque 爬杆50分做法容易发现，如果可以加梯子，那么$i$到$j(i<j)$的距离是$h_i+h_j-2\min^j_{k=i}h_k+j-i$，因为必须要经过最小的位置。 其中 ...

点击下载题目 color 我们可以把染黑看成删掉这条边，那么每次相当于是，如果存在一个点有且仅有一条出边，那么把这条边也删掉，最后要删完所有的边。那么我们考虑一个环，可以发现这个环如果一条边都不删，那么最后一定会被留下来，因为每个点都至少有两个出边。所以，在初始的边删完之后，图一定得要无环。我们考虑 ...