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\) 是非降的，一路维护过来就好了。

前几个月的 UyHiP 连题解都没看……

Problem

定义一个括号序列的值为：所有括号对的深度的积。例如 ((())()) 的值为 3*2*2*1 = 12 。

求所有 \(n\) 个括号的括号序列的权值和。要求给出一个 closed-form 。

Solution

下个月再发？

其实非常简单啦。

答案非常简单，但是求一个简单的解释。

我是直接分析 dp 。首先这个题有个非常简单的 dp ： \(f_{i, j}\) 表示 \(i\) 个字符深度为 \(j\) 的积的总和。打出来后发现是有规律的……于是数学归纳法就好。

Brand 给了一个特别漂亮的解释。对于一个合法的串 S ，假设是 (()()) 吧，我们在其左边插入一个 ( ，再在其它任意一个位置插入 ) ，可以得到

• ()(()())
• (()()())
• ((())())
• ((()()))
• ((()()))
• ((()()))

注意每个串可以由很多种方式得到，而方案数恰好就是这个序列的权值。每次的 ) 插入方案数为 \(2n + 1\) ，所以总方案数 \(\prod_{i=0}^{n-1} (2i + 1)\)

某盾曰：这肯定是出题人在算 Catalan 的时候算错了然后发现是这么个东西再出出来的！

nonsense

考试后谈论分数什么的毫无意义吧。

他要考得好我就不开心，我要考得好他就不开心。总会有人不开心，何必戳破这层纸呢。

别了长沙的烟花，不知不觉来北京也有两个多月了，似乎一切还是刚来的样子。

跟风选了抽代，然后就发现我在作死了。作业答案就那么一行一句话，但是想却想了很久还不一定想得出来。 下学期的大物英电原感觉压力很大。

虽然和某人发生了奇怪的不太友好的事导致心情不好吧，但是还是有人会在我旁边的（这里得@大肉盾陪我走过不开心的时光）。我很开心有那么多的高中同学还记得我，这么信任我。

人际关系在慢慢建立中，虽然很多人都很少讲话。关系比较好的例如 hym、zhr ，当然也有关系紧张的。工作能力倒是有点低下，组长都当不好了。

参加了奇怪的赤足运动会，虽然没有拿奖，但是感觉尽力了。和@lz的两人三足，以及后来的10 * 60接力。虽然最后没分，可是也只能说尽力了。

不得不感慨THU的活动就是多。twb来宣讲，叉院各种活动，足球赛，辩论赛，虽然我没参加把，但是还是可以感觉到会占用很多时间。

阳光长跑已经开始了。三千米虽然不多，但是我也只能勉强及格的样子。每次拉着某盾去跑步，虽然速度被拖了下来但是也感觉不错。这就是所谓的存在感吧，我觉得我的存在能给别人带来一些好的改变，一些正能量，我才感受到我的存在感。（所以一开学时跟别人说找不到存在感他就不了解我对存在感的理解吧）

高中同学也组织骗几次聚餐，都感到很怀念。总能从高中同学那里找到安慰。不过那些还在所谓的怀念高中生活，说白了就是没适应大学生活吧。小伙伴们说没找到新的小伙伴，我情况也好不到哪里去。旧的不去新的不来，不要将我们忘了就好。

有人劝我不要太过于学雷锋。不过我有种心有余而力不足的感觉。看到别人不知所措，我也不知道该干些啥，只能口头上说几句安慰的话。

刷水多时间很多，自己都不知道怎么办。空间人人Feedly知乎日报主要就这几个不知道水了我多少时间。

寝室里的公共话题还是插不上嘴。大新闻什么的不喜欢造，访问量什么的不在意（那你写这篇文章的目的是啥233），奇怪的话题什么的我还未成年呢，哲学话题什么的脑子空空如也什么都编不出来。在茶园似乎奇怪的话题或者大新闻才是拉近距离的好方法，但是我都不喜欢……就这样吧。有人能相互绝对信任就好。（……包括愚人节？旧事莫提）

孤帆远影碧空尽，惟见长江天际流。

专注数论分析三十年。

暴力跑了 2min ……

如果你想享受做题的乐趣就不要看啦。。

最近被各种 Deadline 虐成狗了。

既然 PE 的题解写不了了那就翻译一下吧。

PE-441

求 \[\sum_{n=1}^N \sum_{p=1}^n \sum_{q > p, (p, q) = 1, p + q >= n}^n \frac{1}{pq}\] 。

这里的 \(N = 10^7\) 。

PE-442

一个数 \(x\) 被称为 11-free 数，当且仅当 \(x\) 的任意一个子串都不是除 1 以外 11 的幂。例如 2404 和 13431 是 11-free, 而 911 和 4121331 不是的。

求第 \(10^{18}\) 个 11-free 数。

上次被 utomaya 提醒了一遭，在五十人之前肯定是不能发题解了……

那我就来翻译吧～

Problem

PE 438 不会 >__<

Problem

令 \(d(n) = \sum_{d|n} d\) ，求 \[S(n) = \sum_{i = 1}^n \sum_{j = 1}^n d(ij)\] 其中 \(n = 10^{11}\)