这题难在联想到二维平面几何问题上。 对于任意一端的l,r如果其中所有的数字都在( a[l],a[r] )之间的话就一定可以把他们变成等差数列（可以画个图想想） 所以需要求凸壳，将序列分为 几段 等差数列来做 CODE: //#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define all(x)...

这个题坑点在于和我们一般的BBT不一样。我们说平衡因子一般是要<d。但是这里是<=d。这点要注意。 然后就来分析一下题目。 首先，特判两种情况n=1||n==0输出0就行了 考虑一般情况，画个图发现，如果f[n]表示平衡因子不超过d的最小结点数量。那么f[n]=1+f[n-1]+f[n-1-d].前提是n>=d+1那么n<d+1呢？很简单，一条链就ok #include<bits/stdc++.h> using namespace std; typedef long long ll; ll f[70]; int main() { ll n,d; cin&...

Kruskal+Greedy 这个题目还是一个比较有意思的题目啦。我们想解决这个问题还是需要一点前置知识的。首先我们来讲一下最小生成树的一些概念。已经有所了解的小伙伴可以直接跳到分割线后 最小生成树 首先我通俗讲一讲现在比较主流的一些最小生成树的做法。①prim算法。这个是一个基于加入点的做法了，并且写起来的的话和求最短路算法的dijkstra的代码看起来挺像的。什么意思呢？就是我们要迭代n次，并且是妥妥的n-1次，因为每一次是要把不在当前集合的点里面挑一个距离最小的点来加入进来，所以一共有n个点的话，就一定是迭代n次（这里默认我第一个点已经没有加进来，这个地方和dijkstra不一样），这...

一道树状数组的离线询问题下面简单介绍一下树状数组如果已经知道树状数组是什么的可以直接跳到分割线后面 树状数组他其实利用的是类似于二进制的东西，所以英文名也叫做BIT(Binary Index Tree)每一次通过lowbit函数求出来当前这个数的所管范围，假设现在的数是x,他的区间就是[x-lowbit(x)+1,x]，那么我们为什么要用这个树状数组呢？或者说它有什么好处吗？ 其实树状数组它能解决的问题十分有限，相比较线段树这个数据结构，树状数组只能够处理求区间和的问题，但是不能求解区间的最大值，最小值，异或值等等。那么树状数组和普通的数组查询和修改又有什么不一样的？很简单，树状数组由...

这个题目构思十分巧妙，我们考虑把这样的矩阵作为一个图的邻接矩阵，恰好满足题目中的所有条件，并且关键的一点是每一个点都有且仅有2条边。针对这类问题可以使用dp来解决。dp[i]表示i个点满足条件的图的种类数目。分情况讨论可以得到状态转移方程： dp[i]=((i-1)*dp[i-2]+(i-1)*dp[i-1]-(i-2)*(i-1)/2*dp[i-3])%m;代码如下： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m; ll dp[100010]; int main() { ...

这个题是将长度为n的序列里面删去m个元素，问你有多少种剩下来的序列情况。很容易联想到dp首先如果两两都不同，那么直接01背包 dp[i][j]=dp[i-1][j-1]+dp[i-1][j];但是题目里面有可能会出现重复元素，这个时候就要去剪掉一些方案数了。我们记录下来每一个数前面最近的值相同的元素的pos位置，从前到后扫一遍就可以得到。然后我们计数的时候，要加一个判断。如果dp[i][j]此时的pre[i]=k&&j>=(i-k),那么就要减去一部分 dp[i][j]=(dp[i][j]-dp[k-1][j-(i-k)]+mo)%mo;具体见代码吧 #include&l...

很水的一道题目。唯一的难点可能就是，你要知道log这个函数。使用它要包含math头文件，然后他返回的是浮点型的数据，我们如果直接去比较 其实是不好的，因为有可能会溢出，你long long 都没有用，你想想如果出现 ，这是个多大的数字啊。那我们就可以使用log这个函数了，比较上面的函数我们其实要分情况讨论一下，如果a[j]==1,那么一定不行，因为你a[i]^j不可能小于1了。那么反过来想想，如果a[j]!=1&&a[i]==1的时候，一定满足条件。那么剩下的就是a[j]!=1&&a[i]!=1的case了，我们再去使用log函数进行比较 return j*lo...

这个题目其实需要一点思维。关键是要能够想到对于边染色，可以转到对于点去染色，而且我们规定，边颜色等于两个顶点的异或值。仔细想想，如果这样的话我的点可以随便染色，都能够满足环的异或值为0，因为，每个点会连2条边，会异或2次，怎么样都是0.还有一个要注意的点就是，对于n个点有2^n种染色方法，但是会有重复，需要除以二。 知道了这个的话，就好做了。我们只要去找到有多少个连通块，有多少个已经染色的点，这里要判断一下是否产生了矛盾，有矛盾的话直接输出0.否则的话根据公式计算 ANS=2^(K-1) K为未染色的点个数。 具体见代码，写了注释： #include<bits/stdc++.h>...

这题目主要是要能想到使用二分。其实当你遇到看似无从下手的题目的时候，我们就可以从二分的角度去思考。这个题目就是二分枚举x，作为数组b里面的第m大的元素，我们可以考虑check a数组里面大于k个x的区间个数，如果这样的区间个数小于m就说明x取大了。具体见代码 #include typedef long long ll; using namespace std; ll n,m,k; int a[100010]; bool check(int mid) { a[0]=0; ll res=0; ll i=1,right=0,cnt=0; for(i=1;i<...

这个题目的关键是要发现他是一个贪心+dp的题目。 我们具体怎么做这道题目呢？首先我们考虑最早应该做哪些菜肴是最好的，就是要把他们全部排一个序，根据能获得的菜肴美味值。对于编号为i和j的菜肴，他们的美味值总和在先后顺序不同的时候是这样的。如果要i排在j前面就要使得这样的美味值大于第二种方法具体公式是 那么我们根据他排序之后要做的就是简单的01背包了，我们考虑dp[i][j]表示前i个菜肴里面在不超过j时间内所能获得的最大美味值。容易得到转移方程： dp[j]=max(dp[j],dp[j-cai[i].c]+cai[i].a-cai[i].b*j);完整的代码如下 #include<b...

你就是个水题~这个题如果理清思路其实特别好做，我们仔细想想，是不是如果一个人后面没有比他更大的另一个队伍的人那么他一定就活下来了吧那么其实我们要做的就是从后往前维护2个最大值（两个队伍的最大值），那要做的就是如何把这些ci给他优美的加上首先考虑暴力，每次把前面ci个数加上一。时间复杂度是n2。不够优秀，我们可以想到的使用一个差分数组，每次先记录下来区间的更新情况，最后扫一遍线性就出来了。 #include<bits/stdc++.h> using namespace std; int a[50010],b[50010],d[50010]; int n,m; int main() {...

这是个水题，但是有坑点。我们可以这样考虑，我们从n个位置种选2个作为逆序对的两位置，一前一后也不用x2，然后对于剩下的n-2个位置，我们可以随便选，因为题目给了所有01串。所以C(n,2)* 就是答案。坑点是要特判n=1的情况，然后对于组合数，如果你用除法的话，一定要变成逆元，不然会WA #include<bits/stdc++.h> typedef long long ll; using namespace std; ll n; const ll mo=1e9+7; ll qp(ll a,ll b) { ll res=1; while(b) { ...

这个其实是个水题，我们要找树当中所有长度为偶数的路径数目，我们其实可以很快的想到一点就是，我们dfs记录下每一个节点的层数，偶数层到偶数层距离一定为偶数，奇数层到奇数层的路径长度一定为偶数，这一点比较像奇数和奇数相差偶数，偶数和偶数相差为偶数。那么我们就只要dfs记录下来奇数层个数，偶数层个数，然后只要在奇数层选两个点选的方案数量加上偶数层两个点选的方案数量就是最终答案了，以防万一还是要开long long的~ #include<bits/stdc++.h> typedef long long ll; using namespace std; int n; ll ans=0,ou,...

这个是典型的二分答案题目了。我们可以发现，答案的正确性是随着我们取木棍的长度而单调变化的，具体来说，在这道题目里面，我们发现，当木棍长度越小，越有可能获得更多的木棍数量，也就更有可能满足题目条件。容易想到二分。我们设左端点l=0，右端点r=1e9，每次看mid能不能满足，如果可以，那么l=mid,不然r=mid-1,我们就要logn 的时间复杂度，很快就能得到答案。 #include<bits/stdc++.h> typedef long long ll; using namespace std;int a[200010]; int n,k; bool check(int mid)...