自动搬运

查看原文

来自洛谷，原作者为

	木xx木大 已经 AFO 的菜鸡 OIer

搬运于2025-08-24 22:16:05，当前版本为作者最后更新于2020-11-22 18:53:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5968 [POI2017]Reprezentacje ró?nicowe

第一眼，不会。看完题解，这是个sb题，我是sb

仔细观察题面可以发现，每出现两个数，就会有一次$\times 2$ 的操作，所以 $10^9$ 以内的数不会超过 $2 \log10^9$个。对于大小超过 $10^9$ 的数，奇数位和前一项偶数位的差也大于 $10^9$ ，因此能组成题目要求的 repr 函数的只有偶数项和前一位奇数项。

所以我们可以暴力打出 $10^9$ 以内的数（实际上只有56项）。查询时，如果在前面56项里查到了就输出。否则需要二分，在表里找到最大的小于它的数。因为 $r$ 是递增的，如果当前 $x$ 代表了一个 $r_i$，也就意味着前面的 $x-1$ 个数都已经被代表了。又因为表里有 $num$ 个，这是前56项里有的。那么 $x-num$ 就是从56项后的第几个数对有这样一个差 $x$ 。每一个数对2个数，又因为这样的计算包含了最后差等于 $x$ 的那个数对，所以答案就是$(56+(x−num)\times 2，56+(x−num)\times2−1)$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,pair<int,int> > s;
map<ll,pair<int,int> >::iterator it;
ll a[110],b[10010];
const ll INF=1e9;
int main()
{
	int q,n,cnt=0;
	scanf("%d",&q);
	a[1]=1,a[2]=2;
	s[1]=make_pair(2,1);
	for(n=3;;n++)
	{
		if(n&1)a[n]=a[n-1]<<1;
		else for(int i=1;;i++)
		{
			if(!s.count(i))
			{
				a[n]=a[n-1]+i;
				break;
			}
		}
		for(int i=1;i<n;i++)
			s[a[n]-a[i]]=make_pair(n,i);
		if(!(n&1)&&a[n]>INF)break;
	}
	for(it=s.begin();it!=s.end();it++)
		b[++cnt]=it->first;
	while(q--)
	{
		int x;
		scanf("%d",&x);
		if(s.count(x))
			printf("%d %d\n",s[x].first,s[x].second) ;
		else 
		{
			int y=lower_bound(b+1,b+cnt+1,x)-b-1;
			printf("%d %d\n",n+(x-y)*2,n+(x-y)*2-1);
		}
	}
	return 0;
}