题解 P6393 【隔离的日子】

· · 题解

这道题还是比较简单，我相信50\%以上的参赛选手都能够拿到良心出题人的这100pts。（出题人现在才想起交题解）

首先我们观察式子：

(a_j-b_i) \times (b_j+b_i)=a_j \times b_i + a_i \times b_j

发现这个式子非常地不好看，我们想要把下标相同放在一块儿（方便预处理维护），所以我们把式子括号拆开，得：

a_j \times b_j + b_i \times a_j - b_j \times b_i - b_i \times b_i = a_j \times b_i + a_i \times b_j

移项合并同类项，提取公因式得：

(a_j - a_i - b_i) \times b_j = b_i \times b_i

我们设 k = a_j - a_i - b_i

则有:

k \times b_j = b_i \times b_i

和

a_j = a_i + b_i + k

因此我们就列出这样一个不定方程组，只要知道了一个未知项就可以知道其他项。

因此我们考虑枚举k，观察式子可知k必然是b_i \times b_i的因数。而且题目中b_i比较小，因此完全可以去枚举，然后去计算a_i和b_i，之后在判断是否存在a_i和b_i这种元素的情况（可以使用map来维护，其实b的极限数据可以提升到1000去卡\log n的map，但出题人比较良心）。

如果还有不懂的可以去看看下面的代码：

#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5e4 + 5;
map <pair<int , int> , int> M;
int n , a[MAXN] , b[MAXN] , ans[MAXN];
signed main() {
//  freopen("11.in" , "r" , stdin);
//  freopen("11.out" , "w" , stdout);
    scanf("%d" , &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d" , &a[i] , &b[i]);
    }
    for (int i = n; i >= 1; --i) {
        int res = 1e9;
        for (int j = 1; j <= b[i]; ++j) {
            if(b[i] * b[i] % j == 0) {
                int x = 0 , y = 0;
                if(M[make_pair(a[i] + b[i] + j  , b[i] * b[i] / j)]) {
                    x = M[make_pair(a[i] + b[i] + j  , b[i] * b[i] / j)];
                }
                if(M[make_pair(a[i] + b[i] + b[i] * b[i] / j  , j)]) {
                    y = M[make_pair(a[i] + b[i] + b[i] * b[i] / j  , j)];
                } 
                if(x) res = min(res , x);
                if(y) res = min(res , y);
            }
        }
        if(res != 1e9) ans[i] = res;
        else ans[i] = -1;
        M[make_pair(a[i] , b[i])] = i;
    }
    for (int i = 1; i <= n; ++i) printf("%d\n" , ans[i]);
    return 0;
}