4月16号美团点评笔试
这次笔试比前两天阿里的感觉简单一点。一个半小时5题全部ac。
给大家分享一下解法吧。
第一题，给n个学生的m科成绩，如果一个学生的某一科是单科最高，那么这个学生获得奖励，即便该学生有多科最高，也只获得一次奖励。求获得奖励的学生人数。
思路：直接遍历每个科目求最大值就行了，要注意的细节是，可能有很多学生获得该科最高分，此时所有最高分都有奖励。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> data(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int tmp;
cin >> tmp;
data[i].push_back(tmp);
}
}
vector<int> flag(n);
for (int j = 0; j < m; ++j) {
int max_value = 0;
vector<int> max_index;
for (int i = 0; i < n; ++i) {
if (data[i][j] > max_value) {
max_value = data[i][j];
max_index.clear();
max_index.push_back(i);
} else if (data[i][j] == max_value) {
max_index.push_back(i);
}
}
for (int i = 0; i < max_index.size(); ++i) {
flag[max_index[i]] = 1;
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += flag[i];
}
cout << ans << endl;
return 0;
} 第二题，给a,b,x,m四个数，给定递推式 x=(a*x+b)%m，这个x不停算会循环，问递推第几次起x开始循环。
思路：因为取模m，x取值最多m种，维护一个m长度的flag数组，见到没见过的x就标记，如果见过了就代表循环了。
（根据抽屉原理，最多m+1次就一定会开始循环）
#include <iostream>
#include <vector>
using namespace std;
int main() {
long long a, b, x, m;
int cnt = 0;
cin >> a >> b >> m >> x;
vector<int> flag(m);
while (true) {
x = (a * x + b) % m;
if (flag[x] == 1) {
cout << cnt << endl;
break;
}
flag[x] = 1;
++cnt;
}
return 0;
}
第三题，给定n个数，这n个数两两结合构成一共n^2个有序数对（i， j）（可以自己和自己构成有序数对）。给定k，求第k大的有序数对是哪一个。
思路：先排序得到数列data，有序数对中第一个数越小那么有序数对越小。第一想法很容易想到 （data[(k-1)/n], data[(k-1)%n]）是答案，但这样忽略了数列中可能存在相同元素。（这样写答案大概得64%）
例如给定1，2，2那么9个有序数对应该是：
（1，1）（1，2）（1，2）
（2，1）（2，2）（2，2）
（2，1）（2，2）（2，2）
这是第5大的应该是（2，1）而不是第二行第二列的（2，2）
这时候先定位第k大所在的有序数对中第一个数是什么，很明显是data[(k-1)/n]
再数这个数重复出现了几次，假如出现了p次。再数比这个数小的有几个，假如有q个。
那么答案就是（data[(k-1)/n], data[(k-n*q-1)/p]）
这里下标想不清楚的，拿个例子对一下会比较清楚。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n;
long long k;
vector<int> data;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
data.push_back(tmp);
}
sort(data.begin(), data.end());
long long a = (k - 1) / n;
long long l = 0, row = 0;
while (data[l] != data[a]) ++l;
while (data[l+row] == data[a]) ++row;
long long aa = (k - l * n - 1) / row;
printf("(%d,%d)", data[a], data[aa]);
return 0;
} 第四题，给定有序数列伪中位数的定义，m=a[floor((n-1)/2)]，其实就是当n为奇数时就是正常中位数，n是偶数时取中间两个数较小的那个数。
给定一个数列，和一个值k，问至少添加几个数，使得该序列的伪中位数等于k。
思路：稍微分析就可以知道，如果需要往数列里加数，不停加k就行了，现在求需要加几个k。
先遍历数列，统计出比k小的数small个，跟k一样大的数equal个，比k大的数big个。
很容易发现，如果k是伪中位数，就一定有
small+equal >= big
big + equal > small
两个式子同时成立
第二个式子可以变换成 big + equal >= small+1
最后解出equal满足
equal >= big-small 且 equal >= small-big+1
所以equal比二者较大值大，即equal>=max(big-small, small-big+1)
需要补的k的个数即max(big-small, small-big+1) - equal
注意上式可能为负，跟0再取个最大即可。
#include <iostream>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
int cnt_big = 0, cnt_small = 0, cnt_equal = 0;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
if (tmp < k) ++cnt_small;
else if (tmp > k) ++cnt_big;
else ++cnt_equal;
}
cout << max(max(cnt_small - cnt_big + 1, cnt_big - cnt_small) - cnt_equal, 0);
return 0;
} 第五题
给两个字符串s,t求s的子串与t的子序列相同的情况有多少种。
字串的定义是连续的子字符串。
子序列的定义是不必连续的子序列。abcde的子序列可以是ace。
动态规划，定义f[i][j]为字符串s到第i个位置为止，且用上了第i个位置的字符；字符串t到第j个位置为止；此时的相同数目。（描述有点绕，不知讲清楚没有。）
状态转移方程，分两种情况：
第一种是s串的子串就是s[i]自己，（长度为1的字串）
那么此时种类数是cntj[s[i]]，这个数的意思是字符串t的前j个字符里，有多少个s[i]。
这种情况很好理解。
第二种是s串字串长度大于2，且包含s[i]。
这种情况下考虑s[i]和t中的哪一个字符配对。事实上总共有cntj[s[i]]种配对方法（这个数的意思详见上面）。假设这些s[i]分别出现在t串的p1,p2,p3,...,pc (c=cntj[s[i]])这些位置
那么种类数是f[i-1][p1-1]+f[i-1][p2-1]+...+f[i-1][pc-1]
综上，f[i][j] = cntj[s[i]] + (f[i-1][p1-1]+f[i-1][p2-1]+...+f[i-1][pc-1])
最终答案为f[1][nt] + f[2][nt] + ... + f[ns][nt] ns和nt为s串和t串的长度。
另外发现这样递推复杂度还是太高。
cntj[s[i]]可以跟随着迭代更新。
(f[i-1][p1-1]+f[i-1][p2-1]+...+f[i-1][pc-1])这一串也可以跟着迭代更新，这是下面代码中value的意义。
下面代码中value[ch][i]表示假设ch分别出现在t串的p1,p2,p3,...,pc (c=cntj[ch])这些位置,(f[i][p1-1]+f[i][p2-1]+...+f[i][pc-1])的值。
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
const int M = 1000000007;
int f[5001][5001], ns, nt;
string s, t;
int main() {
cin >> s >> t;
ns = s.size();
nt = t.size();
unordered_map<char, int> cnt;
unordered_map<char, vector<int>> value;
for (int j = 1; j <= nt; ++j) {
char tt = t[j-1];
cnt[tt]++;
if (value.find(tt) == value.end()) {
value[tt].resize(ns+1);
}
for (int i = 1; i <= ns; ++i) {
char ss = s[i-1];
f[i][j] = cnt[ss];
if (value.find(ss) != value.end()) {
f[i][j] = (f[i][j] + value[ss][i-1]) % M;
}
value[tt][i] = (value[tt][i] + f[i][j-1]) % M;
}
}
int ans = 0;
for (int i = 1; i <= ns; ++i) {
ans = (ans + f[i][nt]) % M;
}
cout << ans;
return 0;
}
这就是大佬吗？i了i了
