Educational Codeforces Round 111 (Rated for Div. 2)

https://codeforces.com/contest/1550

A. Find The Array

第十五分钟完成

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <math.h>
    #include <set>

    using namespace std;

    typedef long long LL;
    const int N = 130;

    int t, s; 

    int main(){
        cin >> t;
        while(t--){
            cin >> s;
            if(s == 1){
                printf("%d\n", 1);
                continue;
            }
            int i = 1;
            s -= 1;
            int res = 1;
            while(s > 0){
                res++;
                i += 2;
                s -= i;
            }
            printf("%d\n", res);
        }
        return 0;
    }

B. Maximum Cost Deletion

有两次WA，因为没考虑到细节
第73分分钟完成

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <math.h>

    using namespace std;

    int t, n, a, b; 
    string s;

    //计算s最少可以被抽成几段 
    int get_min(){
        int res = 1;
        char tmp = s[0];
        for(int i = 1; i < n; i++){
            if(tmp == s[i]) continue;
            res++;
            tmp = s[i];
        }
        return res / 2 + 1;
    }

    int main(){
        cin >> t;
        while(t--){
            cin >> n >> a >> b;
            cin >> s;
            int res = 0;
            int d = get_min();
            if(b >= 0){
                res = (a + b) * n;
            }else{
                res = a * n + b * d;
            }
            printf("%d\n", res);
        }
        return 0;
    }

C. Manhattan Subarrays

只想到了暴力解法，第112分钟完成，在test3超时。

    #include <iostream>
    #include <cstdio>
    #include <algorithm>

    using namespace std;

    typedef long long LL;
    const int N = 2e5 + 10;

    int t, n; 
    int a[N];

    int get_d(int xp, int yp, int xq, int yq){
        return abs(xp - xq) + abs(yp - yq);
    }

    bool is_badtriple(int bi, int i, int bj, int j, int bk, int k){
        int x = get_d(bi, i, bj, j);
        int y = get_d(bk, k, bj, j);
        int z = get_d(bi, i, bk, k);
        if(x == y + z || y == x + z || z == x + y) return true;
        else return false;
    }

    bool is_goodsubarray(int l, int r){
        for(int i = l; i <= r - 2; i++){
            for(int j = i + 1; j <= r - 1; j++){
                for(int k = j + 1; k <= r; k++){
                    if(is_badtriple(a[i], i, a[j], j, a[k], k))
                        return false;
                }
            }
        }
        return true;
    }

    int main(){
        cin >> t;
        while(t--){
            cin >> n;
            for(int i = 0; i < n; i++){
                cin >> a[i]; 
            }
            if(n == 1 || n == 2) {
                printf("%d\n", n * (n + 1) / 2);
                continue;
            }
            LL res = n + n - 1;  //长度为1和2的子序列数量 

            for(int i = 0; i < n - 2; i++){
                for(int j = 2; j < n; j++){
                    if(is_goodsubarray(i, i + j)) res += 1;
                }
            }

            printf("%d\n", res);
        }
        return 0;
    }