数论继续学习12---康托展开

数论继续学习12---康托展开

在我们做题中,搜索也好,动态规划也好,我们往往有时候需要用一个数字表示一种状态

 

比如有8个灯泡排成一排,如果你用0和1表示灯泡的发光情况

那么一排灯泡就可以转换为一个二进制数字了

 

比如

01100110 = 102

11110000 = 240

10101010 = 170

 

通过这些十进制数,只要把他们展开,我们就知道灯泡的状态了

 

如果这题是一个动态规划题

然后我们就拿这些数字做一些转移了,

比如dp[102],dp[240],dp[170]等等

这对题目很有帮助

 

 

 

 

 

上面讲的那些就是所谓的状态压缩了,状态压缩后面我继续学习。

那对于有些题,我们即使状态压缩后,数字太大,数组都开不下,麻烦的题目(/TДT)/

这些题目也要看情况,比如我接下来要讲的康托展开

康托展开的公式是 X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!  

  

康托展开经典题:hdu 1430          //魔板

 

魔板

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3951    Accepted Submission(s): 930


Problem Description
在魔方风靡全球之后不久,Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成,每个方块颜色均不相同,可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示:从魔板的左上角开始,按顺时针方向依次写下各方块的颜色代号,所得到的数字序列即可表示此时魔板的状态。例如,序列(1,2,3,4,5,6,7,8)表示魔板状态为:

1 2 3 4
8 7 6 5

对于魔板,可施加三种不同的操作,具体操作方法如下:

A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368

给你魔板的初始状态与目标状态,请给出由初态到目态变换数最少的变换步骤,若有多种变换方案则取字典序最小的那种。
 

Input
每组测试数据包括两行,分别代表魔板的初态与目态。
 

Output
对每组测试数据输出满足题意的变换步骤。
 

Sample Input
12345678172453681234567882754631
 

Sample Output
CAC
 

Author
LL
 

Source
 

 

 

 

我们看这题,总共有8个数字,1~8,假如我们把他们看成0~7

那么每个数字可以转换为一个3位二进制

0:000

1:001

2:010

3:011

4:100

5:101

6:110

7:111

 

然后12345678这个状态我们可以表示为二进制000001010011100101110111,总共3*8=24位,

2^24 = 16777216,数组根本开不下啊

 

这时,我们发现了,有一些状态,根本没有用到,因为这题已经规定了有8个数字,每个数字只出现一次

比如000000000000000000000000这个状态,你说可能出现吗?(o ° ω ° O )

 

这个时候,康托就对这种题目做了研究(o ° ω ° O )

这种每个数字只出现一次的问题的所以情况,总共才n!个情况(这个问题叫做全排列)

 

康托的一套算法可以正好产生n!个数字

比如:

123  ->  0

132  ->  1

213  ->  2

231  ->  3

312  ->  4

321  ->  5

 

 

 

 

这是如何做到的(/≥▽≤/)

在峰神的博客里面有很好的解释(对不起了峰神≖‿≖✧,拿过来抄一下)

  

康托展开1

 

 

康托展开2


(/≥▽≤/)好神奇

 

 

 

于是乎,康托展开模板:


void cantor(int s[], LL num, int k){//康托展开,把一个数字num展开成一个数组s,k是数组长度
    int t;
    bool h[k];//0到k-1,表示是否出现过 
    memset(h, 0, sizeof(h)); 
    for(int i = 0; i < k; i ++){
        t = num / fac[k-i-1];
        num = num % fac[k-i-1];
        for(int j = 0, pos = 0; ; j ++, pos ++){
            if(h[pos]) j --;
            if(j == t){
                h[pos] = true;
                s[i] = pos + 1;
                break;
            }
        }
    }
}
void inv_cantor(int s[], LL &num, int k){//康托逆展开,把一个数组s换算成一个数字num 
    int cnt;
    num = 0;
    for(int i = 0; i < k; i ++){
        cnt = 0;
        for(int j = i + 1; j < k; j ++){
            if(s[i] > s[j]) cnt ++;//判断几个数小于它
        }
        num += fac[k-i-1] * cnt;
    }
}

版权声明:本文为weixin_39792252原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39792252/article/details/79594652

智能推荐

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

猜你喜欢

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...

Python和Django的安装

个人博客导航页(点击右侧链接即可打开个人博客):大牛带你入门技术栈  一、下载并安装Python Python 官方下载地址:http://www.python.org/ftp/python/ 我们这里选择的是 Python 2.7.2 。虽然目前最新版是Python 3.2.2, 但是Django目前还不支持 Python 3.2.2。 安装步骤很简单,双击安装包开...

OpenStack代码贡献初体验

为什么80%的码农都做不了架构师?>>>     OpenStack如今已成为开源云平台中的明星项目,得到广泛关注。OpenStack的优秀出众依赖于众多开发者的努力,在享受其带来的便利与快捷的同时,为其做一份贡献也是一个开发者的义务。  在前段时间的OpenStack的测试过程中,我发现Nova项目中的一个Bug,于是向社区提交了Bug报...

SQL Server之8:sql查询每个学生得分最高的两门课

这是一道面试题,今天有空把它记下来,以后遇到此类问题作个参考!刚一看到这个题目,估计好多人都会想到关键字top,其实这里用到的关键字是partition, 好了,先看看表结构,及数据吧!     接下来看一看partition的功能,执行语句   结果如下:   到这里一目了然知道最终结果了!   View Code     &...