题意： 给一个纸条，问是否可以折成一个立方体，纸条用一个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表学习笔记
众所周知，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循环去打表就行了 接着是查询，这里我画了个图来解释。 其中橙色的线表示两个区间。 一维代码…
我在OI中辗转的这千百天
今天是2017年12月16日，距离NOIP2017结束已经过去一个多月了。我想写一篇文章来留念一下我在OI中辗转的这千百天。 0x01 初识OI 我最初知道NOI系列赛事是在初一的时候。 小学到初中有在跟着思明区青少年宫的老师学电脑机器人，当时在班上有个比我大岁的朋友，他刚上高中，知道了有NOIP这个比赛，后来他拉着我学Pascal入坑了。 那段时间他带我入门了Pascal，水平大概达到了会写校门外的树的程度，后来由于我的时间关系和他的时间关系没有继续往下学。当时由于周末还拿出一天上电脑机器人的课，所以也没有太多的闲暇时间。 后来到了NOIP报名的时候，我问了我们班主任能不能我们学校找个信息老师挂名去参加NOIP，之后便没有下文了。 其实现在想来，当时的水平甚至连通过普及组初赛都不够的。那个时候我的水平仅仅只是会用Pascal写入门难度的程序。并且那个时候的我也不了解算法和数据结构，对于计算机的学习处在一个以自己玩为住的状态。当时搞机器人，搞单片机。搞Web开发，搞C#、VB、易语言写点小程序。记得小学六年级的时候写了个控制飞机躲避障碍的游戏和弹球游戏就觉得自己很厉害了，现在自己看来这些东西真是小儿科。正如我当时写的弹球游戏需要考虑的圆以一定的速度和角度与直线碰撞的问题，我根本不会判，当时易语言有个组件叫画板，基于DirectPlay，判断物体碰撞只要设置速度和角度物体就会在屏幕上移动，碰撞的时候会调用一个事件，根本不需要像我写OI的计算几何题目一样去考虑各种东西，所以我当时根本没有想过要学习算法和数据结构，不明白它甚至可以帮忙升学，初中阶段也就把这个事情搁置了。 0x02 高一的NOIP2015 由于一直对计算机感兴趣。初中的时候希望中考能考上一个OI强校成为了一个目标。然而不幸的是，中考的时候考的很差，高中来到了厦门集美中学。 高中的第一节信息课，信息老师就在问我们全班同学有没有人知道NOIP这个比赛，我记得当时全班就我一个人举了手，然后和老师交换了联系方式，周日开始在学校上课。 当时我们学校OI班上大概有20个人，招人方式几乎只是问问谁感兴趣谁进来。其中还有个高二的学长和高二的学姐都是之前电脑制作拿过奖，就被我们老师拉去参加NOIP了。显然这和OI不是一个知识体系，毕竟我们也是老师带的第一届OIer。但不幸的是，初赛结束之后就只剩4个人参加提高组复赛了。而初中普及组的初赛通过人数还是挺多的。 后来自然就到NOIP2015了，然而当时什么算法都不会，只知道C语言的基本使用，也不会STL，甚至连搜索都不太熟练。最后Day 1T1做了出来，剩下的题目要么打个搜索，要么打个特解，要么打个输出random，最后得分150。当年恰逢CCF取消省三等奖，福建省计算机学会和省教育厅自己发省三等奖，当然这个奖自然是毫无卵用除了免信息会考。对我而言也是一个信心上的鼓励。 并且我也听说了福师大附中的hzwer，高一拿省三，高二省一，省选R2翻盘最后进队，最后NOI Ag…
将树形01背包优化到O(n*m)
有先决条件的背包问题通常是树形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你需要注意的问题
这两天写程序时遇到了许多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)，快了许多，因而，线段树非常适合解决区间操作的各类问题。 如何建树？…
POJ 2482 – Stars in Your Window 题目背景翻译
http://poj.org/problem?id=2482 飞逝的的时光不会模糊我对你的记忆。难以相信从我第一次见到你以来已经过去了4年。我仍然还生动地记得，4年前，在美丽的珠海校区，从我看到你微笑着走出教室，你将头向后仰，柔和的晚霞照耀着你玫瑰色的脸颊。我明白，我已经沉醉于你了。之后，经过几个月的观察和窥探，你的优雅与智慧，你对待生活的态度和你对未来的愿望深切地在我心中留下了印象。你是迷人的阳光女孩，我总是梦想着与你分享余生。唉，实际上你远远超过了我最疯狂的梦想。我不知道如何桥起我与你之间的鸿沟。所以我没有任何计划，仅仅只是等待，等待一个适当的机会到来。直到现在，毕业的到来，我意识到我是个傻瓜，我应该创造机会并且抓住它而不只是等待。 这些日子里，我和我的朋友、室友、同学一个接一个地分开。我仍无法相信，在挥手之后，这些熟悉的面孔很快就会从我们的生活中消失，仅仅留下回忆。我明天就将离开学校。你已经计划远走高飞，追求你的未来，实现你的梦想。如果没有命运，也许我们不会再次相遇。所以今晚，我正在你的宿舍楼下徘徊，希望能偶然遇见你。但矛盾的是，你的美貌一定会使我心跳加速，我笨拙的舌头也许无法吐出一个字。我不记得我曾多少次经过你在珠海和广州校区的宿舍楼，每次都希望看到你出现在阳台上或是窗台上。我不记得这个想法曾多少次在我的脑海中涌出：打电话叫她一起吃晚饭或是聊聊天。但每次，考虑到你的优秀和我的平凡，胆怯的优势超越勇气驱使我静静地离开。 毕业，意味着大学生活的终结。这些光荣与浪漫的时代结束。你可爱的微笑是我原来努力学习的动力，这单相思的爱情会被密封，作为一个我心灵深处的记忆。毕业，也意味着新生活的开始，一个到达光明未来的足迹。我真希望你在国外天天开心，一切顺利。同时，我将努力从幼稚中走出来，变得更加成熟。我的理想将是在现实中追求我的爱与幸福，我永远不会放弃。 再见了，我的公主！ 如果有一天，在某个天涯海角，我们有机会相聚，即使是白发苍苍的男人和女人，在那个时候，我希望我们可以成为好朋友来自豪地分享这个记忆，重温年轻快乐的激情。如果这个机会永远没有到来，我希望我是天空中的星星，在你的窗外闪烁。远远地保佑着你，就像一个朋友，每天晚上陪伴在你左右，一同分享甜美的梦亦或是一同经历可怕的梦。 现在问题来了：假定天空是一个平面。所有的星星都躺在它的坐标(x,y)。对于每颗星星，有一个1到100的等级，代表它自身的亮度。其中100是最亮的，1是最暗的。窗口是个矩形，其边缘平行于x轴或y轴。你的任务是告诉我应该把窗口放在哪里，以使窗口中星星的亮度总和最大。注意，窗口边缘的星星不计算在内。窗口可以平移，但不能旋转。
调整环境变量在Windows下使用gdb
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放在最后面是比较保守的选择。…
Back to Top