思路：和背包长得像，那么我们就往背包上想，dp[i][j]表示前i天我们买了j个糖果的最小花费，dp[i][j]可由dp[i-1][k]转移得到，那么怎么转移？j的范围要<=min(n,im)k就最小从i-1个糖果开始（再小就不符合题意）最大到min(j,min(n,(i-1)*m))当第i-1天的k个糖果取到第i天的j个糖果就需要加上此时在第i天买糖果的花费就是+前(j-k)个糖果的价格（我们用前缀和去维护），再加上（j-k）的平方。得到dp方程为dp[i][j]=min(dp[i][j],dp[i-1][k]+a[i][j-k]+(j-k)(j-k)); #include <c...

思路：在树上找2点的最短距离，很容易想到LCA，那么我们在树上找a,b的最短距离，因为缆车的存在所以有3种找法，一种是直接从a节点到b，第二种是a先到缆车x加上b到缆车y的距离，第三种就是a到缆车y加上b到缆车x的距离，我们取个最小值（~ 用C++11会TLE ~） #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<queue>...

思路：异或值最大，我们就让每一位不同的尽可能多，那么给你区间l,r我们将l,r变成成2进制高位补齐，为了不超过L-R区间从高位向低位遍历时，遇到相同的我们就继续走，如果遇到某一位不同那说明从这一位开始后面的每一位0,1我们可以任选，使得从当前位置到后面的每一位异或后变成1，此时值最大 #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<...

思路：当一个数的异或次数为偶数时那么他没有贡献度，所以我们只需要看没个点被走了几次如果是奇数次那么他有贡献度，问题就变成如何求点被走了几次，我们用个数组表示一个个点的儿子个数是多少，假设v是u的儿子，通过dfs遍历u的整个子树，得到儿子的个数，那么从u-》v，u的次数就是p[v] * (n-p[v])，因为遍历时会重复计算一遍要除2，这时我们再看u的父亲fa->u有多少次，就是p[u] * (n-p[u])也要除2，这样就算出了u到被走了几次。 #include <cstdio> #include <cstring> #include <algorithm&...

思路：用dp[i][j]表示从i到j涂好色的最少次数，从RGBGR这个样例我们可以发现，后面的颜色可以是前面就图好了，那么可以得当i,j相同时，这个i位置的颜色就是再涂区间i+1,j时涂好的，j位置是再涂区间i,j-1时涂好的dp[i][j]=min(dp[i+1][j],dp[i][j-1])。i,j不相同的时候，说明1次染色不行，分成2块去染枚举断点。dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]) #include <cstdio> #include <cstring> #include <algorithm> #i...

思路：我们用dfs去想,首先如果此时只有一个人那我们就直接返回答案，dfs（x，y，n）表示边长为x,y,切给n个人长边与短边之比最大值最小的值是多少，为了保证面积相同每次切若沿着x切必定是x/n的倍数若沿着y切必定是y/n的倍数，我们要看切完后分给多少个人，就看他当前切的是多少倍，然后我们按X,Y去切就行了求他们的最大值最小 #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<v...

思路：根据题意我们让左子树为高度n的满二叉树，右子树上的点尽可能少，那么我们首先吧他的高度拉满使其为n-m-1，此时我们在右子树的左子树上高度拉满点最少，然后如果还有点，那么为了维持平衡且让右子树点最少，我们吧点加到i-m+1的树上，可得方程dp[i]=dp[i-1]+dp[i-m-1]。dp[i]表示高度为i的右子树的最少点。 #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<...

思路：我们要他异或的和最大那么我们对第i位为1时X的第i为0，第i位为0时X的第i位为1，这时我们需要知道区间L-R的第i位是1多还是0多，用前缀和的思想sum[i][j]表示从1到第i个数的第j位上1的个数之和，要保证x最小那么我们再1的个数和0的个数相同的情况下将X的第i位置0 #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> //#include&lt...

思路：要求[i,j][x,y]两区间亦或为0，那么[i,j]==[x,y]就行，我们规定[i,j]为左区间,[x,y]为右区间,我们枚举左区间的右端点算出左区间的值，再枚举右区间寻找与左区间相同的。 #include <algorithm> #include <iostream> #include <cstring> #include <iomanip> #include <string> #include <vector> #include <cstdio> #include <queue> #i...

题意：构成连通块的方案数思路：用dp[i][j]表示前i个节点用j种颜色的方案,dp[i][j]是由他上一个节点的颜色相同方案加上他与上一节颜色方案不同的和dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(m-(j-1)) #include <iostream> #include <algorithm> #include <cstdio> #include <set> #include <sstream> #include<string> #include<queue> #include&lt...

题意：给你n个数，当数字个数为奇数时输出此时的中位数思路：以第一个数作为mid值，建立一个大顶堆一个小顶堆，大于mid的加入小顶堆，小于mid 的加入大顶堆若两堆相差2个数更新mid注意格式 #include <iostream> #include <algorithm> #include <cstdio> #include <set> #include <sstream> #include<string> #include<queue> #include<stack> #include<ma...

题意：给你一棵 n个节点的树（保证 n 是偶数），你需要将 n 个节点分为 n/2 个点对，使得每个点对的两个点的距离的和最小。思路：我们可以发现若以u为根的子树节点个数为奇数那么无法在子树内进行匹配，会有一个节点对外匹配，所以标记一下节点数在加上每次对外匹配的值即可 #include <iostream> #include <algorithm> #include <cstdio> #include <set> #include <sstream> #include<string> #include<queue&g...

数论分块，那么咋分呢？我们先手动一发。比如此时r=66.我们要求1的出现次数那么就是1,[10,20)66/1 = 66 , 而66/66 = 1,代表从[1,1]只有1个数最高位为166/10=6,66/6=10,代表从[10,10]有1个数高位为166/11=6,66/6=11，代表[11,11]有1个数高位为166/12=5,66/5=13,代表[12,13]有2个数高位为166/14=4,66/4=16,代表[14,16]有3个数高位166/17=3,66/3=22,22>20代表[17,20)有3个高位1 至此我们就可以看出了如何去分。要求出[l,r]中我们就换成求出 [i,r...

思路：要达成题目要求我们有2种方法1.删除s和子树之间的节点2.删除子树与叶子的节点。那么我们将f[i]表示为以结点i为根节点的最小代价可得f[i]+=min(f[i],wi...j) #include <iostream> #include <algorithm> #include <cstdio> #include <set> #include <sstream> #include<string> #include<queue> #include<stack> #include<map&g...