_LRJ_

分类

题解(29)

/ 注册

全部文章（共29篇）

【每日一题】cf786B（线段树建图+拆点+最短路）

挺好的一个题，线段树建图+拆点+最短路。这个题一眼看上去感觉不就是对于每个条件，对于区间[l,r]的所有点都连上一条边，完了在跑个最短路就完事儿了。但是看见数据范围的时候就傻眼了，因为最坏情况每一次会有O(n)个点相关，因此，边的数目都会最坏达到O(N*N)无法接受。那么，对于1e5左右的数据...

2020-11-12

2 957

【牛客练习赛72】C

这题难在联想到二维平面几何问题上。对于任意一端的l,r如果其中所有的数字都在( a[l],a[r] )之间的话就一定可以把他们变成等差数列（可以画个图想想）所以需要求凸壳，将序列分为几段等差数列来做 CODE: //#pragma GCC&nb...

2020-11-07

2 749

【每日一题】平衡二叉树

这个题坑点在于和我们一般的BBT不一样。我们说平衡因子一般是要<d。但是这里是<=d。这点要注意。然后就来分析一下题目。首先，特判两种情况n=1||n==0输出0就行了考虑一般情况，画个图发现，如果f[n]表示平衡因子不超过d的最小结点数量。那么f[n]=1+f[n-1]+f[...

2020-07-11

1 814

【每日一题】滑雪与时间胶囊（贪心+kruskal）

Kruskal+Greedy 这个题目还是一个比较有意思的题目啦。我们想解决这个问题还是需要一点前置知识的。首先我们来讲一下最小生成树的一些概念。已经有所了解的小伙伴可以直接跳到分割线后最小生成树首先我通俗讲一讲现在比较主流的一些最小生成树的做法。①prim算法。这个是一个基于加入点的做法了，...

2020-05-07

5 886

【每日一题】换个角度思考

一道树状数组的离线询问题下面简单介绍一下树状数组如果已经知道树状数组是什么的可以直接跳到分割线后面树状数组他其实利用的是类似于二进制的东西，所以英文名也叫做BIT(Binary Index Tree)每一次通过lowbit函数求出来当前这个数的所管范围，假设现在的数是x,他的区间就是[x-l...

2020-05-07

0 759

【每日一题】Symmetric Matrix（数形结合+数学+dp）

这个题目构思十分巧妙，我们考虑把这样的矩阵作为一个图的邻接矩阵，恰好满足题目中的所有条件，并且关键的一点是每一个点都有且仅有2条边。针对这类问题可以使用dp来解决。dp[i]表示i个点满足条件的图的种类数目。分情况讨论可以得到状态转移方程： dp[i]=((i-1)*dp[i-2]+(i-1)*dp...

2020-05-06

0 799

【每日一题】Removal

这个题是将长度为n的序列里面删去m个元素，问你有多少种剩下来的序列情况。很容易联想到dp首先如果两两都不同，那么直接01背包 dp[i][j]=dp[i-1][j-1]+dp[i-1][j];但是题目里面有可能会出现重复元素，这个时候就要去剪掉一些方案数了。我们记录下来每一个数前面最近的值相同的元素...

2020-04-30

0 626

【每日一题】子序列(dp+math)

很水的一道题目。唯一的难点可能就是，你要知道log这个函数。使用它要包含math头文件，然后他返回的是浮点型的数据，我们如果直接去比较其实是不好的，因为有可能会溢出，你long long 都没有用，你想想如果出现，这是个多大的数字啊。那我们就可以使用log这个函数了，比较上面的函数我们其实要分情...

2020-04-30

0 655

【每日一题】边的染色

这个题目其实需要一点思维。关键是要能够想到对于边染色，可以转到对于点去染色，而且我们规定，边颜色等于两个顶点的异或值。仔细想想，如果这样的话我的点可以随便染色，都能够满足环的异或值为0，因为，每个点会连2条边，会异或2次，怎么样都是0.还有一个要注意的点就是，对于n个点有2^n种染色方法，但是会有重...

2020-04-30

0 887

【每日一题】K-th Number

这题目主要是要能想到使用二分。其实当你遇到看似无从下手的题目的时候，我们就可以从二分的角度去思考。这个题目就是二分枚举x，作为数组b里面的第m大的元素，我们可以考虑check a数组里面大于k个x的区间个数，如果这样的区间个数小于m就说明x取大了。具体见代码 #include typedef lon...

2020-04-29

0 669