NKOJ 4247 老蒋的数列（乱搞）

发表于 |
字数统计: 725字 | 阅读时长 ≈ 4min

P4247老蒋的数列

问题描述

这里写图片描述

输入格式

第一行一个整数n

接下来n行每行一个整数xi

输出格式

输出共包含n行

每行两个正整数q，p（要求q>p），表示与xi相对应的整数对

样例输入

4
20
36
100
666

样例输出

6 1
38 37
9 2
1156 1155

提示

对于30%的数据，输出的p，q均不超过20

对于另外40%的数据，保证p，q之差为1

对于100%的数据，n<=250000，xi<=10^9

数据是有梯度的

观察发现，$a[i]$的增长速度非常的快，那么当$a[i]$大于$10^9$之后，当$a[i]=2\times a[i-1]$，$a[i]-a[i-1]$的值大于$10^9$就不会对答案产生影响了。

基于这一点，本题可以先递推一部分，处理出一部分差值，存到数据结构里面，然后再处理较大的一部分。递推的复杂度$O(n^2)$

然后需要考虑当$a[i]$比较大的时候，怎么求出所求数对。显然这时差值只能是$b[i]$，即$a[i]=a[i-1]$，那么观察$b[i]$的增长，发现$b[i+2]=b[i]+1$，然而有的时候$b[i+2]=b[i]+k$，这种时候是由于前面递推的一部分中出现了$b[i]+1$，那么可以用二分查找

对于一个询问$x​$，当他大于了我们递推出来的最大差值$T​$时，二分查找$x​$之前，到递推终点之间，有多少个差值已经出现了，然后考虑$b[i]​$何时达到$x​$，显然如果$b[i]+1​$没有出现过，那么$b[i+2]=b[i]+1​$，那么只需要$递推终点+2\times(x-T)-2\times已出现差值数​$

代码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
struct node{ll d,x,y;};
bool cmp(node a,node b)
{return a.d<b.d;}
ll n,A[1234],B[1234],tot;
node C[5555],tmp;
map<ll,bool>Q;
int main()
{
    ll i,j,k=3,x;
	scanf("%lld",&n);
	A[1]=1;A[2]=2;B[1]=1;B[2]=2;
	C[++tot].d=1;C[tot].x=2;C[tot].y=1;
	for(i=3;i<=79;i++)
	{
		if(i&1)A[i]=A[i-1]*2;
		else A[i]=A[i-1]+B[i-1];
		for(j=1;j<i;j++)C[++tot].d=A[i]-A[j],C[tot].x=i,C[tot].y=j,Q[A[i]-A[j]]=1;
		while(Q[k])k++;
		B[i]=k;
	}
	sort(C+1,C+tot+1,cmp);
	tmp.d=k-1;
	k=lower_bound(C+1,C+tot+1,tmp,cmp)-C;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		if(x==0){printf("62 61\n");continue;}
		tmp.d=x;
		j=lower_bound(C+1,C+tot+1,tmp,cmp)-C;
		if(C[j].d==x)printf("%lld %lld\n",C[j].x,C[j].y);
		else printf("%lld %lld\n",C[k].x+2*(x-C[k].d)-2*(j-1-k),C[k].y+2*(x-C[k].d)-2*(j-1-k));
	}
}