牛客练习赛122

A 黑白配

“黑白配”是一款家喻户晓的小游戏。每个人亮出手心或手背，亮出手心的为一队，亮出手背的为一队。

有$n$ 个学生在玩“黑白配”。他们想知道分组结果是否公平，请求出两队人数之差的绝对值。

cout << abs(count(a.begin(), a.end(), 1) - count(a.begin(), a.end(), 0)) << '\n';

B 映射

给定两个长度为 $n$ 的序列 $a$，$b$，$(1\le a_i,b_i\le n)$

询问是否可以构造出一个序列 $p$，满足 $1\le i\le n$，$p_{a_i}=b_i$。

显然，在构造 $p$ 时出现两个相同的下标却出现不同的值时才会无解。

void solve() {
    int n;cin >> n;vector<int> a(n + 1), b(n + 1), p(n + 1), vis(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];
    for (int i = 1;i <= n;i++) {
        if (!vis[a[i]]) {
            p[a[i]] = b[i];vis[a[i]] = 1;
        } else {
            if (p[a[i]] != b[i]) {
                cout << "No\n";return;
            }
        }
    }
    cout << "Yes\n";
}

C 马走日

给出一个 $n\times m(1\le n,m\le {10}^9)$ 的点阵，刚开始，马在 $(1,1)$ 位置，马有八个方向可走($x+dx[i],y+dy[i]$)：

int dx[] = {1,-1,1,-1,2,-2,2,-2};
int dy[] = {2,2,-2,-2,1,1,-1,-1};

求在 $n\times m$ 的点阵中马能跳到多少个位置。

容易知道，当 $n,m$ 较大的时候马就可以走到任意的地方。

• 当 $n,m\ge 4$ 时就可以走到任意位置
• 当 $n=1$ 时，无位置可走，答案是 1
• 当 $n=2$ 时，只有往右边走，且每两个位置可以跳一次
• 当 $n=3$ 时，只有 $n=3,m=3$ 不能走完，其他都可以走完。

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    if (n > m)swap(n, m);
    if (n < 4 || m < 4) {
        if (n == 1) {
            cout << "1\n";return;
        } else if (n == 2) {
            cout << (m - 1) / 2 + 1 << '\n';return;
        } else if (n == 3) {
            if (m == 3) {
                cout << "8\n";return;
            }
        }
    }
    cout << n * m << '\n';
}

D 圆

给出一个圆，圆上等距分布$n$ 个点，编号为 $1\sim n$。

另有 $m$ 条线段，第 $i$ 条线段的端点为 $x_i$ 和 $y_i$，权重为 $w_i$。

定义一个圆是优良的，当且仅当所有线段无交（端点重合也算相交）。

若删掉一条边的代价为其权重，求让圆优良的最小代价。

注意：线段可能重合。

Solution

比赛时我写的贪心？即求在 $[1,n]$ 区间内能容纳的最多权值，这样就是最小的代价。(wa 了，不知道是哪里出了问题)

void solve() {
    int n, m;cin >> n >> m;
    int sum = 0;
    vector<array<int, 4>> a(m);
    for (int i = 0;i < m;i++) {
        int x, y, w;cin >> x >> y >> w;
        if (x > y)swap(x, y);
        sum += w;
        a[i] = {x,y,w,-1};
    }
    sort(a.begin(), a.end(), [&](auto x, auto y) {
        if (x[0] == y[0])return x[1] < y[1];
        return x[0] < y[0];
        });
    for (int i = 0;i < m;i++) {
        for (int j = i + 1;j < m;j++) {
            if (a[i][0] == a[j][0] && a[i][1] == a[j][1]) {
                a[i][2] = max(a[i][2], a[j][2]);
                a[j][2] = max(a[i][2], a[j][2]);
            }
        }
    }
    for (int i = 0;i < m;i++) {
        for (int j = m - 1;j >= i + 1;j--) {
            if (a[i][1] < a[j][0]) {
                a[i][3] = j;
            }
        }
    }
    int ans = 1e18;
    for (int i = 0;i < m;i++) {
        int cost = 0;
        for (int j = i;;j = a[j][3]) {
            cost += a[j][2];
            if (a[j][3] == -1)break;
        }
        ans = min(ans, sum - cost);
    }
    cout << ans << '\n';
}

区间 DP
类似于 Problem - 1399F - Codeforces

将序列复制一遍在后面

(待更 $\dots$)

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    int sum = 0;
    vector<pair<int, int>> g[2 * n + 1];
    for (int i = 0;i < m;i++) {
        int x, y, w;cin >> x >> y >> w;
        if (x > y)swap(x, y);sum += w;
        g[x].push_back({y,w});
        g[y].push_back({x + n,w});
    }
    vector<vector<int> > f(2 * n + 1, vector<int>(2 * n + 1));
    for (int i = 1;i <= 2 * n;i++) {
        for (int j = i - 1;j >= 1;j--) {
            f[j][i] = f[j + 1][i];
            for (auto [k, w] : g[j]) {
                if (k > i)continue;
                if (j + 1 < k - 1)w += f[j + 1][k - 1];
                if (k + 1 < i)w += f[k + 1][i];
                f[j][i] = max(f[j][i], w);
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++)ans = max(ans, f[i][i + n - 1]);
    cout << sum - ans << '\n';
}

F 外向树

给出一个 $n$ 个节点的外向树（每条边都是有向边，从父节点指向子节点），根为 $1$。

$m$ 组询问，每次询问至少需要加多少条有向边才可以让编号 $[l,r]$ 之间的点两两可达。

Solution

虚树/外向树/启发式合并/线段树合并

(待更 $\dots$)

G 括号匹配

给出一个长度为 $n$ 的括号序列（不保证合法）第 $i$ 个位置上的字符为 $c_i$，删掉 $c_i$ 的代价为 $w_i$。

有 $m$ 个限制形如 $(x,y,z)$，表示第 $x,y,z$ 个字符中只能恰好保留一个。保证一个位置至多位于一个三元组中，且对于每个三元组 $(x,y,z)$，都有 $c_x=c_y=c_z$。

若一个位置没有在约束条件中出现过，则必须保留。

询问在满足所有约束条件后，括号序列是否能变成合法括号序列。如果不能输出 No，否则输出 Yes 和在括号序列合法前提下的最小代价。

Solution

网络流

(待更 $\dots$)