[数据结构与算法]暑假学习记录7.31

??????? 这两天总算把搜索完结了，但只能说是过了一遍，让我写个题我还是写不出来（头大），打算学下一章基础算法的时候尽量每天再看看搜索题目，争取自己把题目给写出来。

poj1416

????????按样例123456分析，先对1切，对23456递归；对12切，对3456递归；对123切，对456递归。。。。难点就在如何递归。。。这也正是我不会的。。。又是看的题解，giao！

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int aim,pt,a[10],per[10],pie,len,minn;
char sh[30];
void dfs(int k,int sum,int t){
    //k是从哪里开始切，sum是和，t是一共多少段
    if(sum>aim)
        return;
    if(k>=len){
        if(sum<=aim){
            if(sum==minn)
            pie++;
        else if(abs(aim - sum)<=abs(aim-minn)){
        //这地方就得用绝对值，因为minn一开始是最大值，所以aim-minn一直是负数
        //程序就不会判到这了
            minn=sum;
            pie=1;
            pt=t;
            for(int i=0;i<t;i++) per[i]=a[i];
        }
        }
        return;
    }
    int pk=0;
    for(int i=k;i<len;i++){//主要步骤递归，循环就是找切点的过程（1，23456；12，3456。。。。）
        pk=pk*10+(sh[i]-'0');
        a[t]=pk;
        dfs(i+1,sum+pk,t+1);
    }
}
int main(){
// freopen("in.txt","r",stdin);
   while(scanf("%d%s",&aim,sh)!=EOF){
        if(aim==0&&strcmp(sh,"0")==0) break;
     len=strlen(sh),minn=999999,pie=0;
    int num=0;
   for(int i=0;i<len;i++)
    num+=(sh[i]-'0');
   if(num>aim){//如果最小的数都大于aim，那么一定找不到
    printf("error\n");
    continue;
   }
   num=0;
   for(int i=0;i<len;i++)
    num=num*10+(sh[i]-'0');
    if(num==aim){//判相等
        printf("%d %d\n",aim,aim);
       // cout<<"yes"<<endl;
        continue;
    }
    dfs(0,0,0);
    if(pie>1) printf("rejected\n");
    else{
            printf("%d ",minn);
        for(int i=0;i<pt;i++){
        if(i==pt-1)
            printf("%d\n",per[pt-1]);
        else printf("%d ",per[i]);
    }
    }
    memset(sh,'0',sizeof sh);
}
/*    jieshu=clock();
    cout<<endl;
    cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}

poj2676

????????我一开始的思路就是从第一个为零的点开始递归，但是最后写完答案一点也不对，递归写得太差了，在网上看的别人的感觉处理得非常好，还有一个难点是小方块判断的处理，方法都在代码里

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
char a[15][15];
bool flag1=0;
int zuo[15][15];//数组开的正好或很小会runtime error
void dfs(int x,int y){
  //  cout<<x<<" "<<y<<endl;
    if(flag1) return;
    if(y>9){
        x++;
        y=1;
        if(x>9){
            flag1=1;
            for(int i=1;i<=9;i++){
                for(int j=1;j<=9;j++)
                    cout<<zuo[i][j];
                cout<<endl;
            }
        }
    }
    if(zuo[x][y]==0){//这样的判断方法真没有想到，真是相当的斯巴拉西了
        int f[10]={0,0};
    for(int i=1;i<=9;i++)
        f[zuo[x][i]]++;
    for(int i=1;i<=9;i++)
        f[zuo[i][y]]++;
    for(int i=(x-1)/3*3;i<(x-1)/3*3+3;i++)//把方格的顺序改为0-9，然后利用计算机除法的特性判断
        for(int j=(y-1)/3*3;j<(y-1)/3*3+3;j++)
        f[zuo[i+1][j+1]]++;
    for(int i=1;i<=9;i++){
            if(f[i]==0){
                zuo[x][y]=i;
                dfs(x,y+1);
                zuo[x][y]=0;
            }
    }
    }
    else dfs(x,y+1);
    return;
}
int main(){
 //freopen("in.txt","r",stdin);
   int t;
   cin>>t;
   while(t--){
        int pos1,pos2;
   for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
         cin>>a[i][j];
         zuo[i][j]=a[i][j]-'0';
        }
    }
    flag1=0;
dfs(1,1);
   }
/*    jieshu=clock();
    cout<<endl;
    cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}

poj1126

????????感觉更像是涂色问题，这题我竟然做过，但全忘了。。。第几个字母和多少种颜色作为递归的参数，对第几个使用的字母进行递归，另外一个字母可以使用以前的颜色，也可以用一个新的颜色

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int n,mp[30][30],color[30],flag;
char s[30];
bool pd(int a,int b){
    for(int i=0;i<=n;i++)
        if(mp[i][a]&&color[i]==b)//判断与该字母相邻的字母是否用过相同的颜色
        return 0;
    return 1;
}
void dfs(int p,int num){

    if(flag) return;
    if(p==n){
        flag=1;
        if(num-1==1)
            printf("%d channel needed.\n",num-1);
        if(num-1>1)
            printf("%d channels needed.\n",num-1);
        return;
    }
    for(int i=1;i<num;i++){
        if(pd(p,i)){
            color[p]=i;//用以前的颜色递归
            dfs(p+1,num);
            if(flag) return;
        }
    }
    color[p]=num;//用新颜色进行递归
    dfs(p+1,num+1);
}
int main(){
// freopen("in.txt","r",stdin);
   while(cin>>n&&n){
        for(int i=0;i<27;i++){
            for(int j=0;j<27;j++)
                mp[i][j]=0;
        }
        for(int i=0;i<27;i++)
            color[i]=0;
        flag=0;

       for(int i=1;i<=n;i++){
        scanf("%s",s);
        int len=strlen(s);
        int a=s[0]-'A',b;
        for(int j=2;j<len;j++){
            b=s[j]-'A';
            mp[a][b]=mp[b][a]=1;//存储方式挺特别的
        }
       }

       dfs(0,1);
   }
/*    jieshu=clock();
    cout<<endl;
    cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}

poj1560

????????迭代加深搜索，从n个序列中最长的长度当作新序列的长度，不行就+1进行搜索，从第一个序列开始，若字符一致新序列就添上该字符，长度加1，依次进行

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int n,val[10],pos[10],dep,ans=0;//pos[i]代表第i个序列用到第几个字符了
string c="ACGT";
struct node{
    string s;int len;
}a[10];
int get(){//获取单个序列最多还有几个字符没用
    int ans=0;
    for(int i=0;i<n;i++){
        ans=max(ans,a[i].len-pos[i]);
    }
    return ans;
}
int ida(int cnt){
    if(cnt+get()>dep) return 0;//剪枝，若步数加上剩下的字符大于长度，则返回
    if(!get()) return 1;
    int temp[10];
    memcpy(temp,pos,sizeof pos);
    for(int i=0;i<4;i++){
        bool flag=0;
        for(int j=0;j<n;j++){
            if(a[j].s[pos[j]]==c[i]){
                pos[j]++;
                flag=1;
            }
        }
        if(flag){
            if(ida(cnt+1)) return 1;
            memcpy(pos,temp,sizeof temp);
        }

    }
    return 0;
}
int main(){
// freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
   while(t--){
    scanf("%d",&n);
    dep=0;
    for(int i=0;i<n;i++){
        cin>>a[i].s;
        a[i].len=a[i].s.size();
        dep=max(dep,a[i].len);
        pos[i]=0;
    }
    while(1){
        if(ida(0)) break;
        dep++;
    }
    printf("%d\n",dep);
   }
/*    jieshu=clock();
    cout<<endl;
    cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}

poj1667

????????迭代加深搜索，这题看上去好麻烦，我都不知道该如何下手，到最后看的题解，直接打印出对锁的操作，然后进行搜索就行，对递归还是不会。。。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&!a[x][y])
//#include<bits/stdc++.h>
using namespace std;
const int maxx=1005;
int center[10]={6,7,8,11,12,15,16,17};//中心的八个方格
int reverseop[10]={5,4,7,6,1,0,3,2};//逆操作
int opt[8][7]={//打表操作
{0,2,6,11,15,20,22},//A
    {1,3,8,12,17,21,23},//B
    {10,9,8,7,6,5,4},//C
    {19,18,17,16,15,14,13},//D
    {23,21,17,12,8,3,1},//E
    {22,20,15,11,6,2,0},//F
    {13,14,15,16,17,18,19},//G
    {4,5,6,7,8,9,10},//H
};
int mp[25],max1;
char ans[maxx];
bool flag;
int get(){//
    int cnt=0;
    int num[4]={0};
    for(int i=0;i<8;i++){
            num[mp[center[i]]]++;
        cnt=max(cnt,num[mp[center[i]]]);
    }
    return 8-cnt;//返回最少步数
}
void operation(int op){//执行操作
int tmp=mp[opt[op][0]];
for(int i=0;i<6;i++){
    mp[opt[op][i]]=mp[opt[op][i+1]];
}
mp[opt[op][6]]=tmp;
}
void ida(int dep,int fa){
    if(flag) return;
    if(get()+dep>max1) return;//剪枝
    if(get()==0){
        ans[dep]='\0';
        printf("%s\n",ans );
        printf("%d\n",mp[center[0]]);
        flag=true;
        return;
    }
    for(int i=0;i<8;i++){
        if(fa!=-1&&i==reverseop[fa]) continue;
        operation(i);
        ans[dep]=i+'A';
        ida(dep+1,i);
        if(flag) return;
        operation(reverseop[i]);
    }
}
int main(){
// freopen("in.txt","r",stdin);
    while(scanf("%d",&mp[0])&&mp[0]){
        for(int i=1;i<24;i++)
            scanf("%d",&mp[i]);
        if(get()==0) {//如果一开始8个数字就相同
            printf("No moves needed\n%d\n",mp[center[0]]);
            continue;
        }
        flag=0;
        max1=1;
        while(1){
                ida(0,-1);
            if(flag) break;
            max1++;
        }
    }
/*    jieshu=clock();
    cout<<endl;
    cout<<(double)(jieshu-kaishi)/CLOCKS_PER_SEC<<endl;*/
return 0;
}