题面 传送门：洛谷 Solution 这道题的是一道很巧妙的状压DP题。 首先，看到数据范围，应该状压DP没错了。 根据我们之前状压方程的设计经验，我们很快就能设计出这样的方程： 设$f[i][j]$表示用到第i个元素，当前连接状态为j的开销的min 但是我们很快就会发现，这个方程没法转移，因为随着连接方案的不同，新插入的点的K值会不同。 怎么办呢？ 这时候我们可以重新设计一个巧妙的的状态...

题面 传送门：洛谷 Solution 这是一道很有意思的数论题。 首先，我们可以发现直接枚举a和b会T的起飞。 接下来，我们就可以观察一下式子了，我们略微手算一下，就会有这样的结果： 我们可以发现，a，b在每一项中的数量都可以用同一个斐波那契数列表示。 我们可以用$g[x]$表示斐波那契数列的第x项，那么，我们可以得到$f[x]=a_g[x-1]+b_g[x]$ 接下来，由常识可以知道，...

题面 传送门：洛谷 Solution 如果题目只要求求出第一问，那这题显然就是大水题。 但是加上第二问的话…那这题就成为大（du）火（liu）题了。 对于第一问：求一整个区间的最大线段总数，我们可以很轻松的切掉。 怎么处理第二问呢？ 我们可以考虑这样做： 对于一条线段，如果它属于答案的一部分，那么它一定会有以下性质： 区间③的最大线段数 = 区间①的最大线段数 + 区间②的最大线段数 + ...

题面 传送门：洛谷 Solution 这是一道很有意思的在背包里面做容斥的题目。 首先，我们可以很轻松地想到暴力做背包的做法。 就是对于每一次询问，我们都做一次背包。 复杂度$O(tot_s_log(di))$ (使用二进制背包优化) 显然会T得起飞。 接下来，我们可以换一种角度来思考这个问题。 首先，我们可以假设没有每个物品的数量的限制，那么这样就会变成一个很简单的完全背包问题。 至于完...

题面 传送门：洛谷 Solution 这是一道十分经典的树形DP题，这种类型的树形DP有一种很普遍的解法。 首先，观察题目，我们把这道题转换一下：给定一颗树，选出包含1号节点（根)的一颗子树，使得点权和最大。 我们可以这样子定义状态： 设$f[i][j]$ 表示以i为根节点的子树，选出j个节点，所能达到的最大点权值。 对于二叉树来说，转移很显然，就是枚举左子树分配多少个节点，就可以对应的得...

题面 传送门：洛谷 Solution 这是一道简单的树形DP题。 首先，我们可以转换一下题面，可以发现，题目要求我们求出一颗树上的最大联通子图。 因为我们是在树上取的，实际上就是取一颗子树。 这个就是最基础的树形DP模型了。 我们可以设f[i]表示我们选的子图以i为根所能取的子树的最大值。 转移是： $f[i] = beauty[i] + xigema(max(f[j],0))$ （也就是...

题面 传送门：洛谷 Solution 这题显然有一个$O(n)$的直接计算法，$60$分到手。 接下来我们就可以拿出草稿纸推一推式子了 首先，取模运算在这里很不和谐，我们得转换一下。 对于任意取模计算，我们都有： 所以，我们可以做以下推算 经过一些手算，我们发现$k/i$(向下取整)是由一段一段的区间组成的，如下图 显然，每段区间的右端点可以通过二分的方法来找 对于每一段区间，我们可...

填坑中 $\color{blue} {last update ： Jan,21st,2019}$ 通用 $\color {red} {-1.仔细审题*2}$ 永远要有想法，不要觉得复杂度不对空间就不开够。空间永远开到最大值（或者说是自己不MLE的极限），以免发生复杂度正确但是空间没有开够的惨痛教训（NOI.ac WHZZT 邀请赛R1） 在会爆int的题目中，一定要仔细检查是否有会爆in...

题面 传送门:洛咕 Solution 挺有意思的一道题。 题面已经挺明显的描述出了这题的主要思想：倍增。 先这样想，我们可以把这题这样建模：有一堆点，若两个点之间的距离之和可以达到2的n次方，那么这两个点可以用1的时间相互到达。 也就是说，我们把距离能为2的n次方的点对用边权为1的边连上，再做一次最短路径，就可以求出答案了。 接下来问题就是如何求出每两个点是否能以2的n次方的时间相互到达。...

题面 传送门：洛谷 Solution 先跟我大声念： $\huge poi!$ . 然后开始干正事。 首先，我们先把题目中的点分为两类：去除这个点能把图分为几个部分的，去除这个点不影响整个图的连通性的。 如下图： 点上的数字表示这个点的搜索序。 我们称这些对连通性有影响的点为割点。 先假设我们能求出这些点以及其出去后把图分为几块之后那几块分别的大小。 是不是发现了什么？ 对于非割点，答案...