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 1046: 8数码问题

广搜入门题,经典八数码 题库中已经说的很清楚了,这题是用广搜(又称宽搜),那么,何为宽搜,它与深搜区别何在?

1.深搜与广搜


这两种搜索的全名分别是: 深搜——深度优先搜索 广搜——广度优先搜索 其英文缩写分别是 dfs 与 bfs ,虽然只差一个字母,不过却有所不同 深搜的特点是短而难想 广搜的特点是长且难写 我们就根据八数码这道题,说一下深搜与广搜的区别,先看看下面这张图:
                  0
           /   |    |   \
        上 下 左  右(最优解)
    /  |    |    \
上 下 左 右(次右解)
如果你是用深搜他会这么寻找: 0->上->上->返回上一层->下->返回上一层->左->返回上一层->右(次优解)->返回上一层->下-》……最优解 然而广搜是这个样子的 0->上->下->左->右(最优解)->进入下一层-》上-》下-》左-》右-》次优解 以上应该就可以很明白的看出,深搜是将一步搜索到底再回头,广搜是在每一层搜索,所以广搜第一个搜到的一定是最优解。 不过为什么会右这样的差距,这就要看广搜的原理了

2.何为广搜


广度优先搜索
这不就是没解释 也就是说我们先把同一个步数的所有情况扩展完,然后进行判断,这也就是为什么第一个答案就是最优解 我们说这种情况,每一种情况搜完就不在需要了,而最近被搜到的应该放入最后,也就是说,先进先出——队列 那也就是说,这个东西需要我们开队列=.=,并且这种状况下,重复的可能性很高,关于如何这道题的剪枝方法,你可以看看这个 Caioj 1220:康托展开和康托展开的逆运算

3.题目&思路&部分代码


题目链接: http://caioj.cn/problem.php?id=1046
首先我们知道,这个题我们就是要模拟上下左右,也就是说我们读入初始与截止情况,将初始情况放入队列首,先来看看队列怎么写吧
struct FUCK{
    int a[4][4],x,y,deep;
}dl[400000],ed;
请忽略结构体名 dl[] 也就是队列
  • int a[][] 临时储存数码图
  • x,y 0 的坐标
  • deep 深度,也就是步数
ed 结尾情况 嗯对就是这样 然后就是判断重复,也就是上文所说的康托展开,我们吧每一中情况打成哈希表(坑爹玩意),然后就可以判断重复了,接下来就可以进行搜索
    while(l<=r){
        for(int i=0;i<4;i++){
            FUCK fir=dl[l];
            fir.x=dl[l].x+dx[i];
            fir.y=dl[l].y+dy[i];
            if(fir.x>=1&&fir.x<=3&&fir.y>=1&&fir.y<=3){
                int temp=fir.a[fir.x][fir.y];
                fir.a[fir.x][fir.y]=fir.a[dl[l].x][dl[l].y];
                fir.a[dl[l].x][dl[l].y]=temp;
                int temp_kt=zys(fir);
                fir.deep=dl[l].deep+1;
                if(!xd[temp_kt]){
                    xd[temp_kt]=true;
                    r++;
                    dl[r]=fir;
                    if(temp_kt==z){
                        printf("%d\n",fir.deep);
                        return 0;
                    }
                }
            }
        }
        l++;
    }
其中 l 是队列首指针, r 是队列尾指针, for 循环对应的就是 dx[] , dy[] 这两个增量然后我们就交换变量, 随意说这道题并不是特别的难 当然如果你不加判断重复就会 RE 了2333 ]]>

Caioj 1043:因式分解

这道题我至今为止已经找到了三种做法2333333,也是够了

如何思考


题目题面:[http://caioj.cn/problem.php?id=1043]
这种题目一看就是搜索=.=,然后,我们看一下数据样例
12=12 12=62 12=43 12=34 12=322 12=26 12=232 12=223
等一下12=12???12=34与12=43?? 是的他自己也算一种,并且,两个因数交换后也算一种. 好了让我们开始代码

第一回:爆搜


状态: 20%TLE
#include <cstdio>
#include <cmath>
using namespace std;
int n,cnt;// n 读入的数字; cnt 统计和
 // zs(int k) 判断 k 是否为质数
// 不解释
bool zs(int k){
    int temp=sqrt(k);
    for(int i=2;i<=temp;i++){
        if(k%i==0) return false;
    }
    return true;
}
// dfs(int deep) 深搜; deep 当前值
void dfs(int deep){
    cnt++;//每搜到一个就一定时一种情况
    if(zs(deep)) return ;//是指数就没必要搜了
    for(int i=2;i<deep;i++){// 小于deep 的每个都试一次
        if(deep%i==0){// 如果能整除,继续搜索
            dfs(deep/i);
        }
    }
}
int main(){
    scanf("%d",&n);//读入
    dfs(n);//开始搜索
    printf("%d",cnt);//输出
}
显然这道题目不会这么简单=.=,果然超时了2333

第二回:打个质数表


显然上面这么搜索盲目又耗时间,我们还不如先存下来可以被 n 整除的数,然后从 1 往上一个个找,这样看来会好多 状态: AC 时间:496 ms 内存:1176 kb
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[11000],len;
void fz(int x){
    int t=int(sqrt(double(x+1)));
    for (int i=2;i<=t;i++){
        if (x%i==0){
            a[++len]=i;
            if (x/i!=i)a[++len]=x/i;
        }
    }
}
int n,ans;
void dfs(int d){
    ans++;
    for (int i=1;i<=len;i++){
        if (d*a[i]>n) break;//如果因子比n大则直接跳出
        if (n%(d*a[i])==0&&n!=d*a[i]){
            dfs(d*a[i]);
        }
    }
}
int main(){
    scanf("%d",&n);
    len=0;fz(n);
    sort(a+1,a+len+1);//加了一步排序
    ans=0;dfs(1);
    printf("%d\n",ans);
    return 0;
}

第三回:对称性剪枝

这个玩意儿~是金哥讲的,金哥果然厉害这不废话
我们来看一下面两个:
12=3*4
12=4*3
我们可以发现,这不白白搜索两次吗??? 明白着的浪费时间啊 “浪费就是犯罪”–名人名言   我们该怎么办呢? 我们给这个数开个方,然后循环枚举,i与t/i不相同的ans+2,否则+1,就像下面这一段
void search(int t){
    int temp=sqrt(t);//开方
    for(int i=2;i<=temp;i++){//循环枚举
        if(t%i==0){//能否整除
            if(i!=(t/i)){ //不相同说明可以交换,ans+2,两边都要搜
                ans+=2;
                search(t/i);
                search(i);
            }
            else{ //否则ans+1,只搜一边
                ans++;
                search(t/i);
            }
        }
    }
}
上述代码 状态: AC 时间: 212 ms 内存: 1128 kb

End

]]>

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]);
}
]]>

Caioj 1040:素数圈

0x01


  1. 判断素数
  2. 简单dfs

0x02


代码:
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n,a[110],cnt;// a[] 储存顺序 cnt 临时储存和
bool x[110];//x[] 判重
// 判断质数
bool zs(int x){
    for(int i=2;i<=sqrt(x)+1;i++){
        if(x%i==0) return false;
    }
    return true;
}
// dfs部分
void dfs(int k){
    if(k==n+1){// 到达最终步骤
        if(!zs(a[n]+a[1])) return ;// 如果不是质数,那么下地狱吧
        // 输出
                for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    else{
        for(int i=2;i<=n;i++){
            if(!x[i]){
                cnt=a[k-1]+i; //求这个数与上个数的和
                if(zs(cnt)){// 求质数
                    a[k]=i;
                    x[i]=true;
                    dfs(k+1);
// 回溯
                    x[i]=false;
                    a[k]=0;
                }
            }
        }
    }
}
int main(){
// 输入
    scanf("%d",&n);
    a[1]=1;
    x[1]=true;
    dfs(2);// 目前已经确定第一个数为1(不然会重复)
}
]]>

Caioj 1034:二叉树的后序遍历

Start


原题题面: http://caioj.cn/problem.php?id=1037
这博客从我学oi前就有,,,这么现在逐渐有种要变成算法博客的趋势 咱的老师把这道题讲了似乎许多遍了,不管了,上题解

分析题目


emmm……不知道大家还记不记得,有一年的初赛就有过已知两中遍历求另一种遍历,不过那个题目是到选择,你可以动手试试,这道就需要我们找规律了,首先我们要知道,有一下两种情况
  1. 已知前序与中序遍历,求后序遍历
  2. 已知后序与中序遍历,求前序遍历
这两种状况是有唯一解的,其他的答案可能就会有多种 那么我们先看样例
ABDEHCFGI DBEHAFCIG
根据前序遍历的特性,我们可以轻松的找到A为根,那么我们在两种遍历中去掉A
BDEH CFGI DBEH FCIG
我们知道,中序遍历中,根节点左边是左子树部分,右边是有子树部分,让后我们就找到了左右子树 如果我们吧左子树在看成一个新的二叉树,那么继续搜下去,左后必然会精确到一个点,但是我们不知道要推多少次啊,怎么办?当然是递归

解析代码


先上代码
#include <cstdio>
#include <cstring>
using namespace std;
char a[110],b[110],x[110];//a字符串是前序遍历,b是中序遍历,x是后序遍历
int lx,k[110];
void dfs(int la,int ra,int lb,int rb){//la => 前序遍历左端点  la => 前序遍历左端点 ra => 前序遍历右端点  lb => 中序遍历左端点 rb => 中序遍历右端点 
    if(la>ra) return ;//等价与 if(lb>rb) return ; 如果你不理解,那么你可能还没有将题目读懂
    int temp_a=k[a[la]]-lb;//为什么要减去lb?因为我们要去找到他的位置,然而位置的开始搜索可能并不是0
    dfs(la+1,la+temp_a,lb,k[a[la]]-1);//往左子树找
    dfs(la+temp_a+1,ra,k[a[la]]+1,rb);//往右子树找
    x[lx++]=a[la];
}
int main(){
    scanf("%s",a);
    scanf("%s",b);//读入
    int lena=strlen(a);
    int lenb=strlen(b);//长度
    for(int i=0;i<lenb;i++) k[b[i]]=i;//因为我们要知道前序遍历中的一位在中序遍历中的哪一位,然而搜索有太费时间,所以我们存一下
    lx=0;//x字符串从0开始
    dfs(0,lena-1,0,lenb-1);//开始的步骤
    for(int i=0;i<lx;i++){
        printf("%c",x[i]);
    }
}

End


这道题目,,,,,,代码不难,思路特别的难,,所以,看脑子啦~ ]]>