众所周知，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循环去打表就行了 接着是查询，这里我画了个图来解释。 其中橙色的线表示两个区间。 一维代码…
CQU选课小技巧
很多CQU的学生都遇到一个问题，选课的时候明明选完了，但是在提交上去的最后一步却遇到了Service Unavailable的情况，导致选课全部作废，需要重新选。 其实，借助Chrome浏览器和Fiddler可以很好地帮助我们解决这个问题。 问题根源：抢课系统在遇到提交失败的时候会丢失我们所选课的列表 解决方案：使用抓包工具，如果提交选课结果没有成功，就将提交上去出错的请求重放一遍 这里就不继续阐述诸如“看见加载不要继续点刷新”一类大家都知道的小技巧了 选课之前，你需要先安装好Chrome和Fiddler，Chrome建议安装SwitchyOmega插件，并按照这样设置。 点击上面菜单的黑色圆圈 然后点击选项 之后点击“新建情景模式” 然后按照下图设置代理协议HTTP，代理地址127.0.0.1，代理端口8888 （这个是Fiddler的默认配置） 之后应用选项。 然后打开fiddler，点击Tools，Options，按照这样设置 去掉Capture…
把树莓派作为Wi-Fi路由器（IPv6 passthrough、5GHz 11ac）
最近刚入手了Raspberry Pi 3B+. 打算当做一个高可玩性的路由器用。 毕竟这代硬件配备了千兆以太网（受限于USB总线带宽只能跑到250Mbps左右），和11ac Wi-Fi（受限于SDIO总线只能跑到110Mbps左右）。 参考资料：https://www.raspberrypi.org/documentation/configuration/wireless/access-point.md 我准备实现以下几个功能： Wi-Fi工作在11ac模式（如果你想使用11n模式，建议在hostapd配置部分参考这里），达到433Mbps的Link Speed Wi-Fi共享以太网口的网络，IPv4使用NAT模式 IPv6使用穿透模式（可适用于几乎所有学校和家庭的IPv6环境，甚至你的手机开启个人热点后通过USB连接在Pi上也可以用这种方式使后端设备得到IPv6地址） 接下来开始操作： 0x00. 切换到root用户 sudo su 0x01….
在macOS下编写C++程序
还是由于最近身边许多同学换到了macOS，他们多数曾经是OIer或者大学打算读计算机，跑来问我如何在macOS下编写C++程序，这里介绍一下我的方法。 （如果你已经熟悉在Linux或是WSL下写程序，那这篇真的没啥好看的） 首先，你需要安装编译器。 由于Xcode会自带一个clang LLVM编译器（与gcc不同，如果写了UB可能会和gcc编译的程序运行结果不同），你只需要去App Store安装Xcode并运行一次即可。 然后，你需要安装一个代码编辑器。 推荐2个代码编辑器： Sublime Text Visual Studio Code 然后，准备一个好用的终端环境 推荐参考这篇文章：https://blog.cyyself.name/2018/07/macos/ 你可以选择先处理一下bits/stdc++.h问题 参考这里：https://github.com/tekfyl/bits-stdc-.h-for-mac 执行以下shell代码：…
macOS终端调教历程
工欲善其事，必先利其器。 最近，我的许多朋友换了电脑，其中有不少换了Mac。他们也常常来问我macOS下如何编译程序，VS Code与VS区别等等。其中他们多数是准备在macOS上学习C++、Python等语言。 考虑到身边许多朋友需要这个，而我自己的电脑也需要整理一下，所以今天把电脑数据备份了下然后重装了系统，希望能把我自己配置macOS的历程分享给大家，为大家提供一些帮助。 在做如下操作前，请先到App Store安装好Xcode。 由于Xcode下载需要等待较长时间，在此之前，你可以先了解一下基本的Unix命令。如cd、ls、echo、cat等。 顺带了解一下nano编辑器的使用。 首先，一个好用的软件包管理器有助于环境的配置。 经常使用Linux发行版的朋友肯定对包管理器不陌生。可以用它来管理安装的软件包，并实现软件批量升级。同时还可以一行命令搞定软件安装。比如Debian、Ubuntu使用的apt，CentOS、Fedora使用的yum。 这里推荐一个Mac上的包管理器，Homebrew。 我们只要打开浏览器，将中间的命令一整行复制下来，到终端中粘贴，然后回车。 在安装过程中，你可能遇到需要输入密码的时候。需要提醒大家的是，这里输入密码是看不到输入密码的提示的，许多初学者的感觉是密码没有输进去。不过不要紧，只要在键盘打完当前用户的密码，然后按回车即可。 第二，一个好用的Shell有助于效率的提升 在此安利一下zsh，一个比自带的bash好用得多的Shell，还有各种插件可以添加。 待homebrew安装完后，我们可以来安装一下zsh。 在终端中输入…
QQ坦白说解密教程 for iOS
最近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…
Back to Top