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 ......  查看更多

Telephone Lines

Telephone Lines
简化一下题意,这题是在无向图上求出一条从1N的路径,使路径上第K+1大的边权尽量小。
这样的话我们可以发掘这题的金额是有二分性的,在合法的金额里面一定包含着最优金额,这样子我们就可以二分出最优金额进行求解,跑一下SPFA,金额大于mid的边边权为1,其他为0,最后判断一下d[ed]是否大于k就好,大于就是代表我现在金额不能完全修完前k条路径,然这题就解决了 ......  查看更多

「算进」[图论]最短路

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

兔子与兔子

兔子与兔子
这题的话很好解,先预处理一下再暴力求值。
记我们选取的DNA序列为S,根据我们刚才提到的字符串Hash算法,设F[l]表示前缀子串S[1 ~ i]的Hash值,有F=[F-1]*131+(S[i]-"a"+1)于是可以得到任一区间[l,r]Hash值为F|r]-F|l-1]*131^{r-l+1}。当两个区间的Hash值相同时,我们就认为对应的两个子串相等。整个算法的时间复杂度为O(|S|+Q)。 ......  查看更多

「算进」[基构]HASH

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

Snowflake Snow Snowflake

Snowflake Snow Snowflakes
这题的话就是明显可以用哈希表来做啦,对于两篇形状相同的雪花,那么他们的乘积也是一样的,但是又为了避免偶然,所以哈希函数的计算中增加了他们的和,Hash(x)=sum(x)+mul(x)这样就可以很好的做统计了。

 ......  查看更多