最终得对抗自己

[考试题] A

一场没吃早饭然后爆零的考试题…第一题…

题目大意

给你N堆石子, 第i堆石子有ai个, 你后手和别人玩nim游戏, 你想要取走石子或加入石子来作弊以保证你拥有必胜策略, 但是加入或取走每颗石子需要付出额外代价, 你可以取完一整堆石子但是不能加入新的石子堆, 问最小代价。
N≤15, ai≤1e9

解题报告

简化版题意大约就是问给你N个数, 对某个数+1/-1算一次操作, 然后要这N个数异或和为0, 最少进行多少操作。

首先一个很naive的想法就是设状态dp[i][s]表示前i个数异或和为s的最少操作数, 转移大力ai平方, 可以拿到20分(本垃圾只能想到这个部分分…)

进阶操作, 设答案数列为b, 那么在二进制下从高位向低位确定每一个b的每一位, 设状态dp[i][s][j][0/1]表示当前考虑到第i位, 三进制数s表示当前ax的第30到第i+1位小于/等于/大于bx, 目前正在考虑第j个数, 这一位的异或和是0/1。

易得转移是O(1)常数, 那么复杂度为\(O(N^3\cdot 3^N)\)。

显然这样的复杂度依然无法通过, 考虑优化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位, 当前bx≠ax的情况为二进制数s, 考虑到第j个数, 当前位是否为0, 所有bx≠ax的数字缺省值当前位异或和。

转移很显然, 也是常数级别, 那么总复杂度等于状态数, 为\(O(N^3\cdot 2^N)\)

这场考试我傻乎乎的一道题都没肛出来…它教会了我一定要吃早饭…无论如何…

   

加入讨论

电子邮件地址不会被公开。 必填项已用*标注

关于本站

这是Hineven的博客!
主要保存蒟蒻的解题报告(笔记)
还有发布分享一些奇怪的东西

你可以通过上面的↑友情链接
访问Socialists的其他博客。

The Socialists!

我们的Site:socialists.studio
访问量:

AmazingCounters.com