IPSC 2011 - I - Inverting bits

43 阅读 0 评论 29 点赞

我是靠谱客的博主老迟到白昼，最近开发中收集的这篇文章主要介绍IPSC 2011 - I - Inverting bits，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

非常厉害的一道题。。。

题目大意：
扔给你一种新语言，这种语言只有26个变量（A-Z）（为什么？因为只有26个字母呀。。。），每个变量可以存8个二进制位，你所能进行的操作只有一些基本的位运算+赋值+输入输出。
$and R X$ 将 $Rtext{&}X$ 的值赋给 $R$
$or R X$ 将 $R|X$ 的值赋给 $R$
$not R$ 将 $text{~}R$ 的值赋给 $R$
$shl R C$ 将 $R<<C$ 的值赋给 $R$
$shr R C$ 将 $R>>C$ 的值赋给 $R$
$mov R X$ 将 $X$ 的值赋给 $R$
$get R$ 读入一个数，储存在 $R$ 中
$put R$ 输出R的值
一些注意：
1、位运算只有&,|,~,<<,>>（注意：没有异或！）
2、赋值的时候只能是变量与变量之间，没有常量

请你用此语言编写程序，完成下面两个子问题：
Easy : 读入正好7个非0即1的数，将读入的数取反输出
Hard : 读入正好19个非0即1的数，将读入的数取反输出

限制条件：
Subtask 1中，使用not最多1次，代码长度<=100行
Subtask 2中，使用not最多2次，代码长度<=300行

让我们先忽略一下代码长度，因为那似乎是防止打表用的。。。
Subtask 1比较简单，直接全读进来然后通过“左移+或”就可以全存到一个变量里边，取反一次，最后返回到每个变量里输出就可以了。

关键在于Subtask 2比较蛋疼，一个基本想法就是如果我们可以2次取反而做到取反3个变量就好了。但是。。。这可以做到吗？

（以下不区分变量与bool型变量，因为位运算”&,|”是逐位进行的）

一个关键在于我们肯定是需要求出来一些公共的量（跟A,B,C都有关），而通过这些量我们可以针对不同情况分别对A,B,C取反。

然后。。。我们发现。。。我们需要一些脑洞。。。（因为太自由所以看不出来突破点。。。）

那我们就来猜一猜咯。既然是要针对不同情况而我们的模式都能应付，我们就猜最后~A,~B,~C的表达式是由’|’连接而成的表达式！

既然如此1->0就比较难搞了，因为这些表达式必须同时为0才可以。但我们发现1意味着当前变量占用了整体上的一个1，如果我们能够求出来整体上1的个数，再结合判断一下除当前变量外的其它变量是否能覆盖整体上1的个数的话我们就可以做到一个正确的都没有了！

具体来讲，我们猜测表达式大概是长这个样子： $text{~}A=ex0|(ex1text{&}(B|C))|(ex2text{&}Btext{&}C)$ ，其中 $ex$ 表示当整体上1的个数等于后边跟的那个数的时候为1，否则为0。

这样的话注意到由于 $ex$ 的存在，表达式中只有最多一项为1，当A为0的时候该项为1，当A为1的时候由于通过其它变量不可能凑出1的个数所以该项为0。

好了，这样的话我们就有一个思路了，处理出来 $ex$ 不就好了吗？

而处理出来 $ex$ 算是比较简单的（感觉这道题难点在于不知道如何下手得出最后答案。。。），大概就是这样：
$ex3 = Atext{&}Btext{&}C$ — 正好3个为1
$mo1 = A|B|C$ — 不少于1个为1
$mo2 = (Atext{&}B)|(Btext{&}C)|(Ctext{&}A)$ — 不少于2个为1
$le1 = text{~} mo2$ — 不多于1个为1(第一次not)
$ex1 = le1text{&}mo1$ — 正好1个为1
$ex13 = ex1|ex3$ — 1个或3个为1
$ex02 = text{~} ex13$ — 0个或2个为1(第二次not)
$ex0 = ex02text{&}le1$ — 正好0个为1
$ex2 = ex02text{&}mo2$ — 正好2个为1

这样的话，这道题目就（在我们的猜测下）搞完了！

当然我们是不会满足于此的！我们来考虑一下取反 $n$ 个01变量最少需要多少取反操作！

我们只需要借鉴这道题目的思路，先求出来 $ex$ ，最后用 $ex$ 就可以弄出一个十分复杂的表达式了（从理论分析一下就好了，因为那个表达式似乎直接搞的话是 $n!$ 级别的。。。）

那么对于 $n$ 个变量我们怎么搞出来 $ex$ 呢？我们已经轻车熟路了，我们稍微推广一下就好了！

（我们可以把 $n$ 扩展成2的若干次幂，因为我们多取反几位是没有关系的对吧）

（关于理解上的问题：我个人认为想成一个数轴去理解是比较好的）

通过暴力枚举我们可以先得出 $mo$ 系列表示至少 $x$ 个为1（当然对于最高位那个全 $text{&}$ 起来的东西 $mo[n]$ 其实就是 $ex[n]$ 对吧）

设 $mid=n/2$ ，我们把 $mo[mid+1]$ 取反得到 $le[mid]$ 表示不多于 $mid$ 个为1，通过 $le[mid]text{&}mo[mid]$ 我们就得出了 $ex[mid]$

这时候我们惊奇的发现问题被分成了两个与原问题相同的子问题！也就是说对于小区间 $[1,mid],[mid+1,n]$ ，这两部分我们都是得到了完整的 $mo$ 数组，并且对于最后一位我们得到了它的 $ex[n]$ 。

而且我们还得出了一个变量表示完整地覆盖整个区间（也就是1的个数是否在这个区间中，对于大区间来说就是 $mo[1]$ ，对于左小区间来说就是 $le[mid]$ ，对于右小区间来说就是 $mo[mid+1]$ ），而这个变量是非常有用的，通过这个变量以及 $text{&}$ 操作我们就可以限制1只在当前区间而不会去影响其它区间（如果不这样的话我们每次都会得到一个后缀或者前缀，这是会跨区间影响的！），所以说区间之间就不会再互相影响了！注意到这样的另外一个好处就是我们把每一层要取反的东西同时放到一个变量里边取反一次就可以啦！而一共有 $log_2(n)$ 层，所以对于 $n$ 个变量，我们只需要 $lceil log_2(n)rceil$ 次取反操作！