- [A. The Catcher in the Rye]
- [B. Dissertation]
- [C. Dominoes]
- [D. Endgame]
- [E. Evacuation]
- [F. Factory]
- [G. Grasshoppers]
- [H. Education Nightmare]
- [I. A Really Odd Sequence]
- [J. Spoonerisms]
- [K. A Text Problem]
- [L. Waiter’s Problem]
题意：有一个高度为$h$的大矩形，矩形由三个小矩形拼接成，三个小矩形的高度都为$h$，宽度分别为$a,b,c$。在每个矩形中的移动速度不一样，分别为$v_a,v_b,v_c$。你要从左下角走到右上角，问最少需要多少时间。
题解：考虑有一束光从左下角射入，然后从右上角射出，这个肯定只有唯一一条光路。可以证明，这条光路就是我们要求的路径。
因为光路是唯一的，于是就可以通过二分入射角来计算出这条路径。根据这个光的折射定律，我们可以知道 $$ \frac{\sin \theta_1}{v_1} = \frac{\sin \theta_2}{v_2}. $$ 于是就可以很方便地求出最后光从哪个位置出来了。
题意：给出长度为$n$和$m$的两个串，求他们的最长公共子序列的长度。
题解：令$dp(i,j)$表示第二个串前$i$个字符与第一个串前$dp(i,j)$个字符的LCS至少为$j$，且$dp(i,j)$为满足条件的最小值。
假设已知$dp(i,j)$，考虑转移到第二个串的第$i+1$个位置，如果该位置不对$LCS$产生贡献，则直接转移到$dp(i+1,j)$；否则在第一个串的$dp(i,j)$位置后找到第一个匹配的字符位置转移到$dp(i+1,j+1)$。
题意：有$\frac{n(n+1)}{2}$个多米诺骨牌，骨牌上下分别写着$(1,1),(1,2),\dots,(1,n),(2,2),(2,3),\dots,(n,n)$。现在要把这个写骨牌放到方格里面，要求相同数字的格子要连通。
题解：简单地在纸上画画可以发现，如果$n \ge 5$，因为平面图不存在
题意：一个$8 \times 8$的棋盘上，黑方剩一个国王，白方剩一个国王和一个车先手。保证至多50步白方可以将军，白方想最小化步数，黑方想最大化步数，求白方多少步能将军。
题意：有个人一开始在$x$轴的$0$位置，每单位时间他可以向左或向右走一步或者停在原地。有$n$道闪电$(t,x,r)$，表示$t$时刻的时候这个人不能够站在$[x-r+1,x+r-1]$这个区间内。有$s$个询问$(t,x)$，求出在$t$时刻这个人能否走到位置$x$。
题解：可以发现，在任意时刻，一个人的可行范围一定是若干个不相交的区间，于是我们可以用一个std::set维护。对于一个闪电，就是把区间$[x-r+1,x+r-1]$里的可行范围都删掉。对于询问的话，就是看$x$是否在一个可行区间里面，直接调用std::set的lower_bound即可知道。
考虑到没过一个单位时间，一个可行范围的左右端点都会扩张，这可能会导致可行范围合并，因此我们还需要额外维护合并事件。对于可行范围，我们维护$(l,r,t)$三元组，表示在时刻$t$的时候，这个范围为$[l,r]$。
合并只会发生在相邻的可行范围内，对于两个相邻的三元组$(l_1,r_1,t_1)$和$(l_2,r_2,t_2)$，在时刻$t$合并等价于$r_1+(t-t_1)+1 \ge l_2 - (t - t_2)$，即$t \ge \lceil \frac{l_2+t_2-r_1+t_1-1}{2} \rceil$。于是可以拿第二个std::set维护$(t, (l_1,r_1,t_1), (l_2,r_2,t_2))$这个结构，表示在$t$时刻他们会合并。
每次闪电或者询问前，把能够合并的区间都合并了即可。
题意：给出平面上$n$个点$(x_i,y_i)$，找一个点使得这个点到所有点的欧几里得距离和最小。
题解：显然距离之和关于点坐标$(x,y)$是凸的。于是可以三分套三分，时间复杂度$O(n \log^2 A)$。
题意：圆环上均匀分布有$m$个位置，有$n$只蚱蜢，一开始的时候第$i$只蚱蜢的位置是$A_{i}$, 蚱蜢们要跳$t$轮。对于每一轮，第$i$只蚱蜢会从它当前的位置跳到以圆环中心和第$i+1$只蚱蜢的连线的对称位置上。蚱蜢们每一轮都同时跳，问$t$轮后每只蚱蜢的位置。
题意：你的学校有$n$间教室，以$n-1$条边连接(是一棵树)，你从$s$出发沿着边走，要去上课教室，但是你不知道这节课的教室在哪里。如果你进入了你的上课教室，那么你就马上知道这是你要去的教室。在教室$m$有一张课程表，如果你到了教室$m$，你马上就知道你的上课教室的位置。询问你在最好策略下到达上课教室最坏要多久。
题意：求一个和最大的奇数长度的子区间。
题意: 给$n$个串，在里边找出$4$个串$A, B, C, D$，满足 能够通过交换一次$A$和$B$的某个前缀来得到$C$和$D$。
题意：在允许一个错误的情况下$A$串出现在$B$串中，当且仅当A串出现在$B$串中，或者$A$串在修改了一个字符后出现在$B$串中. 给定一个串$T$, 和$Q$个询问，每个询问给出一个串$S$, 询问在允许一个错误的情况下$S$在$T$中的出现次数.
题意：有$n$个非负整数$A_1, A_2, A_3..A_n$, 你要执行$n$轮操作， 每一轮操作你要从$A$序列里挑出一个数$A_i$, 你获得$A_i$的收益并把$A_i$从$A$中删去，然后序列里剩余的所有大于0的数都减一. 问你在最优策略下，能获得的最大收益和。