AK 了。
A - TLD
给出一个字符串 \(s\)，输出最后一个
.后面的内容。\(|s|\le 100\)。
\(\text{2 sec / 1024 MB}\)。
按照题意模拟即可，时空复杂度均为 \(\mathcal{O}(|s|)\)。
B - Langton's Takahashi
给出 \(H\times W\) 的网格。初始你在 \((1,1)\)，方向朝上。一开始所有格子都是白色。设你当前在 \((x,y)\)，\(a_{x,y}\) 表示当前网格的颜色（\(1\) 为黑，\(0\) 为白）。网格上下边界、左右边界是循环联通的。
重复执行 \(N\) 次：
若 \(a_{x,y}=0\)，则 \(a_{x,y}\leftarrow 1\)，并将你的朝向顺时针转 \(90°\)。
否则 \(a_{x,y}\leftarrow 0\)，并将你的朝向逆时针转 \(90°\)。
向你的朝向往前走一步。
输出最后的网格。
#代表黑色，.代表白色。\(H,W\le 100\)，\(N\le 1000\)。
\(\text{2 sec / 1024 MB}\)。
按照题意模拟即可，处理每一种方向 \(x,y\) 的增量，用取模实现旋转和循环。
时间复杂度为 \(\mathcal{O}(HW+N)\)，空间复杂度为 \(\mathcal{O}(HW)\)。
C - Perfect Bus
有一辆车和 \(n\) 个时刻。初始时刻车上人数未知。第 \(i\) 个时刻车上新增 \(a_i\) 个人。任意时刻车上的人数 \(\ge 0\)。求 \(n\) 个时刻之后车上人数的最小可能值。
\(n\le 2\times 10^5\)。值域为 \(V\)，\(|V|\le 10^9\)。
\(\text{2 sec / 1024 MB}\)。
不难发现答案有单调性。二分答案，则可以计算出任意时刻车上的人数，判断是否 \(\ge 0\) 即可。
时间复杂度为 \(\mathcal{O}(n\log |V|)\)，空间复杂度为 \(\mathcal{O}(n)\)。
D - Synchronized Players
给出一个 \(N\times N\) 的棋盘，有三种格子：
P：表示一个棋子。棋盘中有且仅有两个这样的格子，视为空地。
.：表示一个空地。
#：表示障碍物，不是空地。每步你可以选择上、下、左、右中任意一个方向，对两个棋子执行：
若某个棋子的当前方向上不存在格子或对应的格子不是空地，这个棋子不动。否则在这个方向上移动一格。
求让两棋子到达同一格子的最少步数，或判断无解。
\(N\le 60\)。
\(\text{4 sec / 1024 MB}\)。
BFS。状态设为第一个棋子的位置和第二个棋子的位置的二元组。每次按照题意扩展。根据队列内步数单调不降，最先满足两棋子位于同一格子的状态即为答案。
时空复杂度均为 \(\mathcal{O}(N^4)\)。
E - Smooth Subsequence
给出一个序列 \(A_1\sim A_n\)，选出它的一个子序列，使得任意相邻两项差的绝对值不超过 \(D\)。
\(n \le 5\times 10^5\)。设值域为 \(V\)，\(|V|\le 5\times 10^5\)。
\(\text{2 sec / 1024 MB}\)。
考虑 dp。设 \(f_i\) 为以 \(i\) 结尾的最长子序列，有转移：
\[f_i=\max\limits_{j<i\land |A_i-A_j|\le D}f_j +1 \]然后用正序扫描维护 \(j<i\)，发现 \(|A_i-A_j|\le D\) 等价于 \(A_j\in[A_i-D,A_i]\bigcup[A_i+1,A_i+D]\)，线段树维护之。
时间复杂度为 \(\mathcal{O}(n\log |V|)\)，空间复杂度为 \(\mathcal{O}(n+|V|)\)。
F - Product Equality
给出 \(n\) 个数 \(A_1\sim A_n\)，求三元组 \((i,j,k)\) 的个数，使得 \(A_i\times A_j=A_k\)。
\(n\le 1000\)，\(A_i\le 10^{1000}\)。
\(\text{2 sec / 1024 MB}\)。
如果 \(A_i\) 位数比较少，则可以枚举两维然后第三位桶维护。
考虑 \(A_i\) 位数多的情况，两数相等的一个必要条件是，他们对任意模数后仍然相等。但是不充分。不过多项式哈希很难撞，多取几个模数就可以了。
这里运用到 \(A_i\times A_j≡ (A_i\bmod p)\times (A_j\bmod p)(\bmod p)\)。所以可以枚举两维然后算出哈希值，最后桶匹配计数。
默认取了 \(\mathcal{O}(1)\) 个模数，时间复杂度为 \(\mathcal{O}(n^2\log n)\)，空间复杂度为 \(\mathcal{O}(n)\)。
G - Smaller Sum
给出一个序列 \(A_1\sim A_n\)，\(Q\) 次询问，每次求 \([l,r]\) 内不超过 \(x\) 的数的和。强制在线。
\(n,Q\le 2\times 10^5\)，设值域为 \(V\)，\(|V|\le 10^9\)。
\(\text{3.5 sec / 1024 MB}\)。
其实就是求所有 \(i\in[l,r]\)，\(a_i\in[0,x]\) 的 \(a_i\) 之和。二维数点即可。因为强制在线所以主席树维护。
时间复杂度为 \(\mathcal{O}(n+Q)\log |V|\)，空间复杂度为 \(\mathcal{O}(n\log |V|)\)。
标签：ABC339,le,1024,题解,复杂度,times,text,mathcal From： https://www.cnblogs.com/MnZnOIerLzy/p/18005277