题意： 有n堆石头，每堆石头最多只有三个石头（最少1个），每两堆石头（这两堆各含石头x个和y个）合一起的费用为(x mod 3) * (y mod 3)，现在把所有堆合成一堆，问最小费用题目第一行给出三个数，第i个数表示有i个石头的堆有多少个 题解： 费用是(x mod 3) * (y mod 3)，那也就是说如果x和y有一个是3的倍数，那么费用就是0，那么我们就要将堆内石头尽可能构造3的倍数比如：一个石头和两个石头合并，费用是2三个堆，每个堆都只有一个石头，费用是1+2 = 3三个堆，每个堆都只有两个石头，费用是4+2 = 6说明一个石头和两个石头构造更划算那么我们一开始就让1个石头的堆和两...

题目：  题意： 如果点x和y有连边，当且仅当a[x] or a[y] = 2^60^ - 1 （两者是充分必要）现在给你边的关系，问你每个点的值应该是多少？（给出一种情况即可） 题解： 构造题，思路非常巧妙2^60^就是（1<<60）,减去1也就是从第一位到第59位都是1（第六十位是0省略了）首先01染色，将点分为黑点和白点，让白色的点为个数少一些的选数量较少的一组是确保数量小于等于 50现在每个点都要节点编号id和颜***r>id为该点的编号对于白色的点，我们让其最高位为0，让其第id位也是0，其余位置都是1对于黑色，我们让其最高位是1，与它相邻的所有点（也就是白点）的第...

[HAOI2006]均分数据 题解： 题目稍微解释一下：把n个数以分为m组，计算每一组的和，求得到的这m个数的方差。由于分法是任意的，我们要求这些方差中的最小值我们先用STL中的函数random_shuffle()用来对一个元素序列进行重新排序（随机的）众所周知：如果每个组数的大小都相近的话，方差就越小所以我们每次将第i个数加给当前数之和最小的那个组，这样操作可以使得在当前排列下，m组数最相近，也就是方差最小循环个5e5次就够了，太多就会超时（5e6的话洛谷和牛客的机子都会超时）貌似dp也可以做？？ 代码： #include<bits/stdc++.h> typedef long ...

质数与合数 题意： FFF和GGG正在玩一个质数与合数的游戏一开始有N个石头FFF和GGG轮流对这堆石头进行操作，FFF每次选择1到K之间的一个数x，并拿走x个石头，拿走之后剩下的石头数量必须是质数接着GGG进行同样的操作，但是要求拿走之后剩下的石头数量必须是合数假设双方都足够聪明，第一个不能操作的人输以为到这里就结束了？显然，一开始两人之间有一人知道自己有必胜策略，现在他想要尽可能快的赢，另外一个人则想要尽可能输的慢一点给你N与K，假设游戏最终持续了X轮，如果FFF赢了，输出X，否则输出-X注意：1既不是质数也不是合数 题解： 判断输赢很简单，因为每次取数范围是[1,K]，而FFF要每次取完...

P3803 【模板】多项式乘法（FFT） 题目描述 给定一个 n 次多项式 F(x)，和一个 m 次多项式 G(x)。请求出 F(x)和 G(x)的卷积。从低到高输出F(x)*G(x)的系数另一种问法：如果有两个无限序列a和b，那么它们卷积的结果是：求出yn值 题解： 模板题建议背过模板讲的非常不错的博客 代码： #include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <algorithm> using namespace std...

题意： 两个数列，每个数列都可以顺序旋转，也可以对所有数同时增加一个非负整数，现在问的最小值 题解： 在求卷积前要将A数组倍长，B数组翻转B数组翻转好理解，为什么A数组倍长，因为题目的数列是可以移动的，而我们不知道哪一部分和B卷积是最佳答案，所以讲A数组倍增，然后每次取A中连续长度为n的区间与B倍增，最后取最小值即为最佳答案因为c是我们设的变量，所以最后循环c找式子最小值 关于FFT求卷积（多项式乘法） 如果有两个无限序列a和b，那么它们卷积的结果是如果a和b是有限序列，a最低的项为a0，最高的项为an，b同理，我们可以把a和b超出范围的项都设置成0。 【模板】多项式乘法（FFT） 套上FFT...

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包 题目： 给定一些点，问围住所有点所用的围栏的长度 题解： 凸包模板题凸包详细 代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; int n; struct point { double x,y; }p[10005],s[10005]; double check(point a1,point a2,point b1,...

Jamie and Tree[CF916E] 题意： 有一棵n个点的树，每个节点上有一个权值wi，最开始根为1号点．现在有3种类型的操作：• 1 root, 表示将根设为root.• 2 u v x, 设u, v的最近公共祖先为p, 将p的子树中的所有点的权值加上x.• 3 u, 查询u的子树中的所有点的权值和．对于每个3操作，输出答案． 题解： 须知知识：线段树，树链剖分  如果真的换根太麻烦了，所以我们每次只记录新根，并看看新根在后续操作中会有什么影响 如果在没有换根的情况下，操作2很容易实现，但是因为现在root已经发生改变所以我们需要特判。lca1=lca（u,v）lca2=lca(r...

[SDOI2011]消耗战 题意： 给出n个点的一棵带有边权的树,以及q个询问.每次询问给出k个点,询问这使得这k个点与1点不连通所需切断的边的边权和最小是多少. 题解： 树型dp+虚树dp[x]:切断x及其子树上询问点的最小代价预处理出minv[pos]代表从11到pos路径上最小的边权如果pos是询问点,dp(pos)=minv[pos]否则，最小代价dp(pos)=min(minv[pos],∑dp(to))（其中to是pos的儿子）如果pos为询问点，按理说不用dp[to]的值，但是仍然要对其儿子进行dfs，因为清空虚树需要对整个虚树进行遍历如果对整个子树进行dp，复杂度过高，这时候就...

参考文献：博文1博文2博文3  引入 在一类树上动态规划问题中,题目给出的询问往往包含树上的很多各节点,并保证总的点数规模小于某个值. 如果我们直接在整颗树上进行dp的话,时间复杂度与询问的次数有关,这显然是不可接受的,如果我们可以找到一种动态规划的方法,使其时间复杂度与询问中点的实际规模相关就好了. 于是虚树应运而生. 虚树 虚树并不是真实的树，是根据题意而构造的新树虚树相比于原本，仅仅保留有用的点，重新构造一棵树这里有用的点是指询问的点（也就是关键点）和它们的lca（可以理解为我们只需要保存关键点即可，但为了使得关键点彼此可以构造成树，所以要保留lca）有用的点都是位于叶子节点 具体步骤 ...

B-Suffix Array 题意： 一个字符串只含有a和b，先给出b数组的构造方式：对于每个位置i来说：  如果存在一个位置j，使得j<i,且s[j] == s[i],则b[i]=i-j 否则b[i]=0现在对字符串每个后缀都构造B数组，并按照字典序排序  题解： 参考博客题目标题就已经透露了一切，Suffix Array，说明这个题要用后缀数组来做，但是具体怎么做呢？我们会发现，化为B数组的值后，第一个a的值肯定为0，第一个b的值肯定也为0，那么从第一个a到第一个b之间肯定都是1比如“aaaabaaab”,则B(t) = 011102114，前半段为01110（也就是第一个a到第一个...

H.Minimum-cost Flow 题目： 其实就是给出每条边的单位费用，q次查询，每次查询改变所有边的容量（所有边容量一样），问最后流出1流量的最小花费是多少？ 题解： 暴力做法肯定是每次询问都改一次容量，但是肯定会超时，想想其他方法对于题目的每次询问，每条增广路的容量为u/v，所需最大流是1，我们可以列出一个式子cost(u/v,1) = cost(u,v)也就是把问题变成每条容量为u，所需要的最大流为v为了达到最大流为v的要求，肯定有a条增广路容量用完，但也肯定会有一个增广路只用了部分（假设用了b容量）0<=b<u能得到：v = a * u + b(0<=b<...

题目描述Bobo has a graph with n vertices and m edges where the i-th edge is between the vertices ai and bi. Find out whether is possible for him to choose some of the edges such that the i-th vertex is incident with exactly di edges. 题意： 问能否保留一些边，使得第i个点连接di边（也就是第i个点的度为d[i]）理论上二分图匹配是不可以的。应该用带花树才可以，但因为数据问...

对于一般的二分图匹配我们肯定会想到匈牙利算法，但是如果图中出现奇环怎么办？此时匈牙利算法就不可以了，就需要另一个算法：带花树算法主要就是为了解决奇环的问题我们匹配时会发现，如果存在奇环，传统的匈牙利算法在一个奇环里至少有一个点不能匹配，那么干脆就把这个奇环缩成一个点（也叫开花，这就是算法名字的由来），在处理到奇环的时候把它缩成一个点，路径取反的时候再暴力展开一个个取反。缩点用并查集来维护 流程： 参考代码我们给所有点黑白染色。假设开始增广的点是黑点。把所有黑点压进队列中顺次处理。对于一个黑点u，找与他相邻的点v，会出现一下四种情况： 1、u,v已经被缩成一个点了（这两个点在一朵花里），跳过。 ...