首页 > 代码库 > 模拟。。。 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;}
View Code

 

模拟。。。 Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C