5.15华为机考满分通过,附上解答
- 第一题就是普通的lru,代码未保存,就略了
- 第二题将模式串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; }