题解 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$ 右边的限制
$a_j = x$ 的限制可以让 set 按大小关系排序,然后用 lower_bound 求出来
然后这题就做完了,答案是每个 $b_j$ 求出的答案的 $\min$
时间复杂度:$O(n \log n \times b_i)$
~~其实我觉得暴力没准能卡过去~~
代码:
```cpp
#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;
}
```