《2020年牛客算法入门课练习赛2》

前言：太懒了，有些题懒得详细写。代码中有些注释。应该能看懂。（大概？）
代码会崩就直接发链接了..
A：
dp转移。
用mp来dp了.
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43975592
B：
bfs搜。当搜到了站进去就可以一直呆着的就说明到了安全区。
然后注意的是。先处理每个时刻的爆炸点。然后query
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43976051
C：
对于显然可以发现。
因为要反复回来。所以要先把最慢的人运到对面。
可以发现对于最慢的人a[n]的运输。
无非就是两种方案。
和差距最小的人坐船，和差距最大的人做船
1.和最快的人a[1]过去,然后a[1]回来。
2.先让a[1]和a[2]过去,然后回来一个。然后a[n]和次慢的人a[n-1]过去。然后a[1],a[2]中剩下的一个回来。

可以发现贪心的策略无非就是两种。
1.让最快的人反复接慢的人.
2.让最慢的人和次慢的人同时过岸。让最快的人和次快的人回来，相当于消除没船回来的影响。使得状态变成了相当于就消除了最慢的人和次慢的人。

dp统计即可.
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43977898
D：
显然当在一个连通块中。如果有两个点直接有多条路径必走就说明肯定要走多次。那么肯定就不行。
所以每个连通块肯定是一条链.
主要是这里的排列组合不好理解。（是我太菜了应该）
对于每个数量大于1的连通块。它可以直接反着连一次，这和正着不一样.因为这里是按走的方案不同来统计的。所以正反走肯定不一样。
我们可以这样来排序。
对于每个大于1的连通块。他们都有两种方案。
那么先让他们不需要顺序排序组合就是2^(连通块数目).
然后全部连通块有序排列A(总的连通块数目）。
那么答案就是两个相乘
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43978181
E:
背包dp、
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43976851