题解：CF1368B Codeforces Subsequences

yueyixuan1 · 2026-05-10 14:53:05 · 题解

前言

貌似目前题解区没有。

有的话请无视上一句话。

思路

设 c 出现 c_1 次，o 出现 c_2 次，以此类推，s 出现 c_{10} 次。那么有 c_1 \times c_2 \times \dots \times c_{10} 个这样的子串。

因为要求数量 \ge k，当长度为 x 可以的时候，x+1 以及以后一定都有方法 \ge k。因此有单调性。考虑二分。

那 check 函数怎么写呢？

对于长度为 len 的话，考虑贪心，因为需要个数尽可能多，所以我们考虑贪心：让所有出现的数量尽可能平均。于是便很容易实现。先处理贪心后，然后将那几个出现的数相乘，得到子串数量，然后看到没到 k 即可。

二分完后，按照 check 函数里的方法写就可以辣。

核心代码

int n,k;
int ans[7891];

inline bool check(int M){
    int res=1;
    for(int i=1;i<=10;i++){
        ans[i]=M/10+(i<=(M%10));
        res*=ans[i];
        if (res>=k){
            return true;
        }
    }
    return res>=k;
}

inline void solve(){
    k=read();
    int L=9,R=401;
    while(L+1<R){
        int M=(L+R)>>1;
        if (check(M)){
            R=M;
        } else{
            L=M;
        }
    }
    if (check(L)){
        R=L;
    }
    int res=1;
    for(int i=1;i<=10;i++){
        ans[i]=R/10+(i<=(R%10));
        res*=ans[i];
    }
    for(int i=1;i<=10;i++){
        for(int j=1;j<=ans[i];j++){
            if (i==1){
                printf("c");
            }
            if (i==2){
                printf("o");
            }
            if (i==3){
                printf("d");
            }
            if (i==4){
                printf("e");
            }
            if (i==5){
                printf("f");
            }
            if (i==6){
                printf("o");
            }
            if (i==7){
                printf("r");
            }
            if (i==8){
                printf("c");
            }
            if (i==9){
                printf("e");
            }
            if (i==10){
                printf("s");
            }
        }
    }
    printf("\n");
}

注意

上面的代码并没有 AC。原因在于 k=1 的时候，ans_i=0，不会输出。

于是需要特判 k=1 的时候。

真正的核心代码

int n,k;
int ans[7891];

inline bool check(int M){
    int res=1;
    for(int i=1;i<=10;i++){
        ans[i]=M/10+(i<=(M%10));
        res*=ans[i];
        if (res>=k){
            return true;
        }
    }
    return res>=k;
}

inline void solve(){
    k=read();
    if (k==1){
        return printf("codeforces\n"),void();
    }
    int L=9,R=401;
    while(L+1<R){
        int M=(L+R)>>1;
        if (check(M)){
            R=M;
        } else{
            L=M;
        }
    }
    if (check(L)){
        R=L;
    }
    int res=1;
    for(int i=1;i<=10;i++){
        ans[i]=R/10+(i<=(R%10));
        res*=ans[i];
    }
    for(int i=1;i<=10;i++){
        for(int j=1;j<=ans[i];j++){
            if (i==1){
                printf("c");
            }
            if (i==2){
                printf("o");
            }
            if (i==3){
                printf("d");
            }
            if (i==4){
                printf("e");
            }
            if (i==5){
                printf("f");
            }
            if (i==6){
                printf("o");
            }
            if (i==7){
                printf("r");
            }
            if (i==8){
                printf("c");
            }
            if (i==9){
                printf("e");
            }
            if (i==10){
                printf("s");
            }
        }
    }
    printf("\n");
}