10.18 携程笔试编程题1、2、4题解
1. 给你一个整数x和k，让你反转x的前k位。
a, k = input().split() k = int(k) print(int(a[k-1::-1]+a[k:]))
2. 给你一个长度小于等于10的字符串，求合法字符串的个数。
合法字符串：串中所有相邻两个字符都不相同
#include <bits/stdc++.h>
using namespace std;
int main() {
string s; cin >> s;
const int n = s.length();
sort(s.begin(), s.end());
int cnt = 0;
do {
bool ok = true;
for (int i = 1; i < n; i++) {
if (s[i] == s[i-1]) {
ok = false;
break;
}
}
cnt += ok;
} while (next_permutation(s.begin(), s.end()));
cout << cnt << endl;
return 0;
} 3. 题目大致意思是给定4个数，a，b，low，high。
每次操作你可以给a加上x，其中low<=x<=high。
求最终使a=b的最小和最大操作数。
无解输出-1.
条件：0 <= a <= b <= 1e9
1 <= low <= high <= 1e9
这题不会。有会的大佬麻烦给个思路，谢谢。
4. 给你一个数组和一个数x，从数组中任取两个数，求满足这两个数的乘积末尾至少有x个0的方案数。
思路：
对于两个数a和b，如果它们的因子10、2、5的个数分别为x1, x2, x3，y1,y2,y3，那么它们的乘积末尾总共有x1+y1+min(x2, y3)+min(x3, y2)。可以记录下数组中含有不同10、2、5因子个数各有多少个，剩下的就是组合问题了。
假如有x个a和y个b，而a*b一共能产生target个0。如果a和b相等，则x和y也相等，这种情况就相当于x个相同数中取2个，一共有Cn2=n*(n-1)/2种方案；如果a和b不相等，则一共有x*y/2种方案。
因为2**31>1e9，5**14>1e9，所以最大计算量应该为(31*14*10)**2，大概在8个数量级的样子。数组大小1e5，双重循环暴力判断运算量就是10个数量级了。
补充：
再想了一下，这里可以只考虑因子2和5，可以再减两个数量级，这里就不实现了。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
cin >> n >> x;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
int cnt[11][32][15]{0};
for (int i = 0; i < n; i++) {
int val = v[i];
int f_10 = 0, f_2 = 0, f_5 = 0;
while (val%10 == 0) {
val /= 10;
f_10 ++;
}
while (val%2 == 0) {
val /= 2;
f_2 ++;
}
while (val%5 == 0) {
val /= 5;
f_5 ++;
}
cnt[f_10][f_2][f_5] ++;
}
long long nums[19]{0};
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 32; j++) {
for (int k = 0; k < 15; k++) {
for (int ii = 0; ii < 11; ii++) {
for (int jj = 0; jj < 32; jj++) {
for (int kk = 0; kk < 15; kk++) {
int cnt_0 = i+ii+min(j, kk)+min(jj, k);
nums[cnt_0] += i==ii&&j==jj&&k==kk ? 1LL*cnt[i][j][k]*(cnt[i][j][k]-1) : 1LL*cnt[i][j][k]*cnt[ii][jj][kk];
}
}
}
}
}
}
long long ans = 0;
for (int i = x; i < 19; i++) {
ans += nums[i]/2;
}
cout << ans << endl;
return 0;
} 
查看9道真题和解析
投递中国石油等公司10个岗位 >