5.15华为机考满分通过，附上解答

1. 第一题就是普通的lru，代码未保存，就略了
2. 第二题将模式串n()的形式拆分出来，然后将待匹配串处理成A+N的形式，跑一遍kmp即可

#include <iostream>
#include <string>
#include <stack>
#include <cstring>

using namespace std;

int nxt[1000005];

void getNext(const char *s, int len)
{
  nxt[0] = 0;
  int k = 0;
  for (int i = 1; i < len; i++)
  {
    while (k > 0 && s[i] != s[k])
      k = nxt[k - 1];
    if (s[i] == s[k])
      k++;
    nxt[i] = k;
  }
}

int kmp(const char *T, const char *S)
{
  getNext(S, strlen(S));
  int len_T = strlen(T);
  int len_S = strlen(S);
  for (int i = 0, j = 0; i < len_T; i++)
  {
    while (j > 0 && T[i] != S[j])
      j = nxt[j - 1];
    if (T[i] == S[j])
      j++;
    if (j == len_S)
      return i - len_S + 1;
  }
  return -1;
}

int main(int argc, char const *argv[])
{
  /* code */
  string pattern, s, pp;
  cin >> pp >> s;
  stack<int> num;
  stack<string> sta;
  int cnt = 0;
  if (pp[0] < '0' || pp[0] > '9')
  {
    pattern = "1(";
    pattern += pp;
    pattern += ")";
  }
  else
  {
    pattern = pp;
  }
  for (auto it : pattern)
  {
    if (it >= '0' && it <= '9')
    {
      cnt = 10 * cnt + (it - '0');
    }
    else if (it == '(')
    {
      num.push(cnt);
      sta.push("(");
      cnt = 0;
    }
    else if (it == ')')
    {
      string res = "";
      while (sta.top() != "(")
      {
        res = sta.top() + res;
        sta.pop();
      }
      sta.pop();
      int times = num.top();
      num.pop();
      string r = "";
      while (times--)
      {
        r = r + res;
      }
      sta.push(r);
    }
    else
    {
      sta.push(string(1, it));
    }
  }
  string res = "";
  while (!sta.empty())
  {
    res = sta.top() + res;
    sta.pop();
  }
  string str = "";
  for (auto it : s)
  {
    if (it >= '0' && it <= '9')
    {
      str += 'N';
    }
    else if ((it >= 'a' && it <= 'z') || (it >= 'A' && it <= 'Z'))
    {
      str += 'A';
    }
    else
    {
      str += '*';
    }
  }
  int id = kmp(str.c_str(), res.c_str());
  if (id == -1)
  {
    cout << "!" << endl;
  }
  else
  {
    cout << s.substr(id, res.size()) << endl;
  }
  return 0;
}

3. 第三题就是简单的搜索。

评论区有人指正解法不对，呃………搜索确实是暴力解法理论上肯定超时，标准是动态规划，但是考试的时候暴力直接过了，所以……管他什么狗屁解法呢

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int capacity;
int num;
int a[300];
bool vis[300];

bool dfs(int pos, int cur)
{
  if (cur == capacity)
  {
    return true;
  }
  for (int i = pos; i < num; i++)
  {
    if (cur + a[i] > capacity)
    {
      break;
    }
    vis[i] = true;
    if (dfs(i + 1, cur + a[i]))
    {
      return true;
    }
    vis[i] = false;
  }
  return false;
}

int main(int argc, char const *argv[])
{
  /* code */
  cin >> capacity;
  cin >> num;
  int sum = 0;
  for (int i = 0; i < num; i++)
  {
    cin >> a[i];
    sum += a[i];
  }
  sort(a, a + num);
  if (sum != 2 * capacity)
  {
    cout << "-1" << endl;
    return 0;
  }
  vector<int> l1, l2;
  if (!dfs(0, 0))
  {
    cout << "-1" << endl;
    return 0;
  }
  for (int i = 0; i < num; i++)
  {
    if (vis[i])
    {
      l1.push_back(a[i]);
    }
    else
    {
      l2.push_back(a[i]);
    }
  }
  if (l1[0] > l2[0] || (l1[0] == l2[0] && l1.size() > l2.size()))
  {
    swap(l1, l2);
  }
  bool flag = false;
  for (auto it : l1)
  {
    if (flag)
    {
      cout << " ";
    }
    cout << it;
    flag = true;
  }
  cout << endl;
  flag = false;
  for (auto it : l2)
  {
    if (flag)
    {
      cout << " ";
    }
    cout << it;
    flag = true;
  }
  cout << endl;
  return 0;
}