下发文件
最长反链
首先，如果 l 和 r 的数字位数相同，那么肯定是 r - l + 1.
为了能够增加更多的数，一定是选择最大的那些数.
证明：
一个 n + 1 位数中出现 n 连续数字的种类数一定大于 n 位数中连续数字的种类数.
所以，只需要找出从 1000...0 （就是 r的位数的最开始那个数）到 r 的所有数的个数，这一定就是最大值.
那么前面位数少的是否也能选呢？
答案是，如果 r 开头那一位是 1，那是可以的.
大于 1 的话，前面的数字一定都遍及过了，直接输出即可.
否则，找到比 r 位数少 1 的数中首个没有出现过的数（其实就是 r 减去一个 1000...0）.
点击查看代码
#include<bits/stdc++.h>
#define ll int
#define rg register
#define rll rg ll
#define maxn 50001
#define put_ putchar(' ')
#define putn putchar('\n')
using namespace std;
inline ll read()
{
rll f=0,x=0;rg char ch=getchar();while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();return f?-x:x;
}
inline void write(rll x) { if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10|'0'); }
ll n,l,r,tl,tr,lnum,rnum;
int main()
{
n=read();while(n--)
{
tl=l=read();tr=r=read();lnum=rnum=0;
while(tl) lnum++,tl/=10;while(tr) rnum++,tr/=10;
if(lnum==rnum) { write(r-l+1);putn; continue; }
if(r/(ll)pow(10,rnum-1)==1) write(r-max(l-1,max(r/10,r%(ll)pow(10,rnum-1)))); else write(r-pow(10,rnum-1)+1);
putn;
}
return 0;
}
2A+x
首先抛弃 v，只看乘 2 的部分.
首先找到最大的小于等于序列中最大值的数，不断乘 2 直至再乘 2 就大于最大值了. 然后把加 1 考虑进来，发现最后一次加 1 等于在新数上加 1，倒数第二次加 1 等于在新数上加 2，以此类推.
然后就是找到最小的大于等于序列中最大值的数，从 1,2,4,8,16,... 中找到最小的还能加（前面用的次数小于 n 的数），加一下. 将这个数与不断乘 2 后加数前的取一个最小值（想一想，为什么？）.
这样两个数就都有了.
for(rll i=1;i<=n;i++) a[i]=read(),mx=max(mx,a[i]);
for(rll i=1;i<=n;i++)
{
b[i].nxnum=cnt=-1; while(a[i]<<1<=mx) a[i]<<=1,cnt++; b[i].a=a[i];
for(rll j=cnt;~j;j--)
{
num=min((mx-b[i].a)/(1<<j),x); b[i].a+=(1<<j)*num; if(num^x) b[i].nxnum=j;
}
if(b[i].a==mx) { b[i].nxnum=mx; continue; }
if(~b[i].nxnum) b[i].nxnum=min(b[i].a+(1<<b[i].nxnum),a[i]<<1); else b[i].nxnum=a[i]<<1;
}
忘了说了，如果能到达最大值，那么下一个的数也应设为和它一样的，否则无贡献.
如果当前值比最大值的差小于 x，那么一定能够消去，特判即可.
// 上下两种写法均可
if((b[n].a<<1)-(b[1].a<<1)-x<b[n].a-b[1].a) { puts("0"); return 0; }
if(b[n].a-b[1].a>=x) { puts("0"); return 0; }
按照那个比最大值小的数大小排序，不断把最小的值变成大的值，那么有了最大值，而且因为是单调的，最小值一定是它的下一个.
因此这么查询，注意在每次枚举的时候也要特判：
ans=b[n].a-b[1].a;mn=b[n].a;
for(rll i=1;i<n;i++) if(b[n].a-b[i].a>=x)/*特判*/
{
mn=max(mn,b[i].nxnum);
ans=min(ans,mn-b[i+1].a);
}
// else break; 可写可不写，因为大数对答案无贡献