SaikrOJ - ipc2_5

发表于 | 分类于 | 浏览
字数统计: 647 | 阅读时长 ≈ 3

SaikrOJ - ipc2_5

题目大意

有一个数列，第$i$个数为$x_{i}$，它的长度为$n$

给出了$a$，$b$，$c$，要找到一个$i$，使得$a(i+1)x_{i}^{2}+(b+1)ix_{i}+(c+i)=0$成立

如果有多个$i$满足，要最小的那个$i$

有很多组询问需要回答，但是不确定有多少组，$a=b=c=0$标志着提问的结束

为了加大难度，数据被加密了

比如在输入中读到的数为$a_{0}，b_{0}，c_{0}$​，那么真正需要询问的$a=a_{0}+Last，b=b_{0}+Last，c=c_{0}+Last$

$Last$的值是你对上一个询问给出的答案。如果这是第一个询问，那么$Last=0$

所有的询问都会按以上叙述加密，包括结束标志

解题思路

这题乍一看是一个公式题，但是无论你怎么推算没有不了发现任何规律，但是如果对于每一个询问都$O(n)$遍历的话显然会超时，问题似乎陷入了僵局

仔细读题，我们发现最后一组的$a_{0}，b_0，c_0$均为$0$，那么则有：

可以得到：

？？？我们好像发现了什么不得了的东西

也就是说最后一组的答案我们是知道的，那么对于式子：

我们将其写成

其中$a_0，b_0，c_0$为读入的数据，下标$i$为上一次求得的$Last’$，$x_{i}$已知，那么上式中唯一的未知数即为$Last$，也就是说我们可以通过该组的值直接求出上一组的值

移项可以得到：

那么这题就做完了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500000 + 10;
ll x[maxn];
ll a[maxn], b[maxn], c[maxn];
ll ans[maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> x[i];
	int cnt = 1;
	while (cin >> a[cnt] >> b[cnt] >> c[cnt]) ++cnt;
	--cnt;
	ans[cnt - 1] = -a[cnt];
	for (int i = cnt - 1; i >= 1; --i) {
		ll A = (ans[i] + 1) * x[ans[i]] * x[ans[i]];
		ll B = ans[i] * x[ans[i]];
		ll C = ans[i] + c[i];
		ans[i - 1] = -(a[i] * A + (b[i] + 1) * B + C) / (A + B + 1);
	}
	for (int i = 1; i <= cnt - 1; ++i) cout << ans[i] << '\n';
	return 0;
}