……很久没更新了，随手更一发 →_→ 这次选取的题是 UyHiP 2016 Feb 的题，然而我并不会做。

Problem

给定一个 \(n\) 维的 0/1 cube，要求找若干个不过原点的超平面，使得这些超平面能够覆盖除了原点以外任意 \(\{0, 1\}^n\) 的整点。求至少要多少个超平面。

@ehk 给了我两个很有趣的题目，感觉很不错哦。

Problem

出现次数最多的数

给定一个大小为 \(n+1\) 的数组，每个元素都是 \([1, n]\) 里面的整数，且只有一个数出现两次或以上，不一定所有的数都出现过。要求在 \(O(n)\) 时间 \(O(1)\) 空间内找出这个数，且不允许修改数组。

Peak

给定一个二维矩阵 \(A_{n \times m}\) ，保证：

1. \(n, m \geq 3\)；
2. 每个元素均不相同；
3. 对于 \(1 \leq i \leq n\) ，\(A_{i, 1} < A_{i, 2}, A_{i, m - 1} > A_{m,i }\)
4. 对于 \(1 \leq j \leq m\) ，\(A_{1,j} < A_{2, j}, A_{n-1,j} > A_{n,j}\)

求一个点的坐标 \((x, y)\)，使得 \(A_{x,y} > \max(A_{x - 1, y}, A_{x + 1, y}, A_{x, y - 1}, A_{x, y + 1})\) 。

要求时间复杂度 \(O(n+m)\) 空间复杂度 \(O(1)\) ，可以认为 \(A\) 是 black-box 访问。

今天逛知乎的时候看到了一份计算 \(\pi\) 的 代码。我试图跑了一下，发现其输出的 2400 位居然全部是对的。我试图学习了一下其中的姿势，感觉还是很神奇的。

1
2
3
4

int a=10000,b,c=8400,d,e,f[8401],g;main(){
    for(;b-c;)f[b++]=a/5;
    for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)
        for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}

然后我就试图分析这段代码到底是在干啥。

大家好我是来除草的。

由于 Hexo 更新了导致 blog 莫名奇妙跪了，于是我就很久没有更新了。（其实就是懒了不想更新了。）

于是趁着这个五一假期顺手把 hexo 修复了一下。所谓的修复，就是推倒重来……于是干脆物色了一个新的主题。当前这个主题看起来还不错，NexT.Mist。 看起来非常干净，很适合我这种……只想吐槽不想写公式的人。

在修复的时候遇到的一个奇葩错误，hexo server 老是启动不来，我也不知道为什么。 根据不停的二分哪个文件的哪一行的哪几个字符，终于让我找到了：{ # 这两个字符似乎不能同时出现……

于是 hexo server 终于能跑起来了，但是 Disqus 莫名其妙跪了我也不知道为什么，我几乎什么都没改…… 修了一下失败了，我还是不知道为什么……于是弃疗了。 找到是什么问题了……disqus_url 这是个啥参数呀，我注释掉就好了 = =

寒假的时候写了个小网站，本来想着一个月妥妥的写完，后来发现自己还是 naive。 寒假写了一个月没写完，回到学校后继续写又写了一个月，勉强能用了，但是还是有一堆 bug 要修。 用的技术大概就是 Koa 作为后端，MongoDB 数据库，AngularJS 前端。界面用的是 SemanticUI， 感觉写起来挺爽的，就是查 API 真蛋疼。

然后在这个学期刚开学的时候，由于 Arch 一堆问题要修，于是我就修 qi 复 liao 了一发，直接装了 Ubuntu，所谓的新学期新技术嘛…… Firefox 也换成了 Chrome，装了几个小插件，用起来也感觉还行。 印象最深刻的是一个加空格的小插件，简直好用的无与伦比。 密码管理也换成了 LastPass 。以前写的那个无聊的 HMAC 虽然还在用，但只是用来做兼容的了。

最近出了啥 Visual Studio Code 我也来玩玩。说起来这是要变成码农了吗……我可是青年理论计算机科学家 →_→

说起来上个学期刚开学的时候陪同学去买笔记本，然后我也顺手买了一台……Thinkpad New X1C，轻倒是挺轻的，到处带着基本没问题。 续航的话刚买回来 6h，现在大概 5h 。重装一次系统应该又可以回来。 上个学期天天出去自习，还去罗姆楼刷了几次夜，所以电池充放次数几乎是一天一次。 这个学期又赖在寝室出不去了……然后我也懒得装 Linux 了，用的 Windows 8 也还算凑合。Listary 实在是太好用。

计算机科协的那个啥 vpn9 实在是良心。妈妈再也不用担心我的流量了……但是不知道为什么经常掉线…… 我现在的用法是 Win8 上装了一个 OpenVPN ，树莓派上也装了 OpenVPN 。 然后树莓派上跑一个 cow ，iPad、iPhone、老笔记本全部用 cow 做代理，这样默认就是走 vpn 了……

上学期期末的时候在玩 Portal ，回家后我老弟要玩，那就给他玩呗……结果……结果…… 结果上来就直接联机对战，找到了一个好老师，我当时就被他吓得目瞪口呆。 寒假的时候老弟有时候吃夜宵，于是我也顺带着吃夜宵，老弟给我煮面、煮馄饨、炒蛋炒饭，真是太幸福…… 然后现在在玩炉石……技术实在是菜的不忍直视都快弃疗了。

寒假的时候到外面讲了几天课，然后回学校讲课，现在讲课也讲不动了，出题都出不动了。心好累……反正现在有一些存款，就不急着去圈钱了…… 三月底的时候去师大附中讲了两天课，这应该是最后一次讲课了。然后这几天在给一个大学出 ACM 模拟题，也应该是我最后一次出题了。 以后应该就见不到我在这方面活动了。这一代终究要退去。 CTSC 懒得去出了，其实也没有好的 idea ，于是放弃了。明天 CTSC day1，祝 cyb 小朋友好运吧。

现在就安心的和 papa 一起搞搞 TCS，继续上个学期的课题。但是现在似乎到了瓶颈期，我的所有 idea 看起来都用光了…… 原来想和 clj 一起上 ATCS 的，发现和博弈论冲了我就没上了。看 clj 现在的样子我发现自己真是 naive，不知道何时才能追上去。Anyway……

最近一段发生了一些情感上的事，然后发现我自己真是一个玻璃心的妹子。想太多，猜太多，遇到啥事都要紧张半天。 心情经常 biu 的一下就糟糕的无以复加。Anyway，我并不认为这样太糟糕，我也不打算改，就这样吧。

这学期的数值分析准备和老师套磁一发，用课程报告翘期末。 我写的主题是 Toeplitz 矩阵，其实现在主要在写 Circulant 矩阵的一些性质，把高中学的 FFT 又可以写上去，简直爽。 老师给的模板是 Word，然后我就去和老师套磁改成了 TeX，但是 TeX 模板仍然蛋疼……算了我就用 ctex 默认模板好了。

我现在急需一发鸡血……罗老师不行了，罗老师要倒了……

好吧我就是无聊了……

这玩意是为了解决这么一个问题的：我的 QQ 跑在虚拟机里面，因此里面有消息了我在外面并不知情。消息推送有几个可能的解决方案：

1. WineQQ。我对稳定性产生怀疑。
2. QQ for iPhone。其推送并没有那么及时。
3. 戴上耳机就可以听到 QQ 的声音了。但是我的歌都放在 iPhone 里面且耳机只能用在 iPhone 上。
4. 换成 Windows/Mac 系统。我没那么土豪。

于是就想能不能写一个小程序使得虚拟机里面有消息了就在外部的 KDE 里面出个提示之类的。

琢磨了以下，QQ 自带的提示似乎只能播放声音。于是第一想法是监听声卡播放。搜了搜没找到相关资料（其实是自己懒，觉得如果这样的话有得进行 WinAPI 编程。感觉监听声卡这还是比较底层的，感觉不好搞。），于是就放弃了。

第二想法是播放声音的时候肯定得访问声音文件，我记得 png 还是 jpeg 可以嵌入一个奇怪的东西，不知道 WAV 是否可以。搜了搜还是没找到类似东西。放弃。

第三个想法是监视屏幕，我打开一个 QQ 窗口，如果有消息过来了，其图标会有相应的变化。在我使用的这个版本里面，窗口合并后如果一个人有新消息，其名字后会出现一个橙色小圆圈，里面一个数字表示其消息数目。如果我定时扫描这个位置，获取此时此像素的颜色，就可以知道有没有消息了。后来想到，如果我把 QQ 不设置为当前窗口，那么当有新消息过来的时候 QQ 在任务栏里的图标会变成那种一闪一闪的黄色。于是我监视的点的位置基本上是不变的，只要我保证 QQ 在任务栏中的位置不变就好了。

于是就用了 AutoHotKey 这个小工具，代码大概就长这样：

#Persistent
#SingleInstance
SetTimer, CheckQQNotification, 1000
return

CheckQQNotification:
CoordMode, Pixel, Screen
PixelGetColor, col, 187, 775
; 颜色就是 %col%
return

现在我们知道颜色了。实践发现，图标的颜色不是两种颜色，新消息过来后，由于会闪所以可能会有其余的颜色。于是就直接用 RGB 三元组的 Manhatton 距离来判断处于什么状态了。

现在考虑如何将颜色这个信息传到 Linux 里面去了。第一想法是造一个小型 http 服务器。看起来没那么复杂，就开始写了。

框架用的 Node.js 的 Express 框架，而且我只需要得到一个信息，直接 POST 过去就好了。那么考虑在 AutoHotKey 中如何发送一个 POST 请求。据说 AHK 有一个包可以做这种事，但是我试了试发现不 work ，果断下了一个 curl for Win 然后直接 POST 过去。我很想吐槽 AHK 带参数运行一个程序，照着别人的程序写都发现不 work 。这里有个一个小细节，AHK 运行这种 Console 程序会闪出一个黑框，很影响用户体验。解决方法是找了一个叫做 Hidden Start 的程序， hstart /NOCONSOLE curl 就好了。Win 这边差不多布置好了。

在 Linux 这边，弹窗的话我用的是 notify-send 还附赠一堆小图标。由于请求是 1s 一个的过来的，不能对于每个 Active 的请求我都弹一个窗，于是就设置：如果上一次表示 QQ Active 的请求是在 5s 以前，那么就弹窗，否则不弹。另外如果我现在就在虚拟机里面操作也可以不弹窗。如何判断在是否在虚拟机里面？第一想法是在 Win 里面获取鼠标位置，发现不 work 。第二想法是在 Linux 里面获取活跃窗口，用的 xdotool getactivewindow getwindowname 搞的。为了好看还加了当前时间，moment.js。

（我是不是又造了一个轮子？）

最近买了一个 Raspberry Pi ，原意是想鼓捣成一个支持 IPv6 的路由器。趁着放假先来玩一下。

据说最近的墙越来越厉害了。

上次打 GCJ 的时候遇到了文件下不下来传不上去的情况，不能更囧。后来的几天内学习各种走出国门的知识，现在感觉已经差不多了。

hosts 大法

这个是我用的最久的方案之一了吧。其优点是迅速快捷方便，缺点同样非常明显，只对特定的网站有效，且封锁起来特别容易。

我用的是 Smarthosts，在前一段时间的封锁中不幸牺牲，经常出现 too much request 的情况。

卒。

去阿根廷

这个是最广为人知的方案（没有之一？）

优点是通用，流量虽有限制但是约等于没有。便捷，一个文件夹带着走天下，还可以给别人用。

缺点，部分人对速度要求较高。最近抽风率较高。

如果你愿意一层一层一层的拨开我的心

……我先去学学解剖学

试了一下，速度慢出翔。

原理似乎是基于一层一层的节点转发，因此需要许多志愿者做中间节点。

优点不明。

VPN

免费的著名的有 vpngate.net 。

这是一个很奇怪的论证，你要上 vpngate.net 的话需要翻墙，但是你要翻墙需要 vpngate.net 上面的东西。

当然你要土豪可以自己买个。但是据说靠谱的不好找。

缺点是上国内网速度也不怎么样。当然用个什么 chnroutes 之类的来分流。不过这么高级的我就没用过了。

VPS

目前用的就是这个方案了。

直接蹭了 drd 的 VPS 。DigitalOcean 还算可以吧，最低端的都可以供一堆人一起用了。1T/month 肯定用不完。

具体方案是 shadowsocks 。蛋疼的是 shadowsocks 有好几种不同的实现，我不知道这些实现的区别。后来统一用的是 shadowsocks-libev ，全部是自己手动编译，反正不大，编译起来挺快的。听说 Singapore 的服务器有 ipv6 了，试图折腾了一下，失败。

后来考虑直接通过 tunnel 来搞。我用的是 HE IPv6 ，挺赞的。网上有一些教程。我在这里折腾了好久，原因是因为某些 shadowsocks 对 ipv6 的支持不好（或者是我姿势不对？）

这个月流量只剩下 300M 了，剩下的日子只能靠 IPv6 来打发了。

吐槽一下，看 jzp 买了一个极路由，于是我也查了查相关资料。查了半天没查到开发者资料，这是准备自己一个人写插件的节奏么……反观小米路由，虽然还没见到影子（还不一定抢的到是吧），但是人家的开发者教程已经出来了。如果极路由出了开发者教程的话我还可以考虑买一个，如果不出的话就我还是慢慢等小米路由好了。

不知道从什么时候从 Jekyll 转移到了 Hexo 。我觉得 Javascript 这门语言挺漂亮的，除了其奇怪的变量作用域。起码 Hexo 渲染比 Jekyll 快了一个数量级吧（喂这样比较真的合适吗！）。

转移过去的时候其实出了点问题。大致表现就是首页的 description 里面全是汉字的 unicode 码，然后 & 又被转义掉了，导致汉字一个都显示不出来。我试图在 ejs 里面找问题，似乎是某个地方多转义了一次（<%= %> 和 <%- %> 的区别）。修了很久没修好，最后 sudo npm install hexo -g 好了。

另外前一段时间的 Arch Linux 有 3 个 bug 我修不好（其实是不想修了）：

1. 输入法的快捷键。每次启动时我都要将快捷键重新绑定一次。
2. 休眠后的 VirtualBox 不能启动 Win7 。
3. 休眠启动后连不上 Wi-Fi 。

前两个还可以忍，最后一个简直不能忍。于是一怒之下换了 openSUSE （jzp 眼中的“长者 OS”）。不小心丢了 .emacs.d 呵呵呵呵呵幸亏有早期备份。现在的用户体验还算 OK ，毕竟新学期新系统，新系统新气象。fanhq 表示很喜欢里面的 YaST ，希望 Ubuntu 也搞一个，感觉有点不靠谱。不习惯的一点是 Ctrl-Backspace 的 delete-word ，这个 word 的判定似乎太严格了， tabopen google.com 我习惯 delete com 而不是 google.com 。

为了禁水，将人人客户端从移动设备上卸载了。于是少了一堆水的时间。同时带来的就是我越来越困了，按照 jzp 的介绍：“我的室友 lyp 已经连续几天十一点起床了。”臣妾睡不够啊……

发现让自己从悲伤中缓过来的最好的方法就是让自己忙起来 —— 不过，这算不算的上一种逃避？思考人生哲学问题什么的，一个人凌晨在外面散散心也是不错的——如果有人陪那就更加美妙了。当你想起大物、微积分、电原、线代等等科目都要考试，史纲论文还没写的时候真就没时间忧伤了。

有人说这东西发出来就是 public knowledge —— 反正你也不会看是吧。有些私人信息可以不说但是雷区范围让我难以接受 —— 其实我还不知道具体雷区。而我觉得自己去扫雷挺累的……所以就不管了，安全第一。（其实雷区不可怕，雷区比一般人都大这才可怕吧。）……（安全真的第一吗？）

三点了，去睡了。

为了庆祝 @hym 妹子过生日，他特意写了个游戏让大家玩，请戳 这里 。

作为他无聊的室友，我们就有了各种刷分的乐趣。还未 release 的时候是可以各种刷分的，因为当时 \(10^9\) 这种数的权值非常大。release 之后不那么好刷了，起码手刷不好刷了。我手刷最多只刷了 12w ，就是一轮中凑了两个 99999999 。

于是今天花了一天时间写了个自动刷分机，刷个 30w 基本没问题……

代码主要用 Livescript 写出来的，其实就是一个 GreaseMonkey 脚本 。

使用方法：

1. Firefox：对不起 hym 不支持 Firefox；
2. Chrome: 请先安装 TamperMonkey, 然后安装该脚本；
3. 其余: 自行解决。

我写的主要就是随机一条路径，交给 NAN.Analyzer.analyze 去求值，每次选权值最大的那个……所以基本上没有什么代码。我随机选择了 3k 条路径，各位同学可以根据自己的机器进行相应的配置。

Javascript 代码在 这里 ，Livescript 源文件在 这里 。

还是放出来吧……

请戳 这里 。

如有错误敬请回复指正。