【组合数+字典序】ABC202 D

淡淡的烟草味﹌ 2024-03-16 14:00 47阅读 0赞

**感觉自己什么都不会了....**

[D - aab aba baa (atcoder.jp)][D - aab aba baa _atcoder.jp]

题意：

![2a3fdc6517fe4f1fa243d9fa7e748b91.png][]

思路：

**关于字典序的问题，一定是一位一位地考虑过去**

对于这道题，我们遍历位，对于每一位，怎么去判断是a还是b呢，那就看，如果填b的字典序和K比较，如果K大，那么就一定是b，否则就是a

那么我们怎么得到该位置填a或者填b的字典序呢，考虑算组合数，即在剩下的位置填a的方案数，那就是C(N-i,a-1)了

填了a或者b之后，记得更新A或者B的数量

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    int A,B,K;
    int C[100][100];
    
    void C_init(){
    	for(int i=0;i<=60;i++){
    		for(int j=0;j<=i;j++){
    			if(!j) C[i][j]=1;
    			else C[i][j]=C[i-1][j]+C[i-1][j-1];
    		}
    	}
    }
    void solve(){
    	cin>>A>>B>>K;
    	int N=A+B;
    	for(int i=1;i<=N;i++){
    		int now=C[N-i][A-1];
    		if(A==0) now=0;
    		if(now<K) K-=now,cout<<"b",B--;
    		else cout<<"a",A--;
    	}
    	cout<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	C_init();
    	while(__--)solve();return 0;
    }

[D - aab aba baa _atcoder.jp]: https://atcoder.jp/contests/abc202/tasks/abc202_d
[2a3fdc6517fe4f1fa243d9fa7e748b91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/da558df74ef24bfb84676a1ed6ca225e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

还没有评论，来说两句吧...

相关阅读

相关 202. 快乐数

202. 快乐数题干背景重要思路具体代码题干背景 [力扣入口-202.快乐数][-202.] 编写一个算法来判断一个数 n 是不是快乐

冷不防/ 2024年03月17日 21:18/ 0 赞/ 92 阅读

相关【dfs序+二分】ABC202 E Count Descendants

[E - Count Descendants (atcoder.jp)][E - Count Descendants _atcoder.jp] 题意： ![658e3c96

你的名字/ 2024年03月16日 14:04/ 0 赞/ 46 阅读

相关【组合数+字典序】ABC202 D

感觉自己什么都不会了.... [D - aab aba baa (atcoder.jp)][D - aab aba baa _atcoder.jp] 题意： ![2a3f

淡淡的烟草味﹌/ 2024年03月16日 14:00/ 0 赞/ 48 阅读

相关字典序

一.字典序基础字典序（dictionary order），又称字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两

Dear 丶/ 2024年02月19日 16:38/ 0 赞/ 80 阅读

相关 202. 快乐数

> 编写一个算法来判断一个数 n 是不是快乐数。 > > 「快乐数」定义为： > > 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 > 然后重复这个过

比眉伴天荒/ 2022年10月18日 01:42/ 0 赞/ 154 阅读

相关 leetcode 202 快乐数

前言题目：[202. 快乐数][202.] 参考答案：[202. 快乐数-力扣官方题解][202. _-] 提交代码思路：判断计算之后的数字是否在集合中。建

朱雀/ 2022年09月09日 04:45/ 0 赞/ 196 阅读

相关组合的字典序问题

`` 题目来自：[http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1202][

妖狐艹你老母/ 2022年06月09日 13:40/ 0 赞/ 174 阅读

相关 LeetCode202. 快乐数

编写一个算法来判断一个数是不是“快乐数”。一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无

男娘i/ 2022年05月23日 02:17/ 0 赞/ 205 阅读

相关 202. 快乐数

快乐数 > 编写一个算法来判断一个数是不是“快乐数”。 > 一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这

本是古典何须时尚/ 2021年10月29日 19:52/ 0 赞/ 366 阅读

相关 leetcode：202. 快乐数

编写一个算法来判断一个数是不是“快乐数”。一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无

￡神魔★判官ぃ/ 2021年09月28日 21:34/ 0 赞/ 330 阅读