F - Tickets

F - Ticketshttps://vjudge.csgrandeur.cn/problem/Gym-101911F

 暴力（超时）：

 时间复杂度：2*1e5*1e6，别忘了还有查询

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
signed main()
{
    int n,t;
    scanf("%lld",&n);
    while(n--)
    {
        int sum1,sum2,flag=0;
        int a1,a2,a3,a4,a5,a6;
        scanf("%lld",&t);
        int q=t;
        a6=t%10;
        t/=10;
        a5=t%10;
        t/=10;
        a4=t%10;
        t/=10;
        a3=t%10;
        t/=10;
        a2=t%10;
        t/=10;
        a1=t%10;
        sum1=abs((a1+a2+a3)-(a4+a5+a6));
        for(int j=0;j<=999999&&j<q;j++)
        {
            int i=j;
            a6=i%10;
            i/=10;
            a5=i%10;
            i/=10;
            a4=i%10;
            i/=10;
            a3=i%10;
            i/=10;
            a2=i%10;
            i/=10;
            a1=i%10;
            sum2=abs((a1+a2+a3)-(a4+a5+a6));
            if(sum1>sum2)
            {
//            printf("%d%d%d%d%d%d\n",a1,a2,a3,a4,a5,a6);
                flag++;
            }
        }
        printf("%lld\n",flag);
    }
    

}

打表（预处理）：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int find(int x)
{
    int sum=0,res=0,cnt=0;
    while(x)
    {
        res++;
        if(res<=3)
            sum+=x%10;
        else
            cnt+=x%10;
        x/=10;
    }
    int ans=abs(cnt-sum);
    return ans;
}
int main()
{
    for(int i=0;i<=999999;i++)//记录每个数对应有多少个绝对值比它小的数的个数（预处理）
    {
        int j=find(i);
        t[j]++;
        for(int k=0;k<j;k++)
        {
            a[i]+=t[k];
        }
    }
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",a[x]);
    }
    return 0;
}