WHY TLE?

Purslane @ 2022-12-22 21:44:31

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int T,n,l,p,len[MAXN],pre[MAXN]; char S[MAXN][32]; long double dp[MAXN];
#define fi first
#define se second
int h,t; pair<pair<int,int>,int> ar[MAXN];
long double omega(int lst,int pos) {
    return dp[lst]+pow(abs((long double)(len[pos]-len[lst]+pos-lst-1-l)),p);    
}
int bfind(int i,int lst,int l,int r) {
    int ans=0;
    while(l<=r) {
        int mid=l+r>>1;
        if(omega(lst,mid)<=omega(i,mid)) ans=mid,l=mid+1; else r=mid-1;
    }
    return ans;
}
void output(int k) {
    if(k==0) return ;
    output(pre[k]);
    ffor(i,pre[k]+1,k-1) printf("%s ",S[i]); printf("%s\n",S[k]);   
}
void work(void) {
    scanf("%d %d %d",&n,&l,&p);
    ffor(i,1,n) scanf("%s",S[i]),len[i]=strlen(S[i])+len[i-1];
    h=1,t=0;
    ar[++t]={{1,n},0};
    ffor(i,1,n) {
        while(ar[h].fi.se<i) h++;
        dp[i]=omega(ar[h].se,i),pre[i]=ar[h].se;
        ar[h].fi.fi=i+1; if(ar[h].fi.fi>ar[h].fi.se) h++;
        int L=-1;
        while(h<=t) {
            int lst=ar[t].se,l=ar[t].fi.fi,r=ar[t].fi.se;
            if(omega(i,l)<=omega(lst,l)) {L=l,t--;continue;}
            if(omega(i,r)>=omega(lst,r)) {L=r+1;break;}
            L=bfind(i,lst,l,r-1)+1; ar[t].fi.se=L-1; break;
        }
        if(L<=n) ar[++t]={{L,n},i};
    }
    if(dp[n]>1e18) printf("Too hard to arrange\n");
    else {
        printf("%lld\n",(long long)(dp[n]+0.5));
        output(n);  
    }
    printf("--------------------\n");
}
int main() {
    cin>>T; while(T--) work();
    return 0;
}

by Purslane @ 2022-12-22 21:46:51

突然想起来 pow 好像比快速幂要慢 , 换成快速幂就过了 .

此贴终 .

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int T,n,l,p,len[MAXN],pre[MAXN]; char S[MAXN][32]; long double dp[MAXN];
#define fi first
#define se second
int h,t; pair<pair<int,int>,int> ar[MAXN];
long double pows(long double k,int v) {
    long double res=1;
    while(v) {
        if(v&1) res*=k;
        k*=k,v>>=1;
    }
    return res;
}
long double omega(int lst,int pos) {
    return dp[lst]+pows(abs((long double)(len[pos]-len[lst]+pos-lst-1-l)),p);   
}
int bfind(int i,int lst,int l,int r) {
    int ans=0;
    while(l<=r) {
        int mid=l+r>>1;
        if(omega(lst,mid)<=omega(i,mid)) ans=mid,l=mid+1; else r=mid-1;
    }
    return ans;
}
void output(int k) {
    if(k==0) return ;
    output(pre[k]);
    ffor(i,pre[k]+1,k-1) printf("%s ",S[i]); printf("%s\n",S[k]);   
}
void work(void) {
    scanf("%d %d %d",&n,&l,&p);
    ffor(i,1,n) scanf("%s",S[i]),len[i]=strlen(S[i])+len[i-1];
    h=1,t=0;
    ar[++t]={{1,n},0};
    ffor(i,1,n) {
        while(ar[h].fi.se<i) h++;
        dp[i]=omega(ar[h].se,i),pre[i]=ar[h].se;
        ar[h].fi.fi=i+1; if(ar[h].fi.fi>ar[h].fi.se) h++;
        int L=-1;
        while(h<=t) {
            int lst=ar[t].se,l=ar[t].fi.fi,r=ar[t].fi.se;
            if(omega(i,l)<=omega(lst,l)) {L=l,t--;continue;}
            if(omega(i,r)>=omega(lst,r)) {L=r+1;break;}
            L=bfind(i,lst,l,r-1)+1; ar[t].fi.se=L-1; break;
        }
        if(L<=n) ar[++t]={{L,n},i};
    }
    if(dp[n]>1e18) printf("Too hard to arrange\n");
    else {
        printf("%lld\n",(long long)(dp[n]+0.5));
        output(n);  
    }
    printf("--------------------\n");
}
int main() {
    cin>>T; while(T--) work();
    return 0;
}

by Chthologist7507 @ 2022-12-23 07:59:21

谔谔