如今，玩云计算的人越来越多，很多人都喜欢去租个云服务器做个博客或是挂一些需要长时间一直运行的程序。这些服务器也多数是Linux系统，但是服务器的问题是一个不可忽视的问题。常常能在日志中看到每天有大量IP尝试连接22端口，希望使用弱密码能够登录服务器。这些服务器被黑客攻下后往往会被用作DDOS肉鸡，造成重大的安全威胁。而实际上，用ssh密钥登录可以有效解决这一问题，至少在当下很难在有限的时间内根据rsa公钥破解出rsa私钥。 现在介绍Windows下用PuTTY gen工具生成SSH密钥的方法。 首先，打开PuTTY gen 点击Generate，然后在界面中晃动鼠标，PuTTY gen会根据鼠标移动的轨迹来生成一对rsa密钥 生成后结果如下图所示 之后，把这个Public Key复制下来，然后先登录到我们原来的服务器上。 由于OpenSSH Server默认读取用户主目录的.ssh/authorized_keys文件，所以我们把ssh的公钥放到该位置。 具体操作为，在用户主目录下建立.ssh文件夹，然后放置authorized_keys文件，在里面放上公钥 将刚刚复制的SSH公钥粘贴进去（PuTTY导出的密钥有时候会分行，请注意删除多余的换行符，authorized_keys里面可以放多个密钥，一行一个分开即可） 然后按Ctrl+X，按Y再按回车退出 之后，我们就可以使用刚刚生成的sshkey连接服务器了。 注意：SSH Pubkey是可以对外宣告的，但是Private Key一定要自己保存好。RSA采用非对称加密，具体原理参见我之前写的博文https://cyyself.name/2017/07/rsa-algorithm/，RSA身份认证原理一样，就是用客户端的Private…
将树形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)…
使用ngrok架设你在NAT背后的服务器
如今，越来越多的家庭宽带取消了公网IPv4地址的分配，给许多人在外面连接自家网络服务带来了诸多不便，比如连接自己家电脑的RDP远程桌面或者获取自家NAS上的文件，为此，一个简单的解决方法就是使用ngrok作为外网端口映射。 本教程使用Debian 9为例。 首先，我们先去https://ngrok.com/注册一个账号。 之后便进入了ngrok的Dashboard页面，我们先点击Download把ngrok下载到自己的服务器(路由器/树莓派/….)上。 在这个下载页面上，我们用本机的浏览器访问，然后在相应的链接上获取链接地址。 对于树莓派/路由器等设备，选择Linux ARM，对于自己用PC组建的NAS等设备选择Linux 64-Bit。 然后我们ssh到自己的设备上，用wget命令下载相应版本的ngrok，并解压，安装到相应的目录，推荐/usr/bin （解压的时候需要unzip软件包，如果没有请使用apt install unzip来安装） 这里使用的shell命令包括： wget https://bin.equinox.io/c/4VmDzA7iaHb/ngrok-stable-linux-amd64.zip unzip ngrok-stable-linux-amd64.zip…
关于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的处理方式，所以我们还是手动%一下再操作吧。
小绿锁背后的RSA算法
如今，我们上网时常能见到一把小绿锁，这便是多数浏览器对于HTTPS连接的标识。即HTTP over SSL，它代表着我们与网站服务器的连接是经过SSL加密的。然而，不论何种加密算法，总是有加密和解密的过程，其中最关键的就是密钥交换过程，如果在交换过程中这个密钥被窃取，之后的加密便毫无意义。那么SSL是如何确保即使我们的网络流量被抓取的情况下也能保证加密信息安全的呢？这就是我们今天要说的非对称加密算法，而最早的非对称加密算法便是从RSA开始。 算法介绍 RSA算法是1977年由麻省理工学院的Ron Rivest、Adi Shamir、Leonard Adleman三人共同提出的，RSA名字便取自他们三人的姓氏。在RSA算法之前，密钥交换主要采用预共享密钥的方式，例如我们生活中连接WPA2-PSK的Wi-Fi便是采用预共享密钥的方式，它的特点是需要通信双方事先共享密钥才能加密，也称为对称加密。而RSA采用的是非对称加密，需要生成两组密钥，称为公钥(Public Key)和私钥(Private Key)，这两组密钥是成对的。使用公钥加密的数据可以被私钥解密，使用私钥加密的数据可以被公钥解密。 在了解这个算法前，你需要了解以下数学知识，我假设读者已经具备初中数学知识。 对于OIer，你如果了解过扩展欧几里得、欧拉函数、费马小定理，你可以跳过这一段，而且你看这个会很轻松。 最大公因数： Greatest Common Divisor，即两个数的因数集合的交集中最大的数，通常我们使用gcd表示。 例如a、b的最大公因数记为gcd(a,b) 互质关系：…
在移动硬盘上安装Windows To Go+Linux双系统（EFI）
自己多出了一块128G的SSD，本着闲着也浪费的想法就用了一个老的硬盘盒装起来当移动硬盘使用，没想到新固件还支持Trim，便有了在上面安装Windows To Go，然后给Mac提供Windows的想法。可是，安装完Windows的我似乎还不满足，还希望在上面安装一个Ubuntu系统，几经辗转，终于找到了办法。 话不多说，直接入题。 首先，备份移动硬盘上的数据，使用WTG辅助工具写入Windows系统文件，记得勾选UEFI+GPT。 用压缩卷空出一部分空间留给Linux使用 至此，我们已经完成了Windows的安装，并且这时直接启动移动硬盘已经可以使用Windows了。 将移动硬盘挂在到虚拟机中，记得使用EFI模式，比如VirtualBox勾上“启用EFI”，Hyper-V选择第二代虚拟机即可，在虚拟机中安装好所选的Linux发行版 待Linux安装完成后，此时的系统并不能直接启动的，若直接启动出现的是一个蓝屏的Windows，因为之前安装的grub没有使用removable模式，因此，我们手动安装grub 将/boot分区挂载到任意目录，这里我选择/target/boot，若没有单独分出/boot就直接挂载/到任意目录即可。同时，将ESP分区挂载到/target/boot/efi，然后删除EFI/Boot/bootx64.efi文件 安装grub-efi软件包 使用grub-install安装grub，之后便得到了一个可启动的Linux 来看看成果吧！ 可以看出，grub已经接管了Windows Boot Manager，我们可以在这选择操作系统启动。 同样，在Mac上也没有问题 效果如图…
线段树入门
什么是线段树？ 线段树，是一种二叉搜索树。它可以把一个从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轴。你的任务是告诉我应该把窗口放在哪里，以使窗口中星星的亮度总和最大。注意，窗口边缘的星星不计算在内。窗口可以平移，但不能旋转。