文章目录

T1：Star Way To Heaven题目题解代码实现 T2：飞扬的小鸟题目题解代码实现

T1：Star Way To Heaven

题目

小 w 伤心的走上了 Star way to heaven。 到天堂的道路是一个笛卡尔坐标系上一个 n*m 的长方形通道 顶点在 (0,0) 和 (n,m) 。 小 w 从最左边任意一点进入，从右边任意一点走到天堂，最左最右的距离为 n，上下边界距离为m 。 其中长方形有 k 个Star ，每个 Star 都有一个整点坐标，Star 的大小可以忽略不计。 每个 Star 以及长方形上下两个边缘宇宙的边界都有引力，所以为了成功到达 heaven 小 w 离他们越远越好。 请问小 w 走到终点的路径上，距离所有星星以及边界的最小距离最大值可以为多少？

输入格式 一行三个整数n,m,k。 接下来 k 行，每行两个整数 表示一个点的坐标。 输出格式 一行一个数表示答案。保留到小数点后9位。

样例 样例输入 10 5 2 1 1 2 3 样例输出 1.118033989 数据范围与提示 对于 100% 的数据：k ≤ 6000；n,m ≤10⁶

题解

以考虑二分答案result，对k个star都建一个半径为r的圆入手， 那么对于两个相交的圆把它们弄到一个集合， 对上下边界特殊判断，如果说上下边界被弄到了一个集合， 即说明，有若干个圆将矩形拦腰折断，分成了两个不连通的部分，是无法走到天堂的 则这个答案不合法，舍去

难道真的去搞二分？？ 把几个圆弄到一个集合就会想到并查集，再到kruskal，最后联想到得到prim算法， 现将一个边界加入集合，找到距离它最小的点，加入集合， 将与之相连的点的距离更新

如此加边，知道另一边界也加入集合中，此时刚好上下界拦腰截断，其实这时的maxdis为恰好不能走过去时的最小dis，那么只要小一点点，就符合了，精度不用怕

代码实现

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define MAXN 6005 #define LL long long #define INF 10000000 int n, m, k; double result; double x[MAXN], y[MAXN], dis[MAXN]; bool vis[MAXN]; double count ( int u, int v ) { return sqrt ( ( x[u] - x[v] ) * ( x[u] - x[v] ) + ( y[u] - y[v] ) * ( y[u] - y[v] ) ); } int main() { scanf ( "%d %d %d", &n, &m, &k ); for ( int i = 1;i <= k;i ++ ) scanf ( "%lf %lf", &x[i], &y[i] ); for ( int i = 1;i <= k;i ++ ) dis[i] = y[i]; dis[k + 1] = m; for ( int i = 1;i <= k + 1;i ++ ) { int t = -1; double now = INF; for ( int j = 1;j <= k + 1;j ++ ) { if ( ! vis[j] && dis[j] < now ) { now = dis[j]; t = j; } } result = max ( dis[t], result ); if ( t == k + 1 ) return ! printf ( "%.9f", result * 0.5 ); vis[t] = 1; for ( int j = 1;j <= k;j ++ ) { double tmp = count ( j, t ); if ( ! vis[j] ) dis[j] = min ( dis[j], max ( dis[t], tmp ) ); } dis[k + 1] = min ( dis[k + 1], m - y[t] ); } return 0; }

T2：飞扬的小鸟

题目

Flappy Bird是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编: 游戏界面是一个长为 n，高为 m 的二维平面，其中有 k 个管道（忽略管道的宽度）。 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 Y。小鸟位于横坐标方向不同位置时，上升的高度 XX 和下降的高度 Y 可能互不相同。 小鸟高度等于 0 或者小鸟碰到管道时，游戏失败。小鸟高度为 m 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

输入格式 第 1 行有 3 个整数 n, m, k分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开； 接下来的 n 行，每行 22 个用一个空格隔开的整数 X 和 Y，依次表示在横坐标位置 0∼n−1 上玩家点击屏幕后，小鸟在下一位置上升的高度 X，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 Y。 接下来 k 行，每行 33 个整数 P, L, H，每两个整数之间用一个空格隔开。每行表示一个管道，其中 P 表示管道的横坐标，L 表示此管道缝隙的下边沿高度，H 表示管道缝隙上边沿的高度（输入数据保证 P 各不相同，但不保证按照大小顺序给出）。

输出格式 共两行。 第一行，包含一个整数，如果可以成功完成游戏，则输出 1，否则输出 0。 第二行，包含一个整数，如果第一行为 1，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

输入输出样例 输入 10 10 6 3 9 9 9 1 2 1 3 1 2 1 1 2 1 2 1 1 6 2 2 1 2 7 5 1 5 6 3 5 7 5 8 8 7 9 9 1 3 输出 1 6

输入 10 10 4 1 2 3 1 2 2 1 8 1 8 3 2 2 1 2 1 2 2 1 2 1 0 2 6 7 9 9 1 4 3 8 10 输出 0 3 说明/提示 【输入输出样例说明】 如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。 【数据范围】 对于 30%的数据：5≤n≤10,5≤m≤10,k=0，保证存在一组最优解使得同一单位时间最多点击屏幕 3次； 对于 50%的数据：5≤n≤20,5≤m≤10，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次； 对于 70%的数据：5≤n≤1000,5≤m≤100； 对于 100%的数据：5≤n≤10000, 5≤m≤1000，0≤k<n, 0 < X < m, 0 < Y < m, 0 < P < n， 0≤L<H≤m, L + 1 < H

题解

考虑$DP[i][j]$：表示当鸟在$(i,j)$时点击屏幕的最少次数 1.鸟是从i-1掉下来的 $$DP[i][j]=DP[i-1][j+y[i]](j+y[i]\le m)$$ 2.鸟是前面i-1多次点击上来的 $$DP[i][j]=DP[i-1][j-x[i]\ast k](j\ge x[i]\ast k)$$ 此时思考时间复杂度$O(nmk)$，肯定TLE 那么就可以将这种情况想成前面跳一次，然后自己往上竖直跳k-1次 $$DP[i][j]=min(DP[i-1][j-x[i]]+1,DP[i][j-x[i]]+1)$$ 3.注意当往上跳过m的时候，鸟就一直在m处往后飞 4.因为x可能会有限制水管，所以算完后把水管赋值成INF，就可以了

---

其实这道题就是一个很板的背包问题，加一点点优化就可以了

代码实现

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define MAXM 2005 #define MAXN 10005 #define INF 0x3f3f3f3f int n, m, k; bool flag[MAXN]; int x[MAXN], y[MAXN]; int low[MAXN], high[MAXN]; int dp[MAXN][MAXM]; int main() { scanf ( "%d %d %d", &n, &m, &k ); for ( int i = 1;i <= n;i ++ ) scanf ( "%d %d", &x[i], &y[i] ); for ( int i = 1;i <= k;i ++ ) { int P, H, L; scanf ( "%d %d %d", &P, &L, &H ); flag[P] = 1; low[P] = L; high[P] = H; } memset ( dp, 0x3f, sizeof ( dp ) ); for ( int i = 1;i <= m;i ++ ) dp[0][i] = 0; for ( int i = 1;i <= n;i ++ ) { for ( int j = x[i] + 1;j <= m + x[i];j ++ ) dp[i][j] = min ( dp[i - 1][j - x[i]] + 1, dp[i][j - x[i]] + 1 ); for ( int j = m;j <= m + x[i];j ++ ) dp[i][m] = min ( dp[i][m], dp[i][j] ); for ( int j = 1;j + y[i] <= m;j ++ ) dp[i][j] = min ( dp[i][j], dp[i - 1][j + y[i]] ); if ( flag[i] ) { for ( int j = 1;j <= low[i];j ++ ) dp[i][j] = INF; for ( int j = high[i];j <= m;j ++ ) dp[i][j] = INF; } } int result = INF; for ( int i = 1;i <= m;i ++ ) result = min ( result, dp[n][i] ); if ( result < INF ) printf ( "1\n%d", result ); else { int i, j, tot = 0; for ( i = n;i >= 1;i -- ) { for ( j = 1;j <= m;j ++ ) if ( dp[i][j] < INF ) break; if ( j <= m ) break; } for ( int j = 1;j <= i;j ++ ) if ( flag[j] ) tot ++; printf ( "0\n%d", tot ); } return 0; }