【HULU】笔试

除了第一题，其他都跪

第四题不会，感觉像是容斥，不知道怎么做。。

八点多才开始做的，看了一下感觉前两题难度还行，只a了第一道签到题，第二题没时间了。。。

AC前三道，第四题来不及做了......

第一题 #include <bits/stdc++.h> using namespace std; struct node { int id; int val; int sum; }; node nn[100005]; int n; bool cmp1(node a, node b) { return a.val < b.val; } bool cmp2(node a, node b) { return a.id < b.id; } int main() { ios::sync_with_stdio(false); //freopen("input.txt", "r", stdin); cin >> n; for (int i = 0; i < n; ++i) { cin >> nn[i].val; nn[i].id = i; } sort(nn, nn + n, cmp1); int now = 0; int pre = 0; nn[0].sum = 0; now += nn[0].val; pre = 0; for (int i = 1; i < n; ++i) { if (nn[i].val > nn[i-1].val) { nn[i].sum = now; pre = now; now += nn[i].val; } else { nn[i].sum = pre; now += nn[i].val; } } sort(nn, nn + n, cmp2); for (int i = 0; i < n; ++i) { cout << nn[i].sum << endl; } return 0; } 第二题代码，三个角到圆心角之和小于360度就是钝角了 #include <bits/stdc++.h> using namespace std; int arr[1005]; int n; int ct; bool check(int a, int b, int c) { int aa = abs(arr[a] - arr[b]); if (aa > 18000) aa = 36000 - aa; int bb = abs(arr[a] - arr[c]); if (bb > 18000) bb = 36000 - bb; int cc = abs(arr[b] - arr[c]); if (cc > 18000) cc = 36000 - cc; return aa + bb + cc != 36000; } int main() { ios::sync_with_stdio(false); //freopen("input.txt", "r", stdin); cin >> n; for (int i = 0; i < n; ++i) { cin >> arr[i]; } sort(arr, arr+n); ct = 0; for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if (check(i, j, k)) { ct ++; } } } } cout << ct << endl; return 0; } 第三题拓扑排序，不过不知道为啥，怎么做都是73% #include <bits/stdc++.h> using namespace std; int m, n, k; int a, b; map<int, int> ma; map<int, vector<int> > mb; set<pair<int, int> > se; // 去重 void solve() { if (m == 0) { cout << 0 << endl; return ; } if (n == 0) { cout << "E" << endl; return; } int ans = 0; stack<int> st; for (int i = 1; i <= m; ++i) { if (ma[i] == 0) st.push(i); } int tp; vector<int> tv; while(!st.empty()) { ans ++; for (int wo = 0; wo < n; ++wo) { if (st.empty()) break; tp = st.top(); st.pop(); for (int i = 0; i < mb[tp].size(); ++i) { -- ma[mb[tp][i]]; if (ma[mb[tp][i]] == 0) { tv.push_back(mb[tp][i]); } } } for (int i = 0; i < tv.size(); ++i) { st.push(tv[i]); } tv.clear(); } bool flag = true; for (int i = 1; i <= m; ++i) { if (ma[i] > 0) { flag = false; break; } } if (flag) { cout << ans << endl; } else { cout << "E" << endl; } } int main() { ios::sync_with_stdio(false); //freopen("input.txt", "r", stdin); cin >> m >> n >> k; pair<int, int> tpa; for (int i = 0; i < k; ++i) { cin >> a >> b; if (a == b) continue; if (a <= 0 || a > m) continue; if (b <= 0 || b > m) continue; tpa.first = a; tpa.second = b; if (se.find(tpa) != se.end()) { continue; } else { se.insert(tpa); } ma[a] ++; mb[b].push_back(a); } solve(); return 0; } 第四题不会

第三题咋做啊，只会拓扑排序73%。。。

第三题： #include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> using namespace std; int main() {     int m, n, k;     cin >> m >> n >> k;     vector<int> tmp;     map<int, vector<int> > datas; // int为序号，vector为依赖他的结点     for (int i = 0; i <= m; i++) {         vector<int> tmp;         datas[i] = tmp;     }     vector<int> yilai(m + 1, 0); // 结点i是否有依赖，0为无依赖可以直接操作     vector<int> done(m + 1, 0); // 结点i是否已完成，0为未完成     int left, right;     for (int i = 0; i < k; i++) {         cin >> left >> right;         yilai[left] = 1;         datas[right].push_back(left);     }     int ans = 0;     int conutOfDone = 0; // 当前已完成计数     while (conutOfDone != m) {         int conutoftodo = 0;         vector<int> deal;         for (int i = 1; i <= m; i++) {             if (yilai[i] == 0 && done[i] == 0) {                 conutoftodo++;                 conutOfDone++;                 deal.push_back(i); // 存储当前待完成结点，用于更新各数组             }         }         if (conutoftodo == 0 && conutOfDone != n) {             cout << "E" << endl;             return -1;         }         else if (conutoftodo <= n)             ans++;         else if (conutoftodo > n) {             if (conutoftodo % n == 0)                 ans = ans + conutoftodo / n;             else                 ans = ans + conutoftodo / n + 1;         }         for (int i = 0; i < deal.size(); i++) { // 更新各个数组             done[deal[i]] = 1;             vector<int> ttt = datas[deal[i]];             for (int j = 0; j < ttt.size(); j++)                 yilai[ttt[j]] = 0;         }     }     cout << ans << endl;     return 0; }

求解第四题