跳转至

ABC334(A-G)

A - Christmas Present

题目大意

有两种商品 Bat 和 Glove，前者的价格是 \(B\)，后者的价格是 \(G(B \neq G)\)，输出价格较高的商品。

参考代码 
#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << (a > b ? "Bat" : "Glove");
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int b = in.nextInt(), g = in.nextInt();
        System.out.println(b > g ? "Bat" : "Glove");
        in.close();
    }
}

B - Christmas Trees

题目大意

有一条无限长度的数轴，给你一个整数 \(A(-10^{18} \le A \le 10^{18})\) 和一个正整数 \(M(1 \le M \le 10^9)\)，表示在所有形如 \(A+kM\) 的位置上都有一棵树，\(k\) 可取任意整数。问：在闭区间 \([L, R]\) 有多少棵树？

解题思路

\(A+kM\) 和 \(A+M+k'M\) 等价，所以先将其变成 \(0 \le A < M\) 的形式，同理对 \(L\) 和 \(R\) 也做类似的处理，\(L\) 变成第一个大于等于的树，\(R\) 变成第一个小于等于的树，然后 \(k\) 值相减即可。

参考代码 
#include <iostream>

using namespace std;
typedef long long LL;

int main()
{
    LL a, m, l, r;
    cin >> a >> m >> l >> r;
    a %= m;
    if(a < 0)
        a += m;
    LL k1 = l / m, r1 = l % m;
    if(r1 < 0)
    {
        r1 += m;
        k1--;
    }
    if(r1 > a)
        k1++;
    LL k2 = r / m, r2 = r % m;
    if(r2 < 0)
    {
        r2 += m;
        k2--;
    }
    if(r2 < a)
        k2--;
    cout << k2 - k1 + 1 << endl;
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long a = in.nextLong(), m = in.nextLong(), l = in.nextLong(), r = in.nextLong();
        a %= m;
        if (a < 0)
            a += m;
        long k1 = l / m, r1 = l % m;
        if (r1 < 0) {
            r1 += m;
            k1--;
        }
        if (r1 > a)
            k1++;
        long k2 = r / m, r2 = r % m;
        if (r2 < 0) {
            r2 += m;
            k2--;
        }
        if (r2 < a)
            k2--;
        System.out.println(k2 - k1 + 1);
        in.close();
    }
}

C - Socks 2

题目大意

有 \(N\) 双袜子，第 \(i\) 双袜子的颜色值是 \(i\)，现在有 \(K\) 只袜子不见了，不见的袜子是 \(A_1, A_2, \cdots, A_K(1 \le A_1 < A_2 < \cdots < A_K \le N)\)， 如果将颜色为 \(i\) 的袜子和颜色为 \(j\) 的袜子组合成一双袜子，则会产生 \(|i-j|\) 的奇异值。在 \(K\) 双袜子丢失之后，将剩余的袜子两两配对（如果袜子的数量是奇数则可以丢弃任意一只袜子），输出最小的奇异值之和。

解题思路

首先将剩余的袜子按颜色大小排序。

可以发现如果剩余袜子是偶数的话，只需要按相邻的顺序配对答案一定是最小的。

考虑奇数如何处理。显然，丢弃的袜子一定是第奇数个袜子，那么可以弄一个前缀和 pre[i] 表示将 \(i\) （\(i\) 是第奇数个袜子）之前的袜子两两配对产生的奇异值的前缀和，同理再弄一个后缀和 suf[i]。最后枚举丢弃的袜子就可以了。

本题还有一个小结论，注意到所有被丢弃的袜子都是一只一只的丢弃，所以剩下的完整的袜子不用动，直接保持配对关系，将剩下的袜子配对就可以了。这是因为当 \(a < b < c\) 时，有等式 \(|a - b| + |c - b| = |a - c|\)。（ps：这个结论放在实际生活中也很显然）。

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

using namespace std;

const int maxn = 2E5 + 10;
int a[maxn], pre[maxn], suf[maxn];

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < k; i++)
        scanf("%d", &a[i]);
    for(int i = 2; i < k; i += 2)
        pre[i] = pre[i-2] + a[i-1] - a[i-2];
    if(k & 1)
    {
        for(int i = k - 3; i >= 0; i -= 2)
            suf[i] = suf[i+2] + a[i+2] - a[i+1];
        int m = 2E9;
        for(int i = 0; i < k; i += 2)
            m = min(m, suf[i] + pre[i]);
        cout << m;
    }
    else
        cout << pre[k-2] + a[k-1] - a[k-2];
    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 k = in.nextInt();
        int[] a = new int[k];
        int[] pre = new int[k];
        int[] suf = new int[k];
        for (int i = 0; i < k; i++)
            a[i] = in.nextInt();
        for (int i = 2; i < k; i += 2)
            pre[i] = pre[i - 2] + a[i - 1] - a[i - 2];
        if (k % 2 == 0)
            System.out.println(pre[k - 2] + a[k - 1] - a[k - 2]);
        else {
            for (int i = k - 3; i >= 0; i -= 2)
                suf[i] = suf[i + 2] + a[i + 2] - a[i + 1];
            int m = (int) 2E9;
            for (int i = 0; i < k; i += 2)
                m = Math.min(m, pre[i] + suf[i]);
            System.out.println(m);
        }
        in.close();
    }
}

D - Reindeer and Sleigh

题目大意

有 \(N\) 个雪橇，第 \(i\) 个雪橇需要 \(R_i\) 只驯鹿才能拉得动。有 \(Q\) 个询问，每个询问给你一个数字 \(X\) 代表驯鹿的数量，你需要回答出在拥有 \(X\) 只驯鹿的条件下最多能拉动多少个雪橇。

解题思路

把 \(R_i\) 排序，在前缀和上二分就好。

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

using namespace std;
typedef long long LL;
const int maxn = 2E5 + 10;
int n, q;
LL a[maxn];

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    sort(a+1, a+1+n);
    for(int i = 2; i <= n; i++)
        a[i] += a[i-1];
    LL x;
    int l, r, mid;
    while(q--)
    {
        scanf("%lld", &x);
        l = 0, r = n;
        while(l < r) 
        {
            mid = (l + r + 1) / 2;
            if(x >= a[mid])
                l = mid;
            else
                r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}

import java.util.Arrays;
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();
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = in.nextLong();
        Arrays.sort(a);
        for (int i = 2; i <= n; i++)
            a[i] += a[i - 1];
        long x;
        int l, r, mid;
        for (; q > 0; q--) {
            x = in.nextLong();
            l = 0;
            r = n;
            while (l < r) {
                mid = (l + r + 1) / 2;
                if (x >= a[mid])
                    l = mid;
                else
                    r = mid - 1;
            }
            System.out.println(l);
        }
        in.close();
    }
}

E - Christmas Color Grid 1

题目大意

有一个 \(H \times W(1 \le H, W \le 1000)\) 的网格，每个网格可能是红色或绿色，红色用 . 表示，绿色用 # 表示。每个网格和上下左右是相邻的。相邻的绿色网格组成一个绿色连通分量。现在，所有的红色网格会被随机等概率的挑选出一个，然后染成绿色，问：在一个红色被染成绿色之后，绿色连通分量数量的数学期望是多少？答案对 \(998244353\) 取模。

解题思路

先统计红色的个数以及绿色连通分量的个数，在统计的绿色连通分量的个数的时候对每个连通分量进行编号。接下来遍历所有的红色网格，红色网格染色之后可能会连接上下左右的绿色连通分量，用绿色连通分量的编号来判别是否连通分量合并的情况。

参考代码

喜报：本题 Java 代码超时

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

typedef long long LL;
const int maxn = 1000 + 10;
const int mod = 998244353;
char g[maxn][maxn];
int n, m, p[maxn][maxn];

const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

bool inlim(int r, int c)
{return r >= 0 && r < n && c >= 0 && c < m;}

void dfs(int r, int c, int f)
{
    p[r][c] = f;
    for(int i = 0; i < 4; i++)
    {
        int nr = r + dr[i], nc = c + dc[i];
        if(inlim(nr, nc) && g[nr][nc] == '#' && p[nr][nc] == -1)
            dfs(nr, nc, f);
    }
}

void exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

int inv(int a, int p)
{
    int x, y;
    exgcd(a, p, x, y);
    if(x < p)
        x += p;
    return x;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        scanf("%s", g[i]);
    memset(p, -1, sizeof p);
    int a = 0, b = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(g[i][j] == '.')
                b++;
            else if(p[i][j] == -1)
                dfs(i, j, a++);
    b = inv(b, mod);
    LL ans = 0;
    for(int r = 0; r < n; r++)
        for(int c = 0; c < m; c++)
            if(g[r][c] == '.')
            {
                set<int> ng;
                for(int i = 0; i < 4; i++)
                {
                    int nr = r + dr[i], nc = c + dc[i];
                    if(inlim(nr, nc) && g[nr][nc] == '#')
                        ng.insert(p[nr][nc]);
                }
                ans += (a + 1 - ng.size()) * b % mod;
                ans %= mod;
            }
    cout << ans << endl;
    return 0;
}

F - Christmas Present 2

题目大意

圣诞老人打算给 \(N\) 个小孩送礼物，其中圣诞老人的家在 \((S_X, S_Y)\)，第 \(i\) 个小孩的家在 \((X_i, Y_i)\)。圣诞老人打算按照 \(1, 2, \cdots, N\) 的顺序给每个小孩都送一个礼物。圣诞老人一次只能持有最多 \(K\) 个礼物，如果手上没有礼物，就必须回家补充。问：圣诞老人从家里出发，给所有小孩都送一个礼物，然后返回家中，最短的路程是多少？

解题思路

由于顺序是一定的，需要考虑的就是在哪一段中间回家补充礼物。

定义 \(dp[i]\)：前 \(i\) 个房子都已经送完，然后回家补充礼物所需要的最短距离

转移时，考虑枚举上一次回家补充礼物的位置，可得：

\[ dp[i] = \min_{i - j \le k}^{i-1}\{dp[j] + dist(j+1) + w(j+1, i) + dist(i)\} \]

上式中，\(dist(i)\) 表示第 \(i\) 个房子到圣诞老人的家的距离，\(w(j+1, i)\) 表示按顺序从第 \(j+1\) 个房子一直走到第 \(i\) 个房子的路程之和。

\(dist(i)\) 可以预先处理出来，用 \(d[i]\) 表示。\(w(j+1, i)\) 可以先处理出前缀和，\(s[i]\) 表示按顺序从圣诞老人的家一直走到第 \(i\) 个房子的路程之和，则有 \(w(j+1, i) = s[i] - s[j+1]\)，于是：

\[ \begin{matrix} dp[i] & = & \min_{i - j \le k}^{i-1}\{dp[j] + d[j+1] + s[i] - s[j+1] + d[i]\} \\ & = & \min_{i - j \le k}^{i-1}\{dp[j] + d[j+1] - s[j+1]\} + s[i] + d[i] \end{matrix} \]

这个式子中只包含变量 \(j\)，用单调队列优化即可。

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

using namespace std;

// i - j <= k
// dp[i] = min{ dp[j] + d[j+1] + s[i] - s[j+1] + d[i] }
// dp[i] = min{ dp[j] + d[j+1] - s[j+1] } + s[i] + d[i]
const int maxn = 2E5 + 10;
int n, k;
double x[maxn], y[maxn], d[maxn], s[maxn], dp[maxn];

double dist(double x1, double y1, double x2, double y2)
{
    double dx = x2 - x1, dy = y2 - y1;
    return sqrt(dx*dx + dy*dy);
}

double val(int j)
{return dp[j] + d[j+1] - s[j+1];}

double cal(int i, int j)
{return val(j) + s[i] + d[i];}

int main()
{
    cin >> n >> k >> x[0] >> y[0];
    for(int i = 1; i <= n; i++)
    {
        scanf("%lf %lf", &x[i], &y[i]);
        d[i] = dist(x[0], y[0], x[i], y[i]);
        s[i] = s[i-1] + dist(x[i-1], y[i-1], x[i], y[i]);
    }
    deque<int> dq;
    dq.push_back(0);
    for(int i = 1; i <= n; i++)
    {
        int j = dq.front();
        dp[i] = cal(i, j);
        if(i - j == k)
            dq.pop_front();
        while(!dq.empty() && val(dq.back()) >= val(i))
            dq.pop_back();
        dq.push_back(i);
    }
    printf("%lf\n", dp[n]);
    return 0;
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    private static double[] x, y, d, s, dp;

    private static double dist(double x1, double y1, double x2, double y2) {
        double dx = x2 - x1, dy = y2 - y1;
        return Math.sqrt(dx * dx + dy * dy);
    }

    private static double val(int j) {
        return dp[j] + d[j + 1] - s[j + 1];
    }

    private static double cal(int i, int j) {
        return val(j) + s[i] + d[i];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        x = new double[n + 2];
        y = new double[n + 2];
        d = new double[n + 2];
        s = new double[n + 2];
        dp = new double[n + 2];
        x[0] = in.nextInt();
        y[0] = in.nextInt();
        for (int i = 1; i <= n; i++) {
            x[i] = in.nextInt();
            y[i] = in.nextInt();
            d[i] = dist(x[0], y[0], x[i], y[i]);
            s[i] = s[i - 1] + dist(x[i - 1], y[i - 1], x[i], y[i]);
        }
        Deque<Integer> dq = new ArrayDeque<>();
        dq.addLast(0);
        for (int i = 1; i <= n; i++) {
            int j = dq.getFirst();
            dp[i] = cal(i, j);
            if (i - j == k)
                dq.removeFirst();
            while (!dq.isEmpty() && val(dq.getLast()) >= val(i))
                dq.removeLast();
            dq.addLast(i);
        }
        System.out.printf("%.8f", dp[n]);
        in.close();
    }
}

G - Christmas Color Grid 2

题目大意

同 E 题，但是本题问的是将一个 绿色 变成 红色 之后绿色的连通分量的数量的数学期望。

解题思路

绿色是图中的原有的点，涂成红色相当于删去这个点。显然就是要找图中的割点，用 tarjan 算法找割点的时候有两种情况：

  • 点 \(u\) 是 dfs树 的根节点，则记录其在 dfs树 中孩子的个数 \(son\)，如果 \(son \ge 2\)，则点 \(u\) 就是割点。此时割点 \(u\) 后连通分量数增加 \(son-1\) 个。
  • 点 \(u\) 不是 dfs树 的根节点，则考察点 \(u\) 在 dfs树 中的孩子 \(v\)，若 \(low[v] \ge dfn[u]\)，则点 \(u\) 是割点。在计算割去这个点所增加的连通分量时，每当有一个孩子 \(v\) 满足，则割去点 \(u\) 后连通分量数就会加一。
参考代码 
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;
const int maxn = 1000 + 10;
const int mod = 998244353;
char g[maxn][maxn];
int n, m, p[maxn][maxn];

const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

bool inlim(int r, int c)
{return r >= 0 && r < n && c >= 0 && c < m;}

void dfs(int r, int c, int f)
{
    p[r][c] = f;
    for(int i = 0; i < 4; i++)
    {
        int nr = r + dr[i], nc = c + dc[i];
        if(inlim(nr, nc) && g[nr][nc] == '#' && p[nr][nc] == -1)
            dfs(nr, nc, f);
    }
}

void exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

int inv(int a, int p)
{
    int x, y;
    exgcd(a, p, x, y);
    if(x < p)
        x += p;
    return x;
}

int dfn[maxn][maxn], low[maxn][maxn], ti = 1, cnt[maxn][maxn];
void tarjan(int r, int c, int R, int C)
{
    dfn[r][c] = low[r][c] = ti++;
    if(r == R && c == C)
    {
        int son = 0;
        for(int i = 0; i < 4; i++)
        {
            int nr = r + dr[i], nc = c + dc[i];
            if(!inlim(nr, nc) || g[nr][nc] == '.')
                continue;
            if(!dfn[nr][nc])
            {
                son++;
                tarjan(nr, nc, R, C);
            }
        }
        cnt[r][c] = son - 1;
    }
    else
    {
        for(int i = 0; i < 4; i++)
        {
            int nr = r + dr[i], nc = c + dc[i];
            if(!inlim(nr, nc) || g[nr][nc] == '.')
                continue;
            if(!dfn[nr][nc])
            {
                tarjan(nr, nc, R, C);
                low[r][c] = min(low[r][c], low[nr][nc]);
                if(low[nr][nc] >= dfn[r][c])
                    cnt[r][c]++;
            }
            else
                low[r][c] = min(low[r][c], dfn[nr][nc]);
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        scanf("%s", g[i]);
    memset(p, -1, sizeof p);
    LL a = 0, b = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(g[i][j] == '#')
            {
                b++;
                if(p[i][j] == -1)
                    dfs(i, j, a++);
            }
    b = inv(b, mod);
    LL ans = 0;
    for(int r = 0; r < n; r++)
        for(int c = 0; c < m; c++)
            if(g[r][c] == '#')
            {
                if(!dfn[r][c])
                    tarjan(r, c, r, c);
                ans += (a + cnt[r][c]) * b % mod;
                ans %= mod;
            }
    cout << ans << endl;
    return 0;
}
最后更新: 2024-03-01
创建日期: 2024-02-29