Accumulation Degree

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

选课

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

「算进」[图论]最短路

图论是信息竞赛的一个极其重要的专题,那么,就先从图论里面最简单的最短路开始讲起。
对于一张有向图,我们一般采用的是邻接矩阵和邻接表两种储存路径的方式。对于一张无向图,我们可以把无向边看作两条方向相反的有向边,然后我们就可以把有向边和无向边加在一起储存了。
所以对于我们讨论图的最短路问题时,我们都以有向图为例设图G=(V,E)V是点集,E是边集。(x,y)代表从xy有一条边,他的边权为w(x,y),设n=|V|,m=|E|,邻接矩阵的大小为n^2
那么我们矩阵的时空复杂度为O(n^2)
假如我们用邻接表代码时,我们每一个点只记录一个边,每个边之后再记录一个边,就是类似HASH里面的链表一样。
那么邻接表的复杂度就会比邻接矩阵少的多,一般为O(n+m)
最短路有很多种算法如单多源最短路等。
那么就一个一个分析一下各种最短路的区别。 ......  查看更多

「算进」[基构]HASH

首先,「算进」是什么?
就是《算法竞赛进阶》,大神写的书,一个蒟蒻怎么能不好好磕一下呢,于是就有了这第一篇文章。
[基构]是什么?
就是基础数据结构的意思呢,基础不扎实就要好好学基构。
从我最不好的地方开始学习,来Hash把! ......  查看更多

[SHOI2015]自动刷题机

[SHOI2015]自动刷题机
一题明显的二分,只要两遍二分分别搞一下最大值何最小值就好。

[PA2014]Iloczyn

[PA2014]Iloczyn
因为斐波拉契数列到了50已经很大了,所以预处理50然后离线处理就好。

[PA2014]Lustra

[PA2014]Lustra
就是随便排序一下然后就取个最大值比较一下就好了呀。