题目链接:

HDU 5812 Distance

题意分析:

给出一个空集合和三个操作。操作I向集合中插入元素X,操作D删除集合中的元素X,操作Q,查询集合中与X的最小距离最小是多少?
定义最小距离 d(x,y)d(x,y) 为从x变为y只通过乘或者除素数所需要的最少操作。例如:d(15,50)=3d(15, 50) = 3,因为 15/3×2×5=5015 / 3 \times 2 \times 5 = 50

解题思路:

  1. 求d函数第一反应就是把两个元素分解成质因数,然后去掉公共的部分,剩下的就不是公共部分,必须通过乘法和除法才能变为对方。所以有 d(x,y)=f(x/gcd(x,y))+f(y/gcd(x,y))d(x,y) = f(x / gcd(x,y)) + f(y / gcd(x, y)) 其中 f(x)f(x) 是该数的质因子个数。(看到式子感觉确实挺显然的,但比赛中去掉公共部分后就没怎么往这方面想)

  2. 考虑枚举x的约数,那么现在问题就在于如何快速的对整个集合中的可行元素求出 f(y/gcd(x,y))f(y / gcd(x, y)) 显然,此时只有集合中是约数倍数的数才需要被考虑(这样才能和x一样整除约数)。

  3. 尝试定义数组d[i],代表集合中以i为约数,能达到的最小f值。那么每加入一个集合中不存在的值X,我们就能将X进行约数分解,比如分解成了 X=y×zX = y \times z,那么就能这么更新:
    d[y] = min(d[y], f[z]); d[z] = min(d[z], f[y]);
    然而这样存在一个问题,当能得到最小值的那个元素被删除后,d[]数组的值就不知道该怎么更新了。也许可以记录次小值,那如果次小被删除呢?第三小?所以显然要转换下策略。

  4. 由于对于一个数x,他的质因数个数不超过20个(220=10485762^20 = 1048576),所以我们直接把所有可行值存下来,然后遍历二进制位,找到最小的那一位1所在位置,就是d[]数组对应的值了。所以我们d[]数组存放二进制即可。比如d[3] = 0000101010,那么最小的f值就是1了。

  5. 最后我们开个二维数组c[i][j]:记录约数i能得到的f值j出现的次,用它来维护d[]数组的更新即可(次数为0说明不存在了,要剔除)。

个人感受:

这场多校题感觉都好劲啊,那种细细读题解,然后恍然大悟的感觉,那道炉石的DP也是。不像有些场,看了题解一脸懵比。

具体代码链接:

传送门


广告时间

Java学习网站: how2j

VPS: VPS