属于CYY自己的世界

题意： 给一个纸条，问是否可以折成一个立方体，纸条用一个h*w的矩阵上的#来描述，h<=100，w<=100，T<=30（数据组数）。 分析： 当时多校赛场上读完题就想到了可以枚举点然后BFS填充格子，只要有一个起点能满足不重复地填充给出图形上的所有#号点，且立方体被填满，就输出yes。由于h<=100,w<=100，所以最大的正方体的边长为100/4=25，因此我们枚举点25*25，check使用25*25*6的复杂度可以完成。 不过因为后来跟榜先搞别的题去了这题就先放一边，结果我们队后来因为开车那题自闭到最后. 这题的难点在于处理BFS时转向的问题。 我们可以先建立一个三维坐标，第一维是所属的面，第二维和第三维是这个坐标在这个面中的位置。如下图所示，中间的数字是面坐标的编号。 然后对于编号1的面，向周围4个面走的时候都是直接走即可，不需要进行坐标变换。 而对于需要进行坐标变换的情况，比如从0这个面一直向上走，走到4，需要将x和y坐标对调，然后逆时针转90°，再继续填充这个格子。 对于6个面，向4个方向走只有6*4=24种情况，所以直接把这24种情况x和y和方向的变化写出来（可以用if或者switch），然后直接做就完了。 然后就直接上一段很丑的代码吧。（为什么这么丑还要写博客呢，因为这算是在多校期间补的题中AC的人最少的一道题吧） 代码： #include <bits/stdc++.h> using namespace std; int…

众所周知，ST表是一种离线解决RMQ(区间最值)问题的方法。 可以在O(n \log {n} ) 的时间内进行预处理，然后在O(1)时间内查询到结果。 复习一维 我们先来复习一下，一维st表的预处理和查询过程。 对于预处理，我们先定义一个名为st的二维数组，其中st[i][j]表示以i为起点，从起点开始（含起点）往后2^j个元素的最值。 满足i+2^j-1不越界 因为2^0 = 1 ，因此st[i][0]=a[i] 然后我们用2个for循环去打表就行了 接着是查询，这里我画了个图来解释。 其中橙色的线表示两个区间。 一维代码…

有先决条件的背包问题通常是树形DP的一个典型问题。 常见的例题有选课（洛谷P2014、Vijos 1180） 这类问题的定义是，在背包中，我们需要先选某个物品，才能选择这个物品的子物品。最后求出在花费满足限制的情况下，实现最大的价值。 实际生活中的例子有选课、买家具等。 朴素的做法就是用邻接表将树存下来，然后用DFS去深度优先遍历这棵树。 DP方程如下 f[father][j] = max(f[father][j],f[father][j–k]+f[child][k–cost[child]]+weight[child]); 其中father为当前节点，child为这个节点的一个子节点。 不难看出这个需要两重循环，我们对于f[father][j]这个状态需要去枚举k一次次取max来求解最优问题。 相当于，我们需要枚举，对于这个物品我们需要使用它和它的子物品多少价值。 这样做出来的时间复杂度就是O(n*(m^2) ) 尽管大部分题目对于这样的时间复杂度是会放水的。   但是后来，有一次我想用树形DP去解决NOIP2006…

想必许多使用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放在最后面是比较保守的选择。…

背包问题是信息学奥赛中最经常考的动态规划形式，而01背包又是背包问题的基础。除此之外，背包问题还分为完全背包、多重背包等。 01背包定义如下： 对于1个容积为v的背包和n个物品，这些物品分别有自己的体积Vi，和价值Pi，我们需要有一种算法在背包可以容纳的情况下使装入的物品价值最大。此时n个物品不一定全部放入，背包也不一定装满。 与完全背包不同的是，01背包中是n个物品，而完全背包是n种物品，每种物品可多次放入。 这样的问题为什么不用搜索解决呢？ 显然，如果搜索可以完美解决这样的问题，我们自然也就不需要用更好的算法来解决问题了。 通过分析问题，我们可知，对于每个物体都有放入背包和不放入背包两种情况，如果我们使用传统的搜索算法解决这个问题，那么时间复杂度为O(2^n)，数据大了难免超时。 何为动态规划： 动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。继续分析，我们可以通过递推的方式解决该问题，从问题分析出递推式的方法，便是动态规划。 如何用动态规划高效地解决01背包问题？ 这是一个01背包常见的递推式 f[i][j]=max(f[i-1][j],f[i-1][j-Vi]+Pi) 其中，i从1到n，j从1到v，条件为j>=Vi 许多人与我一样，在第一次看到这个递推式的时候都十分困惑，全然不知它的含义。 实际上，f[i][j]就是我们在写动态规划程序时所需要开的一个数组，f[i][j]表示放入前i个物品（包含i，但这前i个物品不一定完全放入），背包容积为j时，背包内物品价值和的最大值。 这样，f[i-1][j]显然就是不考虑放入编号为i的物品的情况下背包内物品的最大价值和，而f[i-1][j-Vi]+Pi，便是在只考虑放入前i-1号物品且背包容积为j-Vi时，背包内物品的最大价值和，再放入编号为i的物品，因此加上Pi，也就得到了f[i][j]，即放入前i个物品，背包容积为j时背包内物品的价值的最大值。 对于这个算法，在C语言中通常采用两层for循环解决，以下为C++写法。大家可以根据题目自己修改以符合题目要求。 该方法的时间复杂度为O(n*v)…