【水题合集】6.13考试

讲道理这次考的题以前都考过(虽然以前没做出来过一道)

1.哲哲回家

每趟公交车建\(p\)个点跑最短路

2.旋转单词阵

排个序跳一跳

3.切蛋糕

\(dp[i][j][k]\)表示尺寸为\(i\times j\)并且不允许直接横/竖切/随便切的方案数

转一下就可以了

或者记忆化搜索

4.套圈游戏

这题讲道理和前面三道题的出处不一样

这题是从一套叫做“挫折教育”的题里出来的

非常害怕 只有我一个人A了

首先求出每个点\((x,y)\)到直线\(Bx+Ay=0\)的距离\(dis[i]\)

$$\frac{Bx+Ay}{\sqrt{A^2+B^2}}$$

那么一个点\(i\)能包含另一个点\(j\)必须满足

$$dis[j]-dis[i]\in[0,\frac{AB}{\sqrt{A^2+B^2}}]$$

但这还不是充要条件

还要满足\(x_j\ge x_i\)且\(y_j\ge y_i\)

那么我们按照距离排序后依次加入,每加入一个点可以删掉离它太远的点

再用树状数组分别记录横纵坐标比它小的点的权值和

就可以用当前权值和减去上面两部分权值得到它覆盖区域的权值

注意这里因为横纵坐标都比它小的点肯定距离也小还没有被加入所以不需要加上

说点什么

  Subscribe  
提醒