康拓展开 [HDU1043]
2022/4/8 23:23:16
本文主要是介绍康拓展开 [HDU1043],对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
康拓展开
背景
由\(1,2,3,4,5...N\)组成的一个数共有\(N!\)种排列可能。
以\({N = 4}\)为例,康拓展开可理解为\((1234,1243,1324,1342,1423,1432...,4321)\)到\((1,2,3...24)\)的映射,显然也可以有对应的逆映射。其中,\(1,2,3,...,24\)可由下式表示
\[X = a_{N-1}*(N-1)!+a_{N-2}*(N-2)!+...+a_0*0! \]\(a_{N-1}\)表示该位有\(a_{N-1}\)个数比当前的数小。
以\(42531 = 3*4!+1*3!+2*2!+1*1!+1*0! = 84\)为例,在最高位上,比\(42531\)小的数有\(1,2,3,4\)四种情况,在次高位上,有\({1,2}\)两种情况,以此类推。\(a_0=1\)恒成立代表当前数。
正变换
以\(N=4\)为例解释正变换
原象 | 映象 | 多项式表示 | 原象 | 映象 | 多项式表示 |
---|---|---|---|---|---|
1234 | 1 | 0*3!+0*2!+0*1!+1*0! | 3124 | 13 | 2*3!+0*2!+0*1!+1*0! |
1243 | 2 | 0*3!+0*2!+1*1!+1*0! | 3142 | 14 | 2*3!+0*2!+1*1!+1*0! |
1324 | 3 | 0*3!+1*2!+0*1!+1*0! | 3214 | 15 | 2*3!+1*2!+0*1!+1*0! |
1342 | 4 | 0*3!+1*2!+1*1!+1*0! | 3241 | 16 | 2*3!+1*2!+1*1!+1*0! |
1423 | 5 | 0*3!+2*2!+0*1!+1*0! | 3412 | 17 | 2*3!+2*2!+0*1!+1*0! |
1432 | 6 | 0*3!+2*2!+1*1!+1*0! | 3421 | 18 | 2*3!+2*2!+1*1!+1*0! |
2134 | 7 | 1*3!+0*2!+0*1!+1*0! | 4123 | 19 | 3*3!+0*2!+0*1!+1*0! |
2143 | 8 | 1*3!+0*2!+1*1!+1*0! | 4132 | 20 | 3*3!+0*2!+1*1!+1*0! |
2314 | 9 | 1*3!+1*2!+0*1!+1*0! | 4213 | 21 | 3*3!+1*2!+0*1!+1*0! |
2341 | 10 | 1*3!+1*2!+1*1!+1*0! | 4231 | 22 | 3*3!+1*2!+1*1!+1*0! |
2413 | 11 | 1*3!+2*2!+0*1!+1*0! | 4312 | 23 | 3*3!+2*2!+0*1!+1*0! |
2431 | 12 | 1*3!+2*2!+1*1!+1*0! | 4321 | 24 | 3*3!+2*2!+1*1!+1*0! |
代码实现思路:
由于当我们确定某一位可以有多少种组合时,其之前的数已经确定,若寻找比当前位小的数,我们只需从当前为往后寻找,有几位比当前数大当前位多项式的系数即为几。
求解正变换的过程可看做是求解多项式系数的问题。
代码
#include <iostream> using namespace std; //定义数位 const int numbits = 4; //阶乘数 int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; int cantor(int a[]) { int ans = 0; for (int i = 0; i < numbits; ++i) { int t = 0; //统计当前位以后有几个数大于当前位 for (int j = i + 1; j < numbits; ++j) { if (a[i] > a[j]) { ++t; } } ans += t * fac[numbits - 1 - i]; } return ans + 1; } int main() { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); int N; cin >> N; //输入数据 int a[numbits]; while (N--) { for (int i = 0; i < numbits; ++i) { cin >> a[i]; } for (int i = 0; i < numbits; ++i) { cout << a[i]; } cout << '\t' << "------------->" << '\t'; cout << cantor(a) << endl; } fclose(stdin); fclose(stdout); return 0; }
输入示例
输出示例
反变换
我们注意到,当多项式的某一位的系数累积到该位的阶乘数时,该位会置零,并向高位进一。求解逆变换的过程也是求解多项式系数的问题。
以\(N = 5\)为例解释逆变换。每位上的多项式系数可分别看做一个\(24,6,2,1\)进制数,最低位系数为\(1\)。
首先给个例子,由\(1,2,3,4,5\)组成的\(84\)号元素,其多项式表示为\(3*4!+1*3!+2*2!+1*1!+1*0!\),根据多项式系数的解释,\(4!\)系数表示该位有\(3\)种情况比\(4\)小,即\(1,2,3\),所以最高位为
\(4\),第二位的一种情况为\(1\),所以第二位上为\(2\),在第三位上,当前两位固定为\(42\)时,有两种情况比当前系数小,由于\(2\)和\(4\)已经去除,所以需再去除\(1,3\),所以第三位为\(5\),以此类推,该数
为\(42531\)。具体求解过程为:由于最低位的多项式系数为\(1\),先将\(84-1\),根据十进制数转化为其他进制数的方法,求解当前位的多项式系数,即\(84/24 = 3...8\),再将余数作为下一次的被除数,
每次找寻当前位的数字时,先排除掉已经确定的数。
代码实现
#include <iostream> #include <string> typedef long long ll; using namespace std; int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; string revcantor(int num, int numbits) { if (num > numbits*fac[numbits - 1]) { return string("error input"); } std::string ans; int divided = num; divided -= 1;//减一以去除最低位多项式的一 int *vis = new int[numbits];//用于排除已经确定的数 memset(vis, 0, sizeof(int) * numbits); for (int i = numbits - 1; i >= 0; --i) { int divisor = fac[i]; int tmp = divided / divisor; divided = divided % divisor; //确定当前位 for (int j = 0; j < numbits; ++j) { //当前数没被使用且tmp已经为0,则即为该数字 if (!vis[j] && tmp == 0) { ans += (char)(j + 1 + '0'); vis[j] = 1; break; } //当前数未被使用但tmp!=0 else if (!vis[j] && tmp != 0) { --tmp; } //已被使用,直接跳过 else { continue; } } } return ans; } int main() { freopen("out.txt", "w", stdout); for (int i = 1; i <= 121; ++i) { cout << "NO." << i << '\t' << revcantor(i, 5) << endl; } fclose(stdout); return 0; }
输出示例
这篇关于康拓展开 [HDU1043]的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解