文章

1. 题目 传送门=￣ω￣= 题意：给你 n 种硬币，第 i 种的面值是 ai，个数时 ci，求这些硬币能凑成区间 $[1,m]$间的那些值 2. 题解 普通的多重背包复杂度为 $O(n\times m\times c)$显然超时 二进制优化复杂度大致刚好卡在 1e8 的复杂度上，多组数据就挂了 只 阅读更多…

题意： 给定一些物品的价值、大小、数量。求一个大小为 m 的背包最多装得下多少价值的物品。 虽然这道题乱搞都可以 AC，但是我们还是实用单调队列优化 这里的 f[i] 表示容量为 i 的背包可以装下的最大价值 (而不是恰好装下)。因此可以很方便地使用单调队列优化 这所谓的单调队列是神码样的呢？它其实 阅读更多…

题目 ak47 题意 在数轴上有两个点 A B（给出坐标），还告诉你 a，b 表示可以向左或向右走 a 或 b 或者走 a+b 6 种走法 走一次算一步 问从 A 走到 B 最少要多少步。 题解 容易想到方程 ax+by=c x 表示用 a 走了多少次 y 表示用 b 走了多少次 这样用扩展 gcd 阅读更多…

先看下面一道题： 将一个序列划分为若干个连续子序列，每个子序列的权值是它们和与常数 L 的差的平方。求所有子序列的权值和最小是多少？ 思路： 最简单的思路是：$f[i]=min(f[j]+(sum[i]-sum[j]-L)^2)$ 于是我们就可以在 $O(n^2)$时间内求解。 但是，能不能更快一些 阅读更多…

卡常神题 多重背包最基本的状态转移方程是这样的： 用 f[i][j] 表示前 i 个物品装进背包占容量为 j 时的最大价值。 $$ f[i][j]=max(f[i-1][j-k\times w[i]]+k\times v[i]) (0<=k<=c[i]) $$ 但是我们有一个经常会问的问 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 数学归纳法 什么鬼？其实就是找规律…… 考试找了两个小时没找到规律然后就爆炸了 不难发现当前状态进行 $2^k$次操作后，第 i 位上的数字只受第 $i-2^k$位上的数字和第 $i+2^k$位上的数字，即它们如果相同则第 i 位上的数字为 1，否则为 2。 阅读更多…

在 MiNa! 里的 markdown 和别的 markdown 使用方法大同小异，但是。。。还是讲一下吧 博客的编辑器采用开源的 HyperMD，食用方式与 Typora 非常相似，预览与编写合为一体 QwQ 还是非常不错的（逃 -1. 注意 因为 Remmina 有强迫症+神经病，所以对文章格式 阅读更多…

原文连接 (YSP dalao%%%%%)：http://www.cnblogs.com/Robert-Yuan/p/5122784.html 本文是蒟蒻 XZY 转自学长 YSP 的博客的！ 其实讲的是动态树中的一种——lct(link cut tree) 蒟蒻 XZY 再推荐一些博客： http 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 把 pushup 改成求异或和就行了 代码： #include <bits/stdc++.h> #define NS (300005) using namespace std; template<typename _Tp>inline 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 搞个 lct，实现 link 和 cut 和判断连通性即可。 判断连通性的话，写个 find(x) 函数，返回 x 所在的树的根的编号，判断两个点的 find 值相不相同，相同则联通。 代码： #include <bits/stdc++.h> # 阅读更多…