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\)

总结：题目描述比较奇怪，没有太理解，所以最后也没有花很多时间思考

我们考虑求两个动点之间的距离是一件非常困难的事情

所以我们可以考虑以其中一个点作为参照点，另外一个点作为动点，这里选择龙卷风作为参照点更加合适

不难发现，另外一个点移动的轨迹是两组平行线段的结合

分别对于两组平行线段中求距离的最小值，之后在取一个总的最小值即可