首页 > 代码库 > UVA 718 - Skyscraper Floors(数论)
UVA 718 - Skyscraper Floors(数论)
UVA 718 - Skyscraper Floors
题目链接
题意:在一个f层高的楼上,有e个电梯,每个电梯有x,y表示y + k * x层都可以到,现在要问从a层能否到达b层(中间怎么换乘电梯不限制)
思路:对于两个电梯间能不能换乘,只要满足y[i] + xx x[i] == y[j] + yy y[j].然后移项一下,就可以用拓展欧几里得求解,进而求出x,y的通解,然后利用通解范围x‘ >= 0, y‘ >= 0, x[i]x‘ + y[i] <= f, x[j] y‘ + y[j] <= f,求出通解中t的上限和下限,就可以判断有无解了,然后就建图,把两个可以换乘电梯建边,然后在让a, b分别和电梯判断能不能到,能到建边,最后dfs一遍就能判断能否达到了。
代码:
#include <stdio.h> #include <string.h> #include <vector> #include <math.h> using namespace std; const int INF = 0x3f3f3f3f; int t, f, e, a, b, x[105], y[105], vis[105]; vector<int> g[105]; int exgcd(int a, int b, int &x, int &y) { if (!b) {x = 1; y = 0; return a;} int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } void build(int v, int u, int i) { if (v < y[i]) return; if ((v - y[i]) % x[i] == 0) { g[u].push_back(i); g[i].push_back(u); } } void build2(int i, int j) { int xx, yy; int a = x[i], b = -x[j], c = y[j] - y[i]; int d = exgcd(a, b, xx ,yy); if (c % d) return; int down = -INF; int up = INF; if (b / d > 0) { down = max(down, (int)ceil(-xx * c * 1.0 / b)); up = min(up, (int)floor(((f - y[i]) * 1.0 * d / x[i] - xx * c * 1.0) / b)); } else { down = max(down, (int)ceil(((f - y[i]) * 1.0 * d / x[i] - xx * c * 1.0) / b)); up = min(up, (int)floor(-xx * c * 1.0 / b)); } if (a / d > 0) { down = max(down, (int)ceil((yy * c * 1.0 - (f - y[j]) * 1.0 * d / x[j]) / a)); up = min(up, (int)floor(yy * c * 1.0 / a)); } else { down = max(down, (int)ceil(yy * c * 1.0 / a)); up = min(up, (int)floor((yy * c * 1.0 - (f - y[j]) * 1.0 * d / x[j]) / a)); } if (down > up) return; g[i].push_back(j); g[j].push_back(i); } bool dfs(int u) { if (u == e + 1) return true; vis[u] = 1; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (vis[v]) continue; if (dfs(v)) return true; } return false; } int main() { scanf("%d", &t); while (t--) { memset(g, 0, sizeof(g)); scanf("%d%d%d%d", &f, &e, &a, &b); for (int i = 1; i <= e; i++) { scanf("%d%d", &x[i], &y[i]); build(a, 0, i); build(b, e + 1, i); } for (int i = 1; i <= e; i++) { for (int j = i + 1; j <= e; j++) { build2(i, j); } } memset(vis, 0, sizeof(vis)); if (dfs(0)) printf("It is possible to move the furniture.\n"); else printf("The furniture cannot be moved.\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。