339

A - TLD

输出最后一个点后面的字符

void solve()
{
    string a;
    cin >> a;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        if (a[i] == '.')
        {
            for (int j = i + 1; j < a.size(); j++)
                cout << a[j];
            break;
        }
    }
}

B - Langton's Takahashi

给出要旋转的次数，刚开始方向向上且在 $(1, 1)$ 位置，则

如果当前单元格是 .，则将其变为 #，顺时针旋转 $90^{\circ}$ ，并沿着他面对的方向向前移动一个单元格。
否则，将当前单元格变为 .，逆时针旋转 $90^{\circ}$ ，并沿着他所面对的方向向前移动一个单元格。

输出最后的二维字符串.

Solution

坑点：刚开始是向上的，所以 curDir = 3; 而不是 $0$

主要是顺时针与逆时针旋转：

int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
curDir = (curDir + 1) % 4;  // 顺时针
curDir = (curDir + 3) % 4;  // 逆时针

void solve()
{
    int H, W, N;
    cin >> H >> W >> N;

    vector<vector<char>> grid(H, vector<char>(W, '.')); // Initialize the grid with all white cells

    int x = 0, y = 0; //位置

    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int curDir = 3;

    for (int i = 0; i < N; i++)
    {
        if (grid[x][y] == '.')
        {
            grid[x][y] = '#'; 
            curDir = (curDir + 1) % 4;  // 顺时针
        }
        else
        {
            grid[x][y] = '.'; // Change color
            curDir = (curDir + 3) % 4;  // 逆时针
        }
		x += directions[curDir][0];
		y += directions[curDir][1]; // Move to the next cell
		x = (x + H) % H;            // Wrap around if out of bounds
		y = (y + W) % W;            // Wrap around if out of bounds
    }

    // Print the grid
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
            cout << grid[i][j];
        cout << endl;
    }
}

C - Perfect Bus

一辆公共汽车正在运营。公共汽车上的乘客人数总是一个非负整数。

在某一时刻，公交车上的乘客人数为零或更多，此后公交车停靠了 $N$ 次。在第 $i$ 个站点，乘客人数增加了 $A_{i}$ 。这里， $A_{i}$ 可以是负数，即乘客人数减少了 $- A_{i}$ 。此外，除了停靠站点外，没有乘客上下车。

请找出与给定信息相符的当前公交车上乘客人数的最小值。

Solution

很简单，算出刚开始的乘客有多少即可。

利用前缀和算出乘客最有可能为 0 的位置，在那个位置刚好为 0 即可，再加上从开始到最后折合上来的人数即可。

#define int long long
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    pre[1] = a[1];
    for (int i = 2; i <= n; i++)
        pre[i] = pre[i - 1] + a[i];
    int ini = 0;
    for (int i = 1; i <= n; i++)
        ini = min(ini, pre[i]);
    cout << abs(ini) + pre[n] << ' ';
}

D - Synchronized Players

有一个 $N \times N (2 \leq N \leq 60)$ 网格，其中每个单元格要么是空的，要么包含一个障碍物。

网格中不同的空单元上也有两个玩家。每个单元格的信息以长度为 $N$ 的 $N$ 字符串 $S_{1}, S_{2}, \dots, S_{N}$ 的形式给出，格式如下：

如果 $S_{i}$ 的 $j$ 个字符是 P，上面有一名棋手。
如果 $S_{i}$ 的 $j$ 个字符是 .，是空格。
如果 $S_{i}$ 的 $j$ 个字符是 #，包含一个障碍物。

重复下面的操作，找出将两位棋手带到同一格所需的最少步数。如果重复操作无法将两位棋手带到同一格，则打印 -1。

从四个方向中选择一个：上、下、左或右。然后，每个玩家都会尝试移动到该方向的相邻单元格。如果目标单元格存在且为空，则每个玩家都会移动，否则不会移动。

Solution

搜索(bfs)

官方题解：

现在我们的图是一个有 $N^{4}$ 个顶点的图，每个顶点都被标记为 $1$ 到 $N$ 之间的四个整数的组合。

每次操作后在顶点 $(x_{1}, y_{1}, x_{2}, y_{2})$ 和顶点 $(x_{1}^{'}, y_{1}^{'}, x_{2}^{'}, y_{2}^{'})$ 之间添加一条边（如果不能进行操作，则不添加边）。

假设初始时两个玩家的位置分别是 $(X_{1}, Y_{1})$ 和 $(X_{2}, Y_{2})$ ，那么要使两个玩家在位置 $(i, j)$ 相遇所需的操作次数，就是从图中顶点 $(X_{1}, Y_{1}, X_{2}, Y_{2})$ 到顶点 $(i, j, i, j)$ 的最短路径（注意：如果无法在位置 $(i, j)$ 相遇，则不存在从 $(i, j, i, j)$ 的路径）。由于图中顶点和边的数量是 $O (N^{4})$ ，因此通过 BFS 计算最短路径的时间复杂度为 $O (N^{4})$ 。

(待更 $\dots$ )

E - Smooth Subsequence

给出 $A$ 序列，将其中删除某些元素后使得两个相邻项之间的绝对差 $\leq D$ ，求 $A^{'}$ 的最大长度。

Solution

线段树

官方题解：

$d p_{i, j}$ 定义为相邻两项之差的绝对值不超过 $D$ ，且末尾为 $j$ 的 $(A_{1}, A_{2}, \dots, A_{N})$ 的子序列的最大长度。

在这种情况下，

$d p_{i, j} = {\begin{cases} max_{k \in [A_{i} - D, A_{i} + D]} d p_{i - 1, k} + 1 & (j = A_{i}) \\ d p_{i - 1, j} & (j \neq A_{i}) \end{cases}$

此公式用于计算 dp 数组，可以得到正确的答案，但时间复杂度和空间复杂度为 $Θ (N^{2})$ 。

因此，我们可以使用 $d p_{i - 1, j}$ 和 $d p_{i, j}$ 在大多数情况下相等的事实来加速计算。

通过不显式地存储每个 $(i, j)$ 的 $d p_{i, j}$ ，而是重复使用数组，我们可以将上述 dp 改写为仅需要一个一维数组 $d p$ ，并按顺序替换 $d p_{j}$ 为 $max_{k \in [A_{i} - D, A_{i} + D]} d p_{k} + 1$ 。

这样，空间复杂度就变成了 $O (N)$ 。时间复杂度如果直接计算 max 的话仍然为 $Θ (N^{2})$ ，但是通过使用区间 max 单点更新的线段树，时间复杂度可以降低为 $O (N \log N)$ 。

$O (n^{2})$ 做法(DP)：

void solve()
{
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> dp(n, 0);
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (abs(a[i] - a[j]) <= d)//a[i]和a[i]前面的数比较是否<=d，如果有，直接等于那个数的最大长度+1
                dp[i] = max(dp[i], dp[j] + 1);
    }

    int ans = *max_element(dp.begin(), dp.end());
    cout << ans << '\n';
}

$O (n \log n)$ 做法(线段树)：

#include <bits/stdc++.h>
using namespace std;

const int A = 500010;

int seg[A * 4];

void update(int v, int tl, int tr, int pos, int new_val)
{
    if (tl == tr)
        seg[v] = new_val;
    else
    {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v * 2, tl, tm, pos, new_val);
        else
            update(v * 2 + 1, tm + 1, tr, pos, new_val);
        seg[v] = max(seg[v * 2], seg[v * 2 + 1]);
    }
}

int query(int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return 0;
    if (l == tl && r == tr)
        return seg[v];
    int tm = (tl + tr) / 2;
    return max(query(v * 2, tl, tm, l, min(r, tm)),
              query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}

int main()
{
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int &e : a)
        cin >> e;

    for (int i = 0; i < n; i++)
    {
        int l = max(0, a[i] - d);
        int r = min(A - 1, a[i] + d);
        int mx = query(1, 0, A - 1, l, r);
        update(1, 0, A - 1, a[i], mx + 1);
    }
    cout << seg[1] << '\n';
}

F - Product Equality

给你 $N$ 个整数 $A_{1}, A_{2}, \dots, A_{N}$ 。 - $1 \leq N \leq 1000$ , $1 \leq A_{i} \leq 10^{1000}$
求满足以下条件的整数 $(i, j, k)$ 的三元组数：

$A_{i} \times A_{j} = A_{k}$ ( $1 \leq i, j, k \leq N$ )

Solution

官方题解：(看不懂)

有 $N^{2}$ 种选择两个变量进行乘法的方法。然而，由于每个变量都非常大，即使使用多倍长算术，计算量也会达到 $O (N^{2} d \log d)$ 的数量级，而且很难在解决此问题时考虑溢出等情况。

首先，让我们考虑判断三个变量 $p, q, r$ 是否满足 $p \times q = r$ 。在这里，我们可能会进行稍微大胆一些的判断：

选择一个整数 $x$ ，如果 $p \times q \equiv r$ (mod x)，那么我们判定 $p \times q = r$ 。

这种方法会在 $(p \times q - r) \equiv 0$ (mod x)的情况下失败。

接下来，我们可以考虑选择素数 $x$ ，其中 $x$ 大于 $10^{9}$ 。这种情况下，这种判断方法最多会失败 $222$ 次（原因： $| p \times q - r | \leq 10^{2000}$ ）。而在 $10^{9}$ 到 $2 \times 10^{9}$ 范围内的素数却有数千万个。

因此，实际上以下的随机算法是正确的解决方法：

令 $S$ 为随机选择的素数集合（每个值都是 $10^{9}$ 以上 $2 \times 10^{9}$ 以下的素数）。
对于 $S$ 中的每个元素 $x$ ，如果对所有的 $A_{k}$ ， $A_{i} \times A_{j} \equiv A_{k}$ (mod x)成立，则判定 $A_{i} \times A_{j} = A_{k}$ 。
首先对所有的 $A_{k}$ ，对 $S$ 中的每个元素 $x$ 进行取模运算，然后判断 $A_{i} \times A_{j}$ 的取模值是否与之匹配。

通过这种方法，我们可以在 $O (| S | \times N^{2} \log N)$ 的时间内得到这个问题的正确解。虽然我们省略了精确估计成功概率的方法，但是选择大约 $20$ 个合适的整数作为 $| S |$ 是一个不错的选择。

此外，我们也可以只选择足够大的整数，而不进行素数判断，同样也可以得到这个问题的正确解。（很难准备这样的案例，使得这种解法失败）

(待更 $\dots$ )

G - Smaller Sum

给你一个长度为 $N$ 的序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 。

请回答以下 $Q$ 个查询。 $i$ 个查询如下：

求 $A_{L_{i}}, A_{L_{i} + 1}, \dots, A_{R_{i}}$ 中不大于 $X_{i}$ 的元素之和。

在此，您需要在线回答这些查询。
也就是说，只有在回答了当前查询后，下一个查询才会显示出来。

因此，我们给你的不是 $i$ -th 查询本身，而是查询的加密输入 $α_{i}, β_{i}, γ_{i}$ 。使用以下步骤还原原始的 $i$ /th 查询，然后回答它。

让 $B_{0} = 0$ 和 $B_{i} =$ （ $i$ -th 查询的答案）。
然后，查询可以按如下方式解密：
- $L_{i} = α_{i} \oplus B_{i - 1}$
- $R_{i} = β_{i} \oplus B_{i - 1}$
- $X_{i} = γ_{i} \oplus B_{i - 1}$

Solution

(待更 $\dots$ )