首页 > 软件开发 > 软件开发

aab aba baa abc202

admin 软件开发 2021-05-25 09:25:13 算法 
后台-系统设置-扩展变量-手机广告位-内容正文底部

原题链接
赛后补题:

输入a,b,k;
题目大意:存在a个‘a’,b个‘b’,要我们求第k个的字典序。(从小到大数)。

思路:dp[i][j]表示前i个字符中取出j个字符(不考虑他的顺序)的组合数
因为可以用dp的思想去理解,所以数组命名为dp了。
先打个表,即组合数的表:C(i,j)=C(i-1,j-1)+C(i-1,j)。
核心:就是下面这个if
if(b&&dp[i-1][b]<k) 这个if表示
{
假设这段字符串有这么长,我们第一个位置放a。即[a … … ]省略号表示后面还有很多,你看,如果我们第一个位置放a的话,我们后面的字典序数量最多为C(a+b-1,a-1)如果比k还要小的话,那我们第一个位置肯定就不能放a啊,只能改换b.
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#define IOS ios::sync_with_stdio(false);cin.tie();cout.tie(0)

using namespace std;
typedef long long ll;
const int N=5e5+100;
const int maxn=110;

map<string,int> q;
ll dp[maxn][maxn];
char g[maxn][maxn];

void itie()
{
    for(int i=0;i<=60;i++)
        for(int j=0;j<=i;j++)
    {
        if(!j) dp[i][j]=1;
        else
        {
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
        }
    }
}

int main()
{
    IOS;
    itie();

    ll a,b,k;
    cin>>a>>b>>k;

    for(int i=a+b;i>0;i--)
    {
        if(b&&dp[i-1][b]<k)
        {
            cout<<"b";
            k-=dp[i-1][b];
            b--;
        }
        else cout<<"a";
    }
    return 0;
}

文章来源:https://blog.csdn.net/weixin_46088152/article/details/117198403

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://www.jcdi.cn/ruanjiankaifa/30739.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码