NOIP2018翻车记包括部分题解

&&

最终OI退役记

一切的原因都是因为不够好。

首先还是先说一下今年的noip奇怪的感受吧,第一天早上起来就很难过,突然感觉就是最后一次来到这个地方了,也害怕自己成绩不好(果然如此)。机房从此缺了很多人的身影,学弟们也都见不到了吧,很开心最后两周还和他们度过。早上到在酒店吃饭就看到了yyc(雾),到了考场zgz,lkh大爷貌似再说一些东西。Rec安静地坐着。。。ltx姐姐又开始了发糖模式%%%,tyk一脸轻松的样子emmm一定是稳了。没有抽签按照姓名分,哇周围又肯定是一群神犇。今年貌似初中生参加很多(都比我分高),到了考场开题,道路???这特么不是积木???luogu原题开场看的时候还是挺开心的。
大概想了一下只需要从后往前枚举如果后面大于前面就加就可以了,我特意看了一眼边界大概到不了long long?但是我还是开了一发。大样例还是很好过的。大概10分钟就去看T2了。

T2就是我最大的失败点了,先没太看懂题,后来读了读大概想到就是用几个数来组成所有数的意思啊,想到了背包,但是一写发现没法记录我哪些数可以被表示??而且当时没想到排序的问题。也不知道在想什么,就感觉药丸,赶紧出去上了个厕所,发现依然没有想法,看了一眼部分分,啊原来有小的点,打特判???结果真就是打了40分特判滚粗,后来想了想woc不就排序一下然后用小的数不断枚举前面的数被组成就行?但是考虑到这是个多重背包ai<=25000如果这样会不会T几个点啊,然后发现dp【】可以连续性,判断新的dp[a[ i]]可以从dp[a[i-1]]开始枚举,这样貌似就优了很多了。回来不用5分钟就A了。。。。可惜啊
放刚才写的代码。

打完特判的我慌张不已还期盼T3能有好结果,被疯狂打脸,看的时候就觉得肯定有二分的事,其他的并没特别想到,想了一下贪心连边,如果小于K就往里面一直连接,证明正确性失败了?自我否定正确答案,无敌操作。后来听他们说想起来可以通过枚举每个点连的边,因为连接成功的赛道贡献都是1,所以根据每个点的子节点对其贡献排序后继续二分,看是否能在赛道不减少情况下得到最大k值就可以了。大概复杂度也是nlog方的感觉也是可以通过的。我就打了m=1特判和链特判。滚粗滚粗。

晚上学弟们都说暴力过大样例??让我当时无地自容,感觉完全炸掉,心情也不是很好。10点就睡了,

第二天在考场外呆的时间较长,听说很多人D1 都AK了,哇,,那我是不是拉吉林省平均分了。。。菜的要死,希望D2翻盘(假假)

进考场T1就想了一会,发现只会60,dfs序哇谁都会吧。。。后来想了想枚举删边然后把剪枝做的优一点就能A了吧刚才写了个88的没法卡过最后两个点了:

T2是一个完全我没看懂的题,想了半天都不知道他说的合理方案是啥,在此也就不说了。
T3 恩用点控制别的点,树上dp吧,
44很好打的吧,(我当时不会),dp[0/1][i]分别表示i点选或者不选,直接对每个询问进行dp的预设值和处理就行O(nm),正解ddp???有点神了毕竟要退役了也没有多看那些奇怪的东西。
恩就这样开心的滚粗了。

现在开始退役记:

依然是阳光慵懒的午后,熟悉了那条穿梭于实验楼的小路,想到去年一同去dsfz,他总是很开心的,和同学们一同在外学习,在刚开始进入高中时候从来没想过的事情,第一次自己和同学坐火车出外校进行学习,真正有了一个自己爱好的科目,在dsfz也是有很多传奇不断发生,结识了一群强大到无法再强的人,他们说的我都听不懂,他们写出来的我都不会,每天的测验偶尔能够拔尖,有时候就是垫底,他当时还是太年轻了,根本没有想到那些平常打出来的东西出在考场就是做不出来的神题。也由于去年的过分自大他暴毙了,不知道他是怎么思考的还是想继续学省选?那段时间他真正掌握了一些东西,也算是有所收获,和smzz度过的每一天也都很安逸并且快乐,省选就又一次打败了他,没有办法只能够学习文化课。但每日的中午他依然不缺席,因为那已经成了一个习惯,一个角落的位置,好像就永远属于他,虽然教练总说让他收拾东西,但是他还是习惯于平铺开寻找各种书或是笔。不久高二学弟也部分来到了这屋,_Convex和pcktrsss真的是让他非常佩服的两个人,一个掌握了很多知识很多算法数学很好,另一个思维很快,经常能yy到一些想不到的东西(看到了smz的影子)。就这样安逸的日子持续到了30天前,之后我便重新又回到这里准备NOIP2018,他又开始天真以为这回我会的东西总够了吧,但是他也在担心,所以每天他比去年努力多了,每天专注于他不擅长的dp,积极复习各种算法,但还是不够,在NOIP赛场上本能AK的第一天就挂了150,第二天心态完全消失也就草草打了60,很多学弟都比他分数高的多,这么多次的考试爆炸真的很有力量的打击了他,他真的很失落,这不仅仅是对他而言,对他周围的一切亦是如此,他也不知道真的是能力太差,还是真的状态不好,原来他总能以状态不好为由逃避,可如今他没法说服自己了。但是他依然明白这就是结束了,没有任何的尾声需要进行,OI生活对于他已经彻底消失了,他一边在怀念,一边在悔恨,如果很多转折的点不同他的OI就完全不同。可惜没有如果,过去了就已经成为无法改变的历史,永远刻在他心里。。。
可能还会有人问,他真的水平足够么
我想,不然吧。。。。

退役了退役了,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)中带入,算总能量的使用。
接下来就是代码实现了



感觉好神