AtCoder Beginner Contest 385 A~D

IronMen · 2025-03-06 22:53:13 · 题解

A - Equally

洛谷链接

AtCoder链接

题目

给你三个整数 A,B,C。请判断能否将这三个整数分成两组或更多组，使这些组的和相等。

代码

#include <bits/stdc++.h>

using namespace std;

int a, b, c;

int main()
{
    scanf("%d %d %d", &a, &b, &c);
    if (a == b && b == c)
        puts("Yes");
    else if (a + b == c)
        puts("Yes");
    else if (b + c == a)
        puts("Yes");
    else if (a + c == b)
        puts("Yes");
    else
        puts("No");
    return 0;
}

B - Santa Claus 1

洛谷链接

AtCoder链接

题目

有一个网格，网格中有 H 行和 W 列。让 (i,j) 表示从上往下数第 i 行和从左往上数第 j 列的单元格。

如果 S_{i,j} 是 #，则 (i,j) 单元格无法通过；如果是 .，则该单元格可以通过且不包含房屋；如果是 @，则该单元格可以通过且包含房屋。

起初，圣诞老人在 (X,Y) 单元中。他将根据字符串 T 采取以下行动。

• 假设 |T| 是字符串 T 的长度。对于 i=1,2, \ldots ,|T|，他的移动步骤如下。
  • 假设 (x,y) 是他目前所在的单元格。
  • 如果 T_i 是 U，且 (x-1,y) 单元格可以通过，则移动到 (x-1,y) 单元格。
  • 如果 T_i 是 D，且 (x+1,y) 单元格可以通过，请移至 (x+1,y) 单元格。
  • 如果 T_i 是 L，且 (x,y-1) 单元格可以通过，请移动到 (x,y-1) 单元格。
  • 如果 T_i 是 R，且 (x,y+1) 单元格可以通过，则移动到 (x,y+1) 单元格。
  • 否则，停留在 (x,y) 格。

找出他完成所有行动后所在的单元格，以及他在行动过程中经过或到达的不同房子的数量。如果多次经过同一间房子，则只计算一次。

代码

#include <bits/stdc++.h>

using namespace std;

int h, w, x, y, c;
string s[110], t;
bool f[110][110];

int main()
{
    scanf("%d %d %d %d", &h, &w, &x, &y);
    for (int i = 0; i < h; i ++ )
        cin >> s[i];
    cin >> t;
    x --;
    y --;
    for (int i = 0; i < t.length(); i ++ )
    {
        if (t[i] == 'U' && s[x - 1][y] != '#' && x - 1 >= 0)
            x --;
        else if (t[i] == 'D' && s[x + 1][y] != '#' && x + 1 < h)
            x ++;
        else if (t[i] == 'L' && s[x][y - 1] != '#' && y - 1 >= 0)
            y --;
        else if (t[i] == 'R' && s[x][y + 1] != '#' && y + 1 < w)
            y ++;
        if (s[x][y] == '@')
            f[x][y] = 1;
    }
    for (int i = 0; i < h; i ++ )
    {
        for (int j = 0; j < w; j ++ )
        {
            if (f[i][j])
                c ++;
        }
    }
    cout << x + 1 << ' ' << y + 1 << ' ' << c << '\n';
    return 0;
}

C - Illuminate Buildings

洛谷链接

AtCoder链接

题目

有 N 幢楼房等间距排成一行。第 i 幢楼房从正面看的高度是 H_i。

你想给其中一些建筑物装上灯饰，要同时满足以下两个条件：

• 所选建筑物的高度相同。
• 所选建筑物的排列间隔相等。

您最多可以选择多少座建筑物？如果您选择的建筑物只有一幢，则认为它满足条件。

思路

我们设 dp[i][j] 表示到第 i 个数字时，数列间隔为 j 的最长子序列个数。

设计完状态，我们来推方程：

我们分两类讨论：

• 若 h[i]=h[i−j] 则易得有 dp[i][j]=dp[i−j][j]+1。
• 若 h[i]=h[i−j] 则因为 dp[i][j] 不能从 dp[i−j][j] 转移而来，所以 dp[i][j]=1。

答案即为 dp 数组中的最大值。

代码

// LUOGU_RID: 207347596
#include <bits/stdc++.h>

using namespace std;

int n, ans, h[3010], dp[3010][3010];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &h[i]);
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++ )
            dp[i][j] = 1;
        for (int j = 1; j <= i; j ++ )
        {
            dp[i][j] = 1;
            if (h[i] == h[i - j])
                dp[i][j] = dp[i - j][j] + 1;
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << '\n';
    return 0;
}

D - Santa Claus 2

洛谷链接

AtCoder链接

题目

在二维平面上的点 (X_1,Y_1), \ldots ,(X_N,Y_N) 上有 N 座房子。

最初，圣诞老人位于点 (S_x,S_y)。他将按照 (D_1,C_1), \ldots ,(D_M,C_M) 序列进行如下操作：

• 对于 i=1,2, \ldots ,M 的顺序，他的移动如下：
  • 假设 (x,y) 是他目前所在的点。
  • 如果 D_i 是 U，则从 (x,y) 直线移动到 (x,y+C_i)。
  • 如果 D_i 是 D，则从 (x,y) 直线移动到 (x,y-C_i)。
  • 如果 D_i 是 L，则从 (x,y) 直线移动到 (x-C_i,y)。
  • 如果 D_i 为 R，则从 (x,y) 沿直线移动到 (x+C_i,y)。

找出他完成所有行动后所在的点，以及他在行动过程中经过或到达的不同房子的数量。如果多次经过同一房屋，则只计算一次。

思路

我们分析一下算法的大致流程。我们考虑第一种行走方式，即 (x,y) \to (x,y+C_i) 这种。你会发现 x 不变，那么此时你固定 x，找出所有满足 X_i=x 的 Y_i，并找出那些满足 y \le Y_i \le y+C_i 的 Y_i，并把这些 (X_i,Y_i) 都删掉。其他情况同理。

这很好写，只需要开一个 map<int, set<int> >，同时完成了坐标的离散化和统计，删除的时候就在 set 上二分找出左边界和右边界直接暴力删就可以了，因为你会发现最多只有 M 个点会被删掉。

时间复杂度 O((m+n) \log n)。

十年 OI 一场空，不开 long long 见祖宗。

代码

#include <bits/stdc++.h>

using namespace std;

long long n, m, x, y, c, ans;
char op;
vector <long long> temp;
map<long long, set<long long> > mpx, mpy;

void work (long long x, long long y, long long u, long long v, map<long long, set<long long> > &i, map<long long, set<long long> > &j)
{
    if (i[x].empty() || abs(x) > 1e9 || abs(y) > 1e9)
        return;
    temp.clear();
    auto bg = i[x].lower_bound(y + u), ed = i[x].upper_bound(y + v);
    for (auto it = bg; it != ed; it ++ )
    {
        ans ++;
        temp.push_back((*it));
    }
    for (auto p : temp)
    {
        j[p].erase(x);
        i[x].erase(p);
    }
}

int main()
{
    scanf("%lld %lld %lld %lld", &n, &m, &x, &y);
    for (long long i = 1, u, v; i <= n; i ++ )
    {
        scanf("%lld %lld", &u, &v);
        mpx[u].insert(v);
        mpy[v].insert(u);
    }
    for (long long i = 1; i <= m; i ++ )
    {
        cin >> op >> c;
        if (op == 'U')
        {
            work(x, y, 0, c, mpx, mpy);
            y = y + c;
        }
        if (op == 'D')
        {
            work(x, y, -c, 0, mpx, mpy);
            y = y - c;
        }
        if (op == 'L')
        {
            work(y, x, -c, 0, mpy, mpx);
            x = x - c;
        }
        if (op == 'R')
        {
            work(y, x, 0, c, mpy, mpx);
            x = x + c;
        }
    }
    cout << x << ' ' << y << ' ' << ans << '\n';
    return 0;
}