Caioj 1047: 魔板

二维魔方,全是套路

题目


题目链接: [http://caioj.cn/problem.php?id=1047]
二维的魔方貌似并没有比三维的魔方简单到哪里 我们可以看出,这道题是一个搜索,并且求的是最优解,也就是宽搜的事了 然后再让我们想想哈希表的问题,首先我们知道只有八个数,并且还都是 1-8 ,显然就应该用康托展开了

部分代码 & 想法


我们要对这一串数字进行处理,显然是应当以数组方式存的(当然你也可以存成整数操作,如果你不觉得累的话),我们要输出操作,这是这道题中的一个大坑=.=,显然我们将操作以字符串的形式存起来内存会非常大,所以我们应当换一种方法. 我们知道,每中搜索都会有一颗对应的搜索树,以这个为基础,我们就可以想到,将他的父节点存下来,只在当前的结构体中存我们从父节点过来的操作,然后在输出时一路递归回到根节点,再逆序输出即可。 结构体:
struct node{
    int deep,a[3][5],k,last;
    char d;
}b[400000],ed;
deep – 当前深度(步数) a[][] – 当前魔板的状况 k – 康托展开 last – 父亲节点 d – 从父节点过来的操作 输出操作:
void sc2(int k){
    if(b[k].last!=-1) sc2(b[k].last);
    if(b[k].last!=-1) printf("%c",b[k].d);
    return ;
}
然后就是广搜的基本套路=.=,大家都会写的说

部分小坑


  1. 这个魔板是在第二列是从右往左读入的
  2. 别忘记输出 no !
  3. 处理时谨慎点
]]>

Caioj 1220:康托展开和康托展开的逆运算

宽搜剪枝法!智障展开康托展开

何为康托展开


对于一个有n个不同元素的集合{1,2,3,4,…,n}的从小到大排序(从大到小 同理)的全排列
显然它有n!项。如n=4,那么就有4!=4×3×2×1=24项。 那么问题来了,如果我们已经知道他的顺序了,要求他是中剪第几个该怎么办呢? 比如下面这道题:
求4132是第几个排列?
我们来看,它是从小到大排的序,我们就要考虑,比它小的有几个 先看千位:4 小于 4 的数有: 3 2 1 那么总共有几种呢? 这时问题就变成了
有三个数进行全排列,总共有多少种可能?
3!=321=6 又因为他有三个比它小的数 所以有 3*3!=18种排列 那么以此类推,我们再往下一位看,此时问题变成这样
求132是第几个排列?
先看最高位-1 小于 1 的数有0个 所以有0种排列 问题继续转化,变成
求32是第几个排列?
小于最高位: 3 并且没有出现过的数有: 2
将一个数进行全排列,总共有多少种排列?
1!=1 综上所述,小于4132的排序有 18+1=19 种 那么,4132就是第20种 上面这些就是康托展开

逆运算?


看看这个问题
1~4从小到大全排列中,找出第20个排列? 和上面的刚好反过来了,怎么办呢?
还是一样,比它小的有19个 我们先考虑一下它的千位 我们想一下,如果千位上的数是固定的,有多少种排列? 3!=321=6 种 所以每过六种排序,千位上的数就会加1 19/6=3…1 所以千位上应该1-4中从小到大第四个没有出现过的数: 4 继续转化问题,上面那个除法算出来还余 2 呢!
1-3从小到大的全排列中,求第2个排列?
1/2!=0…1 所以千位上应该1-4中从小到大第一个没有出现过的数: 1 带着1继续转化问题:
2-3从小到大的全排列中,求第1个排列?
1/1!=1 所以千位上应该1-4中从小到大第二个没有出现过的数: 3 那么最后一位就是剩下唯一没有用过的数字: 2 也就是说,这个排列是4 1 3 2 是不是和上面那个吻合呢? 自己试几个吧!

代码


康托展开

long long zys(){
    long long ans=0;// ans 储存和
    memset(x,false,sizeof(x));// 清空判重数组
    for(long long i=1;i<=n-1;i++){
        long long tcnt=0;
        for(long long j=1;j<a[i];j++) if(x[j]==false) tcnt++;// 寻找有几个比当前数小的
        ans=ans+tcnt*p[n-i];// 结果相加
        x[a[i]]=true;
    }
    ans++;// 加上自己
    return ans;// 返回
}

康托展开逆运算

void nys(long long cnt){
    cnt--;// cnt 第cnt个排列
    memset(x,true,sizeof(x));
    for(long long i=1;i<=n;i++){
        long long tcnt=cnt/p[n-i];
        cnt-=tcnt*p[n-i];// 将cnt的值变成余数
        long long j;
        for(j=1;j<=n;j++){
            if(x[j]==true){
                if(tcnt==0) break;
                tcnt--;
            }
        }
        x[j]=false;
        a[i]=j;
    }
  // 输出
    for(long long i=1;i<n;i++) printf("%lld ",a[i]);
    printf("%lld\n",a[n]);
}
]]>