一个数列.
\(a_1=1,a_2=2\)
当 \(n>2\) 时
\(a_n\left\{\begin{matrix}2a_{n-1},\text{n is an odd number}\\a_{n-1}+r_{n-1},\text{ n is an even number }
\end{matrix}\right.\)
\(S_n=\{a_i-a_j,1 \leqslant j<i\leqslant n\}\)
\(r_n\) 为最小不在 \(S_n\) 中的非负整数.
给出 \(x\),求一对 \((p,q)\) 使得 \(a_p-a_q=x\)
打表+二分.
可以发现 \(\{a_n\}\) 是一个单调递增的数列,而且有 \(*2\) 的递推式存在,所以当 \(n>2log_2 10^9\) 的时候小于 \(10^9\) 的差只可能是相邻的两个数字.
对于前面几行的元素直接打表存起来,后面的就二分一下在表内的元素算一下就可以了.
/**************************************************************
Problem: 4725
User: BeiYu
Language: C++
Result: Accepted
Time:568 ms
Memory:5280 kb
****************************************************************/
#include <cstdio>
#include <utility>
#include <map>
#include <iostream>
using namespace std;
#define mpr make_pair
typedef long long LL;
typedef pair< LL,LL > pr;
const int N = 505;
LL p=1,n=65,m,T;
map< LL,pr > mp;
LL a[N][N];
LL b[N*N];
inline LL in(LL x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar();
while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; }
void _add(LL x,pr y){ mp[x]=y; }
LL _get(){ while(mp.count(p)) p++;return p; }
int main(){
a[2][1]=1,mp[1]=mpr(2,1);
for(int i=3;i<=n;i++){
if(i&1){
for(int j=1;j<i;j++) a[i][i-1]+=a[j][j-1];
a[i][i-1]+=1;
}else{
a[i][i-1]=_get();
}
_add(a[i][i-1],pr(i,i-1));
for(int j=1;j<i-1;j++){
a[i][j]=a[i-1][j]+a[i][i-1];
_add(a[i][j],pr(i,j));
}
}
for(map< LL,pr >::iterator it=mp.begin();it!=mp.end();it++) b[++m]=(*it).first;
for(T=in();T--;){
LL l=1,r=m,mid,x;
x=in();
if(mp.count(x)){ printf("%lld %lld\n",mp[x].first,mp[x].second);continue; }
while(l<=r){
mid=(l+r)>>1;
if(b[mid]<x) l=mid+1;
else r=mid-1;
}
printf("%lld %lld\n",n+(x-r)*2-1,n+(x-r)*2-2);
}return 0;
}
BZOJ 4725: [POI2017]Reprezentacje ró?nicowe
原文：http://www.cnblogs.com/beiyuoi/p/6142935.html