P5968 [POI2017]Reprezentacje ró?nicowe（暴力+二分）

· · 题解

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;
}