携程笔试 5.7 研发方向1 专业笔试(二)讨论
三道编程题 63+90+89,没有一道题ac有点难受...
第一题爬楼梯plus版
不知道为什么只有63分!!!
#include <iostream> #include <vector> using namespace std; int climb(int n) { if (n <= 0) return -1; vector<vector<int>> dp(n+1); for (int i = 0; i <= n; i++) dp[i].resize(2); dp[1][0] = dp[1][1] = 1; dp[2][0] = dp[2][1] = 2; dp[3][0] = 3; dp[3][1] = 4; for (int i = 4; i <= n; i++) { dp[i][0] = dp[i - 1][0] + dp[i - 2][0]; dp[i][1] = dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][0]; } return dp[n][1]; } int main() { int n; cin >> n; cout << climb(n) << endl; return 0; }
第二题
一道图论题,求给定两点的所有路径的题,dfs解决,注意读入数据的时候要建立地名和编号的双向映射关系
#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; const int MAXN = 30; int G[MAXN][MAXN]; map<char, int> nameToIdx; map<int, char> idxToName; int N = 0; vector<vector<int>> ans; vector<int> path; vector<bool> vis(MAXN); int st, ed; void dfs(int u) { vis[u] = true; path.push_back(u); if (u == ed) { ans.push_back(path); } else { for (int v = 0; v < N; v++) { if (G[u][v] && vis[v] == false) { dfs(v); } } } path.pop_back(); vis[u] = false; } int convertNameToIndex(char name) { if (!('A' <= name && name <= 'Z')) { cout << "EMPTY" << endl; exit(0); } auto it = nameToIdx.find(name); if (it != nameToIdx.end()) { return it->second; } else { nameToIdx[name] = N; idxToName[N] = name; return N++; } } int main() { //freopen("input.txt", "r", stdin); string str; cin >> str; for (int i = 0; i < str.length(); i += 6) { char st = str[i + 1]; char ed = str[i + 3]; int u = convertNameToIndex(st); int v = convertNameToIndex(ed); G[u][v] = 1; } if (nameToIdx.count('A') == 0 || nameToIdx.count('B') == 0) { cout << "EMPTY" << endl; return 0; } st = nameToIdx['A']; ed = nameToIdx['B']; dfs(st); if (ans.size() == 0) { cout << "EMPTY" << endl; return 0; } sort(ans.begin(), ans.end(), [](const vector<int> &A, const vector<int> &B) { return A.size() < B.size(); }); cout << "["; for (int i = 0; i < ans.size(); i++) { if (i > 0) cout << ","; cout << "["; for (int j = 0; j < ans[i].size(); j++) { if (j > 0) cout << ","; cout << idxToName[ans[i][j]]; } cout << "]"; } cout << "]"; cout << endl; return 0; }第三题
将一个数组划分成M部分,要求每一部分子数组的sum不能重复,求有多少种方案
我用dfs枚举所有可能的方案,再逐一判断,注意这里对区间求和是可以优化的。
#include <iostream> #include <vector> #include <set> using namespace std; int N, M; vector<int> A; vector<int> SUM; // sum[i]表示数组前i个数字的和 vector<int> plan; int cnt; bool judge(vector<int> &plan) { set<int> S; int preCnt = 0; for (int x : plan) { int sum = SUM[preCnt + x] - SUM[preCnt]; if (S.count(sum) > 0) return false; S.insert(sum); preCnt += x; } return true; } void dfs(int N, int M) { if (M == 0) { if (N == 0) { if (judge(plan)) { cnt++; } } } else { for (int i = 1; i <= N; i++) { plan.push_back(i); dfs(N - i, M - 1); plan.pop_back(); } } } int main() { //freopen("input.txt", "r", stdin); cin >> N; A.resize(N); for (int i = 0; i < N; i++) { cin >> A[i]; } cin >> M; if (N < M) { cout << "0" << endl; return 0; } SUM.resize(N + 1); for (int i = 1; i <= N; i++) { SUM[i] = SUM[i - 1] + A[i - 1]; } dfs(N, M); cout << cnt << endl; return 0; }