Codeforces - 1202D - Print a 1337-string...

https://codeforces.com/contest/1202/problem/D

当时想的构造是中间两个3，然后前后的1和7组合出n，问题就是n假如是有一个比较大的质数因子或者它本身就是质数就会超长度。事实上程序会正确执行并分解成两个超大质数，不断putchar导致TLE。

正确的做法是通过3来主要组成答案，考虑133..337，中间有x个3，则有C(x,2)个组合，很明显可以发现在x=45000附近超过1e9的上限，而剩下的余数不会超过x=45000（或者在这个附近？）。

考虑怎么添加这个余数，可以在末尾用1来凑，或者在开头用7来凑。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll C[460005];

int Ctop=460000;

void initC(){

    for(int i=1;i<=Ctop;++i)

        C[i]=(1ll*i*(i-1))/2;

    /*for(int i=1;i<=100;++i)

        cout<<C[i]<<endl;*/

    return;

}

int n;

void solve(){

    int num3=(upper_bound(C+1,C+1+Ctop,n)-C)-1;

    //cout<<num3<<endl;

    //cout<<C[num3]<<endl;

    int num7=n-C[num3];

    printf("133");

    for(int i=1;i<=num7;++i)

        printf("7");

    for(int i=1;i<=num3-2;++i)

        printf("3");

    printf("7\n");

    return;

}

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    initC();

    int T;

    while(~scanf("%d", &T)) {

        while(T--) {

            scanf("%d",&n);

            solve();

        }

    }

    return 0;

}

巴特西

Codeforces - 1202D - Print a 1337-string... - 构造

最新文章

热门文章