[20191009机房测试] 这是一道好题

做了自然就会知道题面
毕竟来这里的途径是有限的

这是图论专题里的一道题,
可能后几届的学弟学妹还会考,所以不该写题解的
但是做完后发现这真的是一道好题,
(再加上被hfu强迫加强数据和重写题解)
所以我就跑博客上来写题解了:

首先,对于要求的式子,我们假设从里面选出了 (x) 个相同或不相同的溶液

[sum_{i=1}^{x} a_i=n*i ]

这个式子让我们很不爽,所以大力化简:

[sum_{i=1}^{x} (a_i-n)=0 ]

这个式子是什么意思呢?
其实就是对于每一个给出的浓度,把它减去(n)
再从这些处理过的数字中选出数字,使它们的和为0

在数据加强之前,这题如果判断数据的特性,是可以骗90甚至100分的
然而既然已经让我加强了嘛……咳咳

来思考一下暴力怎么求出这个玩意儿:
首先建-1000~1000,共2001个节点,表示数字可能的和
(对于负下标,使用加基数的方法处理)
然后对于可能有的数字,我们连一条边权为1的边,代表一次操作

比较乱,大概看看
很明显的,从0到0的最短路为3,所以答案为3

Wait!
这样会超时的啊!
我们需要大力优化

1.染色:如果一个点没有被染色,把它入栈,每次连下一条边的时候已经被染色的就不用入栈了

然后就完了吗?
显然不是
最短路太慢了!我们直接不连边,不搞最短路!

2.dp:去掉邻接表,一个点储存它最少到达次数,如果连过来的点的这个值+1>=本来的次数,不更新

它的本质还是最短路,但是去除了连边和最短路操作,蜕变为了dp!

3.压缩点数

我之前说了,开2001个点,但凭什么这样就是正确的呢?
对于最坏情况,用500和-499凑出498,每次右跳500,左跳-499,连续498次即可
上限为1000,所以只需要1000*2+1个点

经过一系列优化,其实现在这道题已经变了一个模型了
拂去表面的干扰,发现此题已经可以使用拓扑/背包求解

由于每个点最多被扩展一次,去重后酒的个数为m
那么时间复杂度 (Theta{(nm)})

原文地址:https://www.cnblogs.com/tqr06/p/11644137.html