Menu Sidebar
Menu

December 2020

Burnside和Polya

Burnside: https://en.wikipedia.org/wiki/Burnside%27s_lemma Polya: https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Polya是Burnside一种特殊推定, 例题就几个, 都是染色类问题. 个人觉得难点在于如何准确归纳和构建置换.

Poj 3270 Cow Sorting

给一个数组,求通过两两交换后排序这个数组, 交换有代价, 代价是交换的两个元素之和, 求排序的最小代价. 这个题我第一眼看是dp的问题, 但是很难考虑边界的元素交换, 而且很容易超时. 后来看了看答案, 原来是群论的置换群问题, 后来补了补. 发现也不是置换群, 只是单纯的置换中的轮换的概念, 关键是从哪个角度看待问题的本质(排序). 首先看置换群的概念在这里的应用, 拿例题举例: 由例子可以得知, 上面的例子最好的解法是: 取最小的数字作为媒介与其他数字做交换, 得到的成本是最小的. 然而这并不是唯一的最优解, 考虑一下的例子: 这个例子中, 可以把一个数组写成两个三阶置换, 那么对与[1,3,2],交换最小的成本并不是1与其他两个数的交换, 而是把0(全数组中最小的数字)先和1(当前数组最小数字)交换, 然后再次交换.这个最优解我没有想到 下面是如何计算最优解一: 最优解二: 答案在两个最优解中选最小的成本. 最后还有个技巧, 就是如何找到一个数组的index在排序后的对应index, 这里要用counting sort, 在counting sort中取count和的时候, 可以找到index的位置.

Make Sum Divisible by P

给一个数组nums和一个p, 求删去最小的子数组后的数字和可以整除p. let s = sum of nums, r = s mod p -> r = (s + p) mod p 因为我们知道presum可以用两个指针表示其中间隔的和. let (i, j) = indexs in presum where 0 <=i <= j <= presum.length. since r = (s + p) mod p, then r = (pre[j] – pre[i] + p) mod p 因为我们知道2sum中, […]

Maximum Height by Stacking Cuboids

给一些砖块的长宽高, 可以旋转, 问怎么摆放可以有最高的高度, 求高度. 这个题虽然可以旋转, 但是其实因为限制: 必须完全小于长宽高的砖块才能放到另一个砖块上边. 所以没有旋转没有任何意义. 通过排序, 找到最长的, 然后再通过排序找到最大的. 即可做dp. 设dp[i]是包含砖块i作为可用砖块的最佳规划方案. 那么dp[i] = max{dp[j], where j < i and (i,j) meet requirements} 这个是bottom-up.

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.