Codeforces Global Round 8 B. Codeforces Subsequences

女爷i 2023-02-19 03:30 4阅读 0赞

[题目链接][Link 1]

思路：最少的字符数量，必然是利用组合数进行乘法运算。codeforces一共10个字符，当每个字符都增加一个的话，有2^10种选择，同理，每个字符都增加2个的话，有3^10种选择.....

所以首先需要找到x^10 >k 。然后，按位数减小x即可。

#include <bits/stdc++.h>
    using namespace std;
    long long get(long long k)
    {
        int j=k;
        for(int i=1;i<10;i++)
        {
            k*=j;
        }
        return k;
    }
    int main()  
    {  
        #ifndef ONLINE_JUDGE
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
        #endif
        long long k;
        cin>>k;
        if(k==1) cout<<"codeforces"<<endl;
        else
        {
            int d=2;
            while(get(d)<k) d++;
            long long tmp=get(d);
            int bit[11];
            for(int i=0;i<10;i++) bit[i]=d;
            int f=0;
            //cout<<"1..."<<tmp<<endl;
            while(tmp>k)
            {
                tmp = tmp/d*(d-1);
                bit[f]-=1;
                f++;
                // for(int i=0;i<10;i++) cout<<bit[i]<<" ";
                // cout<<endl;
            }
            //cout<<"2..."<<tmp<<endl;
            if(tmp<k)
            {
                f=0;
                while(tmp<k)
                {
                    tmp=tmp/(d-1)*d;
                    bit[f]+=1;
                    f++;
                }
            }
            //cout<<"3..."<<tmp<<endl;
            string ans;
            map<int,char> mp;
            string tm="codeforces";
            for(int i=0;i<10;i++)
            {
                mp[i]=tm[i];
            }
            for(int i=0;i<10;i++)
            {
                //cout<<i<<" "<<bit[i]<<endl;
                while(bit[i])
                {
                    ans.push_back(mp[i]);
                    bit[i]--;
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }

[Link 1]: http://codeforces.com/contest/1368/problem/B