[数据结构与算法]Educational Codeforces Round 111 (Rated for Div. 2) 题解（A、B、C）

Educational Codeforces Round 111 (Rated for Div. 2)

题目链接-https://codeforces.com/contest/1550

A-Find The Array

题意：某种性质：对于长度为n的数组中任意元素a${}_i$，满足a${}_i$ = 1,或者a${}_i$ - 1 = a${}_j$ 或者 a${}_i$ - 2 = a${}_j$（1 <= i, j <= n）。给你一个s，求出和为s的满足该性质的n最小的数组，输出n。

题解：要使数组越短，则应使数组元素越大，由题意我们很容易发现数组最小项为1（不为1则最小项不会满足该性质），那后面每一项的最大值应该是前一项加2，即 a${}_i$ = a${}_{i?1}$ + 2，算出前缀和，查找出大于等于s的下标即可。

int a[110];
int32_t main()
{
    ICO; //关闭同步
    int t, n, p = 1;
    for(int i = 1; i <= 100; i++) {a[i] = a[i - 1] + p; p += 2;}
    cin >> t;
    while(t--)
    {
        cin >> n;
        int res = lower_bound(a + 1, a + 101, n) - a;
        cout << res << endl;
    }
    return 0;
}

B-Maximum Cost Deletion

题意：你有一个只含0和1的字符串s，现在你可以消除s中的元素，但是你每次只能消除相连的并且相同的元素，消除元素后，剩下的字符串会自动连接在一起，假设你每次消除的字符串长度为L，你每次消除会得到a * L + b，现在问你把s完全消除最后你得到的值最大为多少。

题解：无论怎样消除 最终的值为 a * n + b * x （n为s的长度，x为你消除的次数），所以我们只需要求出x即可，由于x * b是线性的，所以我们只需要找出x的最小值和最大值即可，很明显x最大为n，我们将连续且相同的字符看成一块，我们只需要先消除min（0的块数，1的块数）次，然后再消除一次即可，即cnt / 2 + 1，cnt为s可以分成多少块，计算出最大值即可。

char s[1000];
int32_t main()
{
    ICO;
    int t, n, a, b;
    cin >> t;
    while(t--)
    {
        cin >> n >> a >> b >> s + 1;
        int cnt = 1;
        for(int i = 1; i < n; i++) if(s[i] != s[i + 1]) cnt++;
        cnt = (cnt >> 1) + 1;
        int res = a * n;
        res += max(n * b, cnt * b);
        cout << res << endl;
    }
    return 0;
}

C-Manhattan Subarrays

题意：我们设两个点p，r的哈曼顿距离为d(p, r)。某种性质：三个点p, r, q的哈曼顿距离满足d(p, r) != d(p, q) + d(q, r) .
数组元素a${}_i$和其下标i构成一个点（a${}_i$, i），若一个数组中任意三个点都满足该性质，则我们称这个数组是好的。现给你一个数组，问该数组有多少子数组是好的。

题解：由该性质的哈曼顿距离的实际意义（中间点在两边点所构成的矩形内）我们可以发现，长度 > 4的数组都不满足，因为次大值a${}_i$和次小值a${}_j$之间肯定有一个值a${}_k$，所以我们只需要找出长度为3和长度为4的子数组， 判断中间点的值是否在两边点的值构成的区间内即可。

const int N = 2e5 + 7;
int a[N];
bool ok[N];
int32_t main()
{
    ICO;
    int t, n, b;
    cin >> t;
    while(t--)
    {
        cin >> n;
        memset(ok, 0, n + 5); //归零
        for(int i = 1; i <= n; i++) cin >> a[i];
        int res = n + n - 1;
        for(int i = 1; i <= n - 2; i++) //长度为3的子串
            if(a[i + 1] > max(a[i], a[i + 2]) || a[i + 1] < min(a[i], a[i + 2])) {ok[i] = 1; res++;}//ok数组标记该下标长度为3的子数组是好的
        for(int i = 1; i <= n - 3; i++) //长度为4的子串
        {
            if(a[i + 1] >= min(a[i], a[i + 3]) && a[i + 1] <= max(a[i], a[i + 3])) continue;
            if(a[i + 2] >= min(a[i], a[i + 3]) && a[i + 2] <= max(a[i], a[i + 3])) continue;
            if(ok[i] && ok[i + 1]) res++;
        }
        cout << res << endl;
    }
    return 0;
}