三气归来——我能在工程水平下降至千分之一后走出THUWC考场吗？

· · 生活·游记

Day -1

八个小时高铁到达北京西。

Day 0

上午逛了逛中关村。

两点人大附签到，下午一点半就到了。不用排队吼吼。

试机场三道题。秒了个 A+B Problem 之后对着 Linux 系统沉思，最终因为不会用 VS Code 并且忘记了编译指令遗憾离场。100/300pts。

Day 1

所以为什么 THUWC 在人大附考呢。

看 T1。线段树优化 DP 会了，一看是输出方案毁了。暴力。

T2。写了个暴力+O(n\log n) 容斥，一层循环 6 个 map，发现 n=5\times10^5 被卡了。实际/期望 17/35 分。\ T3 暴力。T4 暴力。

T1 特殊性质没写出来失去 20 pts，T2 卡常失去 18 pts。共 103/400pts。

中午拍照和前面两个浙江的考友聊了几句，吹嘘自己咕值排名。前面还有个初一小孩哥，感觉随时要被单调队列。

Day 2

一觉醒来工程能力下降为千分之一。

unsigned long long ability = pow(2ll,64);
ability /= 1000;

你怎么知道我没做过工程题的？

......

七道工程题吼吼。打开题面怎么是空的？原来在下发文件里。\ 打开一看怎么是 80 页的英语论文？原来开错 pdf 了。还有一个 11 页的项目介绍，大意是你需要开发一个人工智能翻译的解码器。

第一题给了一个什么叫做接口的东西，告诉我我的代码需要包含这个：

#include "xxx.h"
void xxx(const float *A, float *B,const int N){}

呃呃看不懂，这个*应该是传引用的意思吧？题面说 B 是用来输出的看来是这样没错了。

还没开始写就发现了问题：怎么说 A 是一个 N 维向量呃呃？小数可以表示向量吗？

沉思许久似乎想起来 * 是指针的意思？会不会可以用 *(A+i) 的形式调用其中内容？

成功了！但是怎么输出向量呢？尝试让 B 指向 vector<float> 于是 CE用同样的方法即可。

联想起用 scanf 读入数组内容时 &a[i] 和 a+i 是等价的，把 *(A+i) 替换为 A[i] 发现可过编译！真是伟大的发现吼吼。

提示可以用 <cmath> 库里的 exp 函数实现 e^x，但是交上去 CE 了两次并没有发现这个函数。只能写 pow(e,x)。

所以 e 是多少来着？

记得整数部分是 2，有个 7，有个 18281828，于是......

$e\leftarrow2.782818281828$！WA。\ $e\leftarrow2.18281828$！WA。\ $e\leftarrow2.28182818$！WA。 没有样例真是太不友好了。最后想起来可以自己求啊，于是输出 $(1+\frac{1}{10^9})^{10^9}$ 得到 $e\approx2.718281828$。 30min 通过 T1 充分展现工程实力。 T2 由 pdf 手把手教我卡常。学会矩阵乘法小技巧。说起来我还没写过矩乘，应该是省一里面线性代数最弱的人吧。 T3 开始迷惑。 “张量是一种物理概念，根据维数可以表示标量、向量、矩阵等。” “我们定义一个二维的张量 $x=[x_1,x_2,x_3,\cdots,x_N]^T\in\R^{N\times D}$......其中 $x_i$ 是一个长度为 $D$ 的向量。” “$f(x_i)$ 为 $x_i$ 的均方根，计算式子为......” “$\hat{x_i}=\frac{x_i}{f(x_i)}$，$y=\gamma\hat{x}$，后者为逐元素相乘......” ？一拳把我从义天山干到疯魔窟。 脑海中念头疯狂闪烁。“$T$ 是张量的意思么？$\hat{x}$ 是向量还是矩阵还是什么别的东西？二维的张量是如何读入的行列应如何表示？” 注意到一个公式中有一个 $x_{ij}$ 中间没打逗号。在平台上提问这个是下标 $ij$ 还是第 $i$ 行第 $j$ 列，得到回复“看定义，看题”。 裂开。 ~~召唤智慧蛊推算~~重新审视题面。输入 $\gamma$ 为 $N\times D$ 的矩阵，既然要逐元素相乘显然 $\hat x$ 也是如此。那么我们可否把 $\hat x$ 也看做成一个二维张量？那么，$\hat x_i$ 就可以当做一个向量了，向量由相同大小的向量除以一个数字得出也合情合理。输入下标问题题面中并未解答，暂时采用前一道题矩乘的写法。 **所以右上角那个 $T$ 应该是张量的意思吧。** 提交，AC。四十分钟鏖战成功解决 C 题！所以后续矩阵元素的下标表示法就应当与 B 题相同了。 开 D 再次傻眼。 “当一个向量经过一个线性层时，会做出如下输出： $$ y=x\cdot W^T+b $$ 其中 $x$ 是一个长度为 $N$ 的向量，$W$ 是一个 $M\times N$ 的矩阵，$b$ 和 $y$ 分别是偏移量和输出，均是长度为 $M$ 的向量。” 懵。一个 $1\times N$ 的向量怎么能和 $M\times N$ 的矩阵相乘？ “输入 $x$ 是一个 `N*hidden_size` 的矩阵，需要经过线性层......” 再懵。不是刚输入不是向量吗？？怎么又变成矩阵了？ 提问得知是合理的定义扩展。但是还是不知道这是怎么乘起来的。难道是把 $W$ 的横纵坐标互换？ 如果互换那么根据题意可以乘起来，但是还有一步是把经过同尺寸线性层后的输出矩阵相乘？这样再怎么转换横纵坐标都是相等的，最终根本不符合输出矩阵的尺寸要求，甚至前面的时候已经因为尺寸不对无法继续计算了。 E 题更是大尺度模拟。 发呆了半个小时。 ...... --- 难道后面的题都要爆零？ “你的工程路到此为止了。”THUWC 在我耳边轻声说道。 ...... 这......就是爆零的滋味吗？ 我终于，是要爆零了吗？ 爆零在这里？ 我的脑海中还有念头闪烁。 爆零在这里？ 我又问自己。 看完前五道题，做出前三道题，对于对工程题和线性代数一无所知的我实在是如山般的压力。 累，实在是太累了。 如果就这样结束，似乎也是一件挺不错的事情呢。 ...... 但是能吗？ 不能！ 没错，我还不能爆零！ 还有两小时，我还有概念未理清，还有 Bug 未收拾，还有错误未纠正！ 作为全校唯一一个争取到这个参与机会的人，我，也绝不能~~倒下~~爆零！ 我要振作起来，我要...... 我！要！再战！ ~~一道玄奥至极的气息，裹挟着一道真传来到他的体内。~~ ~~三气归来！！~~ --- ...... 焕发出新的斗志！虽然 E 题是大模拟，但是步骤繁多可以逐步击破。 十分钟后发现一个极关键的~~阵眼~~点位！ “$\text{position}$...是一个长度为 $N$ 的向量。$\text{freq}=\text{position}^T \cdot \text{inv\_freq}$......$\text{sin}_{i,j}=\text{sin}_{i,j+\frac{\text{dim}}{2}}=\sin(\text{freq}_{i,j})\forall i\in\{1,2,3,\cdots,M\},\forall j\in\{1,2,3,\cdots,\frac{\text{dim}}{2}\}......$” 根据前文已知 $\text{inv\_freq}$ 是一个长为 $\frac{\text{dim}}{2}$ 的向量！而由此文段 $i$ 和 $j$ 的范围可以推断 $\text{freq}$ 是一个 $N\times\frac{\text{dim}}{2}$ 的矩阵！如果上述无误，$\text{freq}$ 又由 $\text{position}^T$ 和一个 $1\times\frac{\text{dim}}{2}$ 的向量相乘可得，那么，$\text{position}$ 就只能是...\ 一个 $N\times1$ 的矩阵！ 结合尝试理解 D 题时的合理猜想，矩阵右上角加一个 $T$ 的意思必然是所有元素的横纵坐标互换！ 没有时间胡思乱想！聚精会神开始实现！ D 题 AC！！ E 题 AC！！此时还剩四十分钟！！ 斗志昂扬地查看 F 题并尝试实现这道超级大模拟。 **“......其中 $W^T$ 是 $W$ 的转置矩阵。”** ？？ ？？？？？？ ？？ 所以你就这么【数据删除】地告诉我了？困扰了我三道题的问题你就这么告诉我了？我从 C 题开始研究了两个小时的问题你就这么告诉我了？ 好吧虽然我在此之前也不知道转置矩阵是什么意思。 （红温） ...... 还剩三十分钟。\ 然后看见题面中“两个矩阵的点积”。 没学过。题面也没彻底看懂。这回是真碎了。 G 与 F 关系紧密。不做 F 必定做不了 G。 ~~工程道与线性代数道大宗师一小时体验卡到期了。~~ F 显然可以随机输出骗分，但不想做盲目的调试了。 得知大部分人的结果也就五道题，工程与线性代数都是普通境界的人临场发挥到这个水平也属实极限了。 下午没去，八小时高铁回家。还要赶期末考。 听说一等奖金牌，二三等奖银牌，鄙人不才只拿了铜牌。 ~~宿命蛊威能太过强大，待我练成春秋必成杀招卷土重来！~~ 挺好玩的。明年说不定还去。