首页 > 代码库 > 模拟。。。 Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C
模拟。。。 Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C
题目大意:给你一个n*m的矩阵,再给你一个小球,从(0,0)以sqrt(2)/s的速度向右上角出发,遇到边框会反弹,遇到角落就直接停止,给你一些点,问小球第一次经过这些点所需要的时间。
思路:模拟一下即可。。。注意爆int
//看看会不会爆int!数组会不会少了一维!//取物问题一定要小心先手胜利的条件#include <bits/stdc++.h>using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha printf("haha\n")const int maxn = 5e5 + 5;map<pair<LL, LL>, int> line;map<pair<LL, LL>, int> ID;vector<LL> v[maxn];bool vis[maxn];LL X[maxn], Y[maxn];LL ans[maxn];int n, m, k;int cnt;int get_id(LL k, LL b){ if (ID.count(mk(k, b))) return ID[mk(k, b)]; ID[mk(k, b)] = ++cnt; return cnt;}bool check(LL k, LL b){ if (line.count(mk(k, b))) return true; line[mk(k, b)] = 1; return false;}void cal_time(int k, int b, LL x, LL y, LL colck){ if (ID.count(mk(k, b)) == 0) return ; for (int i = 0; i < v[ID[mk(k, b)]].size(); i++){ int pos = v[ID[mk(k, b)]][i]; if (vis[pos]) continue; vis[pos] = true; LL tx = abs(X[pos] - x), ty = abs(Y[pos] - y); ans[pos] = colck + min(tx, ty); }}void solve(){ memset(ans, -1, sizeof(ans)); LL colck = 0; int ty = 1; int x = 0, y = 0; while(true){ int nx, ny; if (ty == 1){ if(check(1, y - x)) break; cal_time(1, y - x, x, y, colck); nx = n - x, ny = m - y; if (nx < ny) x = n, y = y + nx, ty = 2; if (nx > ny) x = x + ny, y = m, ty = 4; } else if (ty == 2){ if(check(-1, y + x)) break; cal_time(-1, y + x, x, y, colck); nx = x, ny = m - y; if (nx < ny) x = 0, y = y + nx, ty = 1; if (nx > ny) x = x - ny, y = m, ty = 3; } else if (ty == 3){ if(check(1, y - x)) break; cal_time(1, y - x, x, y, colck); nx = x, ny = y; if (nx < ny) x = 0, y = y - nx, ty = 4; if (nx > ny) x = x - ny, y = 0, ty = 2; } else if (ty == 4){ if(check(-1, y + x)) break; cal_time(-1, y + x, x, y, colck); nx = n - x, ny = y; if (nx < ny) x = n, y = y - nx, ty = 3; if (nx > ny) x = x + ny, y = 0, ty = 1; } colck += min(nx, ny); if(nx == ny) break; }}int main(){ cin >> n >> m >> k; for (int i = 1; i <= k; i++){ scanf("%lld%lld", X + i, Y + i); int t1 = get_id(-1, X[i] + Y[i]); int t2 = get_id(1, Y[i] - X[i]); v[t1].push_back(i); v[t2].push_back(i); } solve(); for (int i = 1; i <= k; i++){ printf("%lld\n", ans[i]); } return 0;}
模拟。。。 Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。