luogu P3385 【模板】负环 SPFA

有点迷茫 ,DFS似乎快的点特别快,慢的点特别慢。BFS似乎都不怎么快,那似乎上限低点,不知道该用哪个。。

BZOJ 1202: [HNOI2005]狡猾的商人 差分约束 spfa

差分约束,有空再详细讲

//之前的写法有问题,数据水,直接过了,需要建一个超级源保证联通才行,否则与0点不连通的负环会不被考虑。

BZOJ 3173: [Tjoi2013]最长上升子序列 splay dp 思维题

我们发现他按照从小到大插入,如果我插入一个值,那可能会影响非常多的上升子序列。但是如果我们反着来,每次删除一个最大的,我们只影响以他为结尾的子序列,相对而言就容易处理多了。所以我们先用平衡树,求出最终序列。

然后我们考虑常规的nlogn最长上升子序列做法,我们可以边做dp,边维护出,保持一个长[……]

Read more

BZOJ 1941: [Sdoi2010]Hide and Seek K-D tree

于是我犯了和上一道题一样的错误,把l和1写混了,de了半个小时……..真是不应该。这道题比上道题能更好的反应K-Dtree 的用途。同时也发现了一些奇妙而高效的写法。比如getmn函数,巧妙的分类出,在区域上,区域中,和区域下三种情况的最小距离。
[crayon-5bef02b8a0f24[……]

Read more

bzoj 4066: 简单题 K-D tree

把l打成1,找了两个小时bug,心态炸裂,又回到了几个小时调一道题的老年状态。

正常来看这道题就是普通的K-Dtree,但是裸的K-Dtree 会tle。上网查了下,需要定期重构树,有点类似替罪羊的感觉,来保持树比较平衡。这样子就可以了。

 
[crayon-5bef02b8[……]

Read more

hdu6403 Card Game(基环树+DP)

看着题觉得很有趣,想了很久没想出来,后来又看了题解发现,这题太好了,我得写一写。然后敲了快300行,然后上网查了别人的代码,100行就写完了,真的是感受到了差距。

网上的大神们直接用普通搜索,外加边点的数量关系,就算出来了弱联通分量,判断出了是不是树或者基环树,然后我用了tarjan和一堆定制[……]

Read more

声明

本人常用id为金企鹅,为dl24退役选手。

本人未参与noip2018八校联考dl24卷的任何命题工作,仅负责了少量的验题工作。

如果各位大佬觉得题目有些毒瘤请不要来D我。

据我所知,命题组对数据均进行了精心的构造,强度确实较大,但也为了更好的模拟noip,增加考试区分度,帮助大家[……]

Read more