饿了么暑期实习笔试（貌似每个人不一样）

三道题，一道字符串，一道思维，一道二分+前缀和

1. 输入一个字符串，将其大写字母转为小写，小写字母转为大写。然后计算下标为奇数的ASCII码的和。

Input:

abcABC

Output:

492

Code:

#include <bits/stdc++.h>

using namespace std;
int main() {
    string s;
    cin >> s;
    int ans = 0;
    for (char c : s) {
        if (c >= 'a' && c <= 'z') ans += c - 'a' + 'A';
        else if (c >= 'A' && c <= 'Z') ans += c - 'A' + 'a';
        else ans += c;
    }
    cout << ans << endl;
    return 0;
}

2. 给一颗树，树上的每个节点值为的整数。定义一个树的路径值，如： 等于 其中表示节点， 表示该节点的值。如果路径值包含前导0，则该路径不算。

• 输入，， 个对表示这棵树。
• 输出该树上所有路径值中是偶数的个数。

Input:

3
0 1 2
1 2
1 3

Output:

5

Code:

#include <bits/stdc++.h>

using namespace std;

#define LL long long

int main() {
    LL x = 0, y = 0, z = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int a;
        scanf("%d", &a);
        if (!a) ++z;
        if (a&1) ++y;
        else ++x;
    }
    while (--n) {
        int u, v; scanf("%d%d", &n, &v); 
    }
    printf("%lld\n", x * y + (x - z) * x + z);
    return 0;
}

3. 给一个数组，小红先选择一个区间，染成红色，小蓝后选择一个区间染成蓝色。并且这两个区间不能相交。小红想让红色区间的和大于等于蓝色区间的和。

• 输入，
• 输出小红可以选择的区间个数。

Input:

3
1 2 3

Output:

4

Code:

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 2e5 + 10;

int n, a[N];
LL s[N];

LL get(int l, int r) {
    if (l > r) return 0;
    return s[r] - s[l - 1];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = n, f = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int L = get(1, i-1), M = get(i, mid), R = get(mid+1, n);
            if (M >= max(L, R)) {
                f = mid; r = mid - 1;
            } else l = mid + 1;
        }
        if (f!=-1) ans += n - f + 1;
    }
    printf("%lld\n", ans);
    return 0;
}