滴滴暑期实习笔试思路(AK)
第一题:
刚开始想着像二分图, 结果发现自己不会写 二分图了... 就先去做第二题了, 结果做完第二题回来暴力骗分的时候发现, woc AC 了... 后台数据有点水了说实话..或者说入 vector 的要求会剪掉很多枝所以时间复杂度是可以过 ? 如果有大佬会非 dfs 做法来浇一下蒟蒻
AC 代码(大雾)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5;
int n, a[N];
bool flag;
void dfs(int n, vector<int>& gt, vector<int>& ls, int dep)
{
if (flag) return ;
if (dep == n + 1) {
flag = 1; return ;
}
if (ls.empty() || a[dep] < ls.back())
{ ls.push_back(a[dep]); dfs(n, gt, ls, dep + 1); ls.pop_back(); }
if (gt.empty() || a[dep] > gt.back())
{ gt.push_back(a[dep]); dfs(n, gt, ls, dep + 1); gt.pop_back(); }
return ;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
flag = 0;
vector<int>gt, ls;
dfs(n, gt, ls, 1);
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
int main()
{
int T; cin >> T;
while (T--) solve();
return 0;
} 第二题简单模拟就行了, 就是被卡细节了, 编译器还卡在 wsl 出不来了.. 心态爆炸...
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s; cin >> s;
int n; cin >> n;
string res;
while (n--)
{
string t1, t2;
cin >> t1 >> t2;
int l = s.size(), i = 0;
for (i = 0; i + t1.size() - 1 < s.size(); i++)
{
string tmp;
for (int j = 0; j < t1.size(); j++)
tmp += s[i + j];
if (tmp == t1) res += t2, i += t1.size() - 1;
else res += tmp[0];
}
for (int j = i; j < s.size(); j++)
res += s[j];
if (n >= 1) s = res, res = "";
}
cout << res << endl;
return 0;
} #滴滴笔试##暑期实习#
查看24道真题和解析