阿里笔试(0314算法岗)
时长:90分钟
总共6道单选+6道多选+3道编程
第一题:
比较简单，数据范围是1000，那么直接二层for循环模拟即可
#阿里笔试##阿里巴巴##笔经##include<stdio.h>
int main()
{
int a, b, c, d, m;
scanf("%d %d %d %d %d", &a, &b, &c, &d, &m);
int ans = 0, x, y;
for (x = a; x <= b; x++)
for (y = c; y <= d; y++)
if (ans < (x * y) % m)
ans = (x * y) % m;
printf("%d\n", ans);
return 0;
}
交换字符
这个题目出的很好，很多边界条件，组合数学
当交换2个相同的字符时，不会产生不同的字符串，因此我们可以用"所有交换的方案数" - "s 维持不变方案数"来得到答案
还要注意特判存在2个字母相同的情况，可以得到原串
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
string s; cin >> s;
ll n = s.size();
map<char, ll> M; for (auto ch: s) M[ch]++;
ll tot = n*(n-1)/2;
for (auto [k,v]: M) tot -= v*(v-1)/2;
//存在2个相同的字母
for (auto [k,v]: M) if (v >= 2) {
tot++;
break;
}
cout << tot << endl;
}
第三题：切割
第三题很难很难，最后才做出来：
做 2 次 dp
第一次 dp，求每个数模 k 等于 x，最少需要切割多少次 ；O(400x400x18)x 400` 个数
第二次 dp，用第一次dp 的结果，求前 i 个数模 k 等于 x，最少需要切割多少次，复杂度 O(400*400*400)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> gao(ll n, int k) {
string s = to_string(n);
vector<vector<int>> dp(s.size()+1, vector<int>(k, 0x3f3f3f3f));
dp[0][0] = 0;
for (int i = 0; i < s.size(); i++) {
int cur = 0;
for (int j = i; j < s.size(); j++) {
cur = (cur * 10 + s[j]-'0')%k;
for (int x = 0; x < k; x++) {
dp[j+1][(cur+x)%k] = min(dp[j+1][(cur+x)%k] , dp[i][x]+(i!=0));
}
}
}
return dp.back();
}
int main() {
int n, k; cin >> n >> k;
vector<ll> A(n); for (auto &x: A) cin >> x;
vector<int> cur(k, 0x3f3f3f3f);
cur[0] = 0;
for (auto &t: A) {
vector<int> nxt(k, 0x3f3f3f3f);
vector<int> tmp = gao(t, k);
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) nxt[(i+j)%k] = min(nxt[(i+j)%k], cur[i]+tmp[j]);
}
cur = nxt;
}
cout << cur[0] << endl;
}
