AtCoder Beginner Contest 383 A~D

IronMen · 2025-02-10 00:16:34 · 题解

A - Humidifier 1

洛谷链接

AtCoder链接

题目

AtCoder 公司办公室有一个加湿器。当前时间是 0，加湿器内没有水。

你要给这个加湿器加水 N 次。第 i 次加水（1 \le i \le N）发生在时间 T_i，您加了 V_i 升水。保证所有 1 \le i \le N-1 的 T_i<T_{i+1}。

但是，加湿器漏水了，只要里面有水，单位时间内水量就会减少 1 升。

求在 T_N 时加完水后加湿器中剩余的水量。

代码

#include <bits/stdc++.h>

using namespace std;

int n, t[110], v[110], s;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d %d", &t[i], &v[i]);
    s = v[0];
    for (int i = 1; i < n; i ++ )
    {
        s -= t[i] - t[i - 1];
        if (s < 0)
            s = 0;
        s += v[i];
    }
    cout << s << '\n';
    return 0;
}

B - Humidifier 2

洛谷链接

AtCoder链接

题目

AtCoder 公司办公室可以表示为由 H 行和 W 列组成的网格。(i,j) 表示从上往下第 i 行和从左往上第 j 列的单元格。

每个单元格的状态由一个字符 S_{i,j} 表示。如果 S_{i,j} 是 #，则该单元格包含一张桌子；如果 S_{i,j} 是 .，则该单元格是一层楼。可以保证至少有两个楼层单元格。

您将选择两个不同的楼层单元格，并在每个单元格中放置一个加湿器。

放置加湿器后，当且仅当一个单元格 (i,j) 与至少一个加湿器单元格 (i',j') 的曼哈顿距离 D 在内时，该单元格 (i,j) 才被加湿。(i,j) 和 (i',j') 之间的曼哈顿距离定义为 |i-i'|+|j-j'|。请注意，任何放置了加湿器的楼层单元总是加湿的。

求加湿楼层单元的最大可能数目。

代码

#include <bits/stdc++.h>

using namespace std;

int H, W, D, maxCount, n, humidifiedCount, dist, distB;
vector<pair<int, int> > floorCells;

int main()
{
    scanf("%d %d %d", &H, &W, &D);
    vector<string> S(H);
    for (int i = 0; i < H; i ++ )
        cin >> S[i];
    for (int i = 0; i < H; i ++ )
    {
        for (int j = 0; j < W; j ++ )
        {
            if (S[i][j] == '.')
                floorCells.push_back(make_pair(i, j));
        }
    }
    n = floorCells.size();
    for (int a = 0; a < n; a ++ )
    {
        for (int b = 0; b < n; b ++ )
        {
            if (a!= b)
            {
                humidifiedCount = 0;
                pair<int, int> cellA = floorCells[a];
                pair<int, int> cellB = floorCells[b];
                for (auto cell : floorCells)
                {
                    dist = abs(cell.first - cellA.first) + abs(cell.second - cellA.second);
                    distB = abs(cell.first - cellB.first) + abs(cell.second - cellB.second);
                    if (dist <= D || distB <= D)
                        humidifiedCount ++;
                }
                maxCount = max(maxCount, humidifiedCount);
            }
        }
    }
    cout << maxCount << '\n';
    return 0;
}

C - Humidifier 3

洛谷链接

AtCoder链接

题目

AtCoder 公司办公室是一个由 H 行和 W 列组成的网格。让 (i,j) 表示从顶部起第 i 行和从左侧起第 j 列的单元格。

每个单元格的状态由一个字符 S_{i,j} 表示。如果 S_{i,j} 为 #，则表示该单元格有一堵墙；如果 S_{i,j} 为 .，则表示该单元格是一个地板；如果 S_{i,j} 为 H，则表示该单元格在地板上放置了一个加湿器。

如果从至少一个加湿器单元格向上、向下、向左或向右移动最多 D 次且不经过墙壁，则该单元格被视为加湿单元格。需要注意的是，任何带有加湿器的单元格总是加湿的。

求加湿地板单元格的数量。

思路

这道题是经典的 BFS。

BFS 即广度优先搜索，对于每一个符合条件的点，我们都寻找他的上下左右四个点，去寻找下一个满足条件的点，并把他加入到一个容器里面方便下一次求解。那么什么容器可以先进先出呢，没错就是队列，于是我们就可以用队列来解决广度优先搜索的题目。

关于这一道 BFS 题，我们可以发现在题目中提到我们在地板上放置若干个加湿器，每个加湿器可以触及到的范围，我们可以设每一个加湿器是一个起点，搜索可以触及到的点，这道题就迎刃而解了。

代码

#include <bits/stdc++.h>

using namespace std;

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; // 右、左、下、上
char grid[1010][1010];
bool vis[1010][1010];
int h, w, d, steps, si, nx, ny, cnt;
queue<pair<int, int> > q;

int main()
{
    scanf("%d %d %d", &h, &w, &d);
    for (int i = 0; i < h; i ++ )
        cin >> grid[i];
    for (int i = 0; i < h; i ++ )
    {
        for (int j = 0; j < w; j ++ )
        {
            if (grid[i][j] == 'H')
            {
                q.push({i, j}); // 每一个加湿器入队
                vis[i][j] = 1; // 加湿器位置标记为加湿
            }
        }
    }
    // BFS可以算作模板了
    while (!q.empty() && steps < d) // 队列不为空且范围不到 d
    {
        si = q.size();
        for (int i = 0; i < si; i ++ )
        {
            auto x = q.front().first, y = q.front().second;
            q.pop();
            for (int d = 0; d < 4; d ++ )
            {
                nx = x + dx[d];
                ny = y + dy[d];
                if (nx >= 0 && nx < h && ny >= 0 && ny < w && !vis[nx][ny] && grid[nx][ny] == '.') // 边界条件、是否访问过、是否为地板不是墙
                {
                    vis[nx][ny] = 1; // 标记走过了
                    q.push({nx, ny}); // 入队
                }
            }
        }
        steps ++;
    }
    // 统计加湿的地板单元格数量
    for (int i = 0; i < h; i ++ )
    {
        for (int j = 0; j < w; j ++ )
        {
            if (vis[i][j])
                cnt ++;
        }
    }
    cout << cnt << '\n';
    return 0;
}

D - 9 Divisors

洛谷链接

AtCoder链接

题目

找出不大于 N 且恰好有 9 个因数的正整数的个数。

思路

突破点在于 9 个因子这一部分。显然我们可以发现结果必然是一个完全平方数。在经过思考，我们可以发现这个完全平方数还是由两个质数相乘得到的。

思考路程如下：设两个质数 a,b 且 a \ne b，它们乘积的平方为所得完全平方数，即 a^2b^2。此时有因子 1,a,b,a^2,ab,b^2,a^2b,ab^2,a^2b^2，恰好为 9。

可以证明惟有 a,b 是不相等质数时有如上结论。

此外我们还需考虑八次方数，易证。

先用线性筛筛出所有质数，然后枚举即可。

由于极限情况下可以发现答案并不大，所以暴力即可。

代码

#include <bits/stdc++.h>

using namespace std;

const long long maxn = 1000000;
long long n, ans, w, w2;
vector<long long> p;
bool vs[1000010];

int main()
{
    scanf("%lld", &n);
    for (long long i = 2; i <= maxn; i ++ )
    {
        if (!vs[i])
            p.push_back(i);
        for (long long j = 0; j < p.size() && i * p[j] <= maxn; j ++ )
        {
            vs[i * p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
    for (long long i = 0; i < p.size(); i ++ )
    {
        w = pow(p[i], 8);
        if (w > n)
            break;
        ans ++;
    }
    for (long long i = 0; i < p.size(); i ++ )
    {
        w = pow(p[i], 2);
        if (w * w > n)
            break;
        for (long long j = i + 1; j < p.size(); j ++ )
        {
            w2 = w * pow(p[j], 2);
            if (w2 > n)
                break;
            ans ++;
        }
    }
    cout << ans << '\n';
    return 0;
}