#848 div2

A:

题目：

现在存在一个字符串，只存在 -1， 1 两种数字。 现在必须进行一次操作：

选择 i， 反转 i 和 i + 1 位置上的数字。

问你操作一次后数组的和最大是多少。

思路：

必须操作一次：

分类讨论：优先 -1 -1 反转。

如果不行就 -1 1。

否则只剩下 1, 1 必须反转了

代码

void solved()
{
    cin >> n;
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }

    for(int i = 0; i < n - 1; i++)
    {
        if(a[i] + a[i + 1] == -2)
        {
            cout << sum + 4 << endl;
            return;
        }
    }

    for(int i = 0; i < n - 1; i++)
    {
        if(a[i] + a[i + 1] == 0)
        {
            cout << sum << endl;
            return;
        }
    }

    cout << sum - 4 <<endl;
}

B：

题目:

现在存在一个排列 p 和一个数组 a，数组 a 内的数字只出现一次。

存在pos 函数 pos（a[i]）表示 ai 在排列 p 中的下标是多少。

如果说数组a中所有下标都满足那个式子，那么他是个 not good， 否则只要有一个不是就可以。

操作： 选择 p 中相邻两个数交换

思路：

只需要满足一对不符合即可，所以枚举每一对，分别考虑是逆序，或者两个数字在 p 中下标差距为 d。

代码

void solved()
{
    map<int, int> pos;
    cin >> n >> m >> d;

    for(int i = 1; i <= n; i++)
    {
        cin >> p[i];
        pos[p[i]] = i;

    }

    for(int i = 1; i <= m; i++) cin >> a[i];

    int ans = 1e9;

    for(int i = 1; i < m; i++)
    {
        int x = a[i], y = a[i + 1];

        if(pos[x] > pos[y] || (pos[x] + d < pos[y]))
        {
            cout << 0 << endl;
            return;
        }

        ans = min(ans, pos[y] - pos[x]);


        if(d <= n - 2)
        {
            ans = min(ans, pos[x] + d + 1 - pos[y]);
        }
    }

    cout << ans << endl;
}

C：

题目：

现在存在两个字符串 a 和 b。和一个数字 k， k 表示可以替换 a 中字符的种类。

尽可能的使得 a 和 b 的相同子串数量最大。

思路：

子串数量最大，尽可能的去让连续最大。因为题目特别标注 a 中不同字符的个数只有10个。

所以不妨通过枚举字符来求得最大值。如果对应位置已经相同，那么不需要替换。

统计需要替换的字符，然后二进制枚举每一位，表示替换或者不替换。

遍历一遍，对于当前字符 i，如果与 bi 相同，并且连续，那么对子串贡献为 len + 1

否则如果可以替换为相同，那么同上，否则维护的连续长度为 0

代码

int pd(int x)
{
    if(x == 0) return 0;
    int cnt = 0;
    for(int i = 0; i <= 10; i++) if(x >> i & 1) cnt++;
    return cnt;
}


void solved()
{
    cnt = 0;

    map<char,int>hs;
    string a, b;
    cin >> n >>m;
    cin >> a >> b;


    for(int i = 0; i < a.size(); i++)
    {
        if(a[i] != b[i])
        {
            if(!hs[a[i]])hs[a[i]] = cnt++;
        }
    }

    int res = 0;

    for(int i = 0; i < 1 << cnt; i++)
    {
        if(pd(i) > m) continue;

        int k = 0;
        int len = 0;
        int ans = 0;
        for(int j = 0; j < a.size(); j++)
        {
            if(a[j] == b[j] || (a[j] != b[j] && ((i >> hs[a[j]]) & 1)))
            {
                len++;
                ans += (len);
            }else
            {
                len = 0;
            }

        }

        res = max(res, ans);
    }

    cout << res << endl;
}