ABC341(A-G)

A - Print 341

题目大意

给你一个整数 \(N\)，交替打印 \(N\) 个 0 和 \(N+1\) 个 1。

参考代码

C++Java

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << 1;
    while(n--)
        cout << "01";
    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();
        System.out.print("1");
        while (n-- > 0)
            System.out.print("01");
        in.close();
    }
}

---

B - Foreign Exchange

题目大意

给你 \(N\) 个数，第 \(i\) 个数是 \(A_i\)，对于 \(1 \le i \le N-1\) 的数字 \(A_i\)，如果 \(A_i \ge S_i\)，你可以让 \(A_i\) 减少 \(S_i\)，然后让 \(A_{i+1}\) 加上 \(T_i\)。问：\(A_N\) 的最大值是多少？

参考代码

C++Java

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;
int n;
LL a[maxn];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for(int i = 1, s, t; i < n; i++)
    {
        scanf("%d %d", &s, &t);
        LL k = a[i] / s;
        a[i+1] += k * t;
    }
    cout << a[n] << endl;
    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();
        long[] a = new long[n + 1];

        for (int i = 1; i <= n; i++)
            a[i] = in.nextLong();
        for (int i = 1, s, t; i < n; i++) {
            s = in.nextInt();
            t = in.nextInt();
            long k = a[i] / s;
            a[i + 1] += k * t;
        }
        System.out.println(a[n]);
        in.close();
    }
}

---

C - Takahashi Gets Lost

题目大意

有一个 \(H \times W(1 \le H, W \le 500)\) 的网格，# 不能走，. 可以走。给你一个长度为 \(N(1 \le N \le 500)\) 的移动序列，序列只可能是 LRUD 之一。问：有哪些位置可以成为这个移动序列的起点？

解题思路

枚举所有的起点进行移动就好，复杂度 \(O(HWN)\)

参考代码

C++Java

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 500 + 10;
int n, m, k;
char g[maxn][maxn], t[maxn];

int main()
{
    cin >> n >> m >> k;
    scanf("%s", t);
    for(int i = 0; i < n; i++)
        scanf("%s", g[i]);
    int ans = 0;
    for(int x = 1; x < n-1; x++)
        for(int y = 1; y < m-1; y++)
        {
            int r = x, c = y, i = 0;
            while(i < k && g[r][c] != '#')
            {
                if(t[i] == 'L')
                    c--;
                else if(t[i] == 'R')
                    c++;
                else if(t[i] == 'U')
                    r--;
                else
                    r++;
                i++;
            }
            ans += g[r][c] == '.';
        }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n, m, k;
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        char[][] g = new char[n][];
        char[] t = in.next().toCharArray();
        for (int i = 0; i < n; i++)
            g[i] = in.next().toCharArray();
        int ans = 0;
        for (int x = 1; x < n - 1; x++)
            for (int y = 1; y < m - 1; y++) {
                int r = x, c = y, i = 0;
                while (i < k && g[r][c] != '#') {
                    if (t[i] == 'L')
                        c--;
                    else if (t[i] == 'R')
                        c++;
                    else if (t[i] == 'U')
                        r--;
                    else
                        r++;
                    i++;
                }
                ans += (g[r][c] == '.' ? 1 : 0);
            }
        System.out.println(ans);
        in.close();
    }
}

---

D - Only one of two

题目大意

给你三个数 \(N\)， \(M(1 \le N, M \le 10^8)\) 和 \(K(1 \le K \le 10^{10})\)，其中 \(N \neq M\)。输出第 \(K\) 个只能能整除 \(N\) 或 \(M\) 其中之一的数。

解题思路

设 \(g = \gcd(N, M)\)，\(N = gn\)，\(M = gm\)，\(L = gnm\)，则在 \([1, L]\) 区间内，最多有 \(\frac{L}{N} = m\) 个可以整除 \(N\) 的数，但要去掉能同时整除 \(N\) 和 \(M\) 的数，这样的数只有 \(L\)（因为 \(L\) 是两者的最小公倍数），所以有 \(m-1\) 个只能整除 \(N\) 的数，同理有 \(n-1\) 个只能整除 \(M\) 的数，两种数字加起来，就是 \(n+m-2\) 个，即 \([1, L]\) 区间内有 \(n+m-2\) 个满足条件的数。同样的，\([L+1, 2L]\) 也有 \(n+m-2\) 个满足条件的数。因此可以快速算出 \(K\) 在第几个区间，假设 \(K\) 在 \([(a-1)L+1, aL]\)，只需要在上面二分出数字即可。

假设当前二分的数字是 \(x\)，则只需要算出 \(\frac{x}{N} + \frac{x}{M} - 2\lfloor\frac{x}{L}\rfloor\) 就能知道 \(x\) 之前有多少个满足条件的数。二分的时间复杂度为 \(O(log_2L) = O(log_2NM)\)，可以通过本题。

参考代码

C++Java

#include <iostream>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b)
{return b ? gcd(b, a % b) : a;}

int main()
{
    LL N, M, K;
    cin >> N >> M >> K;
    LL g = gcd(N, M), n = N / g, m = M / g;
    LL r = (K + n + m - 3) / (n + m - 2), l = r - 1;
    l *= g * n * m;
    r *= g * n * m;
    while(l < r)
    {
        LL mid = (l + r) / 2;
        if(mid / N + mid / M - mid / (g * n * m) * 2 >= K)
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    private static long gcd(long a, long b) {
        return b > 0 ? gcd(b, a % b) : a;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long N = in.nextLong();
        long M = in.nextLong();
        long K = in.nextLong();
        long g = gcd(N, M), n = N / g, m = M / g;
        long r = (K + n + m - 3) / (n + m - 2), l = r - 1;
        l *= g * n * m;
        r *= g * n * m;
        while (l < r) {
            long mid = (l + r) / 2;
            if (mid / N + mid / M - mid / (g * n * m) * 2 >= K)
                r = mid;
            else
                l = mid + 1;
        }
        System.out.println(l);
        in.close();
    }
}

---

E - Alternating String

题目大意

给你一个长度为 \(N(N \le 5 \times 10^5)\) 的字符串 \(S\) ，字符串由 0 和 1 组成。同时给你 \(Q(Q \le 5 \times 10^5)\) 个操作，有两种类型：

• 1 L R：表示将 \(S\) 的 \([L, R]\) 反转。
• 2 L R：询问 \(S\) 的 \([L, R]\) 是否 0 和 1 交替出现，如果是输出 Yes，否则输出 No。

解题思路

定义 \(b\) 数组：

\[ b[i] = \left\{ \begin{matrix} 0, & i < n \land s[i] = s[i+1] \\ 1, & i = n \lor s[i] \neq s[i+1] \end{matrix} \right. \]

考虑 2 L R 操作如何处理，只需要保证 \(b\) 数组 \([L, R-1]\) 的部分全为 \(1\) 即可，所以需要处理出前缀和。

考虑 1 L R 操作怎么做，反转 \([L, R]\) 不会改变 \([L, R-1]\) 部分的值，只会影响 \(b[L-1]\) 和 \(b[R]\) 的值。

只需要维护一个单点修改，区间查询的线段树就可以了。需要注意的就是需要把 \(i = 0\) 这个点加上，因为修改的时候会影响到 \(b[0]\)，但是查询的时候不会查到 \(b[0]\) 的值。

参考代码

C++Java

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 5E5 + 10;
int n, q, t[maxn * 4];
char s[maxn];

void build(int p, int beg, int end)
{
    if(beg == end)
    {
        t[p] = s[beg] != s[beg+1];
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    build(lch, beg, mid);
    build(rch, mid+1, end);
    t[p] = t[lch] + t[rch];
}

void update(int p, int beg, int end, int pos)
{
    if(beg == end)
    {
        t[p] ^= 1;
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    pos <= mid ? update(lch, beg, mid, pos) : update(rch, mid+1, end, pos);
    t[p] = t[lch] + t[rch];
}

int ask(int p, int beg, int end, int l, int r)
{
    if(end < l || beg > r)
        return 0;
    if(beg >= l && end <= r)
        return t[p];
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    return ask(lch, beg, mid, l, r) + ask(rch, mid+1, end, l, r);
}

int main()
{
    cin >> n >> q;
    scanf("%s", s+1);
    int op, l, r;
    build(1, 0, n);
    while(q--)
    {
        scanf("%d %d %d", &op, &l, &r);
        if(op == 1) {
            update(1, 0, n, l-1);
            update(1, 0, n, r);
        }
        else
            puts(ask(1, 0, n, l, r-1) == r-l ? "Yes" : "No");
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static int[] t;
    private static char[] s;

    private static void build(int p, int beg, int end) {
        if (beg == end) {
            t[p] = s[beg] != s[beg + 1] ? 1 : 0;
            return;
        }
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        build(lch, beg, mid);
        build(rch, mid + 1, end);
        t[p] = t[lch] + t[rch];
    }

    private static void update(int p, int beg, int end, int pos) {
        if (beg == end) {
            t[p] ^= 1;
            return;
        }
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        if (pos <= mid)
            update(lch, beg, mid, pos);
        else
            update(rch, mid + 1, end, pos);
        t[p] = t[lch] + t[rch];
    }

    private static int ask(int p, int beg, int end, int l, int r) {
        if (end < l || beg > r)
            return 0;
        if (beg >= l && end <= r)
            return t[p];
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        return ask(lch, beg, mid, l, r) + ask(rch, mid + 1, end, l, r);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        t = new int[n * 4];
        s = new char[n + 2];
        in.next().getChars(0, n, s, 1);

        int op, l, r;
        build(1, 0, n);
        while (q-- > 0) {
            op = in.nextInt();
            l = in.nextInt();
            r = in.nextInt();
            if (op == 1) {
                update(1, 0, n, l - 1);
                update(1, 0, n, r);
            } else
                System.out.println(ask(1, 0, n, l, r - 1) == r - l ? "Yes" : "No");
        }
        in.close();
    }
}

---

F - Breakdown

题目大意

给你一个 \(N(1 \le N \le 5000)\) 个点和 \(M(1 \le M \le \min(\frac{N(N-1)}{2}, 5000))\) 条边的无向图，每个点都有权值 \(W_i(1 \le W_i \le 5000)\) 和 \(A_i(1 \le A_i \le 10^9)\) 个碎片，你可以执行下列操作任意次：

• 首先，选择图中一个权值大于 \(0\) 的点，假设你选择了点 \(x\)。然后，点 \(x\) 减少一个碎片。
• 然后，任意选择一个与点 \(u\) 邻接的点集 \(S\)（可以为空集），这个集合需要满足 。然后，集合 \(S\) 中的每个点的都将增加一个碎片。

可以证明在无限次操作之后，图所有的点都将没有碎片。

问：最多能执行多少次操作？

解题思路

考虑用 dp 解决这个问题，先定义 \(dp[u]\) 表示如果点 \(u\) 上有一个碎片，这个碎片（以及选择子集之后分散之后的所有碎片）最多能操作几次，由于碎片只能流向权值更小的点，则至少要知道所有 \(W_v < W_u\) 的 \(dp[v]\) 值。

很明显应该从权值小的点开始计算，所以将图从无向图改为有向图，若 \(W_u < W_v\)，则连一条 \(u \rightarrow v\) 的边，表示可以从点 \(u\) 更新 \(v\) 的值，这样就是一个 DAG， 初始的值为 \(dp[u] = 1\)。

下面考虑如何计算 \(dp[v]\)，假设所有 \(W_u < W_v\) 的 \(dp[u]\) 都已经计算完毕，则需要选择一个子集 \(S\)，满足 \(\sum\limits_{y \in S}W_y < W_x\)，同时最大化可操作的次数，这就是一个背包问题，所以到这里将扩展成二维的 \(dp[u][j]\) 表示如果点 \(u\) 上有一个碎片，这个碎片（以及选择一个权值之和为 \(j\) 的子集之后分散之后的所有碎片）最多能操作几次，更新的操作和普通的背包类似。注意到 \(W_i \le 5000\)，而且边的数量不会超过 \(5000\)，所以总的时间复杂度就是 \(O(MW)\)，可以通过本题。

参考代码

C++Java

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long LL;
const int maxn = 5000 + 10;
const int maxm = 5000 + 10;
const int maxw = 5000 + 10;
int head[maxn], edge[maxm], ne[maxm], idx = 1, ind[maxn];
void add(int u, int v)
{
    ind[v]++;
    edge[idx] = v;
    ne[idx] = head[u];
    head[u] = idx++;
}

int n, m, eu[maxm], ev[maxm], w[maxn], a[maxn];
LL dp[maxn][maxw];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++)
        scanf("%d %d", &eu[i], &ev[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 0; i < m; i++)
        if(w[eu[i]] < w[ev[i]])
            add(eu[i], ev[i]);
        else if(w[eu[i]] > w[ev[i]])
            add(ev[i], eu[i]);
    queue<int> q;
    for(int u = 1; u <= n; u++) 
        if(!ind[u])
            q.push(u);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        int val = dp[u][w[u]-1]+1;
        for(int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            for(int j = w[v]-1; j-w[u] >= 0; j--)
                dp[v][j] = max(dp[v][j], dp[v][j-w[u]]+val);
            if(--ind[v] == 0)
                q.push(v);
        }
    }
    LL ans = 0;
    for(int u = 1; u <= n; u++)
        ans += (dp[u][w[u]-1]+1) * a[u];
    cout << ans << endl;
    return 0;
}

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

public class Main {
    private static int[] head, edge, ne, ind;
    private static int idx;

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

    private static void add(int u, int v) {
        ind[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();
        int m = in.nextInt();
        int[] eu = new int[m];
        int[] ev = new int[m];
        int[] w = new int[n + 1];
        int[] a = new int[n + 1];

        for (int i = 0; i < m; i++) {
            eu[i] = in.nextInt();
            ev[i] = in.nextInt();
        }
        int mw = 0;
        for (int i = 1; i <= n; i++) {
            w[i] = in.nextInt();
            mw = Math.max(mw, w[i]);
        }
        for (int i = 1; i <= n; i++)
            a[i] = in.nextInt();
        long[][] dp = new long[n + 1][mw + 1];
        graph_init(n + 1, m + 1);
        for (int i = 0; i < m; i++)
            if (w[eu[i]] < w[ev[i]])
                add(eu[i], ev[i]);
            else if (w[eu[i]] > w[ev[i]])
                add(ev[i], eu[i]);
        Queue<Integer> q = new ArrayDeque<>();
        for (int u = 1; u <= n; u++)
            if (ind[u] == 0)
                q.add(u);
        while (!q.isEmpty()) {
            int u = q.remove();
            long val = dp[u][w[u] - 1] + 1;
            for (int i = head[u]; i > 0; i = ne[i]) {
                int v = edge[i];
                for (int j = w[v] - 1; j - w[u] >= 0; j--)
                    dp[v][j] = Math.max(dp[v][j], dp[v][j - w[u]] + val);
                if (--ind[v] == 0)
                    q.add(v);
            }
        }
        long ans = 0;
        for (int u = 1; u <= n; u++)
            ans += (dp[u][w[u] - 1] + 1) * a[u];
        System.out.println(ans);
        in.close();
    }
}

---

G - Highest Ratio

题目大意

给你 \(N(1 \le N \le 2 \times 10^5)\) 个数，第 \(i\) 个数是 \(A_i(1 \le A_i \le 10^6)\)，对每个位置 \(1 \le l \le n\)，求出 \(\max\limits_{l \le r \le n}\frac{A_i}{r-l+1}\)

解题思路

在很多地方看到这道题的题解（包括官解和洛谷）都是用的斜率优化，但其实这道题有非常简单的做法。

首选对平均值，有一个非常直观的应用，假设有一堆数字平均值是 \(x\)，另一堆数字的平均值是 \(y\)，且 \(x \le y\) 则将这两堆数字合并起来，得到的平均值一定是在 \([x, y]\) 区间内的，换言之，第二堆数字加入之后拉高了第一堆数字的平均值。虽然是很直观，但笔者还是证明一下。

已知 \(\frac{a}{b} < \frac{c}{d}(a > 0, b > 0, c > 0, d > 0)\)， 求证 \(\frac{a}{b} < \frac{a+c}{b+d}\) ，证明如下：

\[ \begin{matrix} 要证 & \frac{a}{b} < \frac{a+c}{b+d} \\ 只要证 & ab+ad < ab + bc \\ 只要证 & ad < bc \\ 只要证 & \frac{a}{b} < \frac{c}{d}\\ \end{matrix} \]

这就完成了证明。

应用上述定理可以得到本题的贪心解法，首先我们从右往左计算，假设 \(avg[i]\) 表示第 \(i\) 个位置的答案，初始值就是 \(avg[n] = A[n]\)，在从右往左遍历的时候维护一个栈，栈中存放着右侧的 \(avg\) 值，在计算 \(avg[i]\) 的值时，一开始先假定 \(avg[i] = A[i]\) ，接下来开始判断，如果栈顶的值大于 \(avg[i]\)，表示碰到了均值更大的一堆数，此时将两堆合并，得到的均值一定更大，直到栈为空或者栈顶的值小于 \(avg[i]\)，此时就找到了答案，将 \(avg[i]\) 的值入栈（也就是将合并后的堆入栈）。

显然，这个栈的是单调递减的。由于每个点最多入栈一次、出栈一次，所以时间复杂度是 \(O(n)\) 的，虽然和斜率优化复杂度一样，但代码要简单的多。

参考代码

C++Java

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

const int maxn = 2E5 + 10;
int n, a[maxn];
double avg[maxn];

struct Node {
    double avg;
    int cnt;
};

stack<Node> st;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    avg[n] = a[n];
    st.push(Node{avg[n], 1});
    for(int i = n - 1; i; i--)
    {
        avg[i] = a[i];
        int cnt = 1;
        while(!st.empty() && avg[i] <= st.top().avg)
        {
            Node p = st.top();
            st.pop();
            avg[i] = (avg[i] * cnt + p.avg * p.cnt) / (cnt + p.cnt);
            cnt += p.cnt;
        }
        st.push(Node{avg[i], cnt});
    }
    for(int i = 1; i <= n; i++)
        printf("%.8lf\n", avg[i]);
    return 0;
}

import java.util.Scanner;
import java.util.Stack;

class Node {
    public double avg;
    public int cnt;

    public Node(double a, int c) {
        avg = a;
        cnt = c;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n + 1];
        double[] avg = new double[n + 1];
        Stack<Node> st = new Stack<>();
        for (int i = 1; i <= n; i++)
            a[i] = in.nextInt();
        avg[n] = a[n];
        st.push(new Node(avg[n], 1));
        for (int i = n - 1; i > 0; i--) {
            avg[i] = a[i];
            int cnt = 1;
            while (!st.empty() && avg[i] <= st.peek().avg) {
                Node p = st.pop();
                avg[i] = (avg[i] * cnt + p.avg * p.cnt) / (cnt + p.cnt);
                cnt += p.cnt;
            }
            st.push(new Node(avg[i], cnt));
        }
        for (int i = 1; i <= n; i++)
            System.out.printf("%.8f\n", avg[i]);
        in.close();
    }
}

---

---

最后更新: 2024-03-14
创建日期: 2024-03-14