最近QQ坦白说功能在我的好友之间十分火热，也因此催生了许多人想要查看坦白说发送者的欲望，考虑到网上没有太多的坦白说解密教程，这里打算自己写一个。 首先，你需要准备以下工具 一台iPhone 一台运行着Windows的电脑 在电脑上安装并运行fiddler抓包工具 iPhone和电脑在同一个Wi-Fi下，且可以内网互通（几乎所有的家庭网络都可以，但大部分学校等场所的Wi-Fi会进行客户端隔离，遇到这种情况可以请别人使用手机开热点） 在电脑上运行Fiddler，点击Tools菜单中的Options 进入HTTPS选项卡，左边按照如图设置，点击右边的Actions，然后点击Export Root Certificate to Desktop 再进入Connections选项卡，按照如图设置，特别是要去掉Act as system proxy on startup和勾上Allow…
我在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…
用PuTTYgen在Windows下生成SSH密钥
如今，玩云计算的人越来越多，很多人都喜欢去租个云服务器做个博客或是挂一些需要长时间一直运行的程序。这些服务器也多数是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上也没有问题 效果如图…
Back to Top