还是第一次写这样的笔记呢。。。开博客以来出来在写简介，就是在写题解。像这样的笔记还是第一次写。不过大家应该都会那种算法的笔记，除非写的特别好（像BYVoid神仙那样），不然基本上也没啥用。不过，这篇不一样，因为它讲的是一个很有意思的根号算法。不过我估计我应该会一直整理这个的。
根号思路1.
第一个思路是我在考场上想出来的。链接：这个题
当然，我发现大家可能看不了这个题。这里给大家我在这个上的账号：
用户名：LightningUZ
密码： 123456
但是请不要修改密码，如果修改了请快速改回来。注意，你修改密码是不会影响到我的，顶多就是和老师说一下，换一个账号即可，很简单的。但是会不方便别的同学进行练习，而且以后有比赛了也得再换一个号上来交，很麻烦，浪费时间。
如果您不想交，只想看思路，那好，我贴张图上来：
这个题是hlx学长（清华爷，网名Fuxey）给我们出的。当时他讲题的时候说的正解绝对不是带根号的。但是我考场上就是想到了一个带根号的做法（准确来讲不是带根号吧。。。因为没有控制好平衡）；
当时我先打了一个暴力分。如果，就暴力求（的话是能过的）。接下来自然就是想超过怎么写了。但是我们发现，超过之后并不是让这个问题更复杂了，而是更简单了。因为如果区间长度超过了，那么肯定会包含一个末尾有个的数，那么对于我们求最小值的问题来说，的个数少于个的数就肯定没用了。然后我们最多只要算前三个即可。时间复杂度最多了。
然后总体就能过了。也就是说我们把长度为的区间分解成了，然后两段都是能承受的复杂度。
当然，你要常数小一点，就分配的平均一点即珂。您把它分成也珂以。这样就是标准的算法了（等等。。。仿佛还带个？？？）
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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)先到这~