普通高校招生录取流程
本文是本人对普通高校招生录取流程的整理，可能有误，欢迎指出。文中不涉及一些省份的特殊情况。
others¶
LK-99 相关链接
收录自己找到的一些和 LK-99 相关的信息，非专业人士，看个热闹。
解释 BB84 协议
背景
这周密码学课程，来自 BUPT 的高飞老师讲了一下 qkd 里的 BB84 协议，老师讲得很好，我也想记录一下这个协议的流程和方法。我不是这方面的专业人士，如果有什么问题请指出。
背景知识
QKD（Quantum Key Distribution）目的是让通信双方获得同一个密钥，它需要同时需要量子信道和经典信道。其中经典信道被认为是可信的，它可以被监听，但不能被中间人攻击。
在 BB84（Charles H. Bennett and Gilles Brassard (1984)）协议中，传输的是一个光子，它具有如下的特性：
可以用两个基去测量光子：➕️和✖️️，然后光子有四个偏振角度，分别是 ⬆️️ ⬇️️ ↘️️ ↗️️。定义一个二进制位和偏振角度的对应关系如下：
| 位 | 0 | 1 | 0 | 1 |
|---|---|---|---|---|
| 基 | ➕️ | ➕️ | ✖️️ | ✖️️ |
| 偏振角度 | ⬆️️ | ⬇️️ | ↗️️ | ↘️️ |
对于一个未知光子，可以用两种基进行测量，测量的结果：
| 偏振角度 | ⬆️️ | ⬇️️ | ↗️️ | ↘️️ |
|---|---|---|---|---|
| 用➕️测量 | 0 | 1 | 0/1 | 0/1 |
| 用✖️️测量 | 0/1 | 0/1 | 0 | 1 |
这里的 0/1 表示有 50% 概率测得 0，有 50% 概率测得 1。
协议流程
假如 Alice 要和 Bob 进行 BB84 协议。那么，Alice 首先随机生成一段二进制序列，并随机生成一个基的序列，以 Wikipedia 上的例子为例：
| Alice's random bit | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|
| Alice's random sending basis | ➕️ | ➕️ | ✖️️ | ➕️ | ✖️️ | ✖️️ | ✖️️ | ➕️ |
| Photon polarization Alice sends | ⬆️️ | ➡️️ | ↘️️ | ⬆️️ | ↘️️ | ↗️️ | ↗️️ | ➡️️ |
| Bob 生成随机的基 | ➕️ | ✖️️ | ✖️️ | ✖️️ | ➕️ | ✖️️ | ➕️ | ➕️ |
| Photon polarization Bob measures | ⬆️️ | ↗️️ | ↘️️ | ↗️️ | ➡️️ | ↗️️ | ➡️️ | ➡️️ |
| Bob 认为的二进制信息 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 通过经典信道交换信息 | ||||||||
| Shared secret key | 0 | 丢弃 | 1 | 丢弃 | 丢弃 | 0 | 丢弃 | 1 |
第一步，Alice 生成随机的二进制和随机的基，按照前面谈到过的对应关系，生成带有偏振角度的光子发给 Bob。
第二步，由于 Bob 只收到光子，不知道 Alice 选取的基底信息，而且只能用一个基测量一次，所以 Bob 随机从两种基选择一个来测量，得到了一串二进制。这些二进制里，如果 Alice 和 Bob 选取了同一个基，那么这一位的数据一定是对的；如果选取了不同的基，那么这一位有一半的可能是对的。总的来说，期望有四分之一的位是不正确的。
第三步，Alice 和 Bob 在 可信 的经典信道中把双方的基底进行对比，把基底相等的部分对应的二进制位提取出来，作为最终使用的密钥。
第四步，Alice 和 Bob 在最终使用的密钥中抽取若干位，然后对比，如果这些位都一致，则这个密码是有效的。如果错误率太高，那么很大概率是被攻击了。
安全性
协议的安全性，主要是靠量子的特性：未知量子态不可克隆、对未知量子态的测量可能会改变量子态。
假如在量子信道中间有一个 Eve 想要做坏事，它如果在中间观测了一下光子，它就会影响光子的量子态，导致 Bob 的密钥和 Alice 密钥会不一致，从而在协议的第四步被发现。并且，因为 Eve 并不知道 Alice 所使用的基底（假设 Eve 只能控制量子信道、不能控制经典信道），所以得到的二进制数据也有四分之一是不正确的。即使 Eve 尝试截获并且重发光子给 Bob，Bob 得到的密钥仍然有很高的错误率。通过这个错误率，就可以判断是否被攻击了。
另外，它的安全性还依赖以下几个方面：
- Eve 不能控制 Alice 和 Bob 的量子密码设备
- Alice 和 Bob 的随机数生成器需要足够安全
- 经典信道是可信的
引用
最近比较忙
最近一直没有更新我的 CS140e 系列文章，是因为最近一直忙于各种事情。等有空了再更新吧。
偶遇清华吴文虎教授
今天百团大战，正准备收摊的时候，天空工场那边来了一位长者，在和他们聊着什么。我很感兴趣，就上去听。老人大概已有八十高龄（后来查，是 1936 年生），但依然精神矍铄，首先和我们讲，作为工科的学生，一定在理解原理的基础上，多多去实践。他举了他自己的例子，他首先在电机系学习，后来，计算机系成立（当时还是自动控制系），他转到了计算机系，重新学起了计算机，说计算机编程学起来并没有什么难的。当年，苹果公司送过来了中国第一台 Apple-2，他们就把电脑拆了下来研究原理，又装上去继续工作。后来，他就在计算机系任教，教的正是《程序设计基础》这门课程。他十分重视实践，在第一年开课的时候就说，最关键的就是实践，安排了一些编程实验课，期中期末就是大作业。一开始有一些同学不重视实践，结果期末就挂科了。后来同学们就明白了实践的重要性，实践起来发现并没有那么难，最后就说，“吴老师，你说得对”。他又谈到了他的体育，他当年是北京长跑代表队的集训队选手，擅长一千五百米项目，他三千米只需要九分钟就能跑完。我们都感到自愧不如。我们说，现在的《程序设计基础》是徐明星老师在教，他说徐明星是他的博士生，邬晓钧也是他的博士生，他另外还有一个高徒我记不清楚了。他还是 IOI 中国队的前教练，听到我们有过一些 OI 基础，表示了赞许和鼓励。还有一些细节记不清楚了，记起来了再补充吧。
用 CPUID 获取评测机器的 CPU
受用 CPUID 检测各大 OJ 测评机所用的 CPU（以及日常黑 BZOJ）的启发，我决定去测试一下徐老师自己写的 OJ（名为 Tyche）所跑的机器是什么 CPU。于是我改造一下代码，用以下代码测评：
#include <stdint.h>
#include <iostream>
#include <time.h>
#include <cpuid.h>
#include <sys/time.h>
static void cpuid(uint32_t func, uint32_t sub, uint32_t data[4]) {
__cpuid_count(func, sub, data[0], data[1], data[2], data[3]);
}
int main() {
uint32_t data[4];
char str[48];
for(int i = 0; i < 3; ++i) {
cpuid(0x80000002 + i, 0, data);
for(int j = 0; j < 4; ++j)
reinterpret_cast<uint32_t*>(str)[i * 4 + j] = data[j];
}
struct timeval stop, start;
gettimeofday(&start, NULL);
while(1) {
gettimeofday(&stop, NULL);
if(stop.tv_usec - start.tv_usec > (str[##EDITME##] - 32) * 10000)
break;
}
}
经过测试，usleep()和clock()都被封杀，但是gettimeofday()存活了下来。然后我就不断地C-a上面的###EDITME###，根据评测出来的时间推算出字符串，然后得到以下结果：
0 ~ 7 : PADDING
8 73 I
9 110 n
10 116 t
11 101 e
12 108 l
13 40 (
14 82 R
15 41 )
16 32 SPC
17 67 C
18 111 o
19 114 r
20 101 e
21 40 (
22 84 T
23 77 M
24 41 )
25 32 SPC
26 105 i
27 51 3
28 45 -
29 50 2
30 49 1
31 50 2
32 48 0
33 32 SPC
34 67 C
35 80 P
36 85 U
37 32 SPC
38 64 @
39 32 SPC
40 51 3
41 46 .
42 51 3
43 48 0
44 71 G
45 72 H
46 122 z
连起来就是这个 CPU：
相比之下，还是比 BZOJ 好哈哈哈（又黑 BZOJ）。后来有大神在群里建议，可以用字符串比较的方式，对了就让题目 AC，不对就 WA。这个方法更加适合手里已经知道了一些常见 CPUID 的返回字符串，这里就是这样。
一个代替 Pulse Secure 客户端的工具
清华的校外 VPN 服务使用的是 Pulse Secure，所以在外网我们需要在客户端上安装 Pulse Secure 才能使用内网的 info 和网络学堂等网站。但是 Pulse Secure 一是非自由软件二界面难看，所以我找到了一个代替它的工具：OpenConnect.
安装后，输入以下命令：
sudo openconnect --user 你的学号 sslvpn.tsinghua.edu.cn --juniper --reconnect-timeout 60 --servercert sha256:398c6bccf414f7d71b6dc8d59b8e3b16f6d410f305aed7e30ce911c3a4064b31
然后输入你的 info 密码即可。
一个搞笑的伸展树的 Wiki
光哲同学在群里发了这个链接，特别搞笑，特此分享： 伸展树 - 百度百科
伸展树（Spaly Tree，事实上在国内 IO 界常常被称作 Tajarn 发明的 Spaly Tree，与此同理的还有 Terap），也叫分裂树，是一种二叉排序树，它能在 O(n log n) 内完成插入、查找和删除操作。它由 Daniel Sleator 和 Robert Tajarn 发现，后者对其进行了改造。它的优势可以不断伸展枝干（一个月 2~3 次），从而使树冠散开，提高光合作用效率。木材坚硬，是重要的经济类乔木。与其他植物不同的是，伸展树可以进行出芽生殖，繁殖速度极快。
回顾昨天的酒井知识竞赛
昨天晚上，我作为蒟蒻组的一员在三教 2102 参加了酒井知识竞赛，并因此鸽掉了 TUNA 和 Lab mU 的迎新会 hhh，不过运气好拿到了二等奖的好成绩，获得 Paperang 便携打印机一台。中间遇到了好一些网络方面的知识，这对于没有记忆 OSI 模型的我无疑有巨大的难度。下面是几道比较有印象的题目：
- 以下哪个不是编程语言？ A. J B. L C. R D. K 这题不难，R 肯定对，J 见过，K 略微有印象，选 B
- IPv6 链路层地址解析的协议是？ A. ARP B. Neighbour Solicitation C. Neighbour Advertisement D. Neighbour Discovery 对于一个没研究过 IPv6 的人来说这只好蒙了。。。ARP 是 IPv4 时代的，ND(Neighbour Discovery 则是 IPv6 时代的新产物，把 ARP 和 ICMP 等协议的功能都包含了进来，并且有新的功能。之前样题里还出现过问 IPv6 中去掉了 Unicast,Anycast,Multicast,Broadcast 中的哪种，答案是 Broadcast。
- 第一个把程序错误称做 bug 的是？ 选项太多忘了，答案是 Grace Hopper，因为当时一只飞蛾意外飞入了机器导致了故障，后来慢慢就流传下来了。
- 以下不是网络操作系统的是？ A. Windows NT B. OS/2 warp C. DOS D. Netware 当时我没见过 D，于是就选了。。。然后就挂了，Netware 是 Novell 开发的系统，OS/2 warp 当然是历史悠久的系统啦，而 DOS=Disk Operating System 所以没有“网络”二字。。。晕倒
- 以下是用作局域网的协议是？ A. TCP/IP B. IPX/SPX C. NetBEUI D. RS-232-C TCP/IP 当然不仅限于局域网，RS-232-C 是接口，当时蒙了 B 结果就对了，白白拿了 50 分哈哈哈。IPX/SPX 是 Novell 设计用在 Netware 系统上的局域网协议，NetBEUI 则是 NetBIOS 的一个历史遗留的一个“别称”。
- 姚期智的夫人给谁取了中文名？ 当然是 Donald Ervin Knuth 啦！高德纳万岁！
等时圆
最近学校老师讲了一下等时圆。先从这个题讲起：
在同一个地方向不同倾角光滑斜面用不同的初速度上滑，到达最高点所用时间相等，求最高点的轨迹是什么？
A. 直线 B. 椭圆 C. 抛物线 D. 圆
当时做这个题目的第一想法是把 x 和 y 座标表示出来：
\[
\frac{1}{2}gsin\theta{}t^2=l,
y=lsin\theta,
x=ycot\theta
\]
然后就傻眼了，并得不到 x 与 y 的关系式。当然了可以求出几个点，强行带入二次曲线通式求解。不过想了想还是用解析几何的方法去做吧：
\[
\frac{1}{2}gsin\theta{}t^2=\sqrt{x^2+y^2},
sin\theta=\frac{y}{\sqrt{x^2+y^2}}
\]
这么一代入，显然是圆。但既然这是物理题，可不可以用物理方法做呢？
可以，这就是等时圆。
啥叫等时圆？
等时圆就是，在一个光滑圆环上选择任意一点，让一个小球从这个点沿着光滑直杆到圆的最低点，无论这个点在哪里（最低点不算哈），时间都是一样的。怎么证明？
很简单：设小球与最低点连线与数值方向上夹角为\(\(\theta\)\)，那么
\[
s=2Rcos\theta,
\frac{1}{2}gcos\theta{}t^2=s
\]
你会发现 t 与\(\(\theta\)\)无关。证明完毕。
其实也可以倒过来：从圆的最高点往各个方向下滑，到达圆周时间相等。
好了，到此为止内容都没什么，但你会想问这和前面那道题目有什么关系呢？这怎么等时圆？重力往下诶。运动可是往右上方。
Here comes the black magic :)
我们考虑向下滑到最低点的那个等时圆，在这个圆周上滑倒最低点的时间都相等。好，我们把这个图沿着竖直方向旋转 180 度形成一个球，想想这个球上每一个点到最低点时间是不是也一样？那么考虑逆过程，让小球从斜面上滑下来，我对刚才的球体再竖着切一刀，得到的平面不就是题目中那个吗？得证。
当然了最好能有动画说明，限于本人时间问题暂时不提供 ^_^
Start next term tomorrow
My term starts tomorrow. Sad. Homework haven't finished. I went to Guangzhou for GDKOI thie weekend, and i haven't known the result. It should be bad. I have no confidence at all. I may write less when this term starts. The second term of Senior 2 should a hard time for me. That's all. Sorry for the laziness.