FXJFXJ
0%

339

发表于 更新于 分类于 阅读次数：
本文字数： 2.4k 阅读时长 ≈ 9 分钟

A - TLD

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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\)

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

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

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
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 即可，再加上从开始到最后折合上来的人数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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, \ldots, 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

线段树

官方题解：

\(dp_{i, j}\) 定义为相邻两项之差的绝对值不超过 \(D\)，且末尾为 \(j\) 的 \((A_1, A_2, \dots, A_N)\) 的子序列的最大长度。

在这种情况下，

\(dp_{i, j} = \begin{cases} \displaystyle\max_{k \in [A_i-D, A_i + D]} dp_{i - 1, k} + 1 & (j = A_i) \\ dp_{i-1, j} & (j \neq A_i) \end{cases}\)

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

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

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

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

\(O(n^2)\) 做法(DP)： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)\) 做法(线段树)：

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
#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 \le N \le 1000\), \(\color{red}{1 \le A_i \leq 10^{1000}}\) 求满足以下条件的整数 \((i, j, k)\) 的三元组数：

  • \(A_i \times A_j = A_k\) ( \(1 \le i, j, k \le 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| \le 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 查询本身，而是查询的加密输入 \(\alpha_i, \beta_i, \gamma_i\)。使用以下步骤还原原始的 \(i\) /th 查询，然后回答它。

  • 让 \(B_0=0\) 和 \(B_i =\)（\(i\) -th 查询的答案）。
  • 然后，查询可以按如下方式解密：
    • \(L_i = \alpha_i \oplus B_{i-1}\)
    • \(R_i = \beta_i \oplus B_{i-1}\)
    • \(X_i = \gamma_i \oplus B_{i-1}\)

Solution

(待更 \(\dots\))

  • 本文作者： FXJFXJ
  • 本文链接： https://fxj.wiki/posts/72026fe3/
  • 版权声明： 本博客所有文章除特别声明外，均采用 ZERO 许可协议。转载请注明出处！