小菜鸡第一次编程题ac，百度笔试（9.3）
rt，比较激动，不过百度的前两题感觉挺简单的，基本一遍过。
第一题忘了是啥了。。
第二题 演员期望值：两个数组，一个表示演员期望值，一个表示角色属性值，角色属性值大于等于演员期望即匹配，要求输出匹配最多时的角色属性值索引（按演员输入顺序，没有匹配的为-1）
两个数组，用pair存一下值和索引，然后排序，贪心就ok了，代码甚至都没存。。凭记忆写了一下
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int m, n;
cin >> n >> m;
vector<pair<int, int> > person(n);
vector<pair<int, int> > role(m);
vector<int> res(n);
for (int i = 0; i < n; i++) {
cin >> person[i].first;
person[i].second = i;
}
for (int i = 0; i < m; i++) {
cin >> role[i].first;
role[i].second = i;
}
//
sort(person.begin(), person.end());
sort(role.begin(), role.end());
int index1 = 0, index2 = 0;
while (index1 < n) {
if (index2 < m) {
if (person[index1].first <= role[index2].first) {
res[person[index1++].second] = role[index2].second + 1;
}
index2++;
}
else {
res[person[index1++].second] = -1;
}
}
for (int i = 0; i < n; i++) {
cout << res[i] << ' ';
}
cout << endl;
}
return 0;
}
第三题 上楼梯，一次可以走1~m阶，共n阶，每次走的步数不能和前面两次相同，问到最后一阶有几种走法（输出对1e9+7取余数）
思路就是动态规划，本来想的是dp数组，dp[i]存一个map，键值是前两次走的步数，然后依次更新即可。但是unordered_map没有pair作为键值的构造函数，还好以前特意写过
#include<iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct pair_hash {
template<class t1, class t2>
std::size_t operator () (const std::pair<t1, t2>&p) const
{
auto h1 = std::hash<t1>{}(p.first);
auto h2 = std::hash<t2>{}(p.second);
return h1^h2;
}
};
int mod = 1000000007;
int main() {
int m, n;
cin >> n >> m;
vector<unordered_map<pair<int, int>, int, pair_hash> > dp(n + 1); //first 上一步， second 上两步
dp[0][{mod + 1, mod + 1}] = 1;
for (int i = 1; i <= n; i++) {
int j;
for (j = i - 1; j >= 0 && i - j <= m; j--) {
for (auto& it : dp[j]) {
if (it.first.first != i - j&&it.first.second != i - j) {
dp[i][{i - j, it.first.first}] = (dp[i][{i - j, it.first.first}] + it.second) % mod;
}
}
}
while (j >= 0 && !dp[j].empty()) {
dp[j--].clear();
}
}
int res = 0;
for (auto& it : dp[n]) {
res = (res + it.second) % mod;
}
cout << res << endl;
return 0;
}
不过一直卡在80%、90%，想了半天，应该是空间超了，于是加了
while (j >= 0 && !dp[j].empty()) {dp[j--].clear();}
这一段去清除多余的dp占用的内存。最后还剩10分钟惊险过关。
看了看别的大佬的思路，可以不用哈希表，而用三维数组来实现，而且dp数组只需要维护长度为m的一段就可以了，所以这个代码还是有优化空间的。
总的感觉还是选择题比较难，好几个都不会。。。希望自己再接再厉，早日被捞，也祝愿大家offer多多，早日上岸。
#笔试题型#
