2023.4.11 蚂蚁后端笔试

蚂蚁C++后端暑期实习4.11 笔试题：

1. 签到题：给一个数组，找有多少个出现数量是素数的素数。

2. 给一个n*m的网格（n，m <= 1e9），在每一个点你可以往左上，左下，右上，右下走，当遇到四个顶点时会原路反弹，在遇到不是顶点的边界时90度反弹，类似一个反射面，给定初始位置和出发方向，问走多少步回到起点。

Sample Input 1
5 7 1 7 DL
Sample Output 1
24

Sample Input 2
3 3 1 2 DR
Sample Output 2
4

3. 给一个01串，长度2e5，现在需要构造一个等长度的小写字母的字符串，要求所有相同字母对应位置的01串的数都同为0或同为1，比如01串为010，字符串可以是aba，abc，但不能是aaa，因为a对应了0和1。让你构造一个这样的字符串，使得最多数量的字母最少。

Sample Input
01010101010101010101010101
Sample Output
anbocpdqerfsgthuivjwkxlymz

题解：

1. 签到

2. 把边界当成镜子，然后遇到边界不会反射，而是继续直走，相当于把原来的矩形翻转180度，这样当走到经过一系列翻转后的起点就相当于回到起点，构造二元一次方程使用扩展欧几里得算法求解即可。由于答案可以超过int范围，暴力很容易超时。

#include <bits/stdc++.h>
using namespace std;

int n, m, x, y, start_x, start_y;
char s[3];

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y = y - a / b * x;
    return d;
}

//求解方程ax + by = c的最小正整数解
int solve(int a, int b, int c) {
    int gcd = exgcd(a, b, x, y); 
    if(c % gcd != 0) return -1;
    x = x * (c / gcd);
    x = x % (abs(b / gcd));
    if(x <= 0) x = x + abs(b / gcd);
    return x;
}

int main() {
    scanf("%d %d %d %d %s", &n, &m, &start_x, &start_y, s);

    //通过把图翻转将不同方向统一到DR方向处理
    if(s[0] == 'U' && s[1] == 'R') {
        start_x = n - start_x + 1;
    }else if(s[0] == 'U' && s[1] == 'L') {
        start_x = n - start_x + 1;
        start_y = m - start_y + 1;
    }else if(s[0] == 'D' && s[1] == 'L') {
        start_y = m - start_y + 1;
    }
    long long ans = 2e18;
    //printf("%d %d\n", start_x, start_y);

    //四种类型的点进行分别处理
    int a = 2 * (n - 1), b = -2 * (m - 1), c = 0;
    int p = solve(a, b, c);
    if(p != -1) ans = min(ans, 2LL * p * (n - 1));

    a = 2 * (n - 1), b = -2 * (m - 1), c = -2 * start_y + 2;
    p = solve(a, b, c);
    if(p != -1) ans = min(ans, 2LL * p * (n - 1));

    a = 2 * (n - 1), b = -2 * (m - 1), c = 2 * start_x - 2;
    p = solve(a, b, c);
    if(p != -1) ans = min(ans, 2LL * p * (n - 1) - 2LL * start_x + 2);

    a = 2 * (n - 1), b = -2 * (m - 1), c = 2 * start_x - 2 * start_y;
    p = solve(a, b, c);
    if(p != -1) ans = min(ans, 2LL * p * (n - 1) - 2 * start_x + 2);

    printf("%lld\n", ans == 2e18 ? -1 : ans);
}

3. 可以从小到大枚举这个最高的高度，对字母a - z依次填充，尽量按照枚举的高度填，并且使得0的字母的数量总和为01串的0的数量，1的为1的，如果可以，那更大的高度也一定可以，所以符合二分法，但没有必要，直接暴力搜就完事了。

#include <bits/stdc++.h>
using namespace std;

char s[200005];
int cnt01[2] = {0}, alpha[26], mark[26];
queue<char> avail[2];

int main() {
    scanf("%s", s);
    int n = strlen(s), ans = 1e9;
    for(int i = 0; i < n; i++) cnt01[(int)(s[i] - '0')]++;
    for(int max_height = 1; max_height <= n; max_height++) {
        int sum0 = 0, sum1 = 0;
        for(int i = 0; i < 26; i++) {
            if(sum0 < cnt01[0]) {
                mark[i] = 0;
                alpha[i] = min(cnt01[0] - sum0, max_height);
                sum0 += min(cnt01[0] - sum0, max_height);
            }else{
                mark[i] = 1;
                alpha[i] = min(cnt01[1] - sum1, max_height);
                sum1 += min(cnt01[1] - sum1, max_height);
            }
        }
        if(sum0 == cnt01[0] && sum1 == cnt01[1]) break;
    } 
    for(int i = 0; i < 26; i++) {
        for(int j = 0; j < alpha[i]; j++) {
            avail[mark[i]].push((char)('a' + i));
        }
    }
    for(int i = 0; i < n; i++) {
        printf("%c", avail[(int)(s[i] - '0')].front());
        avail[(int)(s[i] - '0')].pop();
    }
    printf("\n");
}

#软件开发2023笔面经#