题意： 有n个点，有m条边，每条边上有一个权值。当你从u到v时，如果这条边和上一条边的权值不同，代价就加1。问从结点1到结点n的最小代价。 思路： 有两种做法。 做法一（拆点）： 原来的图是左边这样的，可以拆成右边这样，可以知道这样任意两点之间的代价就是走过的权值和加上1。 为了方便存图，可以这样拆点： 这样子的代价也是相同的。 跑一下最短路/2就可以了。 做法二（并查集）： 把权值相同的边拿

题意： 给出n个数字，有q个询问，去掉三个数字，在剩下的数字里面选10个，问和能否刚好为87。其中t \leq5,n \leq 50,q \leq 100000。 思路： O(t*n^3*n*10)的bitset优化的dp居然可以水过…不科学啊… 有另一种做法： 因为删除3个数字，所以对于中间的那个数，pre[i][j][k]表示前i个中选了j个没有选k的和的情况，suf[i][j][k]表示后

题意： 有n件物品，每件物品有体积v_i和价值w_i，问体积为m的背包最多可以装下多大价值的物品。其中n \leq 100 ，其他数据均匀随机并且不超过10^9。 思路： 很典型的背包问题，然而背包的大小变成了10^9，最简单的01背包的做法不行，交换两维状态（前i件物品价值为j占用的最小体积）的做法也不行。n \leq 100，折半枚举也不行。 那怎么办呢？所以看了题解… 这又是数据随机下的玄学

tarjan离线：参考博客： https://www.dreamwings.cn/lca/4874.html https://www.cnblogs.com/JVxie/p/4854719.html 复杂度： O(m+n)，m是询问数，n是节点数。 伪代码： Tarjan(u) // merge和find为并查集合并函数和查找函数 { for each(u,v)

题意： 给出k种属性，一个人的k种属性有初始值为v_1,v_2,...,v_k，他要去打n个怪兽，第i个怪兽也有k种属性a_{i,1},a_{i,2},...,a_{i,k}，如果当前的v_1\geq a_{i,1},v_2\geq a_{i,2},...,v_k\geq a_{i,k}，这个人就可以打第i个怪兽，并且每个属性得到怪兽的加成b_{i,1},b_{i,2},...,b_{i,k}。问

题意： 一张纸条上依次写着N个数字，数字只可能是0或者1。在纸条上剪K刀，这样就形成了K+1段，再把这K+1段按一定的顺序重新拼起来。问前缀 1 的数量最多能是多少。 思路： 分类讨论不会啊…太菜了啊QAQ 看了题解有一种dp的做法，这比较好理解。 要把这个01串原本的前缀1剪下来只要剪1次，把原本的后缀1剪下来也要剪1次，中间的一串1剪下来要剪2次，所以这就是一个背包问题了，但是比如110111

题意： 有一个n*m的矩阵，对于每一行，如果行中有奇数个1，则置1，反之则置0，对于每一列也这样操作。 比如\begin{matrix} 1 & 1 & 1 &1 \\ 0 & 1 & 1 & 1 \\ 0 &1 & 1&1 \\ 0 & 1 & 1 & 0 \end{matrix}，行为[0,1,1,0]，列为[1,0,0,1]。 给出行和列的情况，让你复原这个矩阵。 如果没

想学习一下字符串哈希结果发现以前自己已经脑补出来用过了啊？虽然base和mod取的不是那么好… 参考资料：https://wenku.baidu.com/view/b7d3d1c6804d2b160a4ec090 hash函数：hash[i]=(hash[i-1]*p+idx(s[i]))\%mod。 子串的hash值（下标从1开始）：hash[l,r]=(hash[r]-hash[l-1]*p^

题意： 有n个点，每个点有个坐标，要从第一个点开始到第n个点结束。当在第i个点的时候，他下一步只能去第j个点，i,j满足x_i

题意： 总共有N本书，要放到一个K层的书架上去。假设每一层最后放了cnt_i本书，f[i]为斐波那契数列(f[0]=0,f[1]=1)，定义第i层书架的稳定值为stable_i=f[cnt_i]，第i层书架的美观值为beauty_i=2^{stable_i}-1，定义分数为score=gcd(beauty_1,beauty_2,...,beauty_k)。问分数的期望为多少。 思路： 有两个公式，