CF#821 Div2

A Consecutive Sum

题目：

​ 选择\(i\)和\(j\)，如果\(j = i+xk(x=R)\)，可以交换\(i,j\)。任意选择一段长度为k的相加。

思路：

​ 题目等价于在下标\(mod\) k 相同的数中选一个最大的。简单模拟。可以用vis标记或者优先队列。

实现：

​ 不值一提。

void solve()
{
    cin >> n >> k;
    priority_queue<int> q[105];

    for(int i = 0; i < n; i ++)
    {
        int x; cin >> x;
        q[(i + 1) % k].push(x);
    }
    ll res = 0;
    for(int i = 0; i < k; i ++)
        res += q[i].top();
    cout << res << '\n';
}

B Rule of League（分类讨论）

题目：

​ 有n个人，他们之间会进行n-1场比赛。将人分成两部分，一部分人赢了\(x\)把，另一部分人赢了\(y\)把。请问是否存在这样的情况，如果有，请输出每一局的胜者。否则输出-1。

思路：

​ 可以想到，\(x\)和\(y\)必须有一个是0，且不能都为0。因为如果一个人要赢，一定有一个人会直接输掉（也就是这个直接输的人赢0把）。

实现：

​ 判断合法的情况很简单。不过想要输出每一局的胜者需要稍作思考。

void solve()
{
    cin >> n >> x >> y;
    if(min(x, y) > 0 || max(x, y) == 0) {cout << "-1\n"; return;}
    if(x == 0)  swap(x, y);
    if((n - 1) % x != 0)    {cout << "-1\n"; return;}
    for(int i = 1; i <= (n - 1) / x; i ++)
        for(int j = 1; j <= x; j ++)
            cout << 2 + (i - 1) * x << ' ';
    cout << '\n';
}

C Parity Shuffle Sorting（构造）

题目：

​ 给出一个长度为n的序列。请你在n次操作内将其变为单调不降序列。

​ 操作：选择\(l\)和\(r\)，如果\(a_l+a_r\)是偶数，那么\(a_l=a_r\)，反之，\(a_r=a_l\)。

思路：

​ 对于这类限制操作次数且不要求最少操作次数的问题。我们尽量将思路靠向用完n次操作正好解决问题。每次操作，可以改变一个数，那么我们就能想到把整个序列变成一个数。

​ 我们先把头和尾变成同一个数，不管原来的是哪个都行。然后对于中间的数，根据其加和的奇偶性选择左端点或右端点。

实现：

​ 没什么值得注意的，根据思路模拟即可。

void solve()
{
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    if(is_sorted(all(a)))   {cout << "0\n"; return;}

    cout << n - 1 << "\n";
    cout << 1 << ' ' << n << '\n';
    int g = ((a[1] + a[n]) & 1 ? a[1] : a[n]);
    for(int i = 2; i <= n - 1; i ++)
    {
        if((g + a[i]) & 1)
            cout << 1 << ' ' << i << '\n';
        else
            cout << i << ' ' << n << '\n';
    }
}

D Zero-One（D1贪心，D2记忆化搜索）

题目：

​ 给出\(n,x,y\)和两个长度为n的01串。你可以任选两个\(l,r(l<r)\)，可以取反\(a_l,a_r\)。在不同的情况下，操作的花费是不同的。1. 当\(l+1=r\)的时候，花费为x。 2.其余情况，花费为y。请问将a变成b的最小花费是多少。

思路：

​ 首先我们要想到x和y的操作是可以互换的。比如说，两次y操作可以等价一次x操作。\(a_r-a_l\)次x操作可以等价一次y操作。同时设需要改变的位置有m个。

​ D1的问题是当\(x>=y\)的时候，求解问题。由于我们知道\(x>=y\)，通过贪心的策略我们可以想到我们要尽量地选择操作y。通过手推样例可以发现，除了存在有两个位置不同且这是两个相邻的位置的时候，我们的花费是\(min(x, 2 * y)\)，其他的情况下花费都是m / 2 * y。

​ D2的问题是解除对\(x,y\)间关系的限制。当\(x>=y\)的情况的时候，我们已经在D1求解过了。那么接下来，我们只需要解决\(x<y\)的情况就可以了。发现\(n\)是5000，可以用\(n^2\)的DP算法求解。设状态为\(f[i][j]\)，表示在需要改变的位置的序列中，\([l,r]\)的问题还没有解决时，当前的最小花费。直接递推的话，状态不是很好转移，于是选择记忆化搜索来实现这个DP。

实现：

​ 谨防爆int以及初始化。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 5005;
char s1[N], s2[N];
int n;
ll x, y;
ll f[N][N];
vector<int> a;

void init()
{   
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= n; j ++)
            f[i][j] = 2e18;
}

ll dfs(int l, int r)
{
    if(l > r)   return 0;
    if(f[l][r] != 2e18)    return f[l][r];
    ll &v = f[l][r];
    if(a[l] + 1 == a[r])
        v = min(v, dfs(l + 1, r - 1) + x);
    else
        v = min(v, dfs(l + 1, r - 1) + y);
    v = min(v, dfs(l, r - 2) + min(y, 1ll * (a[r] - a[r - 1]) * x));
    v = min(v, dfs(l + 2, r) + min(y, 1ll * (a[l + 1] - a[l]) * x));
    return v;
}

void solve()
{
    a.clear();
    cin >> n >> x >> y;
    cin >> s1 >> s2;
    
    for(int i = 0; i < n; i ++)
    {
        if(s1[i] != s2[i])
            a.push_back(i);
    }

    int m = (int)a.size();
    if(m == 0)  {cout << "0\n"; return;}
    if(m & 1)   {cout << "-1\n"; return;}

    if(x >= y) //贪心，我们可以全部选择y，除了只有两个相邻位置需要改变的情况。
    {
        if(m == 2 && a[0] + 1 == a[1])
            cout << min(x, 2 * y) << '\n';
        else
            cout << m / 2 * y << '\n';
    }
    else //DP
    {
        init();
        cout << dfs(0, m - 1) << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int _;
    cin >> _;
    while(_--)
        solve();
}