2022.10.04考试总结
得分:\(110/300\)
总结:今天的第一题比较简单,第二题因为看错题意并且思考了比较长的时间导致爆零,第三题在考场上没有一个比较完整并且容易实现的思路
题目如下:
T1
得分:\(100/100\)
总结:考虑二分,不难发现,答案具有单调性,\(check\)用最短路实现即可
T2
得分:\(0/100\)
总结:考虑\(dp\)
首先比较显然可以排序
设\(f[i]\)表示\(1-i\)中最坏情况会丢掉多少个
\(f[i]=max\{f[j]+val(j+1,i)[j < i]\}\)
考虑计算\(val(x,y)\)
枚举要丢掉几个,考虑一下两个问题即可
- 没有被丢掉的能否匹配完
- 被丢掉的能否互相匹配
计算答案即可
T3
得分:\(0/100\)
总结:题目描述比较奇怪,没有太理解,所以最后也没有花很多时间思考
我们考虑求两个动点之间的距离是一件非常困难的事情
所以我们可以考虑以其中一个点作为参照点,另外一个点作为动点,这里选择龙卷风作为参照点更加合适
不难发现,另外一个点移动的轨迹是两组平行线段的结合
分别对于两组平行线段中求距离的最小值,之后在取一个总的最小值即可
标签:总结,得分,04,丢掉,100,2022.10,考试 From: https://www.cnblogs.com/AntelopeWang/p/16753996.html