滴滴暑期实习笔试思路(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;
}