属于CYY自己的世界

想必许多使用gnome桌面环境的用户都玩过一个自带游戏，那就是Lights Off，中文名叫关灯。 在这个游戏中，界面由2种状态的矩阵组成，用方格的亮与暗代表灯的开与关，当鼠标点击一个方块时，与它有公共边的方块和这个方块本身都会改变状态，由开变关或由关变开，相当于二进制中的异或运算。 那么，这个问题如何编程解决呢？我先从一年前的我什么算法都不会只会打搜索是如何解决这道题的。 首先，我们先确定一个规则，因为一个方块改变2次之后，等于没有进行任何一次改变，所以，我们可以肯定的是，一个方块最多改变一次。 所以，我们只要枚举每个方块被点击与没有被点击两种情况进行枚举，时间复杂度是O(2^(h*w))，h、w分别为矩阵的长宽。 显然，这个时间复杂度是不可接受的。我相信大多数人的智商，解决一个6*6的方格都比用这种方法等待计算机算快得多吧。 然后我们还可以用迭代加深搜索进行优化，从每次枚举1个方格，到每次枚举两个方格，再到每次枚举三个方格，这样的时间复杂度是O(玄学)。但一旦这个关卡所需的最少步数太多，也就无法在短时间内找到答案。 此外，我们可以使用广度优先搜索来取代迭代加深搜索，可以优化时间常数为迭代加深搜索的1/2，但有一个严重的后果，如果你的电脑没有足够的内存，根本无法存储如此多的状态数。我曾经写一个9*9的BFS就把我的16G内存给爆了。 那么，我们还有什么办法呢？剪枝？等待量子计算机帮助我们实现？ 实际上，这是一个线性代数的问题。 我们可以采用高斯消元法来解这个异或方程。 对于每个方格的点击，有0和1两种情况，每个方格点击会对自己和周围的方格进行异或(xor)1计算。 那么，对于一个2*2的方格，我们期望从全0变成全1，可以列以下方程，对于方格中的格子，我们采用p(x,y)来表示。对于每个格子是否点击的状态，我们采用b(x,y)来表示。 其中，0为初始状态。 p(1,1)=1=0 xor b(1,1)…

这两天写程序时遇到了许多clang和gcc规范的问题，明明自己Mac电脑上大样例都能过的程序交到OJ上一片WA和RE，百思不得其解怀疑是编译器问题，于是ssh到一台装了gcc的Linux机器上跑一下，果然结果和本地不一样。 函数传参的调用顺序 对于OIer而言，常见的一种优化程序常数的方法就是读入优化。用getchar手写输入，用putchar来取代手写输出。而许多人喜欢一种写法，就是写一个read函数，返回int类型，这样我们可以在调用函数的时候直接调用read，少写几行定义变量，然而，gcc和clang用这种方法时却存在差异。 在clang中，传递的参数默认从左边向右边调用，输入123 456，传给函数的便是a=123,b=456。而在gcc中，却有不同。这是gcc中运行同样代码的结果，可以看到，传递的参数从右边向左边调用。 位运算的异常 位运算也是一种优化程序和让程序更易读的方式，对于OIer而言，在状态压缩和二叉树节点编号中常用。 然而在clang中也有许多这样的坑。比如定义一个unsigned int a = 0xffffffff。 显而易见，它的二进制是全1。那么右移动32位，由于i>>k会被处理为i>>(k%sizeof(i)*8)，所以相当于i>>0。 然而，gcc是这样，clang却不是。 而clang在处理位运算的时候似乎使用了一种不同于gcc的处理方式，所以我们还是手动%一下再操作吧。  

什么是线段树？ 线段树，是一种二叉搜索树。它可以把一个从1…N的数组可以用二叉树划分为许多区间，这个区间成为二叉树的节点，使用线段树可以大大加快进行区间操作时的速度，同时，区间的最大值、最小值等问题也可以方便地使用线段树求出。 这里借用一下百度百科中的线段树图片来简要说明一下。 其中，[1,10]是我们的操作区间范围，这个节点作为根节点。 其下有两个子节点，一个是[1,5]一个是[6,10]。 对于每个节点[x,y]，当x !=y 时其子节点分别为[x,(x+y)\2]与[(x+y)\2+1,y] 其中，\代表整除 当x == y时，没有子节点，即叶节点。 线段树能做什么？ 看到这里，相信很多读者会问，在各个区间的节点上需要保存什么呢？ 其实我相信聪明的读者已经看出来了，学过RMQ问题的读者应该已经想到了线段树是一个实现RMQ相比于ST算法占用内存空间更小的算法。实际上正是，例如POJ 2823，用st算法是过不了的。因此，我们还可以在线段树节点上存储区间的最大值、最小值、区间和、区间非0节点数量、区间0节点数量，等等等等。这样，对于一个区间的查询，只需要O(log n)的时间复杂度，相比于O(y-x)，快了许多，因而，线段树非常适合解决区间操作的各类问题。 如何建树？…

gdb是一个十分方便的调试工具，不仅仅是对开发者，更是信息学竞赛者的一大利器，使用它在竞赛中往往可以获得更高的调试效率，我们可以轻松地查看到代码执行到哪一行时出现了问题，相比于IDE可以更加快速地输出各个变量的数值来分析程序所存在的问题。 然而许多人却因为不会在windows中配置gdb而望而却步，更有甚者在同时安装了fpc和gcc的电脑上使用gdb遇到了种种问题。这里来说明一下解决方法。 首先，在Windows系统中，对于命令行可以在任意目录直接执行的命令，取决于系统或用户环境变量中path的设置。通俗来说，系统在任意目录下只能直接执行在名为path的环境变量中的文件夹下的可执行程序。 然而，对于大多数OIer而言，所使用的Dev-C++在安装时并不会在环境变量中加上MinGW的安装目录，因此许多人对于许多竞赛书中所讲的gdb的使用一直没有去亲自尝试过。因此，我们就要把MinGW安装目录下的bin文件夹加入到path环境变量中。 首先，在Dev-C++中找到Compiler Options 之后，找到MinGW的安装目录 将这个目录加入到系统的环境变量中 对于XP系统，在“我的电脑”右键菜单的属性中就可以进入这个界面。而对于Vista-10这几个版本的Windows系统中，这个界面则是在系统属性的高级系统设置中。 我们找到用户或者系统的Path变量，然后加入刚才在Dev-C++中所见到的路径，放置于变量值的最前面，然后加上; 特别注意，一定要加上; 比如原来的环境变量是 %SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem;%SYSTEMROOT%\System32\WindowsPowerShell\v1.0\; 此时应该更改为 C:\Program Files\Dev-Cpp\MinGW32\bin;%SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem;%SYSTEMROOT%\System32\WindowsPowerShell\v1.0\; 之后，再重新打开命令提示符，此时g++、gcc、gdb就可以使用了。这里要提到一点，为什么不把MinGW的目录加在最后。这是考虑到许多人同时有安装fpc，而fpc安装时会加入MinGW的gdb，由于大多数情况下该版本较旧所以可能遇到下图中的情况。 因此，这里把minGW的安装目录放在环境变量的最前面，就是为了让它拥有最高的优先级。诚然，把它放在fpc的目录前面再加上;也有同样的效果。实际上，为了防止改坏环境变量影响系统的正常运行，把minGW放在最后面是比较保守的选择。…