348

A - Penalty Kick

void solve() {
    int n;cin >> n;
    for (int i = 1;i <= n;i++) {
        if (i % 3 == 0) cout << "x";
        else cout << "o";
    }
}

B - Farthest Point

在 $x y$ \ 平面上，有 $N$ 个点，其 ID 编号从 $1$ 到 $N$ 。没有两个点的坐标相同。

找出离每个点最远的点并打印其 ID 编号。如果多个点都是最远点，则打印这些点中最小的 ID 号。

#define int long long
void solve() {
    int n;cin >> n;vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 1;i <= n;i++) {
        int ans = 0, res = 0;
        for (int j = 1;j <= n;j++) {
            if (j != i) {
                int dis = (a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]);
                if (dis > ans) {
                    ans = dis;res = j;
                }
            }
        }
        cout << res << "\n";
    }
}

C - Colorful Beans

豆子有 $N$ 种，每种一种。其中 $i$ 种豆子的美味度为 $A_{i}$ ，颜色为 $C_{i}$ 。豆子是混合的，只能通过颜色来区分。

您将选择一种颜色的豆子，并吃一颗这种颜色的豆子。通过选择最佳颜色，最大限度地减少所吃豆子的美味度。

void solve() {
    int n;cin >> n;vector<int>a(n + 1), b(n + 1);
    map<int, int>mp;
    for (int i = 1;i <= n;i++) {
        int x, y;cin >> x >> y;
        if (mp.count(y)) mp[y] = min(mp[y], x);
        else mp[y] = x;
    }
    int ans = 0;
    for (auto [x, y] : mp) {
        ans = max(ans, y);
    }
    cout << ans << '\n';
}

D - Medicines on Grid

有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i, j)$ 表示位于从上往下第 $i$ 行和从左往上第 $j$ 列的单元格。每个单元格的状态由字符 $A_{i, j}$ 表示，其含义如下：

.: 空单元格。
#: 一个障碍物。
S: 空单元格和起点。
T: 空单元格和目标点。

高桥可以通过消耗 $1$ 能量从当前单元格移动到垂直或水平相邻的空单元格。如果能量为 $0$ ，则无法移动，也无法离开网格。

网格中有 $N$ 种药物。 $i$ -th 药品位于空格 $(R_{i}, C_{i})$ ，可以用来将能量到 $E_{i}$ 。注意，能量并不一定会增加。他可以在当前牢房中使用药物。使用过的药物会消失。

高桥以 $0$ 的能量从起点开始，并希望到达目标点。请判断这是否可行。

Solution

奇怪的 BFS/图论/优先队列

我之前才做过这种类型的题目[[P2802 回家 ](https // www.luogu.com.cn/problem/P2802 )](../../../ACM/搜索/练习/搜索刷题概要.md# P2802%20回家%20)，但是那个题的数据范围比较小，这个题目数据较大。方法不一样了。

PS:c++11 后可以使用 or and not 来使代码变得更清晰.

将给出的可能补充能量的地方 $(x, y)$ 和 $(e)$ 存储起来。再将 $(x, y)$ 下标储存起来方便标记。

20ms

int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    vector<vector<char>> s(n + 1, vector<char>(m + 1));
    int sx = 0, sy = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            if (s[i][j] == 'S') sx = i, sy = j;
        }
    }
    int k;cin >> k;
    map<pair<int, int>, int>mp;vector<int> e;vector<pair<int, int>> pos;
    for (int i = 0;i < k;i++) {
        int r, c, E;cin >> r >> c >> E;
        pos.push_back({r,c});
        e.push_back(E);
        mp[{r, c}] = i;
    }

    queue<int>q;vector<int> visk(k);
    for (auto [p, i] : mp) {
        if (p.first == sx && p.second == sy) {
            q.push(i);visk[i] = 1;break;
        }
    }
    while (q.size()) {
        auto i = q.front();q.pop();
        auto [x, y] = pos[i];
        queue<pair<int, int>> que;
        vector<vector<int>> vis(n + 1, vector<int>(m + 1));
        que.push({x,y});vis[x][y] = 1;
        int dis = e[i];
        while (que.size() && dis--) {
            int len = que.size();
            while (len--) {
                auto [r, c] = que.front();que.pop();
                for (int j = 0;j < 4;j++) {
                    int a = r + dx[j], b = c + dy[j];
                    if (a<1 || b<1 || a>n || b>m)continue;
                    if (s[a][b] == '#' || vis[a][b])continue;
                    if (s[a][b] == 'T') {
                        cout << "Yes\n";return;
                    }
                    if (mp.count({a,b}) && !visk[mp[{a, b}]]) {
                        q.push(mp[{a, b}]);visk[mp[{a, b}]] = 1;
                    }
                    que.push({a,b});vis[a][b] = 1;
                }
            }
        }
    }
    cout << "No\n";
}

官方题解代码：

void solve() {
    int n, m;cin >> n >> m;
    vector<vector<char>> s(n + 1, vector<char>(m + 1));
    int sx = 0, sy = 0, ex = 0, ey = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            if (s[i][j] == 'S')sx = i, sy = j;
            if (s[i][j] == 'T')ex = i, ey = j;
        }
    }
    int k;cin >> k;
    vector<vector<int>> to(n + 1, vector<int>(m + 1));
    for (int i = 0;i < k;i++) {
        int r, c, e;cin >> r >> c >> e;to[r][c] = e;
    }
    vector<vector<int>> dis(n + 1, vector<int>(m + 1, -1));dis[sx][sy] = 0;
    queue<pair<int, int>>q;q.push({sx,sy});
    while (q.size()) {
        auto [x, y] = q.front();q.pop();
        int t = max(dis[x][y], to[x][y]);
        if (t <= 0)continue;
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a<1 || b<1 || a>n || b>m || s[a][b] == '#')continue;
            if (dis[a][b] < t - 1) {
                dis[a][b] = t - 1;q.push({a,b});
            }
        }
    }
    if (dis[ex][ey] == -1) cout << "No\n";
    else cout << "Yes\n";
}

若将其中 queue 的部分换为 priority_queue 可以从 112 ms->8ms,类似于最短路

priority_queue<array<int, 3>>q;q.push({0,sx,sy});
while (q.size()) {
	auto [g, x, y] = q.top();q.pop();
	int t = max(dis[x][y], to[x][y]);
	if (t <= 0)continue;
	for (int i = 0;i < 4;i++) {
		int a = x + dx[i], b = y + dy[i];
		if (a<1 || b<1 || a>n || b>m || s[a][b] == '#')continue;
		if (dis[a][b] < t - 1) {
			dis[a][b] = t - 1;q.push({dis[a][b],a,b});
		}
	}
}

E - Minimize Sum of Distances

给你一棵有 $N$ 个顶点的树。顶点的编号为 $1$ 至 $N$ ， $i$ -th 边连接顶点 $A_{i}$ 和 $B_{i}$ 。

我们还给出了一个长度为 $N$ 的正整数序列 $C$ 。设 $d (a, b)$ 是顶点 $a$ 和 $b$ 之间的边数，而对于 $x = 1, 2, \dots, N$ ，设 $f (x) = \sum_{i = 1}^{N} (C_{i} \times d (x, i))$ 。求出 $min_{1 \leq v \leq N} f (v)$ 。

Solution

换根 DP/树形 DP/换根/树的重心

原：Problem - F - Codeforces 不过这个题目是求的最大值，前面的处理一样，第二个 DFS 有所区别：

$C F_{D F S_{2}}$

void go(int v, int p = -1) {
	ans = max(ans, res);
	for (auto to : g[v]) {
		if (to == p) {
			continue;
		}
		
		res -= sum[to];
		sum[v] -= sum[to];
		res += sum[v];
		sum[to] += sum[v];
		
		go(to, v);
		
		sum[to] -= sum[v];
		res -= sum[v];
		sum[v] += sum[to];
		res += sum[to];
	}
}

此题目的类似写法：

ll ans = INF;
void dfs(int u, int fa) {
    ans = min(ans, res);
    for (auto v : G[u]) {
        if (v == fa) { 
            continue;
        }
        res -= sum[v];
        res += sum[1] - sum[v];
        dfs(v, u);
        res += sum[v];
        res -= sum[1] - sum[v];
    }
}

先以 $1$ 为根节点扫一遍树， $s u m [i]$ 代表节点 $i$ 及其节点 $i$ 加起来的权重，根节点的权重一定是所有权重的和。

然后去找到权重占到 $>$ 总权重一半的节点 $x$ ，这时将 $x$ 作为根节点，由于本身的权重不计入，这样就可以省去最多的权重，从而答案最小。

若等于总权重一半，则换不换根节点都可以。

若根节点没变，则本身就是最小。

通常的来讲，上面所描述的可以叫做树的重心，可以证明，每一个树都存在重心，至多有两个重心。

以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。这里的大小带有权重，则是指加权大小。

树的重心 - OI Wiki 关于树的重心 (质心)，致力于解决图论及其优化问题

void solve() {
    int n;cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1;i < n;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);g[v].push_back(u);
    }
    vector<int>c(n + 1);
    for (int i = 1;i <= n;i++)cin >> c[i];
    vector<ll> sum(n + 1);
    auto dfs1 = [&](auto self, int x, int p) -> void {
        sum[x] = c[x];
        for (auto y : g[x]) {
            if (y == p)continue;
            self(self, y, x);
            sum[x] += sum[y];
        }
        };
    dfs1(dfs1, 1, 0);

    auto dfs2 = [&](auto self, int x, int p) -> int {
        for (auto y : g[x]) {
            if (y == p || 2 * sum[y] <= sum[1])continue;
            return self(self, y, x);
        }
        return x;
        };
    int x = dfs2(dfs2, 1, 0);
    dfs1(dfs1, x, 0);
    ll ans = 0;
    for (int i = 1;i <= n;i++) {
        if (i != x)ans += sum[i];
    }
    cout << ans << '\n';
}

另：此题目算是换根 DP 模板, 此处并未给出做法。贴上代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<i64> c(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    vector<i64> dp(n + 1), res(n + 1);
    auto pre_dfs = [&](auto &f, int fa, int u)->void {
        dp[u] = c[u];
        for (auto &v : g[u]) {
            if (v == fa) continue;
            f(f, u, v);
            dp[u] += dp[v];
            res[u] += res[v] + dp[v];
        }
    };
    pre_dfs(pre_dfs, 1, 1);
    auto dfs = [&](auto &f, int fa, int u)->void {
        if (fa != u)
            res[u] = res[fa] - (res[u] + dp[u]) + (dp[1] - dp[u]) + res[u];
            // res[u] = res[fa] + dp[1] - 2 * dp[u]
        for (auto &v : g[u]) {
            if (v == fa) continue;
            f(f, u, v);
        }  
    };
    dfs(dfs, 1, 1);
    cout << *min_element(begin(res) + 1, end(res)) << '\n';
}

F - Oddly Similar

有长度为 $M$ 的 $N$ 个序列，表示为 $A_{1}, A_{2}, \dots, A_{N}$ 。长度为 $i$ 的序列由 $M$ 个整数 $A_{i, 1}, A_{i, 2}, \dots, A_{i, M}$ 表示。

长度为 $M$ 的两个序列 $X$ 和 $Y$ 如果且仅当 $i (1 \leq i \leq M)$ 中 $X_{i} = Y_{i}$ 的索引数为奇数时，才可以说这两个序列是相似的。

求满足 $1 \leq i < j \leq N$ 的一对整数 $(i, j)$ 中， $A_{i}$ 和 $A_{j}$ 相似的个数。

Solution

bitset/技巧

#pragma GCC optimize("Ofast,unroll-loops")

开启了 O3 后就可以直接暴力过

int ans = 0;
for (int i = 0;i < n;i++) {
	for (int j = i + 1;j < n;j++) {
		int cnt = 0;
		for (int k = 0;k < m;k++) {
			if (a[i][k] == a[j][k])cnt++;
		}
		if (cnt & 1)ans++;
	}
}
cout << ans << '\n';

bitset 硬凹时间复杂度: $O (\frac{N^{2} M}{64})$

bitset<2010> f[2010][1000];
void solve() {
    int n, m;cin >> n >> m;
    vector<vector<int>>a(n, vector<int>(m));
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cin >> a[i][j];
            f[j][a[i][j]][i] = 1;
        }
    }
    int ans = 0;
    for (int i = 0;i < n;i++) {
        bitset<2010> g;
        for (int j = 0;j < m;j++) {
            g ^= f[j][a[i][j]];
        }
        g[i] = 0;
        ans += g.count();
    }
    cout << ans / 2 << '\n';
}

G - Max (Sum - Max)

给你两个长度为 $N$ 的整数序列 $A$ 和 $B$ 。对于 $k = 1, 2, \dots, N$ ，请解决下面的问题：

考虑在 $1$ 和 $N$ 之间选择 $k$ 个不同的整数。设 $S$ 为所选整数的集合。求 $(\sum_{i \in S} A_{i}) - max_{i \in S} B_{i}$ 的最大值。

Solution

原题：Problem - L - Codeforces