Codeforces 724C - Ray Tracing

#数学 #数论 #思维
Published on 2016-10-10

题目地址

描述

一束激光从 (0,0)(0, 0) 出发，速度向量为 (1,1)(1, 1)，每秒行走 2\sqrt 2 个单位。矩形以 (0,0)(0, 0) 为左下角，(n,m)(2≤n,m≤105)(n, m)(2\le n,m\le {10}^5) 为右上角，这一束激光只能在矩形内部传播，碰到矩形边缘则反射（遵循光的反射定律），如果传播到矩形的角则停止传播。

现在有 k(k≤105)k(k\le {10}^5) 个传感器，第 ii 个的坐标为 ，请问对于每个传感器，激光最早在什么时候经过它？输出最早的时间，若不经过，输出 -1。

分析

这个题显然不好模拟，怎么办呢？在初中物理中有虚像这一概念，光线反射集中某个点，可以看做是光线直射到某个点关于反射面的对称点，我们利用这一性质来进行解题。

我们只对矩形的左右边缘处理虚像，如果上下边缘也处理的话，貌似就不太好做了。我们观察一下 n=3,m=4n = 3, m = 4 的情况：

可以发现最后光线一定会打到角上，终点的横坐标是 lcm(n,m)\mathrm{lcm}(n, m)。可以发现对于点 (x,y)(x, y)，它的坐标变成了两种：(x+k⋅2n,y)(x + k\cdot 2n, y) 以及 (−x+(k+1)⋅2n,y)(-x + (k + 1) \cdot 2n, y)，其中都有 k≥0k \ge 0。无论是哪一种，我们只需要找到一个点，满足它在光线上，而且横坐标最小。有解的充要条件是横坐标不能超过 lcm(n,m)\mathrm{lcm}(n, m)。

如何判断一个点是否在光线上面？假设某个点的形式为：(k⋅2n+a,b)(k\cdot 2n + a, b)，那么光线有两种，一种是上升的，此时可以列出方程：

对于下降的光线，也可以列出方程：

于是无论是上升的或者是下降的光线，我们都可以列出一个关于 kk 的方程，我们只需要解出一个最小的 kk 来，就能解出最小的横坐标，解方程可以采用扩展欧几里德算法，也可以预处理出 visi\mathrm{vis}_i 表示满足 k⋅2n≡i(mod2m)k\cdot 2n \equiv i \pmod {2m} 的最小的 kk。

对于每个传感器 (x,y)(x, y)，我们有四种情况，用 work(a, b) 表示求解方程 k⋅2n+a+b≡0(mod2m)k\cdot 2n + a + b \equiv 0 \pmod {2m}，返回最小的横坐标 k⋅2n+ak\cdot 2n + a，则四种情况都可以用 work(a, b) 一并求解。

如果采用扩展欧几里德算法解方程：时间复杂度：O(klogmin(n,m))O(k\log\min(n, m))，不需要额外的空间。

如果采用预处理的方法解方程：时间复杂度：O(n+k)O(n + k)，额外空间消耗： O(m)O(m)。

代码

//  Created by Sengxian on 2016/10/10.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 724C 同余方程
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_K = 100000 + 3, MAX_M = 100000 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, N, M;
ll vis[MAX_M * 2];

inline ll mod(ll a) {
    return (a % M + M) % M;
}

inline ll work(ll a, ll b) {
    //(kN + a + b) % M = 0
    //(kN + a) is x coordinate
    a = a, b = b;
    ll t = mod(-(a + b));
    if (vis[t] == -1) return INF;
    else return (ll)vis[t] * N + a;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt(), k = ReadInt();
    N = n * 2, M = m * 2;
    memset(vis, -1, sizeof vis);
    ll now = 0, cnt = 0;
    //注意这里所有的 vis[now] 都是合法的，因为 now 的实际值不超过 lcm(n, m)
    while (vis[now] == -1) {
        vis[now] = cnt++;
        (now += N) %= M;
    }
    for (int i = 0, x, y; i < k; ++i) {
        x = ReadInt(), y = ReadInt();
        ll t = min(min(work(x, -y), work(x, y)), min(work(N - x, -y), work(N - x, y)));
        if (t != INF) printf("%lld\n", t);
        else puts("-1");
    }
    return 0;
}
Codeforces 724F - Uniformly Branched Trees