Accumulation Degree

Accumulation Degree
这题简单来说就是任意根到子树的最大流量,这题假如我们枚举n个点的话,我们可以用O(n^2)时间做出这一题,但是呢,n很大,所以呢我们要至少减去一个log的复杂度,又因为我们只枚举一个任意点进行一次DP就可以获得大多数其他点DP得到的结果,所以我们先DP一次,然后再利用dfs计算DP取得的数据据算出其他点的数据。 ......  查看更多

没有上司的晚会

没有上司的晚会
这题的话我们可以把直接上司和员工连一条边,这里f[x][0]表示我不让x来的最大快乐值,f[x][1]表示让x来的最大快乐值,那么我们每次dfs下去回溯时,就分f[x][1]+=f[x][0]f[x][0]+=max(f[y][0],f[y][1]),分情况讨论一下,最后输出max(f[1][0],f[1][1])即可 ......  查看更多

选课

选课
选课这一题我们很容易发现没有根节点,因为可能不止一个不用前置课程的节点,然后我们因为多个课程可能有一个相同的前置课程,所以我们其一可以通过森林转二叉树进行就是左孩子右兄弟,或者采用背包型树形DP,把每一次树形DP的结果都做一个背包,这样子用f[x][t]代表以x为跟的子树选t个节点的最大值,然后再回溯时背包一下,就可以用不同的t取得不同f[x][t]结果,然后就可以正常动归了! ......  查看更多

「算进」[动归]树形DP

动态规划问题是大家都很熟悉的问题了,那么好了,树形DP顾命思意就是在一棵树上DP,解决一些问题,那么我们可以采用Dfs+边目录的方式来处理这些问题。通常来说从x节点递归下去,然后回溯上来,递归的数据x转移。

没有上司的舞会

这题的话我们可以把直接上司和员工连一条边,这里f[x][0]表示我不让x来的最大快乐值,f[x][1]表示让x来的最大快乐值,那么我们每次dfs下去回溯时,就分f[x][1]+=f[x][0]f[x][0]+=max(f[y][0],f[y][1]),分情况讨论一下,最后输出max(f[1][0],f[1][1])即可
AcceptCode ......  查看更多

[GDOI2018]为了不能实现的诺言-续

原本这篇东西我想到是以后心态恢复了我才写的,可是这样的话我也没有这个时间去写了,那么就现在写着吧。

GDOI2018已经正式结束了,在闭幕式当天,我听到最多的一个词莫过于“退役”了,退役的话对已每个选手来说都是一个很痛苦的事情,但也是每一位选手不可缺少的东西,室友经历过才会更加珍惜时间,只有经历过才会变得更加努力和无畏。退役,是竞赛的转折点。
但是现在,我终是要初中退役了,不管怎么说吧,很多人安慰过我,这不重要,高中可以接着搞竞赛,但是一日竞赛人终生竞赛人,竞赛这一点是改不了的了,像毒品一样吧,会上瘾。但是我还是想说一下,不要试图去安慰一个即将退役的选手了,这样完全没有用处,只会使他加剧痛苦罢了,退役这种事,即使经历了无数次,还是会依依不舍不肯忘怀的。所以不要试图安慰他们了,因为你们根本不懂得退役的沉重!这是我作为一个退役选手的感受。
真的你们可能根本不懂得退役的沉重!
对已这些事情,我们能做的只有同情。我是一个不怎么有名气的选手,因为文化课的纠缠,导致了很多矛盾,所以竞赛的时间变得很少了,这样我少了很多时间去复习模板,去刷题,这样导致了我没有进Day3,也因此有了十分之恨
虽然这样,的确是我自己能力的问题,这些事情我经历的太多了,这些除了自己默默承受以外,只能然后重整衣装,再候机会了。
至于为什么在Day4颁奖触景生情,因为别人很多时候问过我,你问什么不在文化课上花同样的时间,为什么没有学好文化课。
这是幻想的问题吧。我对信息学充满着幻想,我相信我可以成功,因为我有这个水平,我有这个兴趣,我有这个环境。
但对于文化课,我也对此充满着幻想,但是一次又一次的失败,让我失去了信心,我相信我可以成功,但是事实给我打打击实在是太大了。于是我就开始躲避这一切。
然后就是退役了,至于为什么退役也和这个有关系,我要回去好好补补文化课了,现在还剩下47天就中考了,即使自己心态爆炸也要好好努力是吧,在这剩下的日子里,我想实现的当初的诺言,即使,有的诺言已经不可能实现了,但是总比一场空好吧。
于是,我按着承诺,退役回去学习文化课,去接受这一切,我希望,这次退役以后,未来我可以更加努力,更加珍惜时间吧。 ......  查看更多

[GDOI2018]为了不能实现的诺言

Day -1

作为东道主的中山一中,我第一次觉得原来东道主学校要做则么多事情啊!就在我愉快的打着代(颓)码(费)时,被教练叫走去当苦力,清理比赛的机房,即使这并不是我们使用的机子,更不是我们训练的机房,但是天命难违,也只要去做。
附上几张搞清洁的图
[GDOI2018]为了不能实现的诺言-1 ......  查看更多

[Usaco2011 Jan]道路和航线

[Usaco2011 Jan]道路和航线
这题一眼看过去就是最短路呢,但是呢?好像有负环,啧啧Dij用不了啦!好像点有点多,Floyd用不了啦,就只剩下spfa啦,但是spfa在极限数据下还是会T掉呢?怎么办,这里引入Spfa其中一个优化SLF优化。全称Small Label First 策略
设要加入的节点是y,队首元素为x,若d[y] \lt d[x],则将y插入队首,否则插入队尾。
其实只要一个优化就可以了,但是为了测试多一下,我就再加了一个优化LLL优化,全称Large Label Last 策略
这样的话我们就可以用上双头队列deque了。
其他的就是普通跑一下spfa就好。
只有SLF优化的 ......  查看更多

[AHOI2005]病毒检测

[AHOI2005]病毒检测
这个可以给出O(n^3)复杂度的代码,肯定就是O(n^3)啦,没有质疑的空间了。那么有什么代码开一跑怎么快呢,DP,DFS,贪心。
这里的话我们就用DP解一下这题
F[i][j]代表母串匹配i个,字串匹配到j个时可不可以匹配到。
然后更新一下,注意*要特判一下,因为他可以匹配很多个字符。 ......  查看更多

后缀排序

后缀排序
这题题目已经告诉你要求些什么了,然后该做什么,当然是求后缀啦,求所有后缀的排名,当然后缀数组啊。这题仅供复习后缀数组的。对于后缀数组,就是先排序再处理,然后每次排一个关键字重复处理直到所有关键字被排序到。 ......  查看更多