题解 P6393 【隔离的日子】

囧仙

2020-04-15 13:31:35

Solution

- **题意** 给出两个长度为 $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; } ```