题解 P6393 【隔离的日子】

囧仙 · 2020-04-15 13:31:35 · 题解

• 题意

  给出两个长度为 n 的序列 a,b，对于每个 i，求一个最小的 j，使得 (a_j - b_i) \times (b_j + b_i) = a_j \times b_i + a_i \times b_j，找不到输出 -1

• 解析

  首先肯定要对那个式子进行化简：

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

  发现两边都有 a_j \times b_i，这样就消去了一项，变为：

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

  然后你就会发现，未知量太多了，有 a_j,b_j 两个，做不了

  那么这个时候怎么办呢？

  弃题，跑路

  这种情况一般需要去看下数据范围

  1 \le b_i \le 100

  考虑对于每个 i 进行求解时枚举一个 b_j，这样未知量就只有 a_j 了

  枚举了 b_j，等式右边的值我们都是已知的，也就可以解出 a_j 了

  于是，问题转化为：5 \times 10 ^ 6 次求 i 右边第一个 a_j = x,b_j = y 的数的位置

  考虑开 100 个 set，第 i 个 set 存所有 b_j = i 的 j，这样满足了 b_j = y 的限制

  然后从左往右求解每个询问，每次从 i 移动到 i + 1 时把 i + 1 删掉，这样满足了在 i 右边的限制

  然后这题就做完了，答案是每个 $b_j$ 求出的答案的 $\min

  时间复杂度：O(n \log n \times b_i)

  其实我觉得暴力没准能卡过去

代码：

#include <cstdio>
#include <set>
using namespace std;
#define ll long long
int n;
ll a[50005],b[50005];

struct node{
    ll val;//存的是编号
    friend bool operator<(node x,node y){
        if(a[x.val] == a[y.val]) return x.val < y.val;//当值相同的时候，编号在前面的更优
        return a[x.val] < a[y.val]; //从小到大排序
    }
};

set <node> fnd[105];

int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        scanf("%lld%lld",&a[i],&b[i]);
        fnd[b[i]].insert({i});
    }
    for(int i = 1;i <= n;i++){
        fnd[b[i]].erase({i});
        int ans = 0x3f3f3f3f;
        for(int j = 1;j <= 100;j++){
            ll val = a[i] * j + b[i] * j + b[i] * b[i];
            if(val % j != 0) continue;//方程无整数解，舍去
            a[0] = val / j;
            set<node>::iterator res = fnd[j].lower_bound({0});
            if(res != fnd[j].end() && a[res->val] == val / j){//lower_bound 找不到会返回end，要判一下
                if(ans > res->val) ans = res->val;
            }
        }
        if(ans == 0x3f3f3f3f) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}