蚂蚁暑期实习笔试

一共三道题，一道字符串，一道二分+前缀和，一道组合计数。

• 定义：
• 圆圈字符: 26个小写字母中里面有圈的字母。（a, b, d, e, g, o, p, q）
• 一个字符串中圆圈字符的个数大于非圆圈字符的个数，那么该字符串为圆圈字符串
• 问题：
• 输入一个字符串，将字符串拆分为多个字串，求拆分后圆圈字符串最多有几个。

Input:

abc

Output:

2

Code:

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt = 0;
    string ot = "abdegopq";
    for (int i = 0; i < s.size(); i++) {
        if (ot.find(s[i]) != string::npos) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

• 问题：输入和，给一个长度为的整数数组，以及个操作。
• 操作1，输入一个1以及一个整数，对所有的进行赋值操作：
• 操作2，输入一个2，输出数组中所有元素的和。
• 输入包含组。
• 

Input:

1
5 3
1 3 5 4 2
2
1 2
2

Output:

15
9

Code:

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

#define LL long long

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

int main() {
    int T;
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d%d", &n, &q);
        for (int i = 1; i <= n; i ++) {
            scanf("%d", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        sort(a + 1, a + n + 1);
        LL ans = s[n];
        int R = n;
        while (q --) {
            int op;
            scanf("%d", &op);
            if (op == 2) printf("%lld\n", ans); 
            else {
                int v;
                scanf("%d", &v);
                int l = 1, r = R, f = -1;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (a[mid] >= v) {
                        f = mid;
                        r = mid - 1;
                    }
                    else l = mid + 1;
                }
                if (f == -1) continue;
                else {
                    R = f;
                    a[f] = v;
                    ans = s[f - 1] + (LL) a[f] * (n - f + 1); 
                }
            }
        }
    }
    return 0;
}

• 定义：一个整数，例如，那么对每一位进行排列组合可以得到，但这个数本身不应该被包含在内。因此最终的集合为。
• 问题：这个集合中，数位上所有数字的和为素数的元素个数。
• 输入个整数，每个整数
• 不考虑前导0

Input:

4
100
123
101
236

Output:

0
0
2
5

Code:

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while (T -- ) {
        char x[12];
        scanf("%s", x + 1);
        int sum = 0, n = strlen(x + 1), cnt[12] = {0};
        for (int i = 1; i <= n; i ++ ) {
            int t = x[i] - '0';
            sum += t;
            cnt[t] ++;
        }
        bool f = true;
        for (int i = 2; i * i <= sum; ++ i) {
            if (sum % i == 0) {
                f = false; break;
            }
        }
        if (sum == 1) f = false;
        if (!f) {
            puts("0"); continue;
        }

        auto A = [&](int x) -> int {
            int res = 1;
            for (int i = 2; i <= x; ++i) res *= i;
            return res;
        };

        int ans = A(n);
        for (int i = 0; i <= 9; ++ i) {
            ans /= A(cnt[i]);
        }
        printf("%d\n", --ans);
    }
    return 0;
}