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

AtCoder Beginner Contest 311

时间：2023-07-22 22:36:04浏览次数：40  
标签：AtCoder Beginner int 311 cin st ++ vector sum

A - First ABC (abc311 A)

题目大意

给定一个字符串，问最短的一个前缀，包含A B C这三个字符。

解题思路

注意到这个前缀的末尾字母一定是这三个字母中的一个，因此答案就是这三个字母出现位置最早的最大值。

神奇的代码 
#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;
    cout << max({s.find('A'), s.find('B'), s.find('C')}) + 1 << '\n';

    return 0;
}

B - Vacation Together (abc311 B)

题目大意

给定\(n\)个人的\(d\)天的空闲与否的情况，问最长的连续天，这\(n\)个人都空闲。

解题思路

我们找到第一个大家都空闲的，以此为左端点，找满足条件的最远的右端点，这作为一个候选答案。

接下来的左端点就不要\(+1\)，而是改成从右端点右边继续找，因为\(+1\)开始的情况不会比刚才最优。

最终答案就是这些候选答案的最大值，双指针法，复杂度是\(O(n^2)\)。

因为数据规模不大，判断某天是否所有人都空闲时，直接遍历即可。

神奇的代码 
#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, d;
    cin >> n >> d;
    vector<string> s(n);
    for (auto& i : s)
        cin >> i;
    int ans = 0;
    auto ok = [&](int day) {
        int free = true;
        for (auto& i : s)
            free &= (i[day] == 'o');
        return free;
    };
    for (int i = 0; i < d; ++i) {
        int j = i;
        while (j < d && ok(j))
            ++j;
        ans = max(ans, j - i);
        if (j != i)
            --j;
        i = j;
    }
    cout << ans << '\n';

    return 0;
}

C - Find it! (abc311 C)

题目大意

给定多个基环内向树，找一个环。

解题思路

题意的构图方式实际上是一棵或多棵基环内向树，其特点是从任意一个点出发，必定会跑到环内。

因此随便从一个点进行\(DFS\)，记录一下每个点是否被访问过，当一个点第二次访问时，它就是环上的点。

然后从它遍历一下得到环上的点即可。

神奇的代码 
#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;
    cin >> n;
    vector<int> to(n);
    for (int i = 0; i < n; ++i) {
        int v;
        cin >> v;
        --v;
        to[i] = v;
    }
    int u = 0;
    vector<int> visit(n);
    for (u = 0; !visit[u]; u = to[u]) {
        visit[u] = 1;
    }
    vector<int> ans{u};
    for (int i = to[u]; i != u; i = to[i]) {
        ans.push_back(i);
    }
    cout << ans.size() << '\n';
    for (auto& i : ans)
        cout << i + 1 << ' ';
    cout << '\n';

    return 0;
}

D - Grid Ice Floor (abc311 D)

题目大意

给定一张二维网格，外围是石头，里面有若干个石头，其余都是冰面，从左上出发，选一个方向前进，会一直前进直到碰到石头。停下来，然后可以继续选一个方向前进。

问能访问到的格子数。

解题思路

考虑能访问到的格子\((i,j)\)的状态，我们发现只有五种，即当我们在格子\((i, j)\)时，此时的运动状态为：

  • 方向往上
  • 方向往下
  • 方向往左
  • 方向往右
  • 停下来

因此我们就设\(dp[i][j][0/1/2/3/4/5]\)表示到达格子\((i,j)\)，此时状态是上述\(5\)种中的一个，这个情况是否发生（即bool型）

转移就根据当前状态，枚举后继状态转移即可。

因为这里的DP顺序不是常规的循环，而是依赖于当前的运动状态的，所以转移类似于\(BFS\)式的转移。

每个格子最终只会访问到\(5\)次，因此复杂度是\(O(n^2)\)。

对于格子\((i, j)\), \(dp[i][j]\)的\(5\)个状态中有任意一个状态访问过（为真），则这个格子就访问过了。

答案就是上述这些格子的总和。

神奇的代码 
#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<string> tu(n);
    for (auto& i : tu)
        cin >> i;
    vector<vector<array<int, 5>>> ok(n,
                                     vector<array<int, 5>>(m, array<int, 5>{}));
    queue<array<int, 3>> team;
    array<int, 4> dx{1, -1, 0, 0};
    array<int, 4> dy{0, 0, 1, -1};
    team.push({1, 1, 2});
    team.push({1, 1, 0});
    ok[1][1][0] = ok[1][1][2] = ok[1][1][4] = 1;
    auto stop = [&](int x, int y) { return tu[x][y] == '#'; };
    while (!team.empty()) {
        auto [x, y, d] = team.front();
        team.pop();
        if (d == 4) { // stop
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (!stop(nx, ny) && !ok[nx][ny][i]) {
                    team.push({nx, ny, i});
                    ok[nx][ny][i] = 1;
                }
            }
            continue;
        }
        int nx = x + dx[d], ny = y + dy[d];
        if (stop(nx, ny)) {
            if (!ok[x][y][4]) {
                team.push({x, y, 4});
                ok[x][y][4] = 1;
            }
        } else {
            team.push({nx, ny, d});
            ok[nx][ny][d] = 1;
        }
    };
    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            bool access = false;
            for (auto& k : ok[i][j])
                access |= k;
            ans += access;
        }
    cout << ans << '\n';

    return 0;
}

E - Defect-free Squares (abc311 E)

题目大意

给定一个二维网格，有一些格子上有洞。

问有多少个正方形大小的网格，其里面都没洞。

解题思路

考虑一维的情况，我们可以枚举右端点\(r\)，然后考虑有多少个左端点\(l\)，满足\([l,r]\)都没洞。

容易发现，如果位置\(i\)有洞，那么所有左端点\(l \leq i\)都不满足上述要求。

我们对洞的数量求一个前缀和\(sum\)，那么\([l,r]\)没洞等价于\(sum[r] - sum[l - 1] = 0\)。

注意到\(sum\)是个单调数组，那么右边的等价式其实是一个关于\(l\)的单调函数，我们可以二分枚举\(l\)，找到最小的满足\(sum[r] - sum[l - 1] = 0\)的位置，那么右端点为\(r\)，满足条件的左端点数量就是\(r - l + 1\)。枚举所有右端点累计求和即为答案。

回到这个二维，我们枚举这个网格的右下角，因为是正方形，我们只需枚举其边长，就能知道左上角的位置，然后题意的条件就相当于一个二维前缀和的相减，同样是一个单调函数，因此问题就解决了，只是一维变二维了。

神奇的代码 
#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 h, w, n;
    cin >> h >> w >> n;
    vector<vector<int>> presum(h + 1, vector<int>(w + 1, 0));
    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        presum[u][v]++;
    }
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j) {
            presum[i][j] +=
                presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1];
        }
    LL ans = 0;
    auto calc = [&](int x, int y) {
        int l = 0, r = min(x, y) + 1;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            int lx = x - mid + 1, ly = y - mid + 1;
            int hold = presum[x][y] - presum[lx - 1][y] - presum[x][ly - 1] +
                       presum[lx - 1][ly - 1];
            if (hold == 0) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    };
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j) {
            ans += calc(i, j);
        }
    cout << ans << '\n';

    return 0;
}

F - Yet Another Grid Task (abc311 F)

题目大意

给定一个初始二维网格，格子有黑有白。

如果一个格子\((i, j)\)是黑的，那么\((i+1, j),(i + 1, j + 1)\)也必须是黑的。

初始不一定满足上述条件，现在你可以对格子涂成黑色，问满足上述条件的局面数。

解题思路

涂一个点，等价于这个点往下的一个直角三角形都被涂，隐隐约约感觉状态就拆成了这个点涂和下面以及旁边的点要不要涂的状态，但总感觉还要一些额外的状态，比如旁边的点涂不涂貌似会影响到当前决策，但想不出来，寄

神奇的代码

G - One More Grid Task (abc311 G)

题目大意

给定一个二维网格，问一个价值最大的矩形区域。

一个矩形区域的价值为，该区域的数字和$\times $该区域的最小值。

解题思路

考虑一维怎么做。

价值有两项，一个是和一个是区域最小值，如果我们枚举左端点，那么右端点变动时，数字和与最小值都可能变化，最坏情况下每移动一个位置，最小值都变一次，感觉避免不了\(O(n^2)\)。

我们还可以枚举区域的最小值\(a_i\)，那么以该值为最小值的区域的左右端点\(l,r\)，可以假想是从\(i\)左右扩张，一直扩张到要小于\(a_i\)位置。这是以它为最小值的最大的区间，因为值都是正的，因此这是一个以该值作为最小值的价值最大的区间。

对每个\(a_i\)都求一遍这个价值取最大就是答案。

而对于一个\(a_i\)，如何找到\(l,r\)，其实这是一个经典问题，即找左边第一个比它小的数，右边第一个比它小的数，可以运用单调栈在\(O(n)\)内找出来。

于是我们事先预处理出每个数的左右边界\(l_i, r_i\)，我们枚举\(a_i\)作为最小值，其一个候选答案就是\(a_i \times (sum[r_i] - sum[l_i - 1])\)，其中\(sum\)数组也是需要预处理的前缀和数组，用于\(O(1)\)求区间和。答案就是所有候选答案的最大值。此时时间复杂度是\(O(n)\)。

回到这个二维，注意规模只有\(300\)，如果我们先花\(O(n^2)\)枚举一个上下边界，此时要考虑的就是左右边界了，问题其实就变成了上述的一维情况，一个位置的最小值就是这上下边界中这一列的最小值，而值（用于算前缀和的）就是这一列的数字之和。问题其实解决了。

考虑实现细节，当我们枚举上下边界后，需要求出变成一维情况的数组，其中算左右边界的最小值是该列的最小值，可以预先花\(O(n^2)\)预处理出每一列的两两行的最小值，也可以用ST表。然后算前缀和的是该列的数字之和，因此还得预处理出每一列的前缀和。

总的时间复杂度就是\(O(n^3)\)

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

// usage:
//   auto fun = [&](int i, int j) { return min(i, j); };
//   SparseTable<int, decltype(fun)> st(a, fun);
// or:
//   SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
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, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m, 0));
    vector<SparseTable<int>> st;
    vector<vector<int>> presum(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
        partial_sum(a[i].begin(), a[i].end(), presum[i].begin());
        st.push_back(
            SparseTable<int>(a[i], [](int x, int y) { return min(x, y); }));
    }
    LL ans = 0;
    auto solve = [&](int L, int R) {
        vector<int> num(n), sum(n);
        for (int i = 0; i < n; ++i) {
            num[i] = st[i].get(L, R);
            sum[i] = presum[i][R];
            if (L)
                sum[i] -= presum[i][L - 1];
        }
        partial_sum(sum.begin(), sum.end(), sum.begin());

        vector<int> l(n), r(n);
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && num[st.top()] >= num[i]) {
                r[st.top()] = i - 1;
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty()) {
            r[st.top()] = n - 1;
            st.pop();
        }
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && num[st.top()] > num[i]) {
                l[st.top()] = i + 1;
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty()) {
            l[st.top()] = 0;
            st.pop();
        }

        for (int i = 0; i < n; ++i) {
            int cur = sum[r[i]];
            if (l[i])
                cur -= sum[l[i] - 1];
            ans = max(ans, 1ll * cur * num[i]);
        }
    };
    for (int i = 0; i < m; ++i)
        for (int j = i; j < m; ++j) {
            solve(i, j);
        }
    cout << ans << '\n';

    return 0;
}

Ex - Many Illumination Plans (abc311 Ex)

题目大意

<++>

解题思路

<++>

神奇的代码

标签：AtCoder,Beginner,int,311,cin,st,++,vector,sum
From： https://www.cnblogs.com/Lanly/p/17574427.html

相关文章

  • Atcoder Regular Contest 154 E - Reverse and Inversion
    只要你发现是诈骗题就好办了。不要像我那样傻傻地瞪一个小时然后才发现那俩sigma里的东西相减是有性质的。先考虑计算单个\(f(p)\)，一眼的树状数组……吗？考虑最终答案式子里\(i\)的系数：\(\sum\limits_{j<i}[p_j>p_i]-\sum\limits_{j>i}[p_j<p_i]\)，因为\(\sum\limits_{j<i}[p......
  • Atcoder Regular Contest 124 E - Pass to Next
    首先第一步是一个浅显的观察：我们要求的是所有可能的最终序列的贡献之和，如果能改为计算所有操作序列的贡献之和那问题会简单很多，并且我们惊奇地发现，如果一组\(x_i\)全大于\(0\)，那么把它们全减去\(1\)以后得到的答案序列不会改变，而对于任意一种可能的最终序列，必然存在一组\(\m......
  • Atcoder Grand Contest 057 D - Sum Avoidance
    先来找些性质：\(A\)中最小的元素\(M\)肯定是最小的不是\(S\)的因子的数，由于\(\text{lcm}(1,2,3,\cdots,43)>10^{18}\)，所以\(M\le43\)。对于每个\(0\lei<M\)，\(\bmodM=i\)的数被选择的部分必然是一段后缀，因为如果你选择了\(M\)选择了某个\(\bmodM=i\)的数\(v\)，......
  • AtCoder Grand Contest 049 E Increment Decrement
    洛谷传送门AtCoder传送门好题。同时考查了slopetrick和选手的计数能力，不愧是AGCE。先考虑问题的第一部分。你现在有一个初始全为\(0\)的序列\(b\)。你每次可以给\(b\)单点\(\pm1\)，代价为\(1\)，或区间\(\pm1\)，代价为\(m\)。求把\(b\)变成给定序列\(a\)的......
  • AtCoder Beginner Contest 310
    A-OrderSomethingElse#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongint32_tmain(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);intn,p,q;cin>>n>>p>>q;......
  • poj 2311 Cutting Game (sg函数)
    小记：这题是对sg函数的初步理解。对于sg函数只要g[x]==0，则此时为必败态。x作为后继，我们就要对所有的后继进行标记，然后mex之。因为每次只能切一刀，所以切完之后，会有两块方格，而对每一块方格进行游戏又会有一个sg函数值，所以根据sg函数的性质，它这一刀所代表的后继，即为这两块方格的sg函......
  • 【2023.07.14】Atcoder：past201912 - 第一回 アルゴリズム実技検定（div4+区域赛难度）过题
    G-Division解法一：位运算+状压枚举（赛时思路）范围显然，可以跑\(2^n\)的算法，考虑位运算状态压缩。以\(\mathcalO(2^n\cdot2^n)\)的复杂度分别枚举位于第一组、第二组中的人，随后计算每一种分组的快乐值，代码较长，赛时敲了半个小时，不过好在一发过了。总结：其实代码里面的剪枝完......
  • beginnersbook C 语言教程·翻译完成 | ApacheCN
    译者：飞龙协议：CCBY-NC-SA4.0首先学习C基础知识如何安装TurboC++：编译并运行C程序C程序结构-第一个C程序C关键词-保留字C中的决策控制语句C编程中的if语句C-if..else，嵌套if..else和else..if语句C编程的switch-case语句C中的循环C编程中for的循环C编程中的wh......
  • beginnersbook C++ 教程·翻译完成 | ApacheCN
    译者：飞龙协议：CCBY-NC-SA4.0基础HelloWorld-第一个C++程序C++中的变量C++中的数据类型C++中的运算符控制语句C++中的if语句C++中的switch-case语句C++中的for循环C++中的while循环C++中的do-while循环C++中的continue语句C++中的break语句C++中的goto语句函数C++......
  • beginnersbook C 语言示例·翻译完成 | ApacheCN
    译者：飞龙协议：CCBY-NC-SA4.0简单的C程序C语言中的HelloWorld程序C程序：检查给定的整数是正还是负C程序：使用递归函数反转给定的数字C程序：查找最大的三个数字C程序：显示Fibonacci序列C程序：使用递归查找数字的阶乘C程序：查找给定范围内的素数C程序：检查阿姆斯特朗数C程序......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99