先思考这个问题：判断一个数是否为某个数的平方该怎么做？可行的方法有两种：1是求floor(sqrt())的平方是否为原数，2是枚举因子，将因子的平方标记。这两种方法一种是O(1)的，一种是需要O(maxnum^(1/2))的时间预处理，以及需要这么大的空间存答案。同样，判断一个数是否为某个数的三次方该怎么做？可行的方法有两种：1是求floor(三次方根)的立方是否为原数，2是枚举因子，将因子的立方标记。这两种方法一种是O(1)的，一种需要O(maxnum^(1/3))的时间预处理，以及需要这么大的空间存答案。接下来就类推了，我们来计算一下两种方法的总复杂度： 第一种方法，首先对于每个数，我们需...

题意是求最短路，可以选择一个点使得与这个点相连的所有边边权变为1。假设我们选择的点是x，经过x的最短路是：1—>......—>a—>x—>b—>......—>n答案就是min{dis(1,a)+dis(b,n)+2}，这里a和b要同时和一个点相连。我们可以用最短路算法求出1和n到其他所有点的最短路，dij和spfa都是可以的。然后再依次枚举点就好，复杂度总的来说，用dij的话，是O(nlogn+m)的。

其实求的是一个显然的结论，每个后来插入的数的父亲节点的权值必是其插入时的前驱或者后继。所以需要快速找到前驱和后继的深度，用线段树或者双向链表可以轻松实现。至于...到底是前驱还是后继，比较深度，一定是深度较大的那个，至于证明，归纳一下，非常简单。

我们先来研究只有两个小朋友的情况，共有4种情况，(0,0)(0,1)(1,0)(1,1)。我们可以发现，只有(1,0)，我们是无论如何都无法避免产生1的失落值的，其他情况均有办法使失落值为0。因此答案就是(1,0)的对数，统计这个数量即可。

设答案为f[n]f[n]/2=(f[1]+f[2]+...+f[n-1])/(n-1)又f[1]=1f[2]=2这样推下去，就可以得到f[n]=n这个结论。

当n=2时，我们该怎么做呢？设p=a[1],q=a[2]p和q能组成的数是py+qz，y和z都是整数，将gcd(p,q)提出来，py+qz=gcd(p,q)*(yp0+zq0)，其中gcd(p0,q0)=0，p0和q0可以通过更相减损得到1，也就是说(yp0+zq0)可以等于任意整数，因此py+qz可以得到任意gcd(p,q)的倍数。所以可以用gcd(p,q)替换a[1]和a[2]。推广到n=任意正整数，可以用gcd(a[1],a[2],...,a[n])替换掉a[1]到a[n]。得到这个gcd，再与询问的x判断是否为倍数关系即可。复杂度O(nlogn+T)

有两种思路可以解决这个题目。思路1：先解决一个问题，如何用最少的步数将一个已知排列排序。不妨将排列看做图，比如n=3，排列a是a[1]=2,a[2]=3,a[3]=1,i向a[i]连边，显然可以连出一个n个点，n条边，每个点度数都为2的，可以有自环，且只有环的图。首先对于自环，这些位置不需要和其他位置交换，因为它们已经在自己的位置上了。然后对于其他环，要使步数最少，交换只会发生在环内，一个长度为k的环，需要k-1次交换才能变得有序，这里手玩几个小环应该就能得到结论。所以交换次数=n-环个数然后我们再来考虑之前的问题，如何求期望。期望交换次数=n-期望环个数所以不妨来求环的个数！设f[i]表示i...

首先我们可以明确的是，除了已经规定好相对顺序的m个数，其他数肯定按照从小到大的方式填最优。接着根据这个思路，我们有一个这样的算法：一开始我们将剩下的n-m个数放进堆(小根堆)里，然后将m个数中的第一个数放进堆中并给这个数做标记，每次弹出堆顶并输出，当弹出了做过标记的数时，往堆中放入m个数中的第二个数并做标记......知道m个数全部放进堆中且堆被弹空。这个算法同时保证了其他数按照从小到大的顺序，且同时保证了m个已知数的相对顺序。复杂度O(nlogn)

这里有一种分治的做法。考虑当前分治区间[L,R]，区间中心为mid，我们需要解决的问题是求出所有跨越mid的区间的答案。首先枚举右端点r(左端点也是一样的，这里只是举个栗子)，对于所有左端点l和最大值(最小值)，可能的情况有三种：1、max(l,mid)>max(mid,r)2、max(l,mid)=max(mid,r)3、max(l,mid)<max(mid,r)可以发现，这三种情况是分别连续的，且随着r的变化，这三种情况的分界点的变化也是单调的。最小值同理。根据这个性质就可以在O(n)的时间里求出所有跨越mid的区间的答案。结合分治，就把问题解决了。总复杂度O(nlogn)

要求字典序最大，故我们可以从 n 到 1 贪心地试探每个数能否加入出栈序列。假设我们已经枚举到了 i，若栈顶元素比 i 大，我们则可以弹出栈顶元素，将其加入出栈序列，直到栈顶元素 ≤ i。若 i 未在栈中，我们则将入栈序列中在 i 前面且未入栈的数入栈，并将 i 加入出栈序列；若 i 在栈中且是栈顶元素，我们则将 i 弹出栈，并加入出栈序列；若 i 已经在栈中且不是栈顶元素，则说明若将 i 加入出栈序列，之前必然要把比 i 小的数弹出栈，我们不这样做，继续枚举 i − 1。时间复杂度为 O(n)。

【前言】 非常简单的动态规划题。 【暴力】 搜索，搜出所有可能性。 【不完美的超时做法】 设f[i][j][k]表示，只买前i种商品，共买了j件，能否达到价钱k。 可以转移到f[i+1][j][k]和f[i][j+1][k] 复杂度是O(nm^2*max(v))极限是500^4 【正解】 考虑优化dp。 这里有个小小的技巧。 将所有物品的价格排序，然后减去最小的，这样的作用是，假设我们选的物品个数不足m个，那么可以默认为不足部分全部选择了最小的那一个，我们就可以省去一维，则复杂度变成了O(nm^2*max(v)) 参考代码： class Solution { publ...

【前言】无。【暴力】枚举每种物品的选择与顺序。复杂度显然很大。【正解】假设我们知道了一个最优解的集合，但不知道顺序。最优顺序显然是按照代价从小到大排序后依次选择。因此，我们可以把物品先按代价排序，然后进行动态规划。设f[i][j]表示在前i个物品中选择了j个的最优答案，注意，这里的物品是按代价排好序的。转移也就非常显然，f[i][j]可以转移到f[i+1][j]和f[i][j+1]，复杂度是O(n^2)转移方程太过于简单，相信对大家来说并不难，如果还是有点困难，可以参考给出的代码： struct nod { int w,v; }b[6000]; bool cmp(nod x,nod y...

【前言】无。【暴力】搜索O(2^n)【正解】对于一个位置，如果这个位置后面有比它小的数，那这个位置肯定是要动的，这显然是答案的下限。我们来证明一下这个下限是可以达到的。有一种很显然的排序方法可以达到这个下限。从后往前看每个位置，如果该位置的身高大于后面的位置，则进行一次选择，这样就达到了下限。这种方法可以保证每次选择，被选择的位置到队尾(不包含被选位置)已经形成升序，排序后被选择的位置到队尾(包含被选位置)也变成了升序，这样每个必须要动的位置被动了一次，刚好达到下限。复杂度O(n)参考代码： class Solution { public: /** * 代码中的类名、方法名、...

【前言】无。【暴力】直接搜索方案数。【打表】通过对小数据的暴力很容易得知答案就是(n+1)(n+2)/2【正解】我们将盘子2和4看做一类，盘子3和5看做一类，这样是可行的，对于任意正整数m，都可以表示为2x+a或5y+b的形式，这里的x和y分别就是在4和5号盘里面取的件数，a和b分别是是小于2的正整数和小于5的正整数。问题就变成了，将n个面包分为三份的方案数，经典隔板问题，相当于C(n+2,2)。因此答案就是(n+1)(n+2)/2.