不开O2会有两个点TLE，请问有更好的改进方法吗

theHermit @ 2020-08-06 21:02:24

const int MAX=15000;
int t,n,num;
int a[2*MAX],b[2*MAX],tmp[2*MAX+5];
int a_len,b_len;
int res;
int add_bit(int *x,int len)
{
    int cntBit=0;
    bool IsFirNumExist=false;
    For(i,1,len+1){
        if(x[i]>=10){
            int yu=x[i]/10;
            x[i]%=10;
            x[i+1]+=yu;
        }
    }
    For(k,1,len+1){
        int i=len-k+1;//highestBit
        if(x[i]!=0&&!IsFirNumExist){
            IsFirNumExist=true;
            cntBit=i;
        }
    }
    return cntBit;
}
void fac()
{
    For(i,1,a_len+1){
        For(j,1,b_len+1){
            tmp[i+j-1]+=a[i]*b[j];
        }
    }
    a_len=add_bit(tmp,a_len+b_len);

    For(i,1,a_len+b_len+1){
        a[i]=tmp[i];
    }
    memset(tmp,0,2*MAX);
}

void show()
{
    For(i,1,a_len+1){
        if(a[a_len+1-i]==num)   res++;
//        cout<<a[a_len+1-i];
    }
    cout<<res<<endl;
    res=0;
//    cout<<endl;
}

void input()
{
    r(t);
    For(index,0,t){
        rr(n,num);
        a[1]=1;
        a_len=b_len=1;
        For(i,1,n+1){
            memset(b,0,2*MAX);
            b[1]=i;
            b_len=i/10+1;
            if(b_len>1) add_bit(b,b_len);
            fac();
        }
        show();
    }
}

by FerventTemp0 @ 2020-08-06 21:12:15

那就开 O3。

by theHermit @ 2020-08-06 21:17:12

@impuk %%%%

by qian_shang @ 2020-08-06 21:22:13

@theHermit 快读快输？

by theHermit @ 2020-08-06 21:24:23

@qian_shang 补上了 谢谢~

#include<bits/stdc++.h>
#define For(i,m,n) for(int i=m;i<n;i++)
#define r(a) read(a)
#define rr(a,b)  read(a),read(b)
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
const ll N=1e4+5;
template <class T>
void read(T &x){
    T f=1;
    x=0;
    char ch=getchar();
    while(ch=='\n'){ch=getchar();}
    while(ch<'0'||ch>'9') if(ch=='-'){f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}
    x*=f;
}

/**
startTime=?
understand_question(?):6.04
endTime=?
AC_Time=?
*/
struct state{//每个工序
    string name;
    string job;
    Ull contri;
    int level;
    int inputOrder;
};
const int MAX=15000;
int t,n,num;
int a[2*MAX],b[2*MAX],tmp[2*MAX+5];
int a_len,b_len;
int res;
int add_bit(int *x,int len)
{
    int cntBit=0;
    bool IsFirNumExist=false;
    For(i,1,len+1){
        if(x[i]>=10){
            int yu=x[i]/10;
            x[i]%=10;
            x[i+1]+=yu;
        }
    }
    For(k,1,len+1){
        int i=len-k+1;//highestBit
        if(x[i]!=0&&!IsFirNumExist){
            IsFirNumExist=true;
            cntBit=i;
        }
    }
    return cntBit;
}
void fac()
{
    For(i,1,a_len+1){
        For(j,1,b_len+1){
            tmp[i+j-1]+=a[i]*b[j];
        }
    }
    a_len=add_bit(tmp,a_len+b_len);

    For(i,1,a_len+b_len+1){
        a[i]=tmp[i];
    }
    memset(tmp,0,2*MAX);
}

void show()
{
    For(i,1,a_len+1){
        if(a[a_len+1-i]==num)   res++;
//        cout<<a[a_len+1-i];
    }
    cout<<res<<endl;
    res=0;
//    cout<<endl;
}

void input()
{
    r(t);
    For(index,0,t){
        rr(n,num);
        a[1]=1;
        a_len=b_len=1;
        For(i,1,n+1){
            memset(b,0,2*MAX);
            b[1]=i;
            b_len=i/10+1;
            if(b_len>1) add_bit(b,b_len);
            fac();
        }
        show();
    }
}

int main()
{
    //其中m(<20)m(<20)表示机器数，n(<20)n(<20)表示工件数）
    input();

    return 0;
}