AtCoder Beginner Contest 413 题解

A. Content Too Large

签到，计算出来物品体积的总和，与袋子的大小做对比即可。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using PII = pair<int, int>;

int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}

void solve()
{	
    int n, m;
    cin >> n >> m;

    while (n--)
    {
        int x;
        cin >> x;
        m -= x;
    }

    if (m >= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

B. cat 2

枚举每一种拼接情况，因为 \(set\) 可以自动去重，可以考虑使用 \(set\) 存储拼接后的字符串，最后输出 \(s.size()\) 即为答案。

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using PII = pair<int, int>;

int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}

void solve()
{	
    int n;
    cin >> n;

    vector<string> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    set<string> s;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j)
                s.insert(a[i] + a[j]);
        
    cout << s.size() << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

C. Large Queue

由于插入和删除的数量级很大，如果每次只操作一个数的话，显然超时。

因此，我们可以考虑每次插入和删除的时候，操作一组数。

定义一个双端队列 \(deque\)，类型为 \(pair<int, int>\)，第一个元素代表个数，第二个元素代表大小。

• 操作 \(1\)，直接插入 \(\{c,x\}\)，代表我插入了 \(c\) 个 \(x\)，复杂度为 \(O(1)\)。
• 操作 \(2\)，在取够 \(k\) 个数之前，我们每次从队列中取出的都是一组数，取出组数的上限是我们插入的组数，也就是说我们插入多少次，最多就取出多少次。由于插入的次数不超过 \(2 \times 10^5\)，因此取出的总次数也不超过 \(2 \times 10^5\)，不会超时。

需要注意的是答案有可能会超出 \(int\) 的范围，需要使用 \(long\ long\)。

时间复杂度 \(O(Q)\)。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using PII = pair<int, int>;

int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}

void solve()
{	
    int n;
    cin >> n;

    deque<PII> q;
    while (n--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int c, x;
            cin >> c >> x;
            q.push_back({c, x});
        }
        else
        {
            int k;
            cin >> k;
            
            ll res = 0;
            while (k)
            {
                auto t = q.front();
                q.pop_front();
                if (t.x > k)
                {
                    res += (ll)t.y * k;
                    t.x -= k;
                    k = 0;
                    q.push_front(t);
                }
                else 
                {
                    res += (ll)t.x * t.y;
                    k -= t.x;
                }
            }
            cout << res << endl;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

D. Make Geometric Sequence

对于一个等比数列，其中的元素一定满足它们的绝对值是有序的。

因此可以分两种情况讨论。

1. 数组中的元素都是同号。此时判断排序后的数组能否构成等比数列即可。
2. 数组中的元素有正有负。那么若要使这个数组构成等比数列，一定要使得其中的元素是一正一负排列，把正数和复数单独分离出来排列即可。

判断数组是否能构成等比数列，为避免出现小数，可以使用 \(a_i \times a_i=a_{i-1} \times a_{i+1}\) 作为判断条件。

时间复杂度 \(O(nlogn)\)

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using PII = pair<int, int>;

int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}

void solve()
{	
	int n;
	cin >> n;
	
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    auto cmp = [&](int A, int B)
    {
        return abs(A) < abs(B);
    };
    sort(a.rbegin(), a.rend(), cmp);

    vector<ll> s1, s2;
    for (int i = 0; i < n; i++)
    {
        if (a[i] < 0) s1.push_back(a[i]);
        else s2.push_back(a[i]);
    }

    if (s1.size() && s2.size() && abs((int)s1.size() - (int)s2.size()) > 1)
    {
        cout << "No" << endl;
        return;
    }
    vector<ll> s;
    if (!s1.size())
    {
        while (s2.size())
        {
            s.push_back(s2.back());
            s2.pop_back();
        }
    }
    if (!s2.size())
    {
        while (s1.size())
        {
            s.push_back(s1.back());
            s1.pop_back();
        }
    }
    if (s1.size() && s2.size())
    {
        bool flag = false;
        if (s1.size() < s2.size()) flag = true;
        else if (s1.size() == s2.size() && abs(s2.back()) < abs(s1.back())) flag = true;
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == flag)
            {
                s.push_back(s1.back());
                s1.pop_back();
            }
            else
            {
                s.push_back(s2.back());
                s2.pop_back();
            }
        }
    }
	
    for (int i = 1; i < n - 1; i++)
        if (s[i] * s[i] != s[i - 1] * s[i + 1])
        {
            cout << "No" << endl;
            return;
        }

    cout << "Yes" << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

E. Reverse 2^i

本场最有意思的题目，可以先操作小区间，再操作大区间，具体实现方法类似于归并排序。

时间复杂度 \(O(nlogn)\)。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using PII = pair<int, int>;

int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}

void solve()
{	
    int n;
    cin >> n;
    n = 1 << n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    function<void(int, int)> calc = [&](int l, int r)
    {
        if (l == r) return;
        int mid = l + r >> 1;
        calc(l, mid), calc(mid + 1, r);
        if (a[l] > a[mid + 1])
        {
            for (int i = l, j = mid + 1; i <= mid; i++, j++)
            {
                swap(a[i], a[j]);
            }
        }
    };
    calc(0, n - 1);

    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << endl; 
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

F. No Passage

对于以当前格子为起点，其答案取决于上下左右四个格子的答案，由于青木会限制最小答案的方向，因此该起点的答案为上下左右四个方向答案的次小值加一。

考虑使用 \(bfs\) 来解决问题，对于每个终点都做一遍 \(bfs\)，当某一个点第二次被更新到的时候，代表此时更新的距离为这个点到终点的次小值（第一次更新到的时候是最小值）。

时间复杂度 \(O(nm)\)。

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using PII = pair<int, int>;

int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}

void solve()
{	
    int n, m, k;
    cin >> n >> m >> k;

    vector c(n + 1, vector<int>(m + 1, 0));
    vector f(n + 1, vector<int>(m + 1, -1));
    queue<PII> q;
    while (k--)
    {
        int x, y;
        cin >> x >> y;
        f[x][y] = 0;
        q.push({x, y});
    }

    ll res = 0;
    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    while (q.size())
    {
        auto [x, y] = q.front();
        q.pop();
        res += f[x][y];
        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            c[a][b]++;
            if (f[a][b] == -1 && c[a][b] == 2)
            {
                f[a][b] = f[x][y] + 1;
                q.push({a, b});
            }
        }
    }

    cout << res << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

G. Big Banned Grid

本质是一个连通块问题，判断障碍构成的若干个连通块是否能够隔断 \((1,1)\) 和 \((H,W)\)。

判断是否隔断的方法也很简单，如图，只需判断连通块的上下左右四个边界，和图上的四种隔断方法作比较即可。

可以使用 \(bfs\) 来构建连通块。

时间复杂度 \(O(klogn)\)。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using PII = pair<int, int>;

int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(int x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}

void solve()
{	
    int n, m, k;
    cin >> n >> m >> k;

    map<PII, int> p;
    vector<PII> s(k + 1);
    for (int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        s[i] = {x, y};
        p[{x, y}] = i;
    }

    auto bfs = [&](int st, int ed)
    {
        queue<PII> q;
        q.push({st, ed});
        s[p[{st, ed}]] = {0, 0};
        p.erase({st, ed});
        int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
        int u = 1e9, d = 0, l = 1e9, r = 0;
        while (q.size())
        {
            auto [x, y] = q.front();
            q.pop();
            u = min(u, x), d = max(d, x), l = min(l, y), r = max(r, y);
            for (int i = 0; i < 8; i++)
            {
                int a = x + dx[i], b = y + dy[i];
                if (a < 1 || a > n || b < 1 || b > m) continue;
                if (!p.count({a, b})) continue;
                s[p[{a, b}]] = {0, 0};
                p.erase({a, b});
                q.push({a, b});
            }
        }
        if (u == 1 && l == 1) return false;
        if (u == 1 && d == n) return false;
        if (l == 1 && r == m) return false;
        if (d == n && r == m) return false;
        return true;
    };

    for (int i = 1; i <= k; i++)
    {
        if (s[i].x == 0) continue;
        if (!bfs(s[i].x, s[i].y))
        {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}