跳转至

ABC366(A-G)

A - Election 2

题目大意

\(N\) 张选票(\(N\) 是奇数),有两个候选人,第一位候选人已经收到了 \(T\) 张选票,第二位候选人已经收到了 \(A\) 张选票,投票结束后选票多的人获胜。问:现在是否已经分出了选举的胜负?

参考代码
#include <iostream>

using namespace std;

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    n -= a + b;
    if(a > b + n || b > a + n)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

B - Vertical Writing

题目大意

给你 \(N\) 行水平书写的字符串,将他们转换成垂直书写。

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

using namespace std;

int main()
{
    int n;
    size_t m = 0;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        m = max(m, s[i].size());
    }
    for (size_t j = 0; j < m; j++)
    {
        int k = 0;
        while (j >= s[k].size())
            k++;
        for (int i = n - 1; i >= k; i--)
            cout << (j < s[i].size() ? s[i][j] : '*');
        cout << '\n';
    }
    return 0;
}

C - Balls and Bag Query

题目大意

你需要维护一个数字集合,按顺序处理 \(Q(1 \le Q \le 2 \times 10 ^ 5)\) 个操作,有三种不同类型的操作:

  • 1 x,在集合中加入一个数字 \(x\),相同的数字在集合中可以存在多个。
  • 2 x,在集合中删除一个数字 \(x\),这个操作保证集合中至少有一个数字 \(x\)
  • 3 查询集合中有多少个不同的数字。
解题思路

用一个 map 维护数字出现的次数即可。

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

using namespace std;

int main()
{
    int n, op, x;
    cin >> n;
    unordered_map<int, int> cnt;
    while(n--)
    {
        cin >> op;
        if(op == 1)
        {
            cin >> x;
            cnt[x]++;
        }
        else if(op == 2)
        {
            cin >> x;
            auto it = cnt.find(x);
            if(it->second == 1)
                cnt.erase(it);
            else
                it->second--;
        }
        else
            cout << cnt.size() << endl;
    }    
    return 0;
}

D - Cuboid Sum Query

题目大意

给你一个 \(N \times N \times N (1 \le N \le 100)\) 的立方体,每个位置都写有一个数字。给你 \(Q(1 \le Q \le 2 \times 10 ^ 5)\) 个询问,每个询问是一个六元组,表示一个子立方体的左下角坐标和右上角坐标,回答出这个子立方体的数字之和。

解题思路

三维前缀和模板题,不用记公式,容斥即可。

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

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<vector<int>>> s(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
            {
                cin >> s[i][j][k];
                s[i][j][k] += s[i - 1][j][k] + s[i][j - 1][k] + s[i][j][k - 1] - s[i - 1][j - 1][k] - s[i - 1][j][k - 1] - s[i][j - 1][k - 1] + s[i - 1][j - 1][k - 1];
            }
    int q;
    cin >> q;
    while (q--)
    {
        int x1, x2, y1, y2, z1, z2;
        cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        x1--, y1--, z1--;
        cout << s[x2][y2][z2] - s[x1][y2][z2] - s[x2][y1][z2] - s[x2][y2][z1] + s[x2][y1][z1] + s[x1][y2][z1] + s[x1][y1][z2] - s[x1][y1][z1] << endl;
    }
    return 0;
}

E - Manhattan Multifocal Ellipse

题目大意

在二维平面上给你 \(N(2 \le N \le 10 ^5)\) 个点的坐标 \((x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\),其中 \(-10^6 \le x_i, y_i \le 10^6\),同时给你一个整数 \(D(0 \le D \le 10^6)\),求出平面上有多少个点满足 \(\sum\limits_{i = 1} ^ N(|x - x_i| + |y - y_i|) \le D\)

解题思路

\(s(x) = \sum\limits_{i = 1} ^ N|x - x_i|\)\(s(y) = \sum\limits_{i = 1} ^ N|y - y_i|\)

由于 \(0 \le D \le 10^6\)\(-10^6 \le x_i, y_i \le 10^6\),因此符合条件的 \((x, y)\) 取值范围是 \(-2 \times10^6 \le x, y \le 2 \times 10^6\),我们可以先枚举 \(x\)。这样,我们还需要解决以下两个问题:

  1. 对于一个 \(x\),如何求出 \(s(x)\),需要用 \(O(1)\) 的时间求出 \(s(x)\)
  2. 对于一个 \(x\),如何求出有多少个 \(y\) 满足 \(s(x) + s(y) \le D\)

先解决第一个问题。我们可以对所有的 \(x_i\)排序,然后枚举 \(x \in [-2 \times10^6, 2 \times10^6]\),逐步求出每一个 \(s(x)\) 的值,设有 \(L(x)\)\(x_i\) 坐标小于等于 \(x\),则有:

\[ s(x) = \left\{\begin{matrix} \sum\limits_{i = 1} ^ N (x_i - x) , & x = -2 \times10^6 \\ s(x - 1) + L(x) - (N - L(x)), & x \ne -2 \times10^6 \end{matrix}\right. \]

所以只需要在遍历的时候维护好 \(L(x)\) 的值即可。这样我们可以预处理出 \(x \in [-2 \times10^6, 2 \times10^6]\) 所有的 \(s(x)\) 的值。

下面解决第二个问题:同样的,我们预处理出 \(y \in [-2 \times10^6, 2 \times10^6]\) 所有的 \(s(y)\) 值,然后对这个数组进行排序,然后每枚举到一个 \(x\) 的时候,直接二分有多少个 \(s(y)\) 值满足 \(s(x) + s(y) \le D\),不过更好的办法是直接双指针。

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

using namespace std;
using LL = long long;

const int MAXC = 2E6;
const int LEN = MAXC * 2 + 1;

int main()
{
    int n, d;
    cin >> n >> d;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        x[i] += MAXC;
        y[i] += MAXC;
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    auto cal_sum = [n](const vector<int> &x) -> vector<LL>
    {
        vector<LL> sum(LEN);
        sum[0] = accumulate(x.begin(), x.end(), 0ll);
        for (int i = 1, j = 0; i < LEN; i++)
        {
            sum[i] = sum[i - 1] + j - (n - j);
            while (j < n && x[j] == i)
                j++;
        }
        return sum;
    };

    vector<LL> xs = cal_sum(x);
    vector<LL> ys = cal_sum(y);
    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());
    LL ans = 0;
    for(int i = LEN - 1, j = 0; i >= 0; i--)
    {
        while(j < LEN && xs[i] + ys[j] <= d)
            j++;
        ans += j;
    }
    cout << ans << endl;
    return 0;
}

F - Maximum Composition

题目大意

\(N(2 \le N \le 2 \times 10 ^5)\) 个一次函数,第 \(i\) 个函数是 \(f_i(x) = A_ix + B_i\), 其中 \(1 \le A_i, B_i \le 50\)。你需要从中选择出 \(K(1 \le K \le \min(N, 10))\) 个不同的函数,假设选择的函数是 \(f_{p1}, f_{p2}, \cdots, f_{pK}\),你需要最大化 \(f_{p1}(f_{p2}(...f_{pK}(1)...))\) 的值。

解题思路

假设 \(K\) 个函数已经选好,考虑如何排列顺序。设有两个函数 \(f_i(x)\)\(f_j(x)\),则将 \(f_i(x)\) 放在外侧更优等价于:

\[ \begin{array}{cl} & A_i(A_jx + B_j) + B_i > A_j(A_i x + B_i) + B_j\\ \Rightarrow & A_iB_j + B_i > A_jB_i + B_j \\ \Rightarrow & (A_i - 1)B_j > (A_j - 1)B_i \\ \Rightarrow & \frac{(A_i - 1)}{B_i} > \frac{(A_j - 1)}{B_j} \\ \end{array} \]

因此,只需要按照 \(\frac{(A_i - 1)}{B_i}\) 升序排序,\(\frac{(A_i - 1)}{B_i}\) 较大的函数应该作用在外部。

下面考虑如何选择出 \(K\) 个函数,直接 dp 就可以了。定义 \(dp[i][j]\) 表示在(排序后的)前 \(i\) 个函数中选择 \(j\) 个能获得的最大值,显然有 \(dp[i][j] = \max(dp[i-1][j], A_j(dp[i-1][j-1]) + B_j)\)

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

using namespace std;
using LL = long long;

struct Fun
{
    LL a, b;
    bool operator>(const Fun &other) const { return (a - 1) * other.b < (other.a - 1) * b; }
};

int main()
{
    int n, k;
    cin >> n >> k;
    vector<Fun> f(n);
    for (int i = 0; i < n; i++)
        cin >> f[i].a >> f[i].b;
    sort(f.begin(), f.end(), greater<Fun>());
    vector<LL> dp(k + 1);
    dp[0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = k; j; j--)
            dp[j] = max(dp[j], f[i].a * dp[j - 1] + f[i].b);
    cout << dp[k] << endl;
    return 0;
}

G - XOR Neighbors

题目大意

给你一个 \(N(1 \le N \le 60)\) 个点 \(M(0 \le M \le N(N-1)/2)\) 的无向简单图。你需要给图中的每个点都写上一个 \([1, 2^{60}-1]\) 之间的数字,同时满足以下条件:

  • 对于图中每个点 \(u\),点 \(u\) 的所有邻居的数字的异或和为 \(0\)

如果存在一种方案能满足这个条件,输出 Yes,同时输出每个点的数字。否则输出 No

解题思路

高斯消元解异或方程组的模板题,前置知识:高斯消元 - OI WikiP3389 【模板】高斯消元法 - 洛谷P2455 [SDOI2006] 线性方程组 - 洛谷P2447 [SDOI2010] 外星千足虫 - 洛谷

图中有 \(N\) 个点,每个点的邻居的数字的异或和都为 \(0\),因此我们可以得到一个异或方程组。但这里要注意每个点的数字不能是 \(0\),也就是说这个异或方程组是有无穷多个解的。由于最多 \(60\) 个点,取值范围也是 \(60\) 位,可以强行指定第 \(i\) 个点的第 \(i\) 位为 \(1\),这样就可以保证每个点都非 \(0\)。然后就是枚举每一位,求解出异或方程即可。

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

using namespace std;
using LL = long long;

const int MAXN = 64;

int n, m;
bool gauss(vector<LL> &ans, vector<bitset<MAXN>> mat, int pos)
{
    bitset<MAXN> spec;
    spec[pos] = spec[n] = 1;
    mat.push_back(spec);
    for (int i = 0; i < n; i++)
    {
        for (int r = i; r <= n; r++)
            if (mat[r][i])
            {
                swap(mat[i], mat[r]);
                break;
            }
        if (!mat[i][i])
            continue;
        for (int r = 0; r <= n; r++)
            if (r != i && mat[r][i])
                mat[r] ^= mat[i];
    }
    if (mat[n][n])
        return false;
    for (int c = 0; c < n; c++)
        ans[c] |= ((long long)mat[c][n]) << pos;
    return true;
}

int main()
{
    cin >> n >> m;
    vector<bitset<MAXN>> mat(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        mat[u][v] = mat[v][u] = 1;
    }
    vector<LL> ans(n);
    for (int i = 0; i < n; i++)
        if (!gauss(ans, mat, i))
        {
            cout << "No" << endl;
            return 0;
        }
    cout << "Yes" << endl;
    for (int i = 0; i < n; i++)
        cout << ans[i] << ' ';
    return 0;
}


最后更新: 2024-11-04
创建日期: 2024-11-04