AtCoder Beginner Contest 379 A~F

IronMen · 2024-12-06 22:49:50 · 题解

A - Cyclic

洛谷链接

AtCoder链接

题目

给你一个三位整数 N。

设 a、b、c 分别是 N 的百位、十位和个位数。依次列印由 b,c,a 组成的整数，以及由 c,a,b 组成的整数。

代码

#include <bits/stdc++.h>

using namespace std;

string s;

int main()
{
    cin >> s;
    cout << s[1] << s[2] << s[0] << ' ' << s[2] << s[0] << s[1] << '\n';
    return 0;
}

B - Strawberries

洛谷链接

AtCoder链接

题目

高桥有 N 颗牙齿，从左到右排列成一排。他牙齿目前的状况用字符串 S 表示。

如果 S_i 是 O，表示左边第 i 颗牙齿是健康的。如果是 X，则表示第 i 个牙齿有蛀牙。

当他有 K 颗连续健康的牙齿时，他可以用这些 K 颗牙齿吃一颗草莓。吃完一颗草莓后，这 K 颗牙齿就会出现龋齿，变得不健康。

求他最多可以吃多少颗草莓。

思路

统计连续 K 个 O 出现了多少次，就是答案。

代码

#include <bits/stdc++.h>

using namespace std;

int n, k, cnt, ans;
char c;

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i ++ )
    {
        cin >> c;
        if (c == 'O')
            cnt ++;
        else
            cnt = 0;
        if (cnt == k)
        {
            ans ++;
            cnt = 0;
        }
    }
    cout << ans << '\n';
    return 0;
}

C - Sowing Stones

洛谷链接

AtCoder链接

题目

在一行中有 N 个单元格，编号从 1 到 N。起初，M 个单元格中含有棋子，X_i 个单元格中含有 A_i 个棋子，(1 \le i \le M) 个棋子。

您可以执行以下任意次数（可能为零）的操作：

• 如果单元格 i(1 \le i \le N-1) 包含一个棋子，则将一个棋子从 i 格移动到 i+1 格。

求达到每个 N 单元格中正好有一块棋子的状态所需的最少操作次数。如果不可能，请打印 -1。

思路

由于只能往后放，显而易见，如果可以达到要求，那么一定只有一种方式。所以重心就在判断是否可行上了。

首先，如果总数量不等于 n 肯定不行。

其次，如果第一堆不在 1 肯定不行。

最后，如果到了某个点的时候石头总和不够 1 到这个点的数量一定是不行的。

那么在统计答案的时候，我们要把从这一个“石头根据地”到下一个“石头根据地”中间的都用当前这个上的石头填满，剩下的移动到下一个“石头根据地”上，因为是正好的，所以如果用不完肯定是后面缺，留以后用，再者如果不移动到后面放着也没用。

小 tips：简化一下第三个判断，我们就直接照着统计答案时候的走，如果移动到下一个“石头根据地”的是负数，那么一定是累加到这一个就不够了，就是不行。（正数为有剩余，0 为刚好，负数为不够了）

一定要排序。

代码

#include <bits/stdc++.h>

using namespace std;

long long n, m, qzh, ans, gs;

struct nd
{
    long long x, a;
} y[200010];

bool cmp(nd l, nd r)
{
    return l.x < r.x;
}

int main()
{
    scanf("%lld %lld", &n, &m);
    for (long long i = 1; i <= m; i ++ )
        scanf("%lld", &y[i].x);
    for (long long i = 1; i <= m; ++ i)
    {
        scanf("%lld", &y[i].a);
        qzh = qzh + y[i].a;
    }
    sort(y + 1, y + 1 + m, cmp);
    y[m + 1].x = n + 1;
    if (qzh != n || y[1].x != 1)
        goto it;
    for (long long i = 1; i <= m; i ++ )
    {
        gs = y[i + 1].x - 1 - y[i].x;
        ans += (1 + gs) * gs / 2;
        gs = y[i].a - gs - 1;
        if (gs < 0)
            goto it;
        ans += gs * (y[i + 1].x - y[i].x);
        y[i + 1].a += gs;
    }
    cout << ans << '\n';
    return 0;
it:
    puts("-1");
    return 0;
}

D - Home Garden

洛谷链接

AtCoder链接

题目

高桥有 10^{100} 个花盆。最初，他没有种植任何植物。

有 Q 个查询，请按顺序处理。

查询有以下三种类型。

• 1：准备一个空花盆，并在其中放入一株植物。这里，植物的高度是 0。
• 2 T：等待 T 天。在此期间，现有植物的高度会增加 T。
• 3 H：收获所有高度至少达到 H 的植株，并输出收获植株的数量。收获的植物会从花盆中移出。

假设执行第一类和第三类查询所需的时间为零。

思路

其实 10^{100} 个花瓶并没有用，只是告诉你花瓶够用。

对于每一个花瓶，我们记录是在哪一个时刻种上的并用小根堆维护种上的时刻并记录当前时间即可做这三种操作。

第一种操作：新增一个时刻。

第二种操作：时间戳增加。

第三种操作：因为是小根堆，所以可以取出时间最小的（但由于一定是按时间顺序加入的，所以其实数组也行），判断一下时间最小的是否够了高度，即和当前时间的差是否大于要求高度，如果符合，收获这个，弹出，再找最小的。

代码

#include <bits/stdc++.h>

using namespace std;

long long q, t, op, x, g, ans, w;
priority_queue<long long, vector<long long>, greater<long long> > h;

int main()
{
    scanf("%lld", &q);
    while (q -- )
    {
        scanf("%lld", &op);
        if (op == 1)
            h.push(t);
        else if (op == 2)
        {
            scanf("%lld", &x);
            t += x;
        }
        else if (op == 3)
        {
            scanf("%lld", &x);
            g = t - x;
            ans = 0;
            while (!h.empty())
            {
                w = h.top();
                if (w <= g)
                {
                    h.pop();
                    ans ++;
                }
                else
                    break;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

E - Sum of All Substrings

洛谷链接

AtCoder链接

题目

给你一个长度为 N 的字符串 S，由从 1 到 9 的数字组成。

对于每一对整数 (i,j)(1 \le i \le j \le N)，将 f(i,j) 定义为将 S 中从第 i 个到第 j 个字符的子串解释为十进制整数后得到的值。求 \displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i,j)。

思路

首先自己列一个样例看一下。

25374
2
25
253
2537
25374
5
53
537
5374
3
37
374
7
74
4

自己手动对齐一下 \ldots

那我们发现：s_1 做为个十百千万位各出现一次，s_2 做为个十百千位各出现两次，\cdots，s_5 做为各位出现了五次。

规律就显而易见了，但不是很好描述，所以就不描述了。

那么结果就是 s_1*11111(n 个 1)+s_2*2222(n-1 个 2)+ \ldots +s_n*n(1 个 n)=s_1*1*10^{n-1}+s_1*1*10^{n-2}+s_1*1*10^{n-3}+ \ldots +s_1*10+s_1*1 + \ldots +s_{n-1}*(n-1)*10+s_{n-1}*n-1*1+s_n*n*1=s_1*1*10^{n-1}+(s_1*1+s_2*2)*10^{n-2}+(s_1*1+s_2*2+s_3*3)*10^{n-3}+ \ldots +(s_1*1+s_2*2+s_3*3+ \ldots +s_n*n)*1。

如果我们把每一项的系数（那个不是 10 的几次方的那个）看做个位数的话，感性理解一下，那么我们可以把这个式子近似的看成一个个位是 s_1*1+s_2*2+ \ldots +s_n*n，十位是 s_1*1+s_2*2+ \ldots +s_{n-1}*(n-1)，百位是 s1*1+s_2*2+ \ldots +s_{n-2}*(n-2)，\ldots 最高位是 s_1*1 的一个 n 位数。

看似不是很有用的样子，但是，这道题要用高精度，那么这个东西就很有用了，我们拿一个数组存一下“每一位”，在进位即可，存每一位的时候可以从高到低，这样每次加一个 s_i 即可。

代码

#include <bits/stdc++.h>

using namespace std;

int n;
char s[200010];
long long q, x[3000010], cn;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        cin >> s[i];
    for (int i = 1; i <= n; i ++ )
        q += (s[i] - '0') * i;
    for (int i = n; i >= 1; i -- )
    {
        x[++ cn] = q;
        x[cn] += x[cn - 1] / 10;
        x[cn - 1] %= 10;
        q -= (s[i] - '0') * i;
    }
    while (x[cn] >= 10)
    {
        cn ++;
        x[cn] += x[cn - 1] / 10;
        x[cn - 1] %= 10;
    }
    for (int i = cn; i >= 1; i -- )
        cout << x[i];
    return 0;
}

F - Buildings 2

洛谷链接

AtCoder链接

题目

有 N 幢楼房，1 号楼，2 号楼，\ldots N 号楼，自西向东依次排列在一条直线上。最西边的是 1 号楼，最东边的是 N 号楼。第 i\ (1 \le i \le N) 的高度为 H_i。

对于一对整数 (i,j)\ (1 \le i < j \le N)，如果满足以下条件，则可以从建筑物 i 看到建筑物 j。

• 在建筑物 i 和 j 之间，没有比建筑物 j 更高的建筑物。换句话说，不存在整数 k\ (i < k < j)，即 H_k>H_j。

给你提供了 Q 个查询。在第 i 次查询中，给定一对整数 (l_i,r_i)\ (l_i<r_i)，求从 l_i 和 r_i 两座建筑物可以看到的 r_i 东侧建筑物（即 r_i+1,r_i+2, \ldots ,N）的数量。

思路

首先我们观察一下，如果一个在 r 右边的 i 可以被 l 和 r 同时看到，那么一定有 \max h_{r+1},h_{i+2}, \ldots ,h_{i-1} \le h_i 和 \max h_{l+1}, h_{l+2}, \ldots, h_{i-1} \le h_i，可以发现，后一个条件严格包含前一个条件，所以不管后一个条件即可。这时，一个任意的 i 被 l 和 r 同时看到的条件就是 \max h_{l+1}, h_{l+2}, \ldots, h_{i-1} \le h_i 且 i>r。

先不看后一个条件怎么做？离线，把每一个 i 挂在 l 上，从后往前扫一个单调栈，存的是从前面能看到的，也就是说，如果来了一个比栈顶大的，栈顶又一定在当前数的后面，被当前数一挡，就看不见了，那么就可以把栈顶弹出了，因为前面的看不到它了，然后在每一个 l 的时候当前在栈里的所有的就都是满足第一个条件的了（能被 l 看到，没有被挡，因为如果挡了就弹出了）。

首先明确一个事，在栈里的一定是单调的，因为从后往前有顺序的加（栈里存的是下标）。

再考虑第二个条件，我们说了，栈是单调的，所以我们可以二分一下下标大于 r 的第一个数，那么这个数到栈底就都符合第二个条件，加上栈里的都符合第一个条件，这些数就是所有符合条件的了。

在每一个 l 上二分每一个 r 即可。

代码

#include <bits/stdc++.h>

using namespace std;

int n, q, l, r, h[200010], st[200010], tp, ans[200010];
vector<pair<int, int> > ques[200010];

int ef(int x)
{
    int l = 0, r = tp;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (st[mid] > x)
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int main()
{
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &h[i]);
    for (int i = 1; i <= q; i ++ )
    {
        scanf("%d %d", &l, &r);
        ques[l].push_back({r, i});
    }
    for (int i = n; i >= 1; i -- )
    {
        if (ques[i].size())
        {
            for(int j = 0; j < ques[i].size(); ++ j)
                ans[ques[i][j].second] = ef(ques[i][j].first);
        }
        while (tp && h[st[tp]] <= h[i])
            tp --;
        st[++ tp] = i;
    }
    for (int i = 1; i <= q; i ++ )
        cout << ans[i] << '\n';
    return 0;
}