【NOIP2012模拟10.20】友好数对

题目链接

友好数对

题目描述

如果一个数\(a\)能由一个数\(b\)旋转得到，那么我们称为友好数对，如\(12345\)和\(45123\)为友好数对，\(12345\)和\(54321\)不为友好数对。给出两个正整数\(L\)，\(R\)，求有多少友好数对,满足\(L<=a\)

输入格式：

第一行一个整数\(T\)，表示数据组数，每组数据两个正整数\(L\),\(R\)。

输出格式：

对于每组数据，输出一个整数表示答案。

样例输入：

4
1 9
10 40
100 500
1111 2222

样例输出：

0
3
156
287

数据范围：

对于30%的数据满足\(L,R<=1000\)
对于100%的数据满足\(L,R<=2000000\)，\(T<=30\),\(L\),\(R\)位数相同。

时间限制：

2S

空间限制：

256M

提示：

remove!!!

题解

看到此题题面，首先我就想到了暴力。
暴力的时间复杂度是\(O(7TR)\)，略微超出\(10^8\)，貌似会TLE。（后来据某些大佬说暴力似乎能过？！）
于是我就想到了使用预处理来减小时间复杂度。
我用\(s[j]\)表示当\(R=j\)，\(L\)为\(R\)的位数的最小值（如\(R=12345\)时，\(L=10000\)，后面用\(min_L\)表示）时，友好数对的对数。
这样每次求\(L\)，\(R\)时只要\(s[R]-s[L-1]\)，再减去\(min_L\)到\(L-1\)之间每个数所减小的答案数。
这样下来时间复杂度就是\(O(7R+TR)\)，勉强能挤进\(10^8\)。
因为要求出每个数对当前组（我们把能互相旋转得到的数称为一组）在\(R\)以内的个数才能求出\(min_L\)到\(L-1\)之间每个数对答案的影响。
所以我这里用了离线操作，输入的\(R\)多大，就预处理多大。
然后用数组\(mx[]\)来维护这个组当前有多少个数。
上代码：

#include<bits/stdc++.h>
using namespace std;
int t;
int l,r;
int slen(int x){
    int u=0;
    while(x){
        x/=10;
        u++;
    }
    return u;
}
struct aa{
    int l,r,x;
    int ans;
}tt[39];
bool cmp(aa x,aa y){
    return x.r<y.r;
}
struct bb{
    int s,fa,son,mx,val;
}a[2000009];
int len=0;
bool pd(int x){
    while(x){
        if(x==1) return 1;
        if(x%10!=0) return 0;
        x/=10;
    }
}
void add(int x){
    if(pd(x)){
        a[x].s=1;
        a[x].val=a[x].mx=0;
//      printf("*%d %d*\n",x,a[x].val);
        return;
    }
    int ll=slen(x);
    int uuu=x;
    int mx=-1;
    int mn=1;
    for(int i=1;i<ll;i++)
        mn*=10;
    for(int j=1;j<ll;j++){
        int u=x%10;
        x/=10;
        for(int j=1;j<ll;j++)
            u*=10;
        x+=u;
//      printf("!%d %d!\n",x,uuu);
        if(x<uuu && x>=mn){
            if(mx==-1 || x>mx) mx=x;
        }
    }
    a[uuu].val=a[uuu-1].val;
    if(mx==-1) a[uuu].s=a[uuu].mx=1;
    else{
        a[uuu].val+=a[mx].s;
        a[uuu].son=mx;
        a[mx].fa=uuu;
        a[uuu].s=a[mx].s+1;
        a[mx].mx=a[uuu].s;
        int i=mx;
        while(a[i].son){
            i=a[i].son;
            a[i].mx=a[uuu].s;
        }
    }
//  printf("*%d %d %d %d*\n",uuu,mx,a[uuu].val,a[mx].s);
//  if(uuu>=100) exit(0);
}
int ans;
bool cc(aa x,aa y){
    return x.x<y.x;
}
int main(){
    scanf("%d",&t);
    for(int j=1;j<=t;j++){
        scanf("%d%d",&tt[j].l,&tt[j].r);
        tt[j].x=j;
    }
    sort(tt+1,tt+t+1,cmp);
    for(int j=1;j<=t;j++){
        while(len<tt[j].r) add(++len);
        tt[j].ans=a[tt[j].r].val;
//      printf("*%d*\n",tt[j].ans);
        int mn=1,ll=slen(tt[j].l);
        for(int i=1;i<ll;i++)
            mn*=10;
        for(int i=tt[j].l-1;i>=mn;i--){
            if(a[i].fa==0) tt[j].ans-=(a[i].s-1)*a[i].s/2;
            else if(a[i].fa>=tt[j].l){
                tt[j].ans-=(a[i].mx-1)*a[i].mx/2;
                tt[j].ans+=(a[i].mx-a[i].s-1)*(a[i].mx-a[i].s)/2;
            }
        }
    }
    sort(tt+1,tt+t+1,cc);
    for(int j=1;j<=t;j++)
        printf("%d\n",tt[j].ans);
    return 0;
}

【NOIP2012模拟10.20】友好数对

原文：https://www.cnblogs.com/linjiale/p/11603009.html