标签：奇数 int 56 POI2017 偶数 num 1e9
题意
一个数列a
当 n≤2 时，\(a_{n}\)=n
当 n>2 时，且 n 为奇数时，\(a_{n}\)=2×\(a_{n-1}\)
当 n>2 时，且 n 为偶数时，\(a_{n}\)=\(a_{n-1}\)+\(r_{n-1}\)
\(r_{n}\)=mex( \(\mid\)\(a_{i}\) – \(a_{j}\)\(\mid\) ) (1≤i≤j≤n-1),mex(S)表示最小的不在S里的非负整数。
n 次询问每次给一个正整数 x 要求把 x 表示为 \(a_{i}\)–\(a_{j}\) 并输出 i 和 j 。
题解
因为任意两个a的差不会相同，且\(a_{56}\)=1062283805，超出1e9。对于大小超过1e9的数，奇数位和前一项偶数位的差也大于1e9， 所以此时答案，不超过1e9的差只能是偶数位与前一项奇数位的差。
所以我们可以暴力打出1e9以内的数（实际上只有56项）。查询时，如果在前面56项里查到了就输出。否则因为此时的答案递增，所以每一个在前56项查不到的x，都从小到大依次对应一个1e9以外的一对数。设num为前面暴力打出的小于x的差的数量，则答案为（56+（x-num）×2，56+（x-num）×2-1)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
map<int,pair<int,int>>mp;
set<int> s;
vector<int> v;
int a[60],T;
int main(){
a[1]=1,a[2]=2;
s.insert(1);
mp[1]={2,1};
v.push_back(1);
for(int i=3;i<=56;i++){
if(i&1){
a[i]=2*a[i-1];
}
else{
int j=1;
while(1){
if(!s.count(j)){
a[i]=a[i-1]+j;
break;
}
j++;
}
}
for(int j=1;j<i;j++){
if(!s.count(a[i]-a[j])){
mp[a[i]-a[j]]={i,j};
s.insert(a[i]-a[j]);
v.push_back(a[i]-a[j]);
}
}
}
sort(v.begin(),v.end());
scanf("%d",&T);
while(T--){
int x;
scanf("%d",&x);
if(mp.count(x)){
printf("%d %d\n",mp[x].first,mp[x].second);
}
else{
int k=upper_bound(v.begin(),v.end(),x)-v.begin();
printf("%d %d\n",56+(x-k)*2,56+(x-k)*2-1);
}
}
return 0;
}
标签：奇数,
int,
56,
POI2017,
偶数,
num,
1e9
From： https://www.cnblogs.com/qianbj/p/17712846.html