好吧我就是无聊了……

这玩意是为了解决这么一个问题的：我的 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 源文件在 这里 。

还是放出来吧……

请戳 这里 。

如有错误敬请回复指正。

2048 已经打入敌人内部了是吗……

Problem

给定一种奇怪规则的 2048 ，问可能凑出来的最大的数是多少。

规则比普通的 2048 多了一条：如果这次合并后还可以继续合并，那么就不会出现新的方块。

注意每次可以出现 2 或 4 。

Solution

其实 yy 一下就可以猜出答案是 \(2^{17}\) 。

怎么解释呢……一开始我的想法是在一个局面中出现两个相同的数是不优的，可是怎么证明是不优的呢。我觉得这显然，但是 Michael 说要给理由，于是我就没继续想下去了。

后来脑洞大开，yy 了另外一个思路。就是考虑整个局面中所有元素的和。每次这个和要么增加 2 要么增加 4 。注意到这个和的二进制表示中 1 的个数的意义，1 的个数表示这个局面中最少要多少个方块。如果要产生一个 \(2^{18}\) ，那么一定存在一个时刻使得整个和要么为 \(2^{18} - 2\) 要么为 \(2^{18} - 4\) 。注意到显然不能为 \(2^{18} - 2\) ，因为 \(2^{18} - 2\) 有 17 个 1，而 \(2^{18} - 4\) 里面有 16 个 1，已经把棋盘塞满了，游戏已结束，也是不可能的。所以 \(2^{18}\) 是不可能出来的。

这样的话就只要考虑 \(2^{17}\) 了。显然这是可能的，很容易构造的吧……

周末还有微积分考试，我现在是不是在作死……

cellBlockA

这一关很简单，就是走过去拿走 Computer ，再走到出口就好了。

theLongWayOut

也很简单。

分别在上面黑线和下面黑线处填入 /* 和 */ 就好了。

validationEngaged

这一关限制了 # 的数目必须为多少，所以不能删掉代码……

改一下位置不就好了。

multiplicity

文件名已经告诉你一切了……

再放一个出口。

minesweeper

背景是红色的这是红果果的提示吧。

照模子画瓢把所有的 mine 标成另一种颜色好了。

drones101

那个 drone 很讨人嫌……

造几个 # 把他挡住不就好了。

colors

重点是要利用 phone 的 Callback 。（也只能利用这个吧）

在里面循环换颜色：红 -> 绿 -> 黄。用 phone 切换颜色。

intoTheWoods

注意 generateForest 这个函数是会清除已有障碍的。

所以你所需要的就是把 phone 的 Callback 设为 generateForest 然后使劲往出口走。走不动了就重新生成。

fordingTheRiver

在 phone 的 Callback 里面把 raftDirection 改掉。

ambush

把 Drone 的移动策略改掉：能向上就向上，否则向右。

robot

写一个简单的 AI 。

先向下，再向右，再向下。

robotNav

你可以用 robot 这一关的技巧继续加强，也可以用下一关的技巧。

robotMaze

迷宫会变，这使得这一关特别蛋疼，不能用 robot 的技巧了。

写个最短路什么的自然可以。

所以你在 behavior 里面写：如果 player 的位置在哪里就往哪边动。

相当于你通过操作 player 远程操作 robot 。

crispsContest

把使用 greenkey 时 removeItem 后面的东西改成 empty 就好了哈哈哈。

然后你就可以不用 greenkey 了。依次进入左上、右上两个角最后再去取 Algorithm 就好了。

exceptionalCrossing

这关实在不会就看了教程。

这要利用 javascript 的异常处理机制。你在里面直接调用一个不存在的函数就不会进入 killedBy 这个过程。

@cxq 的方法就是主动把括号闭合掉，然后加一句 type: "item" 然后你就可以自由自在踏上去了。

lasers

把 laser 的颜色改掉然后继续用 phone 来切换颜色……

pointers

这一关过了纯属巧合。

我把所有的安全的 transporter 标了出来。手动 bfs 几次就过了。

后来又试了好几次，发现成功率不高……

superDrEvalBros

主动把 jump 闭合掉。

既然你用 timer 了那我也可以用是吧……

你的 gravity 是 45ms 一次，那我的 jump 就搞成 30ms 一次好了。

documentObjectMadness

你看代码中的 overrideKey 就知道了。

目标就是和红色的 @ 重合。

bossFight

这一关是我代码量最大的一关。

一开始的想法是——以子之矛攻子之盾。我也 define 一个奇怪的 boss ，发出横着的子弹来打那些 boss 。

但是由于 validateLevel 检测了 dynamic 物体的数目，所以我又添加了一种新的物体，动态的，通过 onCollision 去触发。触发后就放置两个我造的 boss 。

endOfTheLine

说起来也是看攻略过的……

其实重点已经差不多知道了啊……

我想在 placeObject 或者 placePlayer 的时候把 map.finalLevel 清空，但不知道为什么失败了。

结局就是把代码中判断 finalLevel 的地方改掉， /scripts/objects.js ，L28。

结局

似乎就是浪费了一个晚上。

啦啦啦一年一度的女生节到了～

友情提示：如果您是来看清华女生节的，为了方便您更好的阅读，请按Ctrl-w。

（一开始就参考了模板发现我还是不会写啊 T__T）

从有记忆的第一天起，某人总是扮演一个超级学霸的角色。作为纯种理科男，我表示语文等学科亚历山大，某人却表示毫无压力。回想起高二暑假某天路过成绩公告栏的时候，听到有人说“xxx还要再来虐一次啊”，某人急速溜走的场景。长期年级前十，虽然也有保送生模拟考试被虐的飞起的记忆，可无论怎样都遮住不了耀眼的光芒。

说起我刚进高中的时候，却也有有那么一点点的中二。看到个小da朋jie友jie，就忍不住欺mo负tou一番。后来一看这位小朋友成绩这么好，顿时就佩服得五体投地。于是不知道从什么时候开始，我就开始把自己定位成一个英er雄bi，要好好支持这个看起来弱不禁风的小朋友。年少时候的事迹虽然看起来很二逼，但是回忆起来也别有一番风味。愿意一起陪你 2b 的，或者见证过那些光荣事迹的人，又有几个呢。

记得一起做学习委员的时候，有时要到讲台上通知一下大家，或者做做一周的总结之类的。虽然平常总是贪生怕死，但是关键时刻在女生面前还是需要增加一点好感度的，于是我就英勇的走向讲台。作为大xiao哥di哥di，好感度还是很重要的。

你三年生日，高一时送了一只笔芯，高二时送了个笔盖，高三时准备送一个笔筒，看上去很完美。恩，看上去也很二逼。虽然现在还是不知道如何挑选礼物……你送我的那个笔筒，我现在还保留的着。

大部分和你在一起的时候都是在操场，两个人在操场上一圈一圈地逛着。说是运动运动，通常就是我一个人侃来侃去，想把我的欢乐带给你。想起来还和你解释了好久的 233 和 LOL 呢。说起来我平时话也不多，怎么和你在一起的时候就总想着说话呢……

上大学一来，碰面的机会就少很多了。（诶高中碰面的机会也不多）明知道你是吃货，但是却又不知道有哪些好吃的能带给你，真是遗憾。相反倒是你带我吃了 PKU 那边的好吃的。

说到策，我可是专业青姐策哦。三年也不知道策了你多少次。高一下期是策你的巅峰（还有海如语录），每次看着你说“atm别策了我还要写作业呢”，我才胜利者般的离开了，一点也没有打扰你学习的内疚 23333

平时看到你不开心，我都不知道怎么安慰你。情商有限，就只能陪你一起 sad 了。在高三下期的时候，你说你被那些专业书折磨的要疯了，希望我能给你一点支持安慰。但是我发现我不会，我没有特别的安慰技巧。看到你走回一教的背影，那一刻只能在心底里想我怎么这么没用 T_T

没想到你这么快就在 PKU 找 BF 了，真是吓了我一跳。或者我这身份有点尴尬，但我还是会在你身后支持你的。我没有韩雨骊那样的默契，也没有屹大王那样的暗语，我还是和三年前一样写着毫无修饰的句子说着平平淡淡的话听不到话中的话找不到该用的词，但还请留给我一份信任。祝你们幸福哦～

最后就祝某人生日快乐啦～顺便祝沸姐生日快乐～

Auld Lang Syne.

另外就不要吐槽什么我的文笔了（又变成形散神更散的散文了），光写出来就已经竭尽全力了。

小朋友问我的一道题，然后我就看题解了。

原题解写的不任职时，但是 comment 写的还算清楚。可以借鉴一下 comment 的思想然后就可以自己 YY 了。

Problem

现在有 \(n\) 个馅饼，第 \(i\) 个馅饼的价格是 \(a_i\) 。每买一个价格为 \(k\) 的馅饼，你就可以免费得到一个价格严格小于 \(k\) 的馅饼。求购买所有的馅饼的最小总价格。

Solution

要使得最后总价格最小，就是要使得免费获得的馅饼的价格和最大。

还是用 dp 来引入吧。

将所有数从大到小排序，可以得到若干个二元组 \(<val, count>\) 表示 \(val\) 这个价格的馅饼出现了 \(count\) 次。按照 \(val\) 从大到小排序后，每次处理出一个二元组。令 \(f_{i, j}\) 表示处理完前 \(i\) 个二元组后，且有不超过 \(j\) 个馅饼是免费获得的时，免费获得的馅饼最大价格和。

转移思路很简单，就是前枚举当前二元组中有多少个是 free 。 \[f_{i + 1, j} = \max_{valid\ t} (f_{i, t} + (j - t) v_i)\] 注意这里的 \(t\) 要求是合法的。于是就有一个非常简单的 \(O(n^3)\) dp 了（终于可以写拍了）。什么情况下 \(t\) 才是合法的呢，首先为了保证 \(f_{i, t}\) 的合法，要求 \(0 \leq t \leq T_i\) 其中 \(T_i = \sum_j count\) 。为了保证 \(j - t\) 的合法，要求 \(0 \leq j - t \leq \min(count, T_i)\) 。所以有 \(\max(0, j - count) \leq t \leq \min(j, T_i - j)\) 。我们发现，对于相同的 \(i\) ， \(j\) 与 \(j +1\) 的区间相差为 \(O(1)\) ，所以这个 dp 可以很轻松优化到 \(O(n^2)\) 。当然你要写个 \(O(1)\) 的 RMQ 也是可以直接做到 \(O(n^2)\) 的。

\(f\) 有个重要性质： \(f_i\) 是凸的。虽然怎么证明还没想，但是感觉是对的。（你把 \(f_{i, j + 1} - f_{i, j}\) 想成是边际收益就好了嘛）

如何利用这个性质呢？我们观察 \(f\) 的转移： \[f_{i + 1, j} = j v_i + \max_{valid\ t} (f_{i, t} - t v_i)\] 。前面一部分对于 \(j\) 来说是固定的，后面一部分是不是看着很面熟？似乎在各种什么斜率优化上啊，凸包上啊都可以看到这货。由于 \(f\) 的凸性，我们可以保证 \(f_{i, t} - t v_i\) 是单峰的，所以必然存在一个最大值，我们不妨设 \(t = e\) 时取得最大值。

再来看 \(j\) 对应的合法的 \(t\) 的区间 \([L, R]\) ，其中 \(L = \max(0, j - count), R = \min(j, T_i - j)\) 。我们可以直接通过区间推出最优的 \(t\) 的值：

1. 若 \(e < L\) ，则转移的 \(t\) 为 \(L\) ；
2. 若 \(R < e\) ，则转移的 \(t\) 为 \(R\) ；
3. 否则转移的 \(t\) 为 \(e\) 。

所以我们还是得到一个 \(O(n^2)\) 的 dp ，但是更加好写了。

我们把每个 \(j\) 对应的合法区间画出来，有两种可能：

左图表示 \(e + count < T_i - e\) 的情况，右图表示 \(e + count > T_i - e\) 的情况。对于这两种情况，我们都可以把它们分成三部分：

两个图的第一部分均为 \(1 \leq j < e\) 。这时候的区间为 \([\max(0, j - count), j]\) ，转移的 \(t\) 为 \(j\) ，代入后可以直接得到 \[f_{i + 1, j} = f_{i, j}\] 。

两个图的第二部分均为 \(e \leq j \leq \min(e + count, T_i - e)\) 。这时候有 \(\max(0, j - count) \leq e \leq \min(j, T_i - j)\) ，故转移的 \(t\) 为 \(e\) ，代入后有 \[f_{i + 1, j} = j v_i + (f_{i, e} - e v_i)\]

左图的第三部分为 \(e + count < j\) 。此时有 \(e < \max(0, j - count)\) ，故转移的 \(t\) 为 \(\max(j - count, 0) = j - count\) ，可以写出转移为 \[f_{i+1, j}f_{i, j - count} + count v_i\] 。注意 \(count v_i\) 与 \(j\) 是无关的。

右图的第三部分为 \(T_i - e < j\) 。此时 \(\min(T_i - j, j) < e\) ，故有转移的 \(t\) 为 \(T_i - j\) ，可以写出转移为 \[f_{i+1, j} = f_{i, T_i - j} + (2j - T_i)v_i\] 。

令 \(g_{i, j} = f_{i, j} - f_{i, j - 1}\) 。只要知道了 \(g\) ， \(f\) 是很容易求出来的。我们观察一下 \(g_i\) 与 \(g_{i + 1}\) 的关系。对于两个图第一部分，我们有 \(g_{i + 1, j} = g_{i, j}\) 。对于两个图的第二部分，我们有 \(g_{i + 1, j} = v_i\) 。对于 \(j = e\) 的特殊情况，代入可知仍然满足。对于左图的第三部分，我们有 \(g_{i + 1, j} = g_{i, j - count}\) ；对于右图的第三部分，我们有 \(g_{i + 1, j} = 2v_i - g_{i, T_i - j}\) 。

如何维护 \(g_i\) 呢？再次注意到 \(f\) 的凸性，在 \(i\) 固定的情况下， \(g_i\) 是非增的。于是可以直接用一个 multiset 来维护了。对于左图所示情况，直接插入 \(count\) 个 \(v_i\) 即可。对于右图所示情况，我们暴力求出所有 \(j > e\) 的 \(g_{i, j}\) ，直接塞入 multiset 里去。为什么这样可以过，我还没仔细想……

还有一个问题，如何求 \(e\) ？注意到，在 \(j\) 固定的情况下， \(g_{i, j}\) 是非降的，而我们每次比较的值却是越来越小的，也就是说 \(e\) 是非降的，一路维护过来就好了。