一场没吃早饭然后爆零的考试题…第一题…
题目大意
给你N堆石子, 第i堆石子有a
i
个, 你后手和别人玩nim游戏, 你想要取走石子或加入石子来作弊以保证你拥有必胜策略, 但是加入或取走每颗石子需要付出额外代价, 你可以取完一整堆石子但是不能加入新的石子堆, 问最小代价。
N≤15, a
i
≤1e9
解题报告
简化版题意大约就是问给你N个数, 对某个数+1/-1算一次操作, 然后要这N个数异或和为0, 最少进行多少操作。
首先一个很naive的想法就是设状态dp[i][s]表示前i个数异或和为s的最少操作数, 转移大力a i 平方, 可以拿到20分(本垃圾只能想到这个部分分…)
进阶操作, 设答案数列为b, 那么在二进制下从高位向低位确定每一个b的每一位, 设状态dp[i][s][j][0/1]表示当前考虑到第i位, 三进制数s表示当前a x 的第30到第i+1位小于/等于/大于b x , 目前正在考虑第j个数, 这一位的异或和是0/1。
易得转移是O(1)常数, 那么复杂度为[latex]O(N^3\cdot 3^N)[/latex]。
显然这样的复杂度依然无法通过, 考虑优化s的底数。
假设当前确定到第i低位, 对于数字bj, 如果对于某最小的k>i让bj的第k位不等于aj的第k位, 设这两位分别为p和q。
1.若p<q, 我们认为bj的第i位取1是缺省值。
2.若p>q, 我们认为bj的第i位取0是缺省值。
那么有一个显然的性质如下:
第i低位的所有数中至多只有一个数选取非缺省值, 不然肯定不优, 并且如果选取非缺省值, 那么将会支付一个固定的代价\( 2^i \)。
这样, 设计状态dp[i][s][j][0/1]表示从高到低考虑到二进制第i位, 当前b x ≠a x 的情况为二进制数s, 考虑到第j个数, 当前位是否为0, 所有b x ≠a x 的数字缺省值当前位异或和。
转移很显然, 也是常数级别, 那么总复杂度等于状态数, 为[latex]O(N^3\cdot 2^N)[/latex]
这场考试我傻乎乎的一道题都没肛出来…它教会了我一定要吃早饭…无论如何…
Join the discussion