蓝桥杯2018年第九届真题-自描述序列(二分)

解题思路:
如果依照题意直接模拟会超时，只能通过30%的测试点。

没有找到明显的数学规律，我们试图改进模拟方案。

我们发现直接的模拟方案有一个缺陷，大量重复的数字占据了数组，我们改进此种方案，仅仅all数组记录下标的数字在G序列中的开始出现位置的下标，并且有如下递推方程all[i]=all[i-1]+k(all[k]<=i且all[k+1]>=i) ,具体方程的实现:使用noww记录当前的下标位置,ct记录超越此下标的个数，当ct大于all[noww+1]-all[noww]时将noww加一,ct置为0，依照此方法模拟后，遍历数组all,找到满足all[k]<=n且all[k+1]>=n)的k，依照此方法模拟后，可以通过70%的测试点。

注意到，当模拟完毕后,noww并未到达数组最末尾处，这说明我们还可以用noww继续计算数组后的元素，具体实现方法为，我们首先处理ct,将ct置为最大后，再将noww加一，ct清零，此方案进行完毕后发现得到的元素已经大于等于n,那么我们需要二分寻找第一个大于n的ct,找到后减1即为最后一个小于等于n的ct,将先前的数组长度与ct相加即为答案;若元素小于n，我们先移动noww,同时更新数组的元素，更新策略为，增加noww*(all[noww+1]-all[noww])，若我们在更新过程中找到发现当前元素小于等于n,而后一个大于n,我们停止更新noww,利用二分寻找出第一个大于n的ct,找到后减1即为最后一个小于等于n的ct,将all[noww]与ct和作为答案输出。这样可以通过全部测试点。

注意事项:

数组长度的选取尽量偏大，选择2000000可以承受大约10^16大小的n的结果计算。

代码时间复杂度在于循环的次数，二分是对数级别复杂度，模拟复杂度线性。

实际上第二个改进对n的大小增幅比较明显，在第二个改进前，第一种改进在数组长度取到千万级别时也只能计算10^10大小的n的结果，而改进后仅仅百万级别的长度就可以计算10^16大小的n。

参考代码:

#include<bits/stdc++.h>
using namespace std;
#define maxx 2000000
#define int long long
int ans,n,q,noww,ct;
int all[maxx];
int erfen(int l,int r)
{
   while(l<r)
   {
    int mid=(l+r)/2;
    if(q+mid*noww<=n) l=mid+1;
    else r=mid;
   }
   if(q+l*noww==n) return l;
   else return l-1;
}
signed main()
{
  cin>>n;
  all[1]=1,all[2]=2;
   ct=0,noww=2;
  for(int i=3;i<=maxx;++i)
   {
     all[i]=all[i-1]+noww;
     ++ct;
     if(ct>=all[noww+1]-all[noww]) {++noww;ct=0;}
   }
   
   for(int i=1;i<=maxx;++i) if(all[i]<=n&&all[i+1]-1>=n) ans=i;
   
   if(ans==0)
   { q=all[maxx];
    if(q+(all[noww+1]-all[noww]-ct)*noww>=n)
    {
      ans=maxx+erfen(1,all[noww+1]-all[noww]-ct);
    }
    else
    {
      q=q+(all[noww+1]-all[noww]-ct)*noww;
      ++noww;ct=0;
       for(int i=noww;i<maxx;++i)
       {
         if(q<=n&&q+i*(all[i+1]-all[i])>=n) break;
         q=q+i*(all[i+1]-all[i]);
         ++noww;
       }
       ans=all[noww]+erfen(1,all[noww+1]-all[noww]);
    }
   }
 
   cout<<ans;
 
}