比赛链接：https://codeforces.com/contest/1353

A - Most Unstable Array

题意

构造大小为 $n$，和为 $m$ 的非负数组 $a$，使得相邻元素之差的绝对值之和最大。

题解

稍加推导发现：将 $m$ 拆分和单独用 $m$ 结果是一样的，所以可以直接用 $0$ 和 $m$ 构造。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n, m; cin >> n >> m;

    if (n == 1) cout << 0 << "\n";

    else if (n == 2) cout << m << "\n";

    else cout << 2 * m << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

B - Two Arrays And Swaps

题意

有大小为 $n$ 的数组 $a$ 和 $b$，最多可以交换 $a$ 中某一元素和 $b$ 中某一元素 $k$ 次，问数组 $a$ 中元素的最大和为多少。

题解

取 $a$ 中 $n$ 个和 $b$ 中前 $k$ 大个元素中前 $n$ 大个元素即可。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n, k; cin >> n >> k;

    vector<int> a(n);

    for (int i = 0; i < n; i++) {

        cin >> a[i];

    }

    vector<int> b(n);

    for (int i = 0; i < n; i++) {

        cin >> b[i];

    }

    sort(b.rbegin(), b.rend());

    for (int i = 0; i < k; i++) {

        a.push_back(b[i]);

    }

    sort(a.rbegin(), a.rend());

    cout << accumulate(a.begin(), a.begin() + n, 0) << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

C - Board Moves

题意

有一边长为奇数 $n$ 的正方形网格，每一次一个方块可以移到相邻八个位置中的某一个，问所有方块移到一个位置最少需要移动几次。

题解

从中心考虑：中心外第 $i$ 圈的每个方块移到中心需要 $i$ 步。

代码

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

void solve() {

    int n; cin >> n;

    ll ans = 0, a = 3, b = 1;

    for (ll i = 1; i <= (n - 1) / 2; i++) {

        ans += (a * a - b * b) * i;

        a += 2, b += 2;

    }

    cout << ans << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

D - Constructing the Array

题意

有一大小为 $n$ 初始时每个元素均为 $0$ 的数组，第 $i$ 次操作如下：

选取最长最靠左的一段连续为 $0$ 的子区间
如果区间长度为奇数，$a_{\frac{l+r}{2}} = i$
如果区间长度为偶数，$a_{\frac{l+r-1}{2}} = i$

输出进行 $n$ 次操作后的数组。

题解

递归分解区间，按照题意排序赋值即可。

代码

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v;

int cal(int l, int r) {

    return ((r - l + 1) % 2 == 1) ? (l + r) / 2 : (l + r - 1) / 2;

}

void recur(int l, int r) {

    if (l > r) return;

    v.push_back({l, r});

    recur(l, cal(l ,r) - 1);

    recur(cal(l ,r) + 1, r);

}

void solve() {

    v.clear();

    int n; cin >> n;

    recur(1, n);

    sort(v.begin(), v.end(), [&] (pair<int, int> a, pair<int, int> b) {

        if (a.second - a.first != b.second - b.first)

            return a.second - a.first > b.second - b.first;

        else

            return a.first < b.first;

    });

    int a[n + 1] = {};

    for (int i = 0; i < n; i++)

        a[cal(v[i].first ,v[i].second)] = i + 1;

    for (int i = 1; i <= n; i++)

        cout << a[i] << " \n"[i == n];

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

E - K-periodic Garland

题意

将一个 $01$ 串变为相邻两个 $1$ 之间周期为 $k$ 的字符串最少需要改变多少字符。

题解

把原字符串分为 $k$ 个周期子串，每次考虑一个子串时需要将其他子串中的 $1$ 都变为 $0$，然后对当前周期子串进行 $dp$，$dp_i$ 表示周期子串中位置 $i$ 的字符变为 $1$，之前的字符变为合法至少需要改变多少字符。

代码

#include <bits/stdc++.h>

using namespace std;

int cal(const string &s) {

    int n = s.size();

    int all = count(s.begin(), s.end(), '1');

    int dp[n] = {};

    int pref = 0;

    int ans = all;

    for (int i = 0; i < n; i++) {

        int cur = (s[i] == '1');

        pref += cur;

        dp[i] = 1 - cur;

        if (i > 0) dp[i] += min(dp[i - 1], pref - cur);

        ans = min(ans, dp[i] + all - pref);

    }

    return ans;

}

void solve() {

    int n, k; cin >> n >> k;

    string s; cin >> s;

    int tot_one = count(s.begin(), s.end(), '1');

    vector<string> v(k);

    for (int i = 0; i < k; i++)

        for (int j = i; j < n; j += k)

            v[i] += s[j];

    int ans = 1e9;

    for (auto &it : v)

        ans = min(ans, cal(it) + tot_one - count(it.begin(), it.end(), '1'));

    cout << ans << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

F - Decreasing Heights

题意

有一个 $n * m$ 、高度不等的三维坐标系，从 $a_{00}$ 走到 $a_{{(n-1)}{(m-1)}}$，每次只能从 $a_{ij}$ 向 $a_{(i+1)j}$ 或 $a_{i(j+1)}$ 行走，且 $a_{xy} - a_{ij} = 1$，每个位置的高度可以不限次地 $-1$，问最少需要减少多少高度。

题解

如果 $a_{00}$ 是确定的，那么每个点 $a_{ij}$ 的高度应为 $a_{00} + i + j$，因为每移动一格高度都会 $+1$，这与路径无关。

那么，根据状态转移方程：

$dp_{ij} = min(dp_{{(i - 1)}{j}} + dp_{{i}{(j - 1)}}) + a_{ij} - (a_{00} + i + j)$

推导即可。

但是 $a_{00}$ 需要变化的高度是不确定，注意到如果有一条从 $a_{00}$ 到 $a_{{(n-1)}{(m-1)}}$ 的最优路径，那么这条路径上一定有点的高度不需要减少，因为如果都需要减少，那么可以增加 $a_{00}$ 的高度来抵消共同减少的部分，如果增加后的高度高于 $a_{00}$，呢么 $a_{00}$ 不需要减少，这条路径上的的高度都需要减少，即仍有点的高度不需要减少。

至此，可以枚举高度不变化的点反推出 $a_{00}$ 的高度，由此得解。

代码

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

const ll INF = 1e18;

void solve() {

    int n, m; cin >> n >> m;

    ll a[n][m] = {};

    for (int i = 0; i < n; i++)

        for(int j = 0; j < m; j++)

            cin >> a[i][j];

    ll ans = INF;

    for (int x = 0; x < n; x++) {

        for(int y = 0; y < m; y++) {

            ll a_00 = a[x][y] - x - y;

            if (a_00 > a[0][0]) continue;

            ll dp[n][m] = {};

            fill(*dp, *dp + n * m, INF);

            dp[0][0] = a[0][0] - a_00;

            for (int i = 0; i < n; i++) {

                for (int j = 0; j < m; j++) {

                    ll a_ij = a_00 + i + j;

                    if (a_ij > a[i][j]) continue;

                    if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i][j] - a_ij);

                    if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i][j] - a_ij);

                }

            }

            ans = min(ans, dp[n - 1][m - 1]);

        }

    }

    cout << ans << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

巴特西

Codeforces Round #642 (Div. 3)