拼多多提前批算法笔试（ac，ac，ac，40%）

第三题 typedef struct node {     int x, y;     friend bool operator <(node a, node b) {         if (a.x == b.x)             return a.y > b.y;         else             return a.x > b.x;     }     node(int a, int b) {         x = a;         y = b;     } }; int main() {     priority_queue<node> q;     int n, m;     cin >> n >> m;     vector<int> need_time(n + 1);     for (int i = 1; i <= n; i++)         cin >> need_time[i];     vector<vector<int>> depen(n + 1);     vector<int> de_nums(n + 1, 0);     for (int i = 0; i < m; i++) {         int a, b;         cin >> a >> b;         de_nums[b]++;         depen[a].push_back(b);     }     for (int i = 1; i <= n; i++)         if (de_nums[i] == 0)             q.push(node(need_time[i], i));     vector<int> res;     while (!q.empty()) {         int y = q.top().y;         res.push_back(y);         q.pop();         for (int i = 0; i < depen[y].size(); i++) {             de_nums[depen[y][i]]--;             if (de_nums[depen[y][i]] == 0)                 q.push(node(need_time[depen[y][i]], depen[y][i]));         }     }     for (int i = 0; i < res.size(); i++)         cout << res[i] << ' ';     cout << endl;     system("pause");         return 0; }

老哥你确定第二题能ac？若是字符串自成俩环呢？比如 ab ba cd dc 也都是偶数？更不用说还有 aa bb cc dd 了？深度递归好伐？

第一题： int main() {     vector<int> A, B;     char temp[10000];     cin.getline(temp, 10000);     int l = 0;     int sum = 0;     while (temp[l] != '\0') {         if (temp[l] == ' ') {             A.push_back(sum);             sum = 0;         }         else             sum = sum * 10 + temp[l] - '0';         l++;     }     A.push_back(sum);     cin.getline(temp, 10000);     l = 0;     sum = 0;     while (temp[l] != '\0') {         if (temp[l] == ' ') {             B.push_back(sum);             sum = 0;         }         else             sum = sum * 10 + temp[l] - '0';         l++;     }     B.push_back(sum);     sort(B.begin(), B.end());     int idx;     for (idx = 0; idx < (int)A.size() - 1; idx++)         if (A[idx] >= A[idx + 1])             break;     for (int i = (int)B.size() - 1; i >= 0; i--) {         if ((B[i] > A[idx]) && (idx == (int)A.size() - 2 || B[i] < A[idx + 2])) {             A[idx + 1] = B[i];             for (int j = 0; j < A.size(); j++)                 cout << A[j] << ' ';             cout << endl;             system("pause");             return 0;             break;         }     }          for (int i = (int)B.size() - 1; i >= 0; i--) {         if ((B[i] < A[idx + 1]) && (idx == 0 || B[i] > A[idx - 1])) {             A[idx] = B[i];             for (int j = 0; j < A.size(); j++)                 cout << A[j] << ' ';             cout << endl;             system("pause");             return 0;             break;         }     }          cout << "NO" << endl;     system("pause");     return 0; }

大佬

第二题 int main() {     vector<int> m(26, 0);     char s[1000000];     cin.getline(s, 1000000);     int l = 0;     string temp = "";     while (s[l] != '\0') {         if (s[l] == ' ') {             m[temp[0] - 'A']++;             m[temp[temp.size() - 1] - 'A']++;             temp = "";         }         else             temp += s[l];         l++;     }     m[temp[0] - 'A']++;     m[temp[temp.size() - 1] - 'A']++;     for (int i = 0; i < 26; i++) {             if (m[i] % 2 != 0) {             cout << "false" << endl;             system("pause");             return 0;         }     }     cout << "true" << endl;     system("pause");     return 0; }

第四题 暴力递归（40%） bool cmp(pair<int, int> &a, pair<int, int> &b) {     if (a.first == b.first)         return a.second > b.second;     else         return a.first > b.first; } void helper(vector<pair<int, int>> x, int max_weight, int height, int &res, int idx, int max_l) {     res = max(res, height);     if (idx == x.size())         return;     if (x[idx].first < max_l && x[idx].second <= max_weight) {         if (max_weight - x[idx].second < x[idx].second * 7)             helper(x, max_weight - x[idx].second, height + 1, res, idx + 1, x[idx].first);         else             helper(x, x[idx].second * 7, height + 1, res, idx + 1, x[idx].first);     }     helper(x, max_weight, height, res, idx + 1, max_l); } int main() {     int n;     cin >> n;     vector<int> L(n), W(n);     for (int i = 0; i < n; i++)         cin >> L[i];     for (int i = 0; i < n; i++)         cin >> W[i];     vector<pair<int, int>> x;     for (int i = 0; i < n; i++)         x.push_back(make_pair(L[i], W[i]));     sort(x.begin(), x.end(), cmp);     int res = 0;     helper(x, INT_MAX, 0, res, 0, INT_MAX);     cout << res << endl;     system("pause");     return 0; }

第二题python A = [str(n) for n in input().split()] start = [] end = [] for i in range(len(A)): start.append(A[i][0]) end.append(A[i][-1]) start.sort() end.sort() print(start == end)

“qaq”,“ewe”，这两个字符串是不能形成环的

第二题欧拉回路，要加一个连通图判断

大佬666

你还是牛逼，能对三个以上的都是大佬

强啊

大佬

膜拜一下大佬

第四题我也想的dp，但是不知道怎么做

第二题思路没懂啊，怎么排出两个闭合圈的情况呢? 比如说我的输入是AB BA CD DC。

第二题思路错误，应该用剪枝dfs

大佬，牛逼

第二题方法有问题，只是测试数据太弱了……mxm axa

有大佬给第一题ac的java代码吗