跳转至

ABC335(A-F)

A - 2023

题目大意

给你一个字符串，将最后一个字符换成 4。

参考代码 
#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    s[s.length() - 1] = '4';
    cout << s << endl;
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        System.out.print(s.substring(0, s.length() - 1));
        System.out.println("4");
        in.close();
    }
}

B - Tetrahedral Number

题目大意

给你一个正整数 \(N\)，输出所有满足 \(x + y + z \le N\) 的非负三元组 \((x, y, z)\)。

参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i <= n; i++)
        for(int j = 0; i + j <= n; j++)
            for(int k = 0; i + j + k <= n; k++)
                printf("%d %d %d\n", i, j, k);
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i <= n; i++)
            for (int j = 0; i + j <= n; j++)
                for (int k = 0; i + j + k <= n; k++)
                    System.out.printf("%d %d %d\n", i, j, k);
        in.close();
    }
}

C - Loong Tracking

题目大意

有一条龙可以分成 \(N(N \le 10^6)\) 个部分，第 \(1\) 个部分为龙头，第 \(N\) 个部分为龙尾。龙的每个部分都可以用一个二维坐标来描述，初始的时候，龙头在 \((1, 0)\) ，第 \(2\) 个部分在 \((2, 0)\)，第 \(3\) 个部分在 \((3, 0)\)，以此类推。有 \(Q(Q \le 2 \times 10^5)\) 个操作：

  • 1 C：表示将龙进行移动，C是一个字符，可能是 U、D 、L、R之一，表示对龙进行上下左右的移动。龙移动的规则是，首先将龙头进行移动，接下来，第 \(2\) 个部分移动到原先龙头的位置，第 \(3\) 个部分移动到原先第 \(2\) 个部分的位置，以此类推。
  • 2 p：表示查询当前龙的第 \(p\) 个部分的坐标。
解题思路

开一个数组逆序存储位置，移动的时候，在数组的末尾加入新坐标，同时数组的边界滑动 \(1\) 格。

参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 1E6 +  2E5 + 10;
int x[maxn], y[maxn];

int main()
{
    int N, Q;
    cin >> N >> Q;
    int idx = N;
    for(int i = 1; i <= N; i++)
        x[idx-i] = i;
    int op, p;
    char C[5];
    while(Q--)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%s", C);
            x[idx] = x[idx-1];
            y[idx] = y[idx-1];
            if(C[0] == 'U')
                y[idx]++;
            else if(C[0] == 'D')
                y[idx]--;
            else if(C[0] == 'L')
                x[idx]--;
            else
                x[idx]++;
            idx++;
        }
        else
        {
            scanf("%d", &p);
            printf("%d %d\n", x[idx-p], y[idx-p]);
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        int[] x = new int[n + q + 1], y = new int[n + q + 1];
        int idx = n, op, p;
        for (int i = 1; i <= n; i++)
            x[idx - i] = i;
        String c;
        for (; q > 0; q--) {
            op = in.nextInt();
            if (op == 1) {
                c = in.next();
                x[idx] = x[idx - 1];
                y[idx] = y[idx - 1];
                if (c.equals("U"))
                    y[idx]++;
                else if (c.equals("D"))
                    y[idx]--;
                else if (c.equals("L"))
                    x[idx]--;
                else
                    x[idx]++;
                idx++;
            } else {
                p = in.nextInt();
                System.out.printf("%d %d\n", x[idx - p], y[idx - p]);
            }
        }
        in.close();
    }
}

D - Loong and Takahashi

题目大意

有一个 \(N \times N(N \le 45)\) 的网格，输出一个自外向内的数字递增的“回”字形，特别的，中间位置（保证 \(N\) 是一个奇数）输出一个字符 T（见输出样例）。

输入输出样例

样例输入

5

样例输出

1 2 3 4 5
16 17 18 19 6
15 24 T 20 7
14 23 22 21 8
13 12 11 10 9
参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 45 + 5;
int n;
int s[maxn][maxn];

int main()
{
    cin >> n;
    int r = 0, c = 0, t = n / 2, num = 1;
    while(r != t || c != t)
    {
        s[r][c] = num++;
        while(c + 1 < n && !s[r][c+1])
            s[r][++c] = num++;
        while(r + 1 < n && !s[r+1][c])
            s[++r][c] = num++;
        while(c - 1 >= 0 && !s[r][c-1])
            s[r][--c] = num++;
        while(!s[r-1][c])
            s[--r][c] = num++;
        c++;
    }
    for(int i = 0; i < t; i++, puts(""))
        for(int j = 0; j < n; j++)
            printf("%d ", s[i][j]);
    for(int j = 0; j < t; j++)
        printf("%d ", s[t][j]);
    cout << "T ";
    for(int j = t + 1; j < n; j++)
        printf("%d ", s[t][j]);
    puts("");
    for(int i = t+1; i < n; i++, puts(""))
        for(int j = 0; j < n; j++)
            printf("%d ", s[i][j]);
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int r = 0, c = 0, t = n / 2, num = 1;
        int[][] s = new int[n][n];
        while (r != t || c != t) {
            s[r][c] = num++;
            while (c + 1 < n && s[r][c + 1] == 0)
                s[r][++c] = num++;
            while (r + 1 < n && s[r + 1][c] == 0)
                s[++r][c] = num++;
            while (c - 1 >= 0 && s[r][c - 1] == 0)
                s[r][--c] = num++;
            while (s[r - 1][c] == 0)
                s[--r][c] = num++;
            c++;
        }
        for (int i = 0; i < t; i++, System.out.println())
            for (int j = 0; j < n; j++)
                System.out.printf("%d ", s[i][j]);
        for (int j = 0; j < t; j++)
            System.out.printf("%d ", s[t][j]);
        System.out.print("T ");
        for (int j = t + 1; j < n; j++)
            System.out.printf("%d ", s[t][j]);
        System.out.println();
        for (int i = t + 1; i < n; i++, System.out.println())
            for (int j = 0; j < n; j++)
                System.out.printf("%d ", s[i][j]);
        in.close();
    }
}

E - Non-Decreasing Colorful Path

题目大意

有一个 \(N(N \le 2 \times 10^5)\) 个点 \(M(N-1 \le M \le 2 \times 10^5)\) 条边的无向连通图。第 \(i\) 个点的点权值为 \(A_i\)。对于一条以点 \(1\) 为起点，以点 \(N\) 为终点的路径 \(P_1 \cdots P_N\)，对应一个权值序列 \(A_1 \cdots A_N\)，定义权值序列的分数为：

  • 如果权值序列是（非严格）单调递增的，则序列中不同数字的个数就是序列的分数。
  • 否则，这个序列的分数是 \(0\)。

请找出所有以点 \(1\) 为起点，以点 \(N\) 为终点的路径中，分数最大的权值序列。

解题思路

将原图中的无向边改为有向（从权值小的点连向权值大的点），然后求出从点 \(1\) 出发的最长路即可，可用拓扑排序。

但是拓扑排序只支持 DAG，而上述建图的方式可能存在两个点的权值相同，导致互相可达。由于序列的分数取决于序列中不同数字的个数，所以将相同权值的点缩成一个点。在缩点的时候可以不用 tarjan 算法来缩点，因为这个题的环都是类似重边的环，用并查集就可以了。缩点之后既能保证最长路的点数对应序列的分数（因为没有权值相同的点了），也能保证图是 DAG，可以拓扑排序。

拓扑排序是从入度为 \(0\) 的点开始的，只需要将点 \(1\) 的值从 \(1\) 开始计算，其他点的值设置为 \(-\infty\)，这样就能保证答案一定是从点 \(1\) 更新得到的。

参考代码 
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int maxn = 2E5 + 10;
const int maxm = 2E5 + 10;

int n, m, a[maxn];
int head[maxn], edge[maxm], ne[maxm], idx = 1;
void add(int u, int v)
{
    edge[idx] = v;
    ne[idx] = head[u];
    head[u] = idx;
    idx++;
}

int p[maxn];
int find(int u)
{return p[u] == u ? u : p[u] = find(p[u]);}
void merge(int u, int v)
{
    u = find(u), v = find(v);
    p[u] = v;
}

struct Edge {
    int u, v;
}e[maxm];

int ind[maxn], dis[maxn];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), p[i] = i;
    for(int i = 0; i < m; i++)
    {
        scanf("%d %d", &e[i].u, &e[i].v);
        if(a[e[i].u] == a[e[i].v])
            merge(e[i].u, e[i].v);
    }
    for(int i = 0, u, v; i < m; i++)
    {
        u = find(e[i].u);
        v = find(e[i].v);
        if(u == v)
            continue;
        if(a[u] > a[v])
            swap(u, v);
        ind[v]++;
        add(u, v);
    }
    queue<int> q;
    for(int u = 1; u <= n; u++) 
    {
        dis[u] = -1E6;
        if(p[u] == u && ind[u] == 0)
            q.push(u);
    }
    dis[find(1)] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            dis[v] = max(dis[v], dis[u] + 1);
            ind[v]--;
            if(!ind[v])
                q.push(v);
        }
    }
    cout << max(dis[find(n)], 0) << endl;
    return 0;
}

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static int[] p;

    private static int find(int u) {
        return u == p[u] ? u : (p[u] = find(p[u]));
    }

    private static void merge(int u, int v) {
        u = find(u);
        v = find(v);
        p[u] = v;
    }

    private static int[] head, edge, ne;
    private static int idx = 1;

    private static void graph_init(int n, int m) {
        head = new int[n];
        edge = new int[m];
        ne = new int[m];
    }

    private static void add(int u, int v) {
        edge[idx] = v;
        ne[idx] = head[u];
        head[u] = idx++;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[] a = new int[n + 1];
        p = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
            p[i] = i;
        }
        int[] eu = new int[m], ev = new int[m];
        for (int i = 0; i < m; i++) {
            eu[i] = in.nextInt();
            ev[i] = in.nextInt();
            if (a[eu[i]] == a[ev[i]])
                merge(eu[i], ev[i]);
        }
        graph_init(n + 1, m + 1);
        int[] ind = new int[n + 1];
        for (int i = 0; i < m; i++) {
            if (a[eu[i]] != a[ev[i]]) {
                int u = find(eu[i]);
                int v = find(ev[i]);
                if (a[u] > a[v]) {
                    int t = u;
                    u = v;
                    v = t;
                }
                ind[v]++;
                add(u, v);
            }
        }
        int[] dp = new int[n + 1];
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (i != find(i))
                continue;
            dp[find(i)] = (int) -1E6;
            if (ind[find(i)] == 0)
                q.add(i);
        }
        dp[find(1)] = 1;
        while (!q.isEmpty()) {
            int u = q.remove();
            for (int i = head[u]; i > 0; i = ne[i]) {
                int v = edge[i];
                dp[v] = Math.max(dp[u] + 1, dp[v]);
                ind[v]--;
                if (ind[v] == 0)
                    q.add(v);
            }
        }
        System.out.println(Math.max(dp[find(n)], 0));
        in.close();
    }
}

F - Hop Sugoroku

题目大意

有 \(N(N \le 2 \times 10^5)\) 个网格排成一行，每个网格的都有一个数字 \(A_i(A_i \le 2 \times 10^5)\)。初始的时候，你在第 \(1\) 个网格。接下来，你可以进行任意次数的移动，移动的规则为：假设你当前在第 \(i\) 个网格，在移动前任意选择一个正整数 \(x\)，然后移动到第 \(i + A_i \times x\) 个网格。每一次移动后，将脚下的网格染黑。初始的时候，第 \(1\) 个网格已经被染黑。你可以进行任意次移动（包括什么都不做，在第 \(1\) 个网格就停下来也是一种方案），在你停下之后，被染黑的网格的下标记为一种方案。问：有多少种不同的染黑方案？

初步思路

不难发现一种移动路线对应一种染黑方案，看着像 dp，定义 \(dp[i]\)：以 \(i\) 为终点的所有路径数量之和。那么答案就是所有的 \(dp[i]\) 之和。先考虑暴力的后向转移：

for(int i = 0; i < n; i++)
    for(int j = i + a[i]; j < n; j += a[i])
        dp[j] = (dp[j] + dp[i]) % mod;

显然，如果 \(A_i\) 全为 \(1\)，这个算法复杂度达到 \(O(n^2)\)，需要优化。

看样例输入：

5
1 2 3 1 1

当 \(i = 1\) 的时候，由于 \(A_1 = 1\)，第二层循环就有 \(1 \rightarrow 2\)，\(1 \rightarrow 3\)，\(1 \rightarrow 4\)，\(1 \rightarrow 5\)，\(1 \rightarrow 6\)，\(\cdots\)，\(1 \rightarrow N\)

当 \(i = 4\) 的时候，由于 \(A_4 = 1\)，第二层循环就有 \(? \rightarrow 4 \rightarrow 5\)，\(? \rightarrow 4 \rightarrow 6\)，\(\cdots\)，\(? \rightarrow 4 \rightarrow N\)

可以注意到，\(A_4\) 开始的路径可以完全复用在 \(A_1\) 从 \(1 \rightarrow 4\) 之后的路径中，只需要进行简单的拼接即可。例如，由于有 \(? \rightarrow 4 \rightarrow 6\)，就有 \(1 \rightarrow 6\)，这是因为 \(A_1 = A_4 = 1\)，步长是一样的，因此可以将 \(A_1\) 的计算交给 \(A_4\) 执行，间接合并。

初步想法是每个点在向后更新时只更新下一跳，并且将步长传播给下一跳，让下一跳代为传播。这样做的目的是，如果下一跳也有同样的步长，就能将相同的步长合并，减少计算量。下一跳开始传播的时候，需要将之前所有交给自己的步长都传播出去。

因此我开了一个 map 来存放点的步长。

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

const int mod = 998244353;

int main()
{
    int n, ans;
    cin >> n;
    vector<map<int, int>> A(n + 1);
    vector<int> dp(n + 1);
    dp[1] = 1;
    for (int i = 1, a; i <= n; i++)
    {
        ans += dp[i];
        if (ans >= mod)
            ans -= mod;
        scanf("%d", &a);
        if (A[i].count(a))
        {
            A[i][a] += dp[i];
            if (A[i][a] >= mod)
                A[i][a] -= mod;
        }
        else
            A[i][a] = dp[i];
        for (auto [p, c] : A[i])
            if (i + p <= n)
            {
                dp[i + p] += c;
                if (dp[i + p] >= mod)
                    dp[i + p] -= mod;
                if (A[i + p].count(p))
                {
                    A[i + p][p] += c;
                    if (A[i + p][p] >= mod)
                        A[i + p][p] -= mod;
                }
                else
                    A[i + p][p] = c;
            }
            else
                break;
        A[i].clear();
    }
    cout << ans << endl;
    return 0;
}

这个代码我多次优化常数，最终优化到 2.7s（本题要求 2.5s），大概有 10 个测试点超时。我认为时间性能的瓶颈在于开了多个 map，在增删改查的时候耗费不少时间。

正确思路

进一步发现，上述代码实质通过合并相同的步长来减少循环次数，而我们可以发现，只有相同的 \(A_i\) 值可以合并，所以没有必要用 map 存储所有经过这个点的步长，只需要存储相同的步长有多少。

换言之，我们仍然让点 \(i\) 不断的向后传播，直到碰到和 \(A_i\) 相同的 \(A_j\)，此时中止 \(i\) 的传播，后续由 \(j\) 代为传播。

最终 AC 代码出乎意料的简单。

参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 2E5 + 10;
const int mod  = 998244353;
int dp[maxn], x[maxn], n, a[maxn], ans;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    dp[0] = 1;
    for(int i = 0; i < n; i++)
    {
        ans = (ans + dp[i]) % mod;
        int y = (dp[i] + x[i]) % mod;
        for(int j = i + a[i]; j < n; j += a[i])
        {
            dp[j] = (dp[j] + y) % mod;
            if(a[i] == a[j]) 
            {
                x[j] = (x[j] + y) % mod;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int mod = 998244353;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n], dp = new int[n], x = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();
        dp[0] = 1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dp[i];
            ans %= mod;
            int t = (x[i] + dp[i]) % mod;
            for (int j = i + a[i]; j < n; j += a[i]) {
                dp[j] += t;
                dp[j] %= mod;
                if (a[i] == a[j]) {
                    x[j] += t;
                    break;
                }
            }
        }
        System.out.println(ans);
        in.close();
    }
}
时间复杂度证明

最坏的情况是没有发生合并，对应的序列是 \(1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \cdots\)，这个序列不会发生合并。

对应的计算次数是 \(n + 2 \times \frac{n}{2} + 3 \times \frac{n}{3} + \cdots\)，对于长度为 \(n\) 的序列，最大的数字不会超过 \(\sqrt{n}\)（将数字堆成下三角形即可），因此总的时间复杂度为 \(n\sqrt{n}\)。

最后更新: 2024-03-25
创建日期: 2024-02-28