选课

选课
选课这一题我们很容易发现没有根节点,因为可能不止一个不用前置课程的节点,然后我们因为多个课程可能有一个相同的前置课程,所以我们其一可以通过森林转二叉树进行就是左孩子右兄弟,或者采用背包型树形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]为了不能实现的诺言

Day -1

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

[技巧]对拍与数据制作

对拍到底是什么东西?
就是用你自己的程序和正确的暴力或者算法比较数据,来判断自己的数据是否出错。
平时自己感觉上Accept的代码去到OnlineJudge上就无辜RE,WA呢,大的数据调不出来,考场上急需验证自己的程序有没有写错,自己出来题目想测试一下标程有没有出错。这样子就用得上对拍了!我们可以制作小的数据,用暴力和正解比较,查出错误,尽管小数据出错几率很小,但是对拍程序可以一直重复运行,帮我们比较,直到查出错误。
那么需要对拍的我们需要准备多少东西呢?其实真的不多
1. 你需要对拍的程序
2. 自己打的暴力或找到的正解
3. 一个数据制作器
4. 一个对拍程序 ......  查看更多

[HAOI2014]贴海报

[HAOI2014]贴海报
就是简单的线段树加上离散化解决就好,但是也可以用分块做,留个坑
就是先离散化一下,然后用线段树维护区间值,然后线段树维护相同值就好。

[HNOI2002]营业额统计

[HNOI2002]营业额统计
这题,其实就是伸展树裸题嘛。
就是找前驱后继,我们主要还是维护一颗伸展树,然后慢慢慢慢插点,然后找前驱后继就好了。
但是这里的前驱后继是可以相等的,所以我们要找x+1的前驱,x-1的后继,然后就好了呀。
留个坑用set其实好像也可以做,真的我很想试试但是懒。 ......  查看更多