AtCoder Beginner Contest 348

A - Penalty Kick (abc348 A)

题目大意

给定\(n\),输出 \(ooxooxoox...\),长度为 \(n\)

解题思路

按题意模拟即可。

神奇的代码
n = int(input())
ans = "oox" * (n // 3) + "o" * (n % 3)
print(ans)


B - Farthest Point (abc348 B)

题目大意

给定\(n\)个点,对每个点,求出与其距离最远的点的下标。

解题思路

\(n\)只有 \(100\),对于每个点,花 \(O(n)\)遍历每个点最大化距离,时间复杂度为 \(O(n^2)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<array<int, 2>> p(n);
    for (auto& i : p)
        cin >> i[0] >> i[1];
    for (int i = 0; i < n; ++i) {
        int dis = 0, ans = 0;
        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;
            int dis1 = (p[i][0] - p[j][0]) * (p[i][0] - p[j][0]) +
                       (p[i][1] - p[j][1]) * (p[i][1] - p[j][1]);
            if (dis1 > dis) {
                dis = dis1;
                ans = j;
            } else if (dis1 == dis) {
                ans = min(ans, j);
            }
        }
        cout << ans + 1 << '\n';
    }

    return 0;
}



C - Colorful Beans (abc348 C)

题目大意

\(n\)个豌豆,每个豌豆有美味值 \(a\)和颜色值 \(c\)

豌豆之间只有颜色区别。

现在你会从一种颜色的豌豆里选一个豌豆出来。

最大化选出来的豌豆美味值的最小值。

解题思路

选定一个颜色,最坏情况就是选出了这个颜色中美味值最小的豌豆。

因此对每种颜色求出美味值最小的豌豆,然后所有颜色(决策)的美味值取个最大值即为答案。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    map<int, int> minn;
    for (int i = 0; i < n; i++) {
        int a, c;
        cin >> a >> c;
        if (minn.find(c) == minn.end()) {
            minn[c] = a;
        } else
            minn[c] = min(minn[c], a);
    }
    int ans = minn.begin()->second;
    for (auto& [c, a] : minn) {
        ans = max(ans, a);
    }
    cout << ans << '\n';

    return 0;
}



D - Medicines on Grid (abc348 D)

题目大意

二维网格,起点终点,有障碍物,有药,药的作用是将体力值变为\(c_i\)

初始起点,体力值为 \(0\),问能否走到终点。

解题思路

考虑朴素搜索,记录状态\((i,j,k)\),表示位于 \((i,j)\),当前体力值为 \(k\),然后枚举四个方向搜索后继情况。

考虑总情况数,即 \(O(200^2 \times 200^2)\),有点危险,可以加一些剪枝,比如设 \(dis[i][j]\)表示到达 \((i,j)\)时的最大体力,采用 \(SPFA\)式的搜索即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> tu(h);
    for (auto& i : tu)
        cin >> i;
    vector<vector<int>> dp(h, vector<int>(w, -1));
    vector<vector<int>> med(h, vector<int>(w, -1));
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int r, c, e;
        cin >> r >> c >> e;
        --r, --c;
        med[r][c] = e;
    }
    queue<pair<int, int>> q;
    vector<vector<int>> inq(h, vector<int>(w, 0));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (tu[i][j] == 'S') {
                dp[i][j] = med[i][j];
                q.push({i, j});
                inq[i][j] = 1;
            }
        }
    }
    const array<int, 4> dx = {0, 0, 1, -1};
    const array<int, 4> dy = {1, -1, 0, 0};
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        inq[x][y] = 0;
        if (dp[x][y] <= 0)
            continue;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || tu[nx][ny] == '#')
                continue;
            if (dp[nx][ny] < dp[x][y] - 1) {
                dp[nx][ny] = max(dp[x][y] - 1, med[nx][ny]);
                if (tu[nx][ny] == 'T')
                    break;
                if (!inq[nx][ny]) {
                    q.push({nx, ny});
                    inq[nx][ny] = 1;
                }
            }
        }
    }
    int ok = false;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (tu[i][j] == 'T' && dp[i][j] >= 0) {
                ok = true;
                break;
            }
        }
    }
    if (ok) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}



E - Minimize Sum of Distances (abc348 E)

题目大意

给定一棵树,点有点权\(c_i\),边权为\(1\)

定义 \(f(x) = \sum_{i}c_i dis(x, i)\),其中\(dis(x,i)\)表示点 \(x\)到点 \(i\)的最小距离。

\(f(x)\)的最小值。

解题思路

朴素求法即\(O(n^2)\)。枚举每个点\(x\),然后求一遍 \(dis(x,i)\) ,然后计算\(f(x)\),取最小值。枚举每个点耗时 \(O(n)\),计算 \(f(x)\)耗时 \(O(n)\)

考虑优化 \(f(x)\)的计算。注意到是棵树,我们一般考虑先枚举根 \(0\),计算 \(f(0)\),然后考虑枚举 \(0\)的儿子 \(x\),看看 \(f(x)\)能否从 \(f(0)\)得到。

枚举的点从 \(0 \to x\),考虑\(f(0) \to f(x)\)的计算变化,只有\(dis(0,i)\)变成 \(dis(x,i)\), 其中\(i \in x\)的子树的 \(dis(x,i) = dis(0,i) - 1\),其余的 \(i\)\(dis(x, i) = dis(0,i) + 1\)

\(f(0) = \sum_{i}c_i dis(0, i)\),这是我们已经算出来的。

\(0 \to x\)时,\(f(x) = \sum_{i}c_i dis(x, i) = \sum_{i \in x\text{子树}}c_i (dis(0, i) - 1) + \sum_{i \notin x\text{子树}}c_i (dis(0, i) + 1) = \sum_{i}c_i dis(0, i) - \sum_{i \in x\text{子树}} c_i + \sum_{i \notin x\text{子树}}c_i\)

代入\(f(0) = \sum_{i}c_i dis(0, i)\)得,\(f(x)= f(0) - \sum_{i \in x\text{子树}} c_i + \sum_{i \notin x\text{子树}}c_i\)

因此我们预处理\(sum_x\)表示以 \(x\)为子树的 \(c_i\)的和, \(sum\)是所有的 \(c_i\)的和,那不在 \(x\)的子树的 \(c_i\)的和可以表示成 \(sum - sum_x\)。这样当 \(0 \to x\)时, \(f(x)\)就可以通过 \(f(0),sum_x,sum\)\(O(1)\)内算出来了。

总的时间复杂度变为 \(O(n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> edge(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    vector<int> c(n);
    for (auto& x : c)
        cin >> x;
    LL sum = accumulate(c.begin(), c.end(), 0ll);
    vector<LL> csum(n);
    LL f = 0;
    auto dfs = [&](auto self, int u, int fa, int deep) -> void {
        for (auto v : edge[u]) {
            if (v == fa)
                continue;
            self(self, v, u, deep + 1);
            csum[u] += csum[v];
        }
        f += 1ll * c[u] * deep;
        csum[u] += c[u];
    };
    dfs(dfs, 0, 0, 0);
    LL ans = f;
    auto dfs2 = [&](auto self, int u, int fa) -> void {
        ans = min(ans, f);
        for (auto v : edge[u]) {
            if (v == fa)
                continue;
            f -= csum[v];
            f += sum - csum[v];
            self(self, v, u);
            f -= sum - csum[v];
            f += csum[v];
        }
    };
    dfs2(dfs2, 0, 0);
    cout << ans << '\n';

    return 0;
}



F - Oddly Similar (abc348 F)

题目大意

给定\(n\)个序列\(a_i\),长度为\(m\),问俩俩序列相似的对数。

俩序列相似,说明有奇数个位置,其数相同。

解题思路

考虑朴素做法,枚举两个序列,然后枚举下标,记录数相同的个数,其时间复杂度是\(O(n^2m)\)。判断数相同如果不用 \(if\)的话,在 \(clang\)下能跑过(吸氧太猛了。

n3方过2e3
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m, 0));
    for (auto& x : a)
        for (auto& y : x)
            cin >> y;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = 0;
            for (int k = 0; k < m; k++) {
                sum ^= (a[i][k] == a[j][k]);
            }
            ans += sum;
        }
    }
    cout << ans << '\n';

    return 0;
}


朴素做法是\(O(nnm)\),分别是枚举\(j\)(一行),枚举 \(i\)(另一行),再枚举 \(k\)(列)。考虑对其中一个因素优化。经过尝试,我们可以对枚举\(i\)优化。

其实\(O(nnm)\)是非常接近 \(10^9\)的,一般是可以采用 \(bitset\)优化,总复杂度可以除以 \(64\)

我们记\(cnt[k][l]\)表示第 \(k\)列值为 \(l\)的那些行的情况,即一个 \(bitset\)\(cnt[k][l][i]=1\)表示第\(i\)行 第\(k\)列的值为\(l\)\(=0\)则不为 \(l\)

枚举一行 \(j\),然后枚举一列 \(k\),我们将所有的 \(cnt[k][a_{j,k}]\)(这些都是 \(bitset\))异或起来,最后得到的就是第 \(j\)行与其余行的相似度情况(同下标数相等的个数的奇偶性),统计其为 \(1\)的个数即为 \((i,j)\)相似的 \(i\)的数量。注意要把 \(i=j\)的情况去掉。

时间复杂度是\(O(\frac{n^2m}{64})\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    vector<vector<bitset<2000>>> cnt(m, vector<bitset<2000>>(1000));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            --a[i][j];
            cnt[j][a[i][j]][i] = 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        bitset<2000> s{};
        for (int j = 0; j < m; j++) {
            s ^= cnt[j][a[i][j]];
        }
        s[i] = 0;
        ans += s.count();
    }
    ans /= 2;
    cout << ans << '\n';

    return 0;
}



G - Max (Sum - Max) (abc348 G)

题目大意

给定长度为\(n\)的数组 \(a,b\),对 \(k = 1,2,...,n\),求解以下答案。

选择\(k\)个下标,使得 \(\sum_{k} a_k - \max_{k} b_k\) 最大。

解题思路

<++>

神奇的代码



热门相关:重生嫡女谋天下   重生之男神追妻忙   永恒王权   我拍戏不在乎票房   亡国公主穿成王府寡妇:二嫁王妃