ACMer程序员智力拾遗

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

浏览网页偶得，遂记录下来，每天进步一点点……

博客园真是个不错的平台，今天我让师姐也注册了……

学会分享吧，孩子们……

一、编程中无穷大量的设置

如果问题中各数据的范围明确，那么无穷大的设定不是问题，在不明确的情况下，很多程序员都取0x7fffffff作为无穷大，因为这是32-bit int的最大值。如果这个无穷大只用于一般的比较（比如求最小值时min变量的初值），那么0x7fffffff确实是一个完美的选择，但是在更多的情况下，0x7fffffff并不是一个好的选择。

很多时候我们并不只是单纯拿无穷大来作比较，而是会运算后再做比较，例如在大部分最短路径算法中都会使用的松弛操作：if (d[u]+w[u][v]<d[v]) d[v]=d[u]+w[u][v]; 我们知道如果u,v之间没有边，那么w[u][v]=INF，如果我们的INF取0x7fffffff，那么d[u]+w[u][v]会溢出而变成负数，我们的松弛操作便出错了，更一般的说，0x7fffffff不能满足“无穷大加一个有穷的数依然是无穷大”，它变成了一个很小的负数。
除了要满足加上一个常数依然是无穷大之外，我们的常量还应该满足“无穷大加无穷大依然是无穷大”，至少两个无穷大相加不应该出现灾难性的错误，这一点上0x7fffffff依然不能满足我们。

所以我们需要一个更好的家伙来顶替0x7fffffff，最严谨的办法当然是对无穷大进行特别处理而不是找一个很大很大的常量来代替它（或者说模拟它），但是这样会让我们的编程过程变得很麻烦。在我读过的代码中，最精巧的无穷大常量取值是0x3f3f3f3f，我不知道是谁最先开始使用这个精妙的常量来做无穷大，不过我的确以前见到过南阳理工的同学用过，当时没注意，今天再次看到，于是我自己也尝试了一下，发现非常好用，而当我对这个常量做更深入的分析时，就发现它真的是非常精巧了。

0x3f3f3f3f的十进制是1061109567，也就是10^9级别的（和0x7fffffff一个数量级），而一般场合下的数据都是小于10^9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。另一方面，由于一般的数据都不会大于10^9，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”），事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。
最后，0x3f3f3f3f还能给我们带来一个意想不到的额外好处：如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))这样的代码来实现（方便而高效），但是当我们想将某个数组全部赋值为无穷大时（例如解决图论问题时邻接矩阵的初始化），就不能使用memset函数而得自己写循环了（写这些不重要的代码真的很痛苦），我们知道这是因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0，现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需memset(a,0x3f,sizeof(a))。所以在通常的场合下，0x3f3f3f3f真的是一个非常棒的选择。

二、全排列被8整除

给定一个非负整数，问能否重排它的全部数字，使得重排后的数能被8整除。输入格式：多组数据，每组数据是一个非负整数。非负整数的位数不超过10000位。输出格式每组数据输出一行,YES或者NO，表示能否重排它的全部数字得到能被8整除的数。注意：重排可以让0开头。

全排序方法在我之后审题中被抛弃了，因为这道题不能够用全排序，里面有个条件很苛刻。全排序方法在我之后审题中被抛弃了，因为这道题不能够用全排序，里面有个条件很苛刻。其实，这道题使用归纳法比较好，为什么？题目有提示非负整数的位数不超过10000位，这意味着什么呢？非负整数的长度可能达到9999位，如果这么大的数使用全排序，估计计算机要死了，更何况我家自用开发机是8年前的老古董，想的出这种馊主意，它肯定受不了了。所以要借助归纳法，为什么可以用归纳法？呵呵，我猜的，别笑，我说得是实话，我猜测它可以使用归纳法，那么就得找出它遵循什么规律了，下面开始做一些假设过程：