跳转至

ABC390(A-F)

A - 12435

题目大意

给你一个 \(1\) 到 \(5\) 的排列，能否通过一次交换相邻的两个数字的操作使得这个排列有序？

参考代码 
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> a(5), target = {1, 2, 3, 4, 5};
    for (auto &x : a)
        cin >> x;
    for (int i = 0; i < 4; i++)
        if (a[i] > a[i + 1])
        {
            swap(a[i], a[i + 1]);
            if (a == target)
            {
                cout << "Yes" << endl;
                return 0;
            }
            break;
        }
    cout << "No" << endl;
    return 0;
}

B - Geometric Sequence

题目大意

给你一个长度为 \(N\) 的数列 \(A\)，判断 \(A\) 是不是一个等比数列。

参考代码 
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    vector<LL> a(n);
    for (auto &x : a)
        cin >> x;

    for (int i = 2; i < n; i++)
        if (a[i] * a[0] != a[i-1] * a[1])
        {
            cout << "No" << endl;
            return 0;
        }
    cout << "Yes" << endl;
    return 0;
}

C - Paint to make a rectangle

题目大意

有一个 \(H \times W(1 \le H, W \le 1000)\) 的网格，每个格子可能是 #（黑色）、.（白色）或 ?（未涂色）。你可以将 ? 涂成黑色或者白色。问：是否存在一种涂色的方案，使得所有黑色格子形成一个长方形？

解题思路

记录下所有黑色格子的横纵坐标的最大最小值，就可以确定长方形的左上角和右下角，然后判断里面有没有白色格子就好。

参考代码 
#include <iostream>
#include <limits>
#include <string>
#include <vector>

using namespace std;

const int PINF = numeric_limits<int>::max();
const int NINF = numeric_limits<int>::min();

int main()
{
    int h, w;
    cin >> h >> w;
    vector<string> g(h);
    int r1 = PINF, c1 = PINF;
    int r2 = NINF, c2 = NINF;
    for (int r = 0; r < h; r++)
    {
        cin >> g[r];
        for (int c = 0; c < w; c++)
            if (g[r][c] == '#')
            {
                r1 = min(r1, r);
                c1 = min(c1, c);
                r2 = max(r2, r);
                c2 = max(c2, c);
            }
    }
    for (int r = r1; r <= r2; r++)
        for (int c = c1; c <= c2; c++)
            if (g[r][c] == '.')
            {
                cout << "No" << endl;
                return 0;
            }
    cout << "Yes" << endl;
    return 0;
}

D - Stone XOR

题目大意

有 \(N(2 \le N \le 12)\) 个袋子，第 \(i\) 个袋子有 \(A_i(1 \le A_i \le 10 ^ {17})\) 个石头。你可以执行以下操作任意次：

  • 选择两个袋子，将其中一个袋子的所有石头移动到另一个袋子中。

在你执行完所有操作后，设第 \(i\) 个袋子最终还有 \(B_i\) 个石头，且 \(X = B_1 \oplus B_2 \oplus \cdots \oplus B_N\)，问：有多少种不同的 \(X\) 值？

解题思路

可以通过搜索实现，问题相当于将 \(N\) 个数字划分成若干个即可，这其实就是贝尔数的枚举方式，每个数字要么加入之前已有的集合中，要么单开一个新的集合。

参考代码 
#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    vector<LL> a(n), b(n);
    for(auto &x : a)
        cin >> x;
    unordered_set<LL> vis;

    auto dfs = [n, &a, &b, &vis](auto &self, int cur, int m) -> void
    {
        if(cur == n)
        {
            LL num = 0;
            for(auto s : b)
                num ^= s;
            vis.insert(num);
            return;
        }

        for(int i = 0; i < m; i++)
        {
            b[i] += a[cur];
            self(self, cur + 1, m);
            b[i] -= a[cur];
        }
        b[m] = a[cur];
        self(self, cur + 1, m + 1);
        b[m] = 0;
    };

    dfs(dfs, 0, 0);
    cout << vis.size() << endl;
    return 0;
}

E - Vitamin Balance

题目大意

有 \(N(1 \le N \le 5000)\) 种食物，有三种维生素类型 \(1\)、\(2\) 或 \(3\)，吃下第 \(i\) 种食物的提供 \(A_i(1 \le A_i \le 2 \times 10^5)\) 单位的维生素 \(V_i(V_i \in \{1, 2, 3\})\)，以及 \(C_i\) 单位的卡路里。

你可以选择吃任意食物，但摄入的卡路里总量不能超过 \(X(1 \le C_i \le X \le 5000)\)。

问：维生素 \(1\)、\(2\)、\(3\) 中摄入量最少的那种维生素的摄入量的最大值是多少？

解题思路

可以轻易的用背包处理出 \(dp[1][i]\)、\(dp[2][i]\)、\(dp[3][i]\) 表示在摄入 \(i\) 卡路里的情况下最多能获得多少维生素 \(1\)、\(2\)、\(3\)。这一块时间复杂度是 \(O(NX)\)

然后可以同样用背包，把 \(dp[1][i]\) 和 \(dp[2][i]\) 组合成摄入 \(i\) 卡路里能能获得前两种维生素中的最小值的最大值，再继续混合成三种的就好。这一块时间复杂度是 \(O(X^2)\)

参考代码 
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, x;
    cin >> n >> x;
    vector<vector<int>> a(3), c(3);
    for (int i = 0; i < n; i++)
    {
        int v, aa, cc;
        cin >> v >> aa >> cc;
        v--;
        a[v].push_back(aa);
        c[v].push_back(cc);
    }

    auto DP = [x](const vector<int> &a, const vector<int> &c) -> vector<int>
    {
        int n = a.size();
        vector<int> dp(x + 1);
        for (int i = 0; i < n; i++)
            for (int j = x; j >= c[i]; j--)
                dp[j] = max(dp[j], dp[j - c[i]] + a[i]);
        return dp;
    };

    vector<int> f = DP(a[0], c[0]);

    auto mix = [x, DP, &f](const vector<int> &a, const vector<int> &c) -> vector<int>
    {
        vector<int> g = DP(a, c);
        vector<int> h(x + 1);
        for (int i = 0; i <= x; i++)
            for (int j = 0; i + j <= x; j++)
                h[i + j] = max(h[i + j], min(f[i], g[j]));
        return h;
    };

    f = mix(a[1], c[1]);
    f = mix(a[2], c[2]);
    cout << f[x] << endl;
    return 0;
}

F - Double Sum 3

题目大意

给你一个长度为 \(N(1 \le N \le 3 \times 10 ^ 5)\) 的整数序列 \(A = (A_1, A_2, \cdots, A_N)\)，其中 \(1 \le A_i \le N\)。

对于一个满足 \(1 \le L \le R \le N\) 的数对 \((L, R)\)，定义 \(F(L, R)\) 的值如下：

  • 首先，在黑板中写下 \(A_L, A_{L+1}, ..., A_R\) 这些数字。
  • 重复以下操作直到黑板中所有的数字都被擦除：
    • 选择两个整数 \(l\)，\(r\)，需满足黑板上所有 \([l, r]\) 范围内的整数至少各出现一次。随后擦除黑板上所有 \([l, r]\) 范围内的整数。
  • \(F(L, R)\) 定义为清除所有整数所需的最小操作次数。

求出 \(\sum\limits_{L=1}^N\sum\limits_{R=L}^N f(L, R)\)

解题思路

问题相当于将一堆数字划分成尽可能少的连续整数段。不妨钦定一个连续整数段中最大的数字作为代表，同时如果有多个元素，选取最靠左的作为代表。

对于一个数字 \(l \le i \le r\)，数字 \(A_i\) 如果是元素，则 \(A_l, ...A_{i-1}\) 中一定没有 \(A_i + 1\) 或者 \(A_i\)，且 \(A_{i+1}, ...A_r\) 中一定没有 \(A_i + 1\)。因此，预处理出两个数组 \(pre[i]\) 表示在 \(i\) 的左边且第一个等于 \(A_i + 1\) 或 \(A_i\) 的位置，\(nxt[i]\) 表示在 \(i\) 的右边且第一个等于 \(A_i + 1\) 的位置。这样 \(A_i\) 的贡献就是 \((i - pre[i]) \times (nxt[i]-i)\)

参考代码 
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &x : a)
        cin >> x;
    vector<int> pre(n), pos(n+2, -1);
    for(int i = 0; i < n; i++)
    {
        int x = a[i];
        pre[i] = max(pos[x], pos[x+1]);
        pos[x] = i;
    }
    pos.assign(n+2, n);
    LL ans = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        int x = a[i];
        ans += (LL)(i - pre[i]) * (pos[x+1] - i);
        pos[x] = i;
    }
    cout << ans << endl;
    return 0;
}
最后更新: 2025-06-14
创建日期: 2025-06-14