20200801猿辅导笔试记录August-us的博客-猿辅导20200801

  最近比较忙，没太多时间，所以题目写的略微粗略一些。

重复的课程

输入N表示N节课，接下来输入N行每行输入课程的开始时间和结束时间，求最多的时候有几节课时间重了。
输入示例 ：
4
1 4
1 2
2 3
3 4
输出：2

  这个题目描述的就很神奇，题目竟然问的是最少？这里就不纠结题目，仅供讨论。
  考虑一个时间段同时有几节课在上，在所有开始和结束的时间中遍历，如果开始一节课则同时上的课数目+1，结束一节课，则同时上的课数目-1。完整通过的人好像都是都是使用优先级队列，我觉得优先级队列在这里没必要。只需要记录一个数目即可。

#include <iostream> #include<algorithm> #include<vector> using namespace std; int main() { int n;  cin >> n;  vector<int> start(n);     vector<int> end(n); int a, b; for(int i=0;i<n;i++) {         cin >>a>>b;   start[i] = a;   end[i] = b; } sort(start.begin(),start.end()); sort(end.begin(),end.end()); int i=0, j=0, k=0, res=0; while(i<n) { if (start[i]<end[j]) { // 说明该在start[i]这个时段有课开了             k += 1;             i +=1;             res = max(k, res); } else {             j+=1;             k-=1; } }     cout << res << endl; return 0; } 

  这是我的思路，但是可能会存在瑕疵，这里把我同学AC100的代码贴上来。使用的是优先级队列，但是思想还是一样的，区别在于用变量记录窗口内课程数目还是使用优先级队列。

#include <iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; int main() { int n;  cin >> n;  vector<pair<int,int>>range(n); for(int i=0;i<n;i++) { int a, b;   cin >> a >> b;   range[i].first = a;   range[i].second = b; } if (n == 1) return 1; if (n == 0) return 0; sort(range.begin(),range.end());   priority_queue<int,vector<int>,greater<int>>q;  q.push(range[0].second); int ans = 1; for (int i = 1; i < n; i++) { while (q.top() <= range[i].first)    q.pop();   q.push(range[i].second);   ans = max(ans, (int)q.size()); }  cout << ans << endl; return 0; } 

  考试的时候，我使用的是python，当时是比较原生，没有优化的代码。直接把start和end放在一个序列中，然后排序，判断窗口的课程数目，放在一个序列的时候依靠另一个标志来记录是开始还是结束。代码如下。

n = int(input()) res = [] for i in range(n):     s, e  =[int(i) for i in input().split(' ')]     res.append([s, -1])     res.append([e, s]) res.sort(key=lambda x:x[0])  maxk = k = 0 for i in res: if i[1]==-1:         k+=1 else:         k -=1     maxk = max(k, maxk) print(maxk) 

  我写的两个代码的理论复杂度是一致的，无非就是python代码比较原生一些。但是这个代码，只过了55%的case。自己没找到原因，如果有人知道，或者指出我方法的问题，感激不尽。

发奖品

题目大意是这样，有个人拿到一堆奖券，但是自己只能持有一张，他需要把剩下的分给别人，每个拿到奖券的人也只能持有一张，需要继续分给别人。最后分完之后开奖，奖券对应一个奖励（会有负收益），最后需要计算每个人开奖的得分。
得分的计算需要保证，每个人只能计算自己的奖券(必须要算)，以及从自己这里分出去的奖券的收益（可以选择部分）。如果要计算间接从自己这里分出去的收益，则经由中间转手送出去的收益都要被计算。举个例子就是A分出去B，B分出去了C和D，如果A要计算C或D的收益，则必须要计算中间收益B。
输入示例：
3
2 0
1 2
-1 2
输入说明：第一行表示有n张奖券，第二行到第n+1行的两个数，表示这个人的奖券收益，和奖券来源。奖券来源i表明这个人的奖券来自于第i行的这个人。0表示他是奖券的源头。如2表示奖券来源于输入第二行这个人。
输出示例： 3

  我已经把题目给大家理的很顺了。接下来就是上代码了。我一开始也看错了题目，题目要求所有人中最大的开奖得分。我以为只求第一个人的。然后一直通过0%。
  最后两分钟发现了问题，改出来如下两版代码。
  我的思想是递归，为每个奖券从这个奖券这里出去的，记为这个奖券的孩子。然后计算收益的时候，从上往下计算，如果孩子只有一张奖券，没有分出去的奖券，则看这个收益是否大于0，如果大于0则选，反之不选。如果孩子也有孩子，则递归计算孩子的收益。
  第一般代码如下：

from collections import defaultdict  n = int(input()) res = []  send = defaultdict(list) for i in range(n):     a, b = [int(i) for i in input().split(' ')]     res.append(a)     b -= 2     send[b].append(i) def getMaxValue(k):     r = res[k] if k in send: for i in send[k]:             r += getMaxValue(i) return max(r, 0) % 1000000003  a = 0 for i in range(n):     a = max(getMaxValue(i), a) print(a) 

  提交后，过了50%的case，接着就回到这个老生常谈的话题，递归重复计算的问题。（注：如果只计算第一个发奖券的人，则不会有重复计算。）提交后还有一分钟，这个时候最快的方法就是加备忘录。
  第二版加了备忘录，代码如下。

from collections import defaultdict  n = int(input()) res = []  send = defaultdict(list) for i in range(n):     a, b = [int(i) for i in input().split(' ')]     res.append(a)     b -= 2     send[b].append(i) me = {} def getMaxValue(k): if k in me: return me[k]     r = res[k] if k in send: for i in send[k]:             r += getMaxValue(i)     me[k] = max(r, 0) % 1000000003 return me[k]  a = 0 for i in range(n):     a = max(getMaxValue(i), a) print(a) 

  本以为第一版是超时，然后提交了第二版，以为没问题了，结果令我大吃一惊，发现AC还是50%。然后时间到了。我猜测这里可能是因为如果所有的中奖收益都是负数，我的代码返回的不是最大的收益，而是0。
  针对这个问题，只需要把最后返回的max移到循环内，对孩子做检查就行了，不需要对自己的收益做检查。修改后代码如下。

from collections import defaultdict  n = int(input()) res = []  send = defaultdict(list) for i in range(n):     a, b = [int(i) for i in input().split(' ')]     res.append(a)     b -= 2     send[b].append(i) me = {} def getMaxValue(k): if k in me: return me[k]     r = res[k] if k in send: for i in send[k]:             r += max(getMaxValue(i), 0)     me[k] =  r % 1000000003 return me[k]  a = 0 for i in range(n):     a = max(getMaxValue(i), a) print(a) 

  至于第三题，是一个简化版的后端模板语言渲染工具，思考了一阵子，发现代码量会很大，放弃了。
  虽然承认自己做的很烂，但还是想写出来留个记录，同时也为了大家讨论吧。