一面

依图是真的只面算法题，感觉回答的不太好，凉凉。

• 先自我介绍一下吧
• 比赛中印象中比较深的题？
• 快排、归并、堆排那个快？
• 基环树找环上的一个点（写代码）。
• 给出两个非负整数 a 和 b ($a, b \le 10^9$)，进行 $10^{18}​$ 次操作，每次操作让小的数变为二倍，并且让大的数变为 a + b - 2 * a (假设 a 为较小的数)。

最后一个题知道解法后很简单，考虑最大的那个数做的变化，就是在 a + b 同余系下的乘二运算。

二面

没想到一面居然过了，之前面试完感觉凉凉，第二个问题疯狂提示才做出来。

• 算法题

  • N 个数，其中一个只出现一次，其他出现两次，找出出现一次的数。

    异或和。

  • N 个数，其中两个只出现一次，其他出现两次。

    异或和后，按二进制的任意一个非零位划分，然后再求异或和。

• 从 cache 的角度优化矩阵乘法。

  • 先写个矩阵乘法。

    1 2 3 4 5 6 7 8 9 10

    void mat_mul(float *A, float *B, float *C, int N) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { C[i * N + j] = 0; for (int k = 0; k < N; k++) { C[i * N + j] += A[i * N + k] * B[k * N + j]; } } } }

  • 考虑访问 B 数组时，下标不是连续访问，进行优化。

    1 2 3 4 5 6 7 8 9 10

    void mat_mul(float *A, float *B, float *C, int N) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { C[i * N + j] = 0; for (int k = 0; k < N; k++) { C[i * N + k] += A[i * N + j] * B[j * N + k]; } } } }

  • 考虑对于每一个 i 每次要遍历整个 B 数组，如果 cache 不能完整存下整个 B 数组时，cache 命中率可能会比较低。

    1 2 3 4 5 6 7 8 9 10 11 12

    void mat_mul(float *A, float *B, float *C, int N) { for (int jj = 0; jj < N, jj += BLOCK) { for (int i = 0; i < N; i++) { for (int j = jj; j < min(jj + BLOCK, N); j++) { C[i * N + j] = 0; for (int k = 0; k < N; k++) { C[i * N + k] += A[i * N + j] * B[j * N + k]; } } } } }

    加入分块优化，每次只计算 B 矩阵的 BLOCK 行对答案的贡献。（这里被面试官疯狂提示才理解）

• 聊下你的项目吧，你选择聊哪一个？

  Web 聊天室，主要用到了多线程，线程间通信，网络编程技术。主要功能是客户端向服务器发送消息，服务器对所有客户端进行广播消息。服务器维护一个消息队列，存储客户端发送的消息，并使用互斥锁保证安全。

  • 你的服务器大概能承载多少用户，如何扩大承载量？

    我认为关键要优化服务器中的消息队列，多个线程对同一个元素进行互斥访问的效率特别差，我们考虑对每一个客户端开一个消息队列进行优化。（面试官提示了为了保证消息的顺序加一个时间戳比较好）

  • 你认为你这个项目中遇到的最难的问题是什么？

    WebSocket 协议的实现，刚开始我以为 WebSocket 协议和 TCP socket 一样，两者可以直接通信，后来才了解到 WebSocket 是一个应用层协议，需要对 TCP 协议进行分组，然后差了许多资料，包括 WebSocket 协议的数据帧，如何从 HTTP 协议升级到 WebSocket 协议等。

• 我没有问题了，你有问题问我吗？

  • 进入公司后，我大概能学到什么东西，公司有什么培养计划？
  • 依图里是不是有好多 ACM 竞赛选手？

一面

其实前一天就接到了电话，问了一下 ACM 获奖情况，对游戏开发的了解，最后问了一个 interesting 的问题，「王者荣耀怎么实现同步」，因为之前了解过同步机制并且实现过一个状态同步，于是稍微讲了一下，然后当晚在外面吃饭于是说明天下午面试了。

面试官刚开始就直接说了，我这几年几乎都在打 ACM-ICPC 比赛，于是先面数据结构和算法了。

• STL 容器使用过吗，deque 了解吗，他支持在首位插入删除和随机访问，你考虑过怎么实现吗？

  我在竞赛中实现过，开一个特别大的数组，并且使用指针指向数组的中央，一个首指针一个尾指针，并且通过首指针加一个偏移量实现随机访问。

• 当储存空间不够时怎么办？

  使用类似于 vector 的方式进行扩容。

• 如果按你这种方式，如果一直插入到首部，后面的好多空间没有用到，有优化方式吗？

  写一个循环队列，例如当首指针达到边界时，让他移到尾部，这样就可以利用全部的存储空间。

• 考虑游戏服务器的高并发场景，假设这个容器我 push 了许多元素之后又 pop 了许多元素，怎么回收空闲的内存？

  因为直接申请一整块内存的话，不容易直接回收部分内存，可以考虑牺牲一部分效率，使用一种块状链表的结构去实现 deque。

• 那你考虑过可以不使用链表这种结构去实现这个功能吗？

  emmm 接下来的问题没有答上来。

• 考虑有一个定时器，他到达某个时刻的时候会执行某个 callback，假设我现在需要一个容器去储存这些定时器，并且一直要查询有没有定时器需要执行，你会使用什么样的数据结构？

  可以用一个小根堆，并且把时间当作 key 来排序，那么堆顶的元素就是时刻最早的，每次可以 $O(1)$ 的查询堆顶。或者使用二叉平衡树也可以实现这个功能，查询是 $O(\log n)$的。

• 讲一下堆和二叉平衡树的删除操作吧，假设我有一个指向堆 or 平衡二叉树的指针，怎么高效的删除这个节点？

  emmm，因为比赛很少遇到这种情况，我只好和面试官讲了下 Splay 这种数据结构…感觉回答的不是很好。

• sort 了解过吗，你们比赛中怎么使用 sort，关于他的 < 语义或者比较函数有什么要求吗？

  基本上就用 std::sort 了，如果要求稳定排序的话把下标当作第二关键字用就好咯。关于比较函数的要求，数学上是要求定义一个严格的弱序关系，我当时说的是两个条件，可传递，并且非对称，a < b and b < c then a < c, a < b 和 b < a 有且只有一个条件成立。

• map 使用过吗，unordered_map 和 map 有什么区别？

  map 使用红黑树来实现的，我只了解过各种接口的复杂度，不清楚内部实现。unorder_map 使用哈希表来实现。

• 你可以自己实现一个 unordered_map 吗，讲一下怎么实现？

  最简单的一种实现就是开一个桶，然后用桶的大小对 hash 后的 value 取模，然后放入桶里面。

• 如果有 hash 碰撞怎么解决？

  开一张链表。

• 如果 hash 碰撞太高了怎么优化？

  可以从两方面入手，一个是 hash 函数本身的优化要做好。另外一点面试官提示了我一下，其实就是鸽巢定理，10 个抽屉放 11 个球，那么至少有一个抽屉有两个及以上的球。当我放入 100 个元素到 大小为 10 的 hash 表中，那么是很容易 hash 碰撞的。这时候我考虑了用之前的方法，对桶进行扩容，这里继续沿用 vector 的方式就 ok 了。

• 你了解过多线程吗，怎么实现一个线程安全的 hash 表？

  我了解过互斥锁，可以考虑给每个元素加一个互斥锁。

• 那我插入时，需要修改一个链表的结构，发生了冲突怎么办？

  给每个链表加一个互斥锁…

• 那我插入的时候，hash 表需要扩容怎么办？

  增加一个变量，用来标志当前是否正在扩容，如果扩容就让所有的插入查询操作阻塞。

• 这样扩容会阻塞掉所有的访问，有更好的做法吗？

  可以将扩容的锁放到每个链表上，然后这样扩容时只阻塞掉正在移动的元素。

• 好的接下来做一个编程题吧，逆转一个字符串？

  水题…

• 逆转单词？ hello world -> world hello

  水题，面试官要看如何分割字符串，于是简单的写了一下，被吐槽代码不规范了 orz。

• 加权随机数？给定一个权重表 [2, 1, 3, 5, 4]，编写一个输入函数 rand_select(weight[])，返回一个 1 - len(weight) 的整数，这个数是随机的，并且保证出现 0, 1, 2 ,3 ,4 , 5 的概率之比为 2, 1, 3, 5, 4。

  写了两个做法，思路都是把权重当作一个区间，然后根据权重区间长度不同，random 从总区间长度中选一个数，落到那个区间中，就把那个区间的编号当作随机的答案。

• 你有什么问题问我吗？

  • 假设我能实习的话，我能学到什么内容，在后台开发岗位的话？
  • 我的表现怎么样，有什么不足的地方？
  • 有什么开源项目推荐吗，或者好数推荐？

二面

感觉二面回答的不是很 OK，感觉凉凉的，但是官网上没给挂。

整体面试官问的问题比一面的多，并且贴近底层和基础，节奏也比较快，最后自己被问的有点懵，后面也没问面试官什么问题就结束了。

• vector 怎么实现？

  动态申请内存，然后倍增扩容。

• 考虑过怎么收缩空间吗？

  提供一个接口函数，重新分配一块恰好的空间。

• 如何使用这个 vector 储存不同大小的数据？

  vector 不直接储存数据，储存指针。

• 怎么用你实现的 vector 实现一个 queue ?

  queue 不用随机访问，我感觉使用链表来实现比较好，使用两个首尾指针。

• sort 算法了解过吗，std::sort 怎么实现的？

  因为 quick sort 是平均复杂度比较好，最差情况能退化到 $O(n^2)​$，具体 STL 源码我没有看过，了解过他使用多种排序结合的方式，比如对于大区间使用什么排序，小区间怎么排序，并且进行随机化，避免最差情况。

• C++ 了解吗，我在两个文件中定义了两个完全相同的函数有没有错？

  编译不会报错，当链接的时候会发生 redefine 错误。

• 怎么避免这个错误？

  使用命名空间或者 static 关键字。

• 模板了解过吗？

  了解过，但没怎么写过代码（然后面试官不继续问了…其实我想让他问一些的）。

• extern 关键字了解过吗？

  可以引用其他文件的变量，具体没怎么用过，竞赛一直写的单文件。（然后面试官不问 C++ 了 orz）

• 操作系统熟悉吗？

  熟悉，最近刚看完 CSAPP 感觉收获很多。

• 解释一下程序如何执行的吧，从命令行输入可执行文件开始。

  首先操作系统分配好程序运行的上下文环境，例如虚拟内存、页表、CPU 寄存器、堆栈等，将文件映射到内存中，然后处理器找到程序的入口地址，并且运行，通常刚开始执行第一行代码时发生缺页中断，然后 CPU 将硬盘中数据载入主存中。

• 可执行文件格式了解过吗？

  了解过 Unix 系统的 ELF 文件格式，影响比较深的有可重定向目标文件和可执行目标文件，通常编译后生成可重定向目标文件，链接后生成可执行文件。这两类文件大同小异，内部通常分为许多个段，主要有符号表，程序代码，全局变量等。对于可重定向目标文件，还会有一些需要重定向的变量、代码段。

• 解释一下链接过程吧？

  我认为链接过程就是将许多可重定向文件或静态库文件合并成一个可执行文件的过程，会把各个文件的代码、全局变量等数据段合并到一起。链接过程中会依次扫描每个文件，并且为引用但为定义的代码定位地址。

• 下面问你一个开放性问题，考虑有 100 个 10 万人的服务器，如何维护一个实时的全服排名？

  首先肯定要考虑并行，不能单线程处理所有服务器的访问的。这样我们根据排名划分成不同的数据段，用不同的服务器来维护，并且设置一个容易并行的代理服务器转发请求到下级储存数据的服务器。考虑到并发的话可以继续让服务器分级，直到划分为一个可以接受的程度。

• 假设有一个人反复改变自己的排名，考虑如何优化？

  这个好难啊…（然后面试官直接不问了…感觉应该随便说一下比较好的）

• 下面问个算法题，给 1000 万个手机号排序？

  直接基数排序吧，手机号 11 位的话时间复杂度就是 $O(11 \times 1000)$ 咯。或者插入到字典树中，然后遍历一遍也 ok。

• 好的我没有其他问题问你了，那….

  直接被问的自闭了，这里抢答了，“那，再见”。然后面试官就说了下再见就结束了。（感觉他可能是要说 “那你有什么问题问我吗”）

三面

隔了两周才接到了电话，面试官说大概只用二十分钟就 ok，然后就直接开始面试了。

• 你为什么参加 ACM 竞赛?

  一是为了可以和别的学校更更强的人同台竞技，二是本身就喜欢算法和数据结构。

• 你认为 ACM 竞赛中那些可以应用到工程中？

  应该是经典的数据结构和算法吧，对于一个工程的需求，我可以考虑用哪种算法和数据结构，可以实现怎样的时间复杂度和空间复杂度。

• 你学校课程中比较喜欢那几个?

  操作系统和计算机网络。

• 你认为编译原理中的知识对你有用吗？

  我认为我最受用的知识是状态机，在竞赛中就用到了 AC 自动机，SAM 等字符串自动机。另外工程中，服务器 IO 复用可以建立状态机的模型进行编程。

• 你讲一下从客户端发送一个 TCP 包到 服务器吧。

  首先先给需要发送的数据加上 TCP 首部，其中包含端口号、序列号等信息；然后将 TCP 包递交给网络层，网络层会加入 IP 首部，其中包括 IP 地址、校验和等信息；然后通过数据链路层发送出去。

  服务器收到数据包后递交给网络层，网络层拆掉 IP 首部，并且进行简单的校验，并且递交给传输层；传输层收到后拆掉 TCP 首部，并且验证数据包的是否正确（损坏、失序等），验证通过后讲数据包递交给对应端口号的程序。

• 子网掩码和网关了解吗？

  解释了一下子网掩码，因为之前都在看运输层，

• 那聊一下操作系统吧，介绍一下进程和线程吧？

  进程是操作系统进行分配资源的基本单位，线程是 CPU 调度的基本单位。（面试官问了一下用户态线程了解吗…直接没听说过）

  然后聊了下虚拟内存，进程间通信和线程通信。

• 总结

  面试官就直接说你基础不怎么好，如果我这过了的话，下一次就是 HR 面了。如果来实习的话一定要多看看基础知识，Unix 网络编程和 Unix 环境高级编程不错你可以看一下。剩下如果来的话需要补很多基础知识很费时间。

  这两本书正好前几天刚买，面试官说的东西正好是最近刚看的，如果能有实习的话，就安心啃书了。

HR 面

• 自我介绍一下。
• 为什么参加 ACM 竞赛？
• 参加比赛的时候怎么学习？
• 印象最深的比赛？
• 聊聊你的项目。
• 为什么选择我们事业群？
• 喜欢游戏吗？
• 个人状况 balbalbala…
• 你有什么问题问我吗？
  • 我的岗位大概是什么事业群？

一面

一定要找一个稳定的网络面试！！！

通过牛客网进行的视频面试，本地测试的时候特别稳定，然后和面试官面试的时候网络就特别差，之后让面试官等了一下才开始的正式面试。

首先面试官先说要自我介绍一下，就说了一下自己的姓名、学校、学院、专业班级之类的，提了下从大一开始打 ACM 的经历。

然后面试官就开始问我 C++ 学的怎么样，我说还可以，然后就开始问对 C++11 了解吗，我提到了比赛中只用到过 auto 关键字和范围 for 遍历，又说了一下智能指针、lambda 表达式只了解过但是没实际用过。

接下来就开始问我智能指针有三种，分别介绍一下他们，这里我忘记了第三种的 weak_prt 了，就直接开始介绍 shared_ptr 和 unique_ptr ，提了下 unique 和 shared 的最大区别在于 unique 不能拷贝，然后面试官问我怎么实现不能拷贝，就是直接把拷贝构造函数和拷贝运算符删掉就 ok 了。

之后我提了一下右值引用（我也忘记是怎么提到的了），然后面试官问我右值引用大概是什么东西，为什么要用得到右值引用。我感觉右值引用就是引用右值吧，介绍了下右值的特点。

之后问了我学校集训队的情况，人数和队内的情况怎么样，自己擅长哪方面的算法之类的。我提到我擅长数据结构、动态规划，然后接下来就给我了一道算法题。

给出一个 n 行 m 列的矩阵，每个位置有 1 或 0，1 代表可以放棋子，0 不能放，任意两个棋子不能相邻放（四连通），问有多少种放的方案。 $n, m < 13$

数据范围这么小，考虑从左上往右下依次放的话，每个棋子只考虑他上方和他左方的棋子就好了，然后考虑转移的话，只需要维护一条轮廓线的状态，大概 $O(n \cdot m \cdot 2^m)$

但是写起来太麻烦了，当时没写出来，和面试官说了一下思路就开始接下来的问题了。

因为我简历中写了一个通过 WebSocket 实现的聊天室，然后面试官问了一下我 WebScoket 协议的工作原理，以及实现方式。使用 WebSocket 协议首先通过发送一个 HTTP 请求将当前协议切换成 WebSocket 协议，大概类似于握手的一个过程，前端我是直接使用的 JavaScript 的 Socket.io 库，后端通过 Python 的 Socket 实现了 WebSocket 协议。

随后问了多线程了解的怎么样，我和他说了一下我上面聊天室项目中多线程的应用，提了下为什么 Python 多线程只对 IO 密集型有用，顺便提了下之前使用多线程优化 Sort。

然后问我编译原理学的好吗，我就直接说考的挺好，但是学的不怎么样，然后就没继续问了。

之后问我对游戏开发感兴趣了，我就聊了一下之前做过一个 H5 的飞机大战游戏，并且看了一下游戏如何实现同步。

最后面试官问我有什么问题问他吗，我就问了他们公司后端开发需要学那些技术，他告诉我他们后端基本上都是自己写的，不用什么框架，甚至开发了自己的一套脚本语言。然后我问了下厦门和深圳那个地方好，薪资啥的。

二面（HR 面）

很意外这次直接是 HR 面，感觉一般要有个三面甚至到四面才到 HR 面的样子，面试的昨晚我还担心一面的时候没有问多少基础问题，二面的时候会不会着重问很多基础问题，又翻了一晚上书…

• 大学期间都在做什么情况，全部都在参加 ACM 比赛吗？

  从大一就开始打比赛，一直持续到大三上学期打完最后一个赛季。

• 你认为参加 ACM 比赛，最大的收获是什么？

  我认为最大的收获是锻炼了自己的自学能力，比如好多高级算法都是要自己去翻博客，啃论文。

• 你当时为什么要参加 ACM 比赛？

  • 第一点因为 ACM 是一个竞赛，参加这样一个竞赛，就有很多次机会去和其他高校非常厉害的人去切磋竞争，能够认识到自己的水平和不足。
  • 我喜欢算法和难题，并且在竞赛中能思考并解决一些很有意思的问题。
  • 我喜欢 ACM 集训队的氛围，大家一起讨论难题、学习算法，以及可以认识很多厉害的人。

• 关于你的第一个投票系统，有没有考虑过各种用户需求等？

  没有，只是一个简单的 demo。

• 你喜欢游戏吗，最近在玩什么游戏？

  特别喜欢，从小就开始玩……直到现在玩……（省略好多字，讲道理如果和我聊游戏的话，我能聊一上午的）

• 你大概可以持续工作多长时间？

  从暑假开始可以实习，理论上持续多久都可以。

• 你希望进入一家怎么样的公司？

  喜欢公司的办事效率高一些，自己身边的同事都喜欢热爱技术。

• 有没有投其他公司？

  投了，腾讯，头条等。

• 有没有女朋友？

  没有（然后 HR 说就不用考虑异地的问题了）。

• 你有什么问题问我吗？

  • 如果我获得实习机会，我会在什么岗位？

  • 至少工作几个月，每周工作时长？

  • 有没有转正机会？

  • 实习工资？

    （可能涉及公司信息，以上 HR 回答不写了，感觉实习的时候一定要问清楚上面四个问题）

01分布

$$P{X = k} = p^k(1-p)^{1-k}, k=0,1$$

$$E(X) = p$$

$D(X) = p(1 - p)$

二项分布 $X\sim b(n, p)$

$$P(X = k) = \binom{n}{k}p^k(1 - p)^{n - k}, k = 0, 1, 2\cdots n.$$

$E(X) = n p$

$D(X) = np(1 - p) $

泊松分布 $X\sim \pi(\lambda)$

$$P(X = k) = \frac{\lambda^ke^{-\lambda}}{k!}, k = 0, 1, 2\cdots$$

$$E(X) = \lambda$$

$$D(X) = \lambda$$

均匀分布 $X\sim U(a, b)$

$$f(x)=\begin{cases}\frac{1}{b-a},&a<x<b \0,&else \end{cases}$$
$$E(X)=\frac{a+b}{2}$$
$$D(X)=\frac{(b-a)^2}{12}$$
$$F(X)=\begin{cases}0,&x<a\\frac{x-a}{b-a},&a\le x<b\1,&x\ge b\end{cases}$$

指数分布

$$f(x)=\begin{cases}\frac{1}{\theta}e^{-x/\theta},&x>0 \0,&else \end{cases}$$

$$E(X) = \theta$$

$$D(X) = \theta^2$$

$$F(X)=\begin{cases}1-e^{-x/\theta},&x>0\0,&else\end{cases}$$

正态分布 $X\sim (\mu, \sigma^2)$

$f(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}, -\infty<x<+\infty$

$F(X) = \frac{1}{\sqrt{2\pi}\sigma}\int^x_{-\infty}e^{-\frac{(t-\mu)^2}{2\sigma^2}}\text{d} t$

$E(X) = \mu$

$D(X) = \sigma^2$

$F(X) = P(X \le x) = \Phi(\frac{x-\mu}{\sigma})$

ST表

ST 表可以 $O(N\log N)$ 的预处理一位的区间信息，然后 $O(1)$ 的进行查询。

二维 ST 表类似，可以 $O(nm\log n \log m)$ 的预处理一个二维矩阵的子矩阵信息，并且 $O(1)$ 的查询。

代码

下面拿 CF713D 为例，题目需要维护二维的区间最大值。

ans[i][j][a][b]的含义为以 $(i, j)$ 为左上角 $(i + 2^a - 1, j + 2^n - 1)$ 为右下角的子矩阵的区间信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1005;
const int INF = 0x3f3f3f3f;

int data[MAX][MAX], dp[MAX][MAX], csum[MAX][MAX], rsum[MAX][MAX];

int n, m;

void solve() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (data[i][j]) {
                rsum[i][j] += rsum[i - 1][j] + 1;
                csum[i][j] += csum[i][j - 1] + 1;
            } else {
                rsum[i][j] = csum[i][j] = 0;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = data[i][j] ? 1 : 0;
            if (dp[i - 1][j - 1]) {
                int v = dp[i - 1][j - 1];
                int c = csum[i][j];
                int r = rsum[i][j];
                dp[i][j] = min(v + 1, min(r, c));
            }
        }
    }
}

int low_log[MAX];

void init() {
    int cnt = 0, now = 1;
    for (int i = 1; i < MAX; i++) {
        if (now * 2 <= i) cnt++, now *= 2;
        low_log[i] = cnt;
    }
}

int ans[MAX][MAX][10][10];

void cal() {
    for (int x = 0; x < 10; x++) {
        for (int y = 0; y < 10; y++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (x + y == 0) {
                        ans[i][j][0][0] = dp[i][j];
                        continue;
                    }
                    int dx = x > 0 ? (1 << (x - 1)) : 0;
                    int dy = y > 0 ? (1 << (y - 1)) : 0;
                    int ox = max(0, x - 1);
                    int oy = max(0, y - 1);

                    int A = ans[i][j][ox][oy];
                    int B = i + dx > n ? 0 : ans[i + dx][j][ox][oy];
                    int C = j + dy > m ? 0 : ans[i][j + dy][ox][oy];
                    int D = (i + dx > n || j + dy > m) ? 0 : ans[i + dx][j + dy][ox][oy];

                    ans[i][j][x][y] = max(max(A, B), max(C, D));
                }
            }
        }
    }
}

int query(int x1, int y1, int x2, int y2) {
    int px = low_log[x2 - x1 + 1];
    int py = low_log[y2 - y1 + 1];
    int dx = (1 << px) - 1;
    int dy = (1 << py) - 1;
    return max(max(ans[x1][y1][px][py], ans[x2 - dx][y1][px][py]),
               max(ans[x1][y2 - dy][px][py], ans[x2 - dx][y2 - dy][px][py]));
}

bool ok(int mid, int x1, int y1, int x2, int y2) {
    if (mid == 0) return true;
    return query(x1 + mid - 1, y1 + mid - 1, x2, y2) >= mid;
}

int main() {
    init();
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &data[i][j]);
        }
    }
    solve();
    int q;
    scanf("%d", &q);
    cal();
    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        int l = 0, r = min(y2 - y1 + 1, x2 - x1 + 1), ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (ok(mid, x1, y1, x2, y2)) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        printf("%d\n", ans);
    }
}

区间第K大

题目完全没有弯，就是区间修改，询问第 K 大。

但是 K 特别小，我们考虑用线段树去维护这个东西，线段树每个节点维护当前区间的前 K 大的数。

首先区间修改操作还是用 Lazy 去做就 OK，打 Lazy 标记的时候把前 K 大的值同时修改，然后我们考虑第 K 大怎么维护。

考虑左右两个区间的信息合并，假设左右区间已经维护了前 K 大的数，那么左右区间合并后的前 K 大的数显然等于这两个区间前 K 大的数降序排序取前 K 个。

然后这个题就做完了，复杂度$O(k\cdot q\cdot \log(n))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 100;
const int INF = 0x3f3f3f3f;

struct Node {
    vector<int> v;
    int lazy;

    Node() {
        lazy = 0;
        v = vector<int>();
    }

    void maintain(int d) {
        for (auto &x : v) x += d;
        lazy += d;
    }

    Node operator+(const Node &t) {
        Node rst;
        rst.lazy = 0;
        for (auto x : v) rst.v.push_back(x);
        for (auto x : t.v) rst.v.push_back(x);
        sort(rst.v.begin(), rst.v.end(), greater<>());
        if (rst.v.size() > 5) rst.v.erase(rst.v.begin() + 5, rst.v.end());
        return rst;
    }
} tree[MAX << 4];

#define lson (o<<1)
#define rson (o<<1|1)
#define MID int m = (l + r) >> 1

void push_down(int o) {
    if (!tree[o].lazy) return;
    int &lazy = tree[o].lazy;
    tree[lson].maintain(lazy);
    tree[rson].maintain(lazy);
    lazy = 0;
}

void update(int o, int l, int r, int ql, int qr, int v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        tree[o].maintain(v);
        return;
    }
    push_down(o);
    MID;
    update(lson, l, m, ql, qr, v);
    update(rson, m + 1, r, ql, qr, v);
    tree[o] = tree[lson] + tree[rson];
}

Node query(int o, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return Node();
    if (ql <= l && r <= qr) return tree[o];
    push_down(o);
    MID;
    return query(lson, l, m, ql, qr) + query(rson, m + 1, r, ql, qr);
}

int A[MAX];

void build(int o, int l, int r) {
    tree[o] = Node();
    if (l == r) {
        tree[o].v.push_back(A[l]);
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m + 1, r);
    tree[o] = tree[lson] + tree[rson];
}

int main() {
    int n, q;
    while (~scanf("%d %d", &n, &q)) {
        for (int i = 1; i <= n; i++) scanf("%d", A + i);
        build(1, 1, n);
        while (q--) {
            int o, l, r, v;
            scanf("%d %d %d %d", &o, &l, &r, &v);
            if (o == 1) update(1, 1, n, l, r, v);
            else printf("%d\n", query(1, 1, n, l, r).v[v - 1]);
        }
    }
}

QAQ子串

我们考虑至少包含 QAQ 的子串比较难求，所以我们反过来考虑，求不包含 QAQ 子串的字符串。

那么这是一个常见的动态规划问题。

我们定义 $dp[i][j]$的含义长度为 $i$，并且结尾的状态为 $j$ 的方案数。

定义状态 $0$ 为不构成 QAQ 任何前缀的结尾，比如 “QAAA”、“bLue”、“UMR” 等。

定义状态 $1$ 为以 Q 字符为结尾，比如 “QWQ”、“QvQ” 等。

定义状态 $2$ 为以 “QA” 为结尾，比如 AQA”，“AQQA” 等。

状态 $0​$ 可由状态 $0​$ 或状态 ‘2’ 加上任意非 ‘Q’ 的字符转移而来，或由状态 $1​$ 加上任意非 ‘Q’ 且非 ‘A’ 的字符转移而来。

状态 $1$ 可由状态 $0$ 或状态 $1$ 加上 ‘Q’ 字符转移而来。

状态 2 仅有状态 1 加上 ‘A’ 转移而来。

即

$dp[i][0] = 25\times dp[i - 1][0] + 24 \times dp[i - 1][1] + 25\times dp[i - 1][2]$

$dp[i][1] = dp[i - 1][0] + dp[i - 1][1]$

$dp[i][2] = dp[i][1]$

初始值 $dp[i][0] = 1, dp[i][1] = dp[i][2] = 0$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAX = 1e5 + 100;
const int MOD = 1e9 + 7;

ll dp[MAX][3];

void add(ll &x, ll y) {
    x = (x + y) % MOD;
}

ll cnt[MAX];

int main() {
    int n;
    dp[0][0] = 1;
    cnt[0] = 1;
    for (int i = 0; i < 1e5; i++) {
        cnt[i + 1] = cnt[i] * 26 % MOD;
        add(dp[i + 1][0], dp[i][0] * 25);
        add(dp[i + 1][0], dp[i][1] * 24);
        add(dp[i + 1][0], dp[i][2] * 25);

        add(dp[i + 1][1], dp[i][0]);
        add(dp[i + 1][1], dp[i][1]);

        add(dp[i + 1][2], dp[i][1]);
    }
    while (~scanf("%d", &n)) {
        ll ans = (cnt[n] - (dp[n][0] + dp[n][1] + dp[n][2]) % MOD + MOD) % MOD;

        printf("%lld\n", ans);
    }
}

题目链接：

bzoj2002

题目大意：

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

题目分析：

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 212345;
 
struct Node {
    int fa, son[2];
    int siz;
 
    inline int &l() { return son[0]; }
    inline int &r() { return son[1]; }
 
    void init() {
        fa = son[0] = son[1] = 0;
        siz = 1;
    }
    void maintain();
} node[MAX];
 
void Node::maintain() {
    siz = 1 + node[l()].siz + node[r()].siz;
}
 
int ori(int st) {
    if (node[st].fa < 0) return 0;
    return st == node[node[st].fa].r();
}
 
int f(int x) {
    return node[x].fa;
}
 
void setc(int st, int sn, int d) {
    if (st > 0) {
        node[st].son[d] = sn;
        node[st].maintain();
    }
    if (sn > 0) node[sn].fa = st;
}
 
void zg(int x) {
    int st = f(x);
    int p = f(st);
    int d = ori(x), dst = ori(st);
    setc(st, node[x].son[d^1], d);
    setc(x, st, d^1);
    setc(p, x, dst);
}
 
void splay(int x) {
    while (f(x) > 0) {
        if (f(f(x)) <= 0) zg(x);
        else {
            if (ori(x) == ori(f(x))) zg(f(x));
            else zg(x);
            zg(x);
        }
    }
}
 
void access(int x) {
    splay(x);
    while (node[x].fa < 0) {
        int fa = -node[x].fa;
        splay(fa);
        node[node[fa].r()].fa *= -1;
        setc(fa, x, 1);
        splay(x);
    }
}
 
int findroot(int x) {
    access(x);
    while (node[x].l()) x = node[x].l();
    splay(x);
    return x;
}
 
void link(int st, int x) {
    access(x);
    node[x].fa = -st;
    access(x);
}
 
void cut(int x) {
    access(x);
    node[node[x].l()].fa = 0;
    node[x].son[0] = 0;
}
 
int main() {
    int n, m;
    scanf("%d", &n);
    for (int i = 0; i <= n; i++) node[i].init();
    node[0].siz = 0;
 
    int x;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        if (i + x <= n) link(i + x, i);
    }
    scanf("%d", &m);
    int ord, v;
    while (m--) {
        scanf("%d %d", &ord, &x);
        x++;
        if (ord == 1) {
            access(x);
            printf("%d\n", node[node[x].l()].siz + 1);
        } else {
            scanf("%d", &v);
            cut(x);
            if (x + v <= n) link(x + v, x);
        }
    }
}

解题过程：

参考资料

一篇特别棒的博客

回文树

回文树又叫回文自动机，算是和 AC 自动机、后缀自动机、KMP 相似的算法。

首先有这样一个定理，一个字符串的不同的回文子串的数量和字符串的长度是同阶的。

回文树上的每一个节点储存的是一个原字符串的回文子串，并且他像 AC 自动机一样有 fail 指针和转移边，一个节点的父亲表示的回文串是当前节点表示的回文串的子串。fail 指针指向的是当前节点表示的回文串的最长回文子串，并且这个回文子串同时是他的前缀和后缀，并且不是他本身。

BZOJ 3676

题目链接

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。

数据满足1≤字符串长度≤300000。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 512345;
const int ALP = 26;
 
struct Palindromic_Tree {
    int son[MAX][ALP]; //转移边
    int fail[MAX]; //fail 指针
    int cnt[MAX]; //当前节点表示的回文串在原串中出现了多少次
    int num[MAX]; //当前节点 fail 可以向前跳多少次
    int len[MAX]; //当前节点表示的回文串的长度
    int S[MAX]; //插入的字符串
    int last; //最后一次访问到的节点，类似 SAM
    int n; //插入的字符串长度
    int p; //自动机的总状态数
 
    int newnode(int l) {
        memset(son[p], 0, sizeof(son[p]));
        cnt[p] = 0;
        num[p] = 0;
        len[p] = l;
        return p++;
    }
 
    void init() {
        p = 0;
        newnode(0);
        newnode(-1);
        last = 0;
        n = 0;
        S[n] = -1;
        fail[0] = 1;
    }
 
    int get_fail(int x) {
        while (S[n - len[x] - 1] != S[n]) x = fail[x];
        return x;
    }
 
    void add(int c) {
        c -= 'a';
        S[++n] = c;
        int cur = get_fail(last); //通过上一次访问的位置去扩展
        if (!son[cur][c]) { //如果没有对应的节点添加一个新节点
            int now = newnode(len[cur] + 2);
            fail[now] = son[get_fail(fail[cur])][c]; //通过当前节点的 fail 去扩展出新的 fail
            son[cur][c] = now;
            num[now] = num[fail[now]] + 1; //记录 fail 跳多少次
        }
        last = son[cur][c];
        cnt[last]++; //表示当前节点访问了一次
    }
    void count() {
        //如果某个节点出现一次，那么他的 fail 也一定会出现一次，并且在插入的时候没有计数
        for (int i = p - 1; i >= 0; i--) cnt[fail[i]] += cnt[i];
    }
} AUT;
 
char data[MAX];
int n;
 
int main() {
    scanf("%s", data);
    n = strlen(data);
    AUT.init();
    for (int i = 0; i < n; i++) AUT.add(data[i]);
    AUT.count();
    long long ans = 0;
    for (int i = 0; i < AUT.p; i++) {
        ans = max(ans, 1ll * AUT.len[i] * AUT.cnt[i]);
    }
    printf("%lld\n", ans);
}

​

一、时间内容

2018 年暑假，山东理工大学信息楼，2018 年 7 月 29 日至 2018 年 8 月 30 日，共记 33 天，评价每天 8 小时，约 33 × 8 = 264 小时。

主要以学习算法提高自己的能力为目的，另外要负责17级新生的训练计划安排和辅导工作。

二、体验和经历

不出意外的话应该是最后一次参加的 ACM 集训了，集训后接下来就要参加下半年的 ICPC 区域赛和 CCPC 了，经过前两年的学习，这次集训的内容基本上是查缺补漏和学习一些比较难的算法了。

首先经过 14 级的学长指导，需要学一下后缀自动机、虚树、Link-Cut-Tree 等算法。

后缀自动机

后缀自动机首先是一类自动机，他可以识别一个串的所有子串。自动机上的每一个节点表示着一个状态，但是又不像 AC 自动机那样，每个节点记录着一个前缀。后缀自动机的每个节点维护的是一个整数的集合，可以叫做子串的结束位置集合。

例如字符串 S = "aabbabd" ，那么对于子串 "ab" 的结束位置集合就是 {3, 6}。

后缀自动机将结束位置集合相同的子串归于一个等价类中，并只在自动机上表示为一个状态，有证明给出，这样自动机上的状态数是和字符串的长度同阶的。

接下来就是需要考虑后缀自动机如何识别一个字符串，给出一个字符串，需要从后缀自动机的初始状态开始转移，依次添加一个新的字符，如果转移中添加了一个新的字符串但是没有对应的状态，那么这个字符串是后缀自动机识别不了的，也就是说这个字符串不是字符串 S 的子串。

后缀自动机还有诸多的性质，例如如果沿着 Parents 边走的话，Right 集合会不断的合并变大，Parents 上方节点能表示的字符串均是下面字符串的一个后缀等…

虚树

据说虚树的英文是叫 Auxiliary tree，简单的来说是维护树上仅于题目有关的信息，除去掉冗余信息以保证时间复杂度的一种算法。为什么说是虚树呢，是因为他是在原来树的基础上建出的一颗全新的树，需要重新建边或分配点权等信息。

虚树的题目通常是这样的，给出一颗大小为 n 有边权或点权的树，然后有 q 次询问，每次给出 $k_i$ 个关键点，要求计算关于这 k 个点的问题（通常和 LCA 有关），但是 $\sum k_i$ 又比较小（通常和树的大小同阶）。

假设你可以 $O(n)$ 的在树上解决单次的询问，那么总时间复杂度是 $O(nq)$ 的，问题的 n 和 q 一般为 $10^5$ 显然这样是不可以过这道题的。这时候就需要用到虚树了，使用虚树我们对于每个询问都可以 $O(k_i)$ 的建出一颗有 $O(k_i)$ 个节点的树，并且可以通过这棵树 $O(k_i)$ 的计算出答案。

Link-Cut-Tree

LCT（Link-Cut-Tree） 又叫动态树，支持让一颗树删除一条边分裂成两颗树，或者两棵树合并成一颗树，并且维护一条链或子树的信息。

LCT 和树链剖分差不多，树链剖分大概是将一棵树划分成若干条链，然后对每条链映射成连续的区间，就可以用线段树去维护每条链的区间信息。LCT 也是把一棵树拆成若干条链来维护，不过 LCT 是直接把一条链用一颗 Splay 当做一个序列来维护，序列按照节点的深度当做关键字排序。

LCT 主要支持三种操作，Access 操作，将一个节点 u 到根节点的路打通（类比树链剖分里的重链），并且将 u 节点设置为其所在的 Splay 的根。Link 操作，将 u 设置成 v 的儿子，先 Access u，给 u 加一条虚边到 v，然后 Access u。Cut 操作，将一个节点 u 和其父亲断开，先 Access u，然后断开 u 与其左儿子的连接，再 Access u。

有证明给出，LCT 的每一个操作都是 $O(\log n)$ 的。

接下来说一下前半年参加的比赛的总结。

CCCC 天梯赛

感觉一直是一项以考察基本数据结构为主的比赛，今年比赛缩水了一下，没有选拔赛直接只有一场决赛了。老师说按照 SDUT 的经验每次都是初赛打的不太好，然后决赛打的不错。不过这次没有初赛，于是决赛相比前几年打的不怎么好。

比赛是在青岛的中国石油大学进行，不得不说中石油的校区环境是真的不错，不过这次不像区域赛那样有个热身赛之类的，所以当天去当天就回学校了，少了几分乐趣。中石油提供伙食的自助餐厅是真的棒，饭菜样式多，肉菜多，又挺好吃的，中午吃饭的时候老师在催要去比赛了我们还在吃…

比赛不知道为什么，前一个半小时整个机房的电脑都不能正常上比赛的网址，本来时间就不太充裕，先锋奖励肯定是放弃了，只能用剩下时间去尽可能的做了会做的题目…

和往届一样，前面几道题都是基础题，大概程序设计基础的难度，后面几道也就涉及到并查集这种基本的数据结构，比赛的核心是考察代码能力，做起来根本不用动脑子，这一点和 ICPC、CCPC、Codeforces 之类的比赛非常不同。然后后面几道题有特别难，一道是写一个格式化代码的程序，一道是一个非常难的字符串题，另外一个是计算几何。基本上也都能写一个暴力程序骗不少分。

最后好像是 226 分滚粗（去年都能打到 236），感觉难题是比去年难，简单题也都没什么感觉，也算是尽力了。

山东省省赛

首先先看的 C，标准的签到题，让队友敲的，结果 WA 了两次才 A，可以说是开局非常爆炸了，于是导致我后面交题也不怎么看罚时了（不知道算不算什么破釜沉舟背水一战），想着只能靠题数取胜了。

然后看的 B，理解错了题意，正确的题意是符合贪心性质的，可以写贪心，我大概是做了个 Hard Version，写了个最小费用流，非常熟练的抄完自己总结的板子，保存边的数量的变量没初始化 RE 了一发，然后由于不考虑罚时，于是改完就立刻交了一发就 A 了。

在我写 B 的时候队友就已经在看 F 题了（数据出错的那个题），等我写完他告诉了我一下容斥的做法，我觉得没什么问题就开始敲了，不过写的过程中感觉非常难写…看到榜单上 6 分钟就 AC 的，怀疑自己的做法是不是不对…然后让队友写了个对拍自己去重新想了一下思路，发现还是得写容斥，于是回来继续写，写完后又对拍了几组数据改了改就交了，然后肯定是 A 的，最后也不知道这个题有没有写对 ORZ

这时候另一个队友一直在读题，我敲完一道题基本上就可以接着看下一道题了，这时候一个队友在想 E 题，我去写 G 题，然后一眼看过去就是 NIM 博弈加 DP 记录方案数，不过这里数据越界改了好几次才过，不过改完一次就交一次不在乎罚时，所幸改的还算快。

在我改 G 题的时候让队友敲了下 E 题，NlogN 的复杂度 TLE 了，感觉必须得线性的算法才能过，这时候封榜还有半个小时，榜上已经有六题的了，于是决定让队友去其他的题了（B 和 D），然后我考虑这个题的答案限制条件比较少，应该用不到队友敲得逆序数之类的，于是正好我们都想到单调队列，于是先写了个单调队列，然后测了下样例对了，要交的时候还是不放心，因为如果这个 WA 的话我不能确定是算法错了还是代码细节错了，于是让队友出了下样例果然错了，后来多考虑了一个条件就 OK 了，然后提交 AC。

这时候队友说 B 题有思路了，不过是图论题还是让我敲，我一直感觉 1e8 的时间复杂度过不去，于是先让队友把板子抄上，然后自己想了下细节怎么处理，感觉没问题之后就开始上手做了，写完 debug 了 20 多分钟，队友板子抄错了两个地方，改完过了另一个队友出的特别强的样例（反转他说是比较强），提交就 AC 了。

这时候比赛结束还有四十分钟，榜上已经有七题的队伍了，加上我们罚时比较高，夺冠要在这 40 分钟 A 两题感觉希望不太大了，有点失望…队友在我写 B 题的时候已经想了下大概的 D 题做法，我问了他一下，感觉加上树链剖分就可以写了，于是拿过来之前直接整理的树链剖分板子就超了起来，心情比较差加上又特别累了，中间电脑还重启耽误了十多分钟，最后还有十分钟结束才写完，总共 200 多行代码，我当时就和队友说，这么长的代码要是不出点 Bug 什么的我都不信，结果运行没编译错误，然后输入样例结果却都是 0 … 非常紧急的改完之后还剩五分钟了，最终居然过了样例，当时 PC ^ 2 显示结束还有三分钟立刻就交了，之后就赶紧看代码还有没有错误。然后看着看着队友说有评测结果了，看了一下返回了一个 Yes，可以说是非常开心了。

西安邀请赛

首先看的 E 题，很显然的一个几何的结论三分钟 A 了。

然后看的 A 题，猜了个显然不对的做法，WA 一次，然后和 szq 讨论后又写了一个优化版的做法，还是 WA，最后又讨论了下，算是推出来了出题人认为的正解，不过这个题目出错了，在我们推出来正解后讨论区裁判公布了正解。算是可惜了两发罚时，不过裁判组处理也是比较得当，如果不这样的话会有好多有水平的队伍卡在 A 题。

在我敲 A 题的时候 szq 就已经在看 D 题，看上去就是 nim 博弈的变种，推出来 SG 函数就基本上做出来的了，不过他没有打好表，还是我上去记忆化搜索一波后打出来表，规律非常显然，出了个小失误 WA 一发后就 AC 了。

然后 lxw 告诉我了下 B 题（最后也没写出来）的题意后我就去看 K 了，这里我大概敲了一个小时，思路越敲越乱，大概浪费了一个多小时，最后 szq 说他有一个比较简单的做法，我就让开机位去让他敲了，自己去洗了把脸清醒一下…最后 szq 写完调试了半个小时多才 A 掉这个题，算是这次比赛里面最大的失误了。

之前看榜上有好多人过了 G 题，并且 szq 和 lxw 已经讨论出来了这是一个简单的板子题，于是 A 完 K 题后直接去做 G 题了，敲完板子后一直 WA，最后我打印代码让他们两个看，去敲了 C 题，C 题在 szq 敲 K 题的时候我已经和 lxw 讨论的差不多了。

最后实在没找到其他的错误，于是只好试试改精度，然后改完之后 G 题居然 AC 了，随后我敲完 C 题过了样例也顺利 1A 了。

这时候刚好封榜，只有一个小时剩余的时间了，看榜上其他有人做出来的题只有 B 和 H 题，F 题只有 GDUT 穷游中国做出来了，感觉可能比较难，于是就去做 B 题了（后来发现这个是错误选择）。

最后让 lxw 读出来了 H 题的题目，B 和 H 最后也没有思路。

比赛后听他们讨论说封榜前没人过的 I 和 J 题都是数据结构的模板题，感觉自己没看有点可惜。

斜率优化