HNOI2012 nand解题报告-by txh.pdfVIP

NAND 解题报告 长沙市雅礼中学 唐翔昊 【引言】 NAND 是HNOI2012 Day1 第二题。本题描述简洁、题意清晰， 考察了选手对逻辑运算的运用，以及从题给条件中发掘特殊性质 的能力。 【题目描述】 NAND （与非）是一种二元逻辑运算，其运算结果为真当且仅当 两个输入的布尔值不全为真。NAND 运算的真值表如下 （1 表示 真，0 表示假）： A B A NAND B 0 0 1 0 1 1 1 0 1 1 1 0 而两个非负整数的NAND 是指将它们表示成二进制数，再在对应 的二进制位进行NAND 运算。由于两个二进制数的长度可能不等， 因此一般约定一个最高位K，使得两个数的二进制表示都不 超过K 位，不足K 位的在高位补零。 容易验证，NAND 运算满足交换律但不满足结合律，故计算若干 个数的NAND 时，应先计算括号内的，无括号时从左往右计算。 给定N 个非负整数A1,A2AN 和约定位数K，利用NAND 运算与括号，每个数可以使用任意次，请你求出范围[L,R]内可 以被计算出的数有多少个。 【输入格式】 输入文件第一行是用空格隔开的四个正整数 N，K，L 和 R， 接下来的一行是N 个非负整数A1, A2 AN，其含义如上 所述。 30%的数据满足 k≤10，70%的数据满足 k≤30，100%的数据 满足K≤60 且N≤1000, 0=Ai=2^k-1, 1=L=R=10^18。 Hint：事实上数据中有L=0 的点。。。 【输出格式】 仅包含一个整数，表示[L，R]内可以被计算出的数的个数。 【输入样例】 3 3 1 4 3 4 5 【输出样例】 4 【算法分析】 算法一： 根据题意，我们可以使用广搜来求得答案。算法十分简单， 无需赘述，但是时间复杂度较高。 k 时间复杂度：O(2 ) 期望得分：30 分 算法二： 为了得到更加高效的算法，我们进一步考察算法一。算法一 为何低效？思考程序运行过程就可以得出，主要原因有如下几个： 1.我们只需要知道可以计算出多少个数，而算法一同时计 算出了所有数，这就做了许多无用功。 2.本题是一个计数问题，而算法一没有使用计数方法来解 决，没有充分利用题目性质。 既然如此，为了得到更加优秀的算法，我们就需要进一步对 题目进行思考。 手算几组稍大的数据即可发现：对某几位，若A 中每个数这 几位都相同，那么所能得出的结果中，这几位也都相同，这样， 我们就为能计算出的数找到了一个必要条件。 我们希望这也是一个充分条件，因为这样原问题就可以转化 为对[l,r]中满足这个限制条件的数的计数，问题就得以简化。 那么究竟是否如此呢？让我们来进行一些分析。 要让上述条件成为充分条件，就需要证明所有满足这个条件 的数都可以通过NAND 运算得出。 a NAND b，实际上相当于~(ab)，也就是说我们现在拥有 两种基本逻辑运算：~和。显然，我们就可以利用NAND 运算来 形成各种逻辑运算。这样，运算就有了较大的任意性。 not a NAND a and not (a NAND b) or not ( (not a) and (not b) ) xor (a or b) and ( not (a and b) ) 这样，很简单就可以构造出任意真值表的二元逻辑