退役了退役了,D类报不上回去搞文化课了。

下次更新可能是NOIP前了。(反正也没人看我博客。

写给自己:相逢是问候,分手是祝愿。

又到了拿手的矩阵乘法系列问题,我最会推式子了。

这道题貌似比JLOI的难一点,不过也比较好想,留在原地的话只需要和自己连接就可以了,还有一个自爆,自爆的话只需要再多出一个结点把每一个和这个结点连接就可以了,唯一值得注意的是,这个结点也需要与自身连接。这个点卡了我很久qwq。下面上代码

好简单啊

众说周知最小点覆盖=(二分图所有点-最大匹配),那么接下来这道题就被转化成了一个求最大匹配的题,唯一需要注意的是,他的连边方向为4个,所以我们连边需要注意一下。剩下的就是这道题里还存在没用的山涧,最后也需要减去.

太神了

这道题很明显我们可以发现他所说的不重复使用道路,可以大概想到最大流这个模型,发现n很小,我们可以在输入的时候找到最小和最大的长度,然后二分长度来找到一个合适解,满足答案
显而易见我们的check只需要每次重新构图然后如果此时流量大于T的话我们把r=mid-1,ans=mid
否则l=mid+1;然后就可以轻松A掉了

太简单了

在此鸣谢zgz大爷

K-D树是一种维护多维空间中,多维数据的数据结构。我们可以用一维的坐标系来暂时看一眼1-D Tree

而我们可以根据每个点做一条与数轴垂直的直线,这样他就被分成了好几个部分,那么每个点都有左右两个部分,并且除了2边端点,都是存在2个点与单个点相靠近的,那么我们这时以中间的点为树根可以建出一个树,并且已知每两个点的相对距离,便可以用一估价函数每次判断从一个点是否应该跳到他的子儿子。这时一般做的查询为插入一个点,查询与他最近点的位置,那么建立完1d-tree之后,便可以轻松的得出答案。

那么kd-tree也就是跟这个一样的意思咯。

那么接下来我们一起来看一看这个东西的基本操作:

新建结点

此处为判断我们的k-d tree是否之前进行了排扁操作,如果已经被排扁并且存在未添加结点,那么我们从rub存储的结点中取出一个添加,否则新建。

建立KD tree

我们在建立整棵kdtree的时候和splay建树是一样的只是我们建立时候需要进行特殊操作的是中心结点,因为kdtree就是以估价函数来进行一系列操作的,而我们的中心结点可以更好的分出树的层次,防止树退化成链(后文还有防止退化的函数)这只中我们用到了一个stl函数,
nth_element(a+l,a+mid,a+r+1)他的范围是左闭右开,并且将序列中的第mid大数排在中间并保证mid左右的数严格满足左边小于右边。剩下的就是基础的建树。

更新结点

这里的代码和splay里的一样,就是更新子树大小,这里我就不赘述了。

拍扁

我们会发现,如果我们向kdtree的一面添加了过多元素之后,他极易变成一个链状结构,所以我们这里的拍扁操作就是重构整棵kdtree。从而使其重新满足查询复杂度较低的性质。

添加结点到树上

先判断树是否有根,没有就新建,有的话需要判断添加新建节点中的单独维度的元素来判断他插入在那个子树中。

check操作

这个看起来就显而易见了,在每次添加完节点之后,我们通过根节点两端子树的大小,来决定这里我们是否拍扁重构他,alph是一个阈值,我这里设置的是0.75,感觉在大多数题中还是跑的很快的。

估价函数

每道题的估价函数一般不同,都会以题目来叙述,通过判断结点的距离来产生不同的价值从而对query操作造成一系列影响。

query

这里我们通过判断子树的距离,来确定哪个结点与我询问的结点更近,通过每次判断距离加上递归其所在子树就可以得出结点编号。

总结

KD-tree一般题中其实不常出现,可以作为一种辅助算法骗分算法,一般用kdtree可以解决的都是一系列偏序问题。

那么这篇博文就写到这里了,如果有错误还希望指正,我的联系方式在右上角。谢谢大家。

好简单啊

炉石神题!!!玩炉石的一定要做一下!

由于我们对炉石的了解,所以这道题的题意我们可以瞬间读懂,也就是m把这些怪物分成了m+1次亵渎才能完全消灭的队形,那么这道题也就可以轻松的转变为求如下公式

f(x)=\sum_{i=1}^{i<=n}i^k

观察到n的值非常大,所以我现学了一个关于求自然数k次幂和的东西,
叫伯努利数。根据其公式可以轻松的推出前n个自然数的k次幂和,且复杂度是O(k^2),由于我们知道
这道题最多用的亵渎次数为51,所以发现可过。接下来就是说伯努利的公式了。

这个是伯努利公式

那么我们显然可以预先处理出组合数,逆元也可以相对求出(n+1)^i我们也可以预先处理,那么最重要的就是求出伯努利数。
伯努利数满足条件b0=1,并且存在

那么我们继续推式子可以继续得到

所以伯努利数的递推式也同样被我们求出,逆元部分依然可以预处理。

好神啊

一道二分加上拉格朗日乘子法的题,我们根据原式中的公式可以推写出以下式子.
我们可以贪心的认为当能量全用完时,所用时间总和最少。

f(x)=\sum_{i=1}^{i\leq n}\frac{Si}{xi}


由于我们知道存在如果要求一个限定内函数极值,需要用到拉格朗日乘数法,所以这道题我们
可以继续列出下列式子。

\frac{\partial g(x)}{\partial xi}=0

\frac{\partial f(x)}{\partial xi}=0


那么为了解出每段的xi,我们设一个常数 \Phi

\Phi \frac{\partial g(x)}{xi}+\frac{\partial f(x)}{xi}=0

\Phi =\frac{1}{2xi^2(xi-vi)ki}


可以得出\Phi 随着xi的增加而单调递增。
那么我们就可以来二分\Phi 从而推出每段xi;
再用每段的xi往g(x)中带入,算总能量的使用。
接下来就是代码实现了



感觉好神