笔记 神奇的根号

博客观赏效果更佳

还是第一次写这样的笔记呢。。。开博客以来出来在写简介，就是在写题解。像这样的笔记还是第一次写。不过大家应该都会那种算法的笔记，除非写的特别好（像BYVoid神仙那样），不然基本上也没啥用。不过，这篇不一样，因为它讲的是一个很有意思的根号算法。不过我估计我应该会一直整理这个的。

根号思路1.

第一个思路是我在考场上想出来的。链接：这个题

当然，我发现大家可能看不了这个题。这里给大家我在这个$OJ$上的账号：

用户名：LightningUZ
密码： 123456

但是请不要修改密码，如果修改了请快速改回来。注意，你修改密码是不会影响到我的，顶多就是和老师说一下，换一个账号即可，很简单的。但是会不方便别的同学进行练习，而且以后有比赛了也得再换一个号上来交，很麻烦，浪费时间。

如果您不想交，只想看思路，那好，我贴张图上来：

这个题是hlx学长（清华爷，网名Fuxey）给我们出的。当时他讲题的时候说的正解绝对不是带根号的。但是我考场上就是想到了一个带根号的做法（准确来讲不是带根号吧。。。因为没有控制好平衡）；

当时我先打了一个暴力分。如果$r-l+1<=1e6$，就暴力求（$1e6$的话$nlogn$是能过的）。接下来自然就是想超过$2e6$怎么写了。但是我们发现，超过$2e6$之后并不是让这个问题更复杂了，而是更简单了。因为如果区间长度超过了$1e6$，那么肯定会包含一个末尾有$6$个$0$的数，那么对于我们求最小值的问题来说，$0$的个数少于$6$个的数就肯定没用了。然后我们最多只要算前三个即可。时间复杂度$O(1000)\ast log1000$最多了。

然后总体就能过了。也就是说我们把长度为$1e9$的区间分解成了$1e6\ast 1e3$，然后两段都是能承受的复杂度。

当然，你要常数小一点，就分配的平均一点即珂。您把它分成$1e5\ast 1e4$也珂以。这样就是标准的$\sqrt{n}$算法了（等等。。。仿佛还带个$log$？？？）

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;int calc(int x)
{while(x%10==0){x/=10;}int f=x%10;int a=0;while(x){++a,x/=10;} return (f==5)?(a<<1)-1:(a<<1);
}//计算一个数的link值int p10[10];
vector<int>val[30];
void Build()
{p10[0]=1;for(int i=1;i<=9;i++) p10[i]=p10[i-1]*10; for(int i=1;i<=6;i++){for(int j=p10[i-1];j<p10[i];j++){if (j%10!=0){if (j%10==5){val[(i<<1)-1].push_back(j);}else{val[(i<<1)].push_back(j);}}}}//预处理出每个link值对应的有哪些数，这是老版本的爆搜里面的一个优化//还有一点，这个vector里面是保证有序的
}int l,r;
void Solve()
{if (r-l<=1000000)//小的情况{int ans=10000,ansk=l;for(int i=l;i<=r;i++){int t=calc(i);if (t==1){printf("%lld\n",i);return;}if (t<ans){ans=t;ansk=i;}}printf("%lld\n",ansk);return;}int ans=10000,ansk=l;//别的情况for(int i=1;i<=12;i++)//从小到大枚举link值,准确来讲枚举到6即可，我当时不放心枚举到了12，只是肯定不会被算到答案里罢了{for(int j=0;j<val[i].size();j++)//枚举一个数{for(int tmp=val[i][j];tmp<=r;tmp*=10)//不断在后面加0，看看能不能进来[l,r]范围内{if (tmp>=l)//for循环中保证了<=r，所以{//更新答案if (i<ans){ans=i;ansk=tmp;}else if (i==ans){由于还要找最小的那个数，所以要这一步ansk=min(ansk,tmp);}}}}}if (ans!=10000) {printf("%lld\n",ansk);return;}printf("testdata is very duliu.\n"); //事实证明没有这样的情况2333
}main()
{Build();//别忘了预处理int T;scanf("%lld",&T);while(T-->0){scanf("%lld%lld",&l,&r);Solve();}return 0;
} 

今天(2019.9.8)先到这~