首页 > 其他分享 >AtCoder Beginner Contest 379

AtCoder Beginner Contest 379

时间：2024-11-15 17:31:06浏览次数：1  
标签：AtCoder cur Beginner int auto cin 379 格子 ans

省流版
  • A. 模拟即可
  • B. 贪心，有\(k\)个就吃，模拟即可
  • C. 维护已经有棋子的格子，有多个棋子往右推，代价等差数列求和，模拟即可
  • D. 注意到植物高度=当前天-种植天，维护植物的种植天然后二分找对应高度的植物即可
  • E. 考虑最终答案每一个数位的值，然后处理进位即可
  • F. 单调栈处理建筑\(r\)能看的建筑数量，然后求 \([l+1,r]\)最大高度，二分找到屏蔽单调栈的楼数量即可
  • G. 维护轮廓线状态\(dp\)，仅从有效状态往后\(dp\)即可

A - Cyclic (abc379 A)

题目大意

给定三个数字，将其进行两次循环移位并输出。

解题思路

可以用rotate函数，将首字母移动到末尾。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string a;
    cin >> a;
    rotate(a.begin(), a.begin() + 1, a.end());
    cout << a << ' ';
    rotate(a.begin(), a.begin() + 1, a.end());
    cout << a << '\n';

    return 0;
}

B - Strawberries (abc379 B)

题目大意

\(n\)个牙齿，如果有连续 \(k\)个牙齿是健康的，则可以吃一个草莓，然后这 \(k\)个牙齿变坏了。

问最多能吃多少个草莓。

解题思路

从左往右依次考虑每个牙齿，很显然，一旦有连续\(k\)个健康的就吃一个草莓，该决策一定不劣。

模拟该策略即可。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    string s;
    cin >> n >> k >> s;
    int ans = 0;
    string good = string(k, 'O');
    for (int i = 0; i < n; i++) {
        if (s.substr(i, k) == good) {
            ++ans;
            fill(s.begin() + i, s.begin() + i + k, 'X');
        }
    }
    cout << ans << '\n';

    return 0;
}

C - Sowing Stones (abc379 C)

题目大意

\(n\)个格子，初始有 \(m\)个格子有棋子数 \(a_i\)。

现可进行操作，如果第 \(i\)个格子有棋子，可以将其一个棋子移动到第 \(i+1\)个格子。

问最少进行的操作数，使得每个格子都恰好有一个棋子。

解题思路

首先看棋子总数是不是\(n\)，不是则做不到。

然后从左到右考虑每个格子，如果其棋子数 \(>1\)，则将多余的部分往右推。

记\(cur\)为从左数第一个还没棋子的格子（这个还没棋子的格子，不考虑该格子原先已有棋子的情况，仅考虑上述向右推的操作的棋子是否到达了该格子）。

对于该格子有 \(a_i\)个棋子，就可以把这些推到\([cur, cur + a_i - 1]\)这些格子，使得每个格子都恰好有一个棋子，其代价是一个等差数列的求和。然后 \(cur = cur + a_i\)，考虑下一个格子的棋子往右推即可。

注意 \(a_i \leq 2e9\)，等差数列时的 \(l+r\)可能会超 \(int\)范围。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> x(m), a(m);
    for (auto& i : x)
        cin >> i;
    for (auto& i : a)
        cin >> i;
    if (accumulate(a.begin(), a.end(), 0ll) != n) {
        cout << -1 << '\n';
    } else {
        vector<int> id(m);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j) { return x[i] < x[j]; });
        LL ans = 0;
        int cur = 1;
        auto calc = [&](int l, int r, int x) {
            int cnt = r - l + 1;
            return (0ll + l + r) * cnt / 2 - 1ll * x * cnt;
        };
        bool ok = true;
        for (auto& i : id) {
            if (cur < x[i]) {
                ok = false;
                break;
            }
            ans += calc(cur, cur + a[i] - 1, x[i]);
            cur += a[i];
        }
        if (!ok) {
            ans = -1;
        }
        cout << ans << '\n';
    }

    return 0;
}

D - Home Garden (abc379 D)

题目大意

问题陈述

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

依次处理 \(Q\) 个操作，分三种

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

解题思路

植物高度为当前天-种植天，因此我们只需维护每个植物的种植天，对于操作三，假设当天是第\(x\)天 ，那只需把所有种植天\(\leq x - H\)的植物全收割即可。

因为植物的 种植天是不断递增的，因此就用一个数组维护一个递增的种植天，然后再用一个变量\(la\)维护，已经被收割植物 的种植天的最大值，每次收割，二分找到\(x - H\)的位置，其与 \(la\)的差值就是本次收割的植株数量。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin >> q;
    vector<LL> pot;
    int l = 0;
    LL day = 0;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            pot.push_back(day);
        } else if (op == 2) {
            int t;
            cin >> t;
            day += t;
        } else if (op == 3) {
            int h;
            cin >> h;
            int nxt =
                upper_bound(pot.begin() + l, pot.end(), day - h) - pot.begin();
            cout << nxt - l << '\n';
            l = nxt;
        }
    }

    return 0;
}

E - Sum of All Substrings (abc379 E)

题目大意

给定一个长达\(1e5\)的数字字符串\(s\)。定义 \(f(i,j) = s[i..j]\) 。即子串的数字。

求\(\sum_{i=1}^{n}\sum_{j=1}^{n} f(i,j)\)。

解题思路

\(f(i,j) = s[i..j] = s[j] + s[j - 1] \times 10 + s[j - 2] + ...\)。

这样我们可以不考虑每个 \(f(i,j)\)，而是考虑每个 \(s[j]\)在答案的贡献，但是因为数很大，这样考虑得写高精度。

怎么办呢？我们还可以考虑最终答案的每一位的数字是多少，即因子\(10,10^2,10^3\)的系数分别是多少。

考虑个简单的例子，即

\[\begin{aligned} &f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3) \\ =& (S_1)+(10S_1+S_2)+(100S_1+10S_2+S_3)+(S_2)+(10S_2+S_3)+(S_3)\\ =& 10^2(S_1)+10^1(S_1+2S_2)+10^0(S_1+2S_2+3S_3) \end{aligned} \]

这样我们就知道个位的数是\(S_1+2S_2+3S_3\)，处理好进位后，再考虑十位的数是多少。

更一般的，即\(A_i=\sum_{j=1}^i j\times S_j\)，最终的答案就是\(\sum_{i=1}^N 10^{N-i}A_i\)。再从低位依次考虑进位的情况即可。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    LL sum = 0;
    for (int i = 0; i < n; ++i)
        sum += (i + 1) * (s[i] - '0');
    vector<LL> ans;
    ans.push_back(0);
    for (int i = n - 1; i >= 0; --i) {
        ans.back() += sum % 10;
        int jin = ans.back() / 10;
        ans.back() %= 10;
        ans.push_back(sum / 10 + jin);
        sum -= (i + 1) * (s[i] - '0');
    }
    while (ans.back() >= 10) {
        int jin = ans.back() / 10;
        ans.back() %= 10;
        ans.push_back(jin);
    }
    while (ans.back() == 0)
        ans.pop_back();
    reverse(ans.begin(), ans.end());
    for (auto& i : ans)
        cout << i;
    cout << '\n';

    return 0;
}

F - Buildings 2 (abc379 F)

题目大意

给定\(n\)个建筑的高度\(h_i\)，回答 \(q\)个询问。

每个询问给定 \(l,r\)，问从 \(l,l+1,...,r-1,r\)建筑往右看，都能看到的建筑的数量。

如果建筑\(i\)能看到建筑 \(j\)，则不存在 \(i < k < j\)，满足 \(h_k > h_j\)。

解题思路

如果单问某个建筑往右看，能看到的建筑物数量，其实就是一个从右往左的单调栈——高的建筑会屏蔽矮的建筑，从而矮的建筑会出栈，使得栈是一个从栈顶到栈低是一个递增的情况。

询问可以离线，因此我们按照\(r\)从大到小的顺序考虑每个询问，当前单调栈的结果是从\(r\)往右看能看到的建筑物高度，然后考虑\([l,..r-1]\)它们的有哪些看不到。

注意到其建筑看到的条件：

  • 如果建筑\(i\)能看到建筑 \(j\)，则不存在 \(i < k < j\)，满足 \(h_k > h_j\)。

\(j\)不变， 序号\(i\)越小，其看到的条件就越苛刻，即 \(i\)能看到的建筑， \([i+1,j-1]\)一定能看到。反之不能看到的话，却不一定。

但我们要找 \([l,r]\)都能看到的建筑，其实就是 \(l\)能能看到的建筑数量，按照单调栈的做法，我们即找到[l+1,r]中最高的建筑\(H\)，它会屏蔽单调栈里高度小于 \(H\)的建筑。

无修改的区间找最大值可以用 \(ST\)表，然后找出屏蔽建筑物的数量，因为单调栈是单调的，因此可以二分找到屏蔽建筑的分界线，进而得出可以看到的建筑物的数量。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
  public:
    int n;
    vector<vector<T>> mat;
    F func;

    SparseTable(const vector<T>& a, const F& f) : func(f) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        mat.resize(max_log);
        mat[0] = a;
        for (int j = 1; j < max_log; j++) {
            mat[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); i++) {
                mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T get(int from, int to) const { // [from, to]
        assert(0 <= from && from <= to && to <= n - 1);
        int lg = 32 - __builtin_clz(to - from + 1) - 1;
        return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> h(n);
    for (auto& i : h)
        cin >> i;
    SparseTable<int> st(h, [&](int i, int j) { return max(i, j); });
    vector<array<int, 2>> query(q);
    for (auto& i : query)
        cin >> i[0] >> i[1];
    vector<int> id(q);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(),
         [&](int a, int b) { return query[a][1] > query[b][1]; });
    vector<int> ans(q);
    vector<int> stack;
    int cur = n - 1;
    for (auto i : id) {
        auto [l, r] = query[i];
        --l, --r;
        while (cur > r) {
            int hei = h[cur];
            while (!stack.empty() && hei >= stack.back()) {
                stack.pop_back();
            }
            stack.push_back(hei);
            --cur;
        }
        int hei = st.get(l + 1, r);
        auto pos =
            upper_bound(stack.begin(), stack.end(), hei, greater<int>()) -
            stack.begin();
        ans[i] = pos;
    }
    for (auto i : ans)
        cout << i << '\n';

    return 0;
}

G - Count Grid 3-coloring (abc379 G)

题目大意

给定\(h \times w\)的格子，每个格子写着 ?123中的一种。

现将所有的?替换成123中的一个。

问有多少替换方法，使得相邻格子的数字不相同。

解题思路

从上到下，从左到右依次考虑每行每列的格子\((x,y)\)，看其?能否替换成123，取决于上一行\((x-1,y)\)的数字和上一列\((x,y-1)\)的数字是否与该格子相同。

因此我们的状态得保留这两处格子的信息，但是仅仅保留这两处的话，当前状态变成下一列时，无法继承之前的状态。

怎样才能继承之前的状态呢？那就需要保留一个轮廓的状态（即已考虑的格子的边界）。如下图蓝色格子所示。此即为轮廓线\(dp\)。

example

即 \(dp[i][j][s]\)表示从上到下，从左到右考虑到格子 \((i,j)\)，外围一圈的数字状态为 \(s\)（这里是一个 \(3^w\)的压缩状态）。

转移即考虑当前格子的数字是什么，是否合法即可。由于 \(hw \leq 200\)，因此 \(\min(h,w) \leq 14\)，保持 \(h \leq w\)，则时间复杂度为 \(O(hw3^w)\)，有 \(1e9\)。

但考虑到\(s\)的有效 状态数没有\(3^w\)（相邻相同的数字是非法状态），而是 \(O(2^w)\)（因为不能和前一列相同，因此该列的数字只有两种，然后还有一些组合数的系数），因此仅从有效状态转移，时间复杂度为 \(O(hw2^w)\)。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (auto& i : s)
        cin >> i;
    if (h < w) {
        vector<string> t(w, string(h, ' '));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                t[j][i] = s[i][j];
            }
        }
        swap(h, w);
        swap(s, t);
    }

    vector<int> base(w, 1);
    for (int i = 1; i < w; ++i) {
        base[i] = base[i - 1] * 3;
    }
    auto get_bit = [&](int x, int y) { return x / base[y] % 3; };
    auto tr = [&](int cur, int pos, int v) {
        int ret = cur;
        ret -= get_bit(cur, pos) * base[pos];
        ret += v * base[pos];
        return ret;
    };
    auto ok = [&](int x, int y, int cur, int v) {
        if (y != 0 && get_bit(cur, y - 1) == v)
            return false;
        if (x != 0 && get_bit(cur, y) == v)
            return false;
        return true;
    };

    int up = 1;
    for (int i = 0; i < w; i++) {
        up *= 3;
    }
    map<int, int> dp;
    dp[0] = 1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            map<int, int> ndp;
            for (auto& [k, v] : dp) {
                if (s[i][j] != '?') {
                    if (ok(i, j, k, s[i][j] - '1')) {
                        auto nxt = tr(k, j, s[i][j] - '1');
                        ndp[nxt] += v;
                        if (ndp[nxt] >= mo)
                            ndp[nxt] -= mo;
                    }
                } else {
                    for (int l = 0; l <= 2; ++l) {
                        if (ok(i, j, k, l)) {
                            auto nxt = tr(k, j, l);
                            ndp[nxt] += v;
                            if (ndp[nxt] >= mo)
                                ndp[nxt] -= mo;
                        }
                    }
                }
            }
            dp.swap(ndp);
        }
    }
    int ans = 0;
    for (auto& [k, v] : dp) {
        ans += v;
        if (ans >= mo)
            ans -= mo;
    }
    cout << ans << '\n';

    return 0;
}

标签：AtCoder,cur,Beginner,int,auto,cin,379,格子,ans
From： https://www.cnblogs.com/Lanly/p/18548361

相关文章

  • Atcoder ABC 216 G 01Sequence 题解 [ 蓝 ] [ 差分约束 ]
    01Sequence：比较板的差分约束，但有一个很妙的转化。朴素差分约束设\(x_i\)表示第\(i\)位的前缀和。我们要最小化\(1\)的个数，就要求最小解，就要求最长路。因为约束条件都是大于等于号，所以求最长路才能满足所有条件。求最大解也是同理。我们可以对于每一个条件，列出如下不等式......
  • Atcoder Beginner Contest 379 (A-F)
    AtcoderBeginnerContest379(A-F)题目链接A-Cyclic#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidShowball(){chara,b,c;cin>>a>>b>>c;cout<<b<<c<<a<<""<......
  • AtCoder Beginner Contest 353 - VP 记录
    Preface这次比赛蛮简单的，就是黄题有点多，少了区分度。而且SigmaProblemAnotherSigmaProblemYetAnotherSigmaProblem是什么奇妙的题目名称？SigmaProblemAnotherSigmaProblemYetAnotherSigmaProblem\(\texttt{\scriptsizeYet\footnotesizeA......
  • AtCoder 板刷记录
    话说为啥这些场都没有G题的说[ABC200F]MinflipSummation显然的策略是把全部都是一个数的段变成全不都是另一个数，然后考虑进行dp设一个dp[i][0/1][0/1]表示一下前i个字符中奇偶性为j填的数是k时j的总和然后直接做就行了，需要矩阵快速幂加速一下[ABC201F]Insert......
  • AtCoder Beginner Contest 378 题解
    AtCoderBeginnerContest378题解比赛链接A-Pairing贪心#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidShowball(){vector<int>a(5);for(inti=0;i<4;i++){intx;cin>>x;a[x]++;......
  • ABC379
    Clink点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m;structnd{ intx,a;}y[200005];intqzh;intans;boolcmp(ndl,ndr){ returnl.x<r.x;}signedmain(){ cin>>n>>m; for(inti......
  • AtCoder Beginner Contest 356 - VP记录
    A-SubsegmentReverse点击查看代码#include<cstdio>#include<numeric>#include<algorithm>usingnamespacestd;constintN=105;intn,a[N],l,r;intmain(){ scanf("%d%d%d",&n,&l,&r); iota(a+1,a+n+1,1); reverse(a+l,......
  • AtCoder Beginner Contest 379
    这次又是倒在了t5，没救了。ABC379A-Cyclic难度：红#include<bits/stdc++.h>usingnamespacestd;intmain(){chara,b,c;cin>>a>>b>>c;cout<<b<<c<<a<<''<<c<<a<<b;return0;}B-......
  • ABC372D ABC379F 题解 单调栈二分
    ABC372DABC379F题解单调栈二分一直觉得AT上面学到的东西比CF要多一些，无意捧一踩一，但可能是我太菜的原因，毕竟ABC的题目普遍要比Div.2简单一些。好多次碰到这个单调栈里面二分的trick了，所以写一篇来总结一下。ABC372D形象地给定一系列Buildings的高度\(h\)，保证每个......
  • ABC 379(E-F)
    ABC379E伪装高精的找规律题#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineintlonglong#definepiipair<int,int>#definemkpmake_pairusingnamespacestd;constintN=3e5+5;intpre[N],ans[N];signedmain(){io......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99