A.Most Unstable Array

题意：

要求构造长度为 $n$ 的非负数组使得和为 $m$ 且 $\sum\limits_{i=1}^{n-1} |a_i - a_{i+1}|$ 最大并输出其最大值

题解：

构造 $0,m,0,0,0,0\ldots$ 即可。特判 $n=1,2$ 的情况

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    if (n >= 3)
        printf("%d\n", 2 * m);
    else
        printf("%d\n", m * (n - 1));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Two Arrays And Swaps

题意：

给定长度为 $n$ 的两个序列 $a_n$ 和 $b_n$ ，至多 $k$ 次机会可以互换数组 $a,b$ 的任何一个数。求 $\sum_{i=1}^{n}{a_i}$ 的最大值。

题解：

将 $a$ 从小开始和 $b$ 大的开始换，直到 $a$ 全部比 $b$ 大或者 $k$ 次结束。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[35], b[35];
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &b[i]);
    sort(a, a + n);
    sort(b, b + n, greater<int>());
    for (int i = 0; i < k; i++)
    {
        if (a[i] >= b[i])
            break;
        swap(a[i], b[i]);
    }
    printf("%d\n", accumulate(a, a + n, 0));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Board Moves

题意：

对 $n×n$ 的方格依次标号（ $n$ 是奇数）。每次操作可以将一个方格中的一个数移动到与其相邻的方格（包括斜对角）。求最少几次操作使得某个方格含有全部数字。

题解：

全移到中间。每一圈距离中心的距离相等。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[35], b[35];
void solve()
{
    int n;
    scanf("%d", &n);
    ll ans = 0;
    for (int i = 1; i <= n / 2; i++)
        ans += 8ll * i * i;
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Constructing the Array

题意：

给定初始全 $0$ 数组。现在对于每次操作，要求找到最长的全 $0$ 子串（相等长度选左边那个）。将其中间（偶数偏左）的数赋值为当前操作的次数。

题解：

模拟即可，用优先队列维护

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int ans[maxn];
struct Node
{
    int l, r;
    bool operator<(const Node &b) const
    {
        return b.r - b.l != r - l ? l - r > b.l - b.r : l > b.l;
    }
    Node(int l0, int r0) : l(l0), r(r0){};
};
priority_queue<Node> q;
void solve()
{
    memset(ans, 0, sizeof ans);
    int n;
    scanf("%d", &n);
    q.push(Node{1, n});
    int cnt = 0;
    while (!q.empty())
    {
        Node tmp = q.top();
        q.pop();
        int mid = (tmp.l + tmp.r) / 2;
        ans[mid] = ++cnt;
        if (tmp.l < mid)
            q.push(Node(tmp.l, mid - 1));
        if (tmp.r > mid)
            q.push(Node(mid + 1, tmp.r));
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.K-periodic Garland

题意：

给定 $01$ 串，每次操作可以使 $0$ 变为 $1$ 或者 $1$ 变成 $0$ 。求最少几次操作使得所有的相邻 $1$ 的间隔为 $k$ 。

题解：

首先我们计算出原串中的 $1$ 的个数为 $cnt$ 。然后枚举 $mod\ k$ 意义下的每一位为 $1$ 的情况所需个数。注意如果一开始或某个位置需要从 $0$ 变为 $1$ 的次数大于之前原本是 $1$ 的个数，我们可以认为前面的序列全 $0$ 。这样次数更小一些。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, k;
    scanf("%d%d",&n,&k);
    string s;
    cin >> s;
    ll cnt = count(s.begin(), s.end(), '1');
    ll ans = 1e18;
    for (int mod = 0; mod < k; mod++)
    {
        ll delta = 0;
        for (int i = mod; i < n; i += k)
        {
            if (s[i] == '0')
                delta++;
            else
                delta--;
            delta = min(delta, 0ll);
            ans = min(ans, cnt + delta);
        }
    }
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

F.Decreasing Heights

题意：

给定一个 $n×m$ 的地图，每个位置都有一个值，每次只能向下或者向右走，且对应的方格的值必须为当前方格的值加 $1$ .现在每次操作可以使得一个方格的值减 $1$ 。问最少几次操作可以使得从 $(1,1)$ 走到 $(n,n)$ 。

题解：

因为数据量不大可以直接枚举最优路径是否经过该点，通过枚举每一个位置的现有值，我们可以确定当前地图所有合法路径应该存在的值。再dp一下就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n, m;
ll a[110][110], dp[110][110];
ll calc(ll st)
{
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = 1e18;
    if (a[1][1] >= st)
        dp[1][1] = a[1][1] - st;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if ((i == 1) && (j == 1))
                continue;
            if (a[i][j] >= (st + i + j - 2))
            {
                ll now = a[i][j] - (st + i + j - 2);
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + now;
            }
        }
    }
    return dp[n][m];
}
void solve()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%lld", &a[i][j]);
    ll ans = 1e18;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = min(calc(a[i][j] - (i + j - 2)), ans);
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

Codeforces Round #642 (Div. 3)