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笔面经#
