0123训练

· · 个人记录

T1
经典的全排列问题。
这里采用递归的写法，枚举每一个数字并用vis数组标记有没有出现过，如果长度到了就输出答案并回溯。
Code:

#include<iostream>
#include<cstring>
using namespace std;
int n,f[11],s[11];
void print(int cnt){
    if(cnt>n){
        for(int i=1;i<=n;i++) cout<<s[i]<<" ";
        cout<<"\n";
        return;
    }
    for(int i=1;i<=n;i++){
        if(!f[i]){
            f[i]=1;
            s[cnt]=i;
            print(cnt+1);
            f[i]=0;
        }
    }
}
int main(){
    while(cin>>n && n){
        memset(f,0,sizeof(f));
        print(1);
    }
    return 0;
}

T2
递归找规律（好像也比较经典）。
如果苹果或盘子只有一个，那就只有一种方案，这是递归的终止条件。
如果x>y，那么就有每个盘子都放一个苹果和不放这个盘子两种情况，答案为两种情况的方案数之和；如果x<y，则无法把盘子全放满，所以可以忽略没放苹果的盘子；如果x==y，那么就有每个盘子都放一个苹果（方案数为1）和有空盘子不放两种情况，答案为两种情况的方案数之和。
按这些推理就可以写出递归函数了。
Code:

#include<iostream>
using namespace std;
int t,n,m;
int f(int x,int y){
    if(x==1 || y==1) return 1;
    if(x>y) return f(x-y,y)+f(x,y-1);
    if(x==y) return 1+f(x,y-1);
    if(x<y) return f(x,x);
}
int main(){
    cin>>t;
    while(t--){
        cin>>m>>n;
        cout<<f(m,n)<<endl;
    }
    return 0;
}

T3
极致的暴搜，完全不用脑子。
Code:

#include<iostream>
#include<cstring> 
using namespace std;
int n,arr[1001],vis[1001];
void dfs(int x){
    vis[x]++;
    if(vis[x]==2){
        cout<<x<<" ";
        return;
    }
    dfs(arr[x]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        dfs(i);
    }
    return 0;
}

T4
听完机房大佬的讲解后大彻大悟了。
首先，这个图形的长和宽都是3^{n-1}，随后，定义l=3^{n-2}，目前图形的左上角为(1,1)，则每个分型的左上角分别为(1,1),(1+2l,1),(1,1+2l),(1+2l,1+2l),(1+l,1+l)。当分型大小为1时，进行特判，把结果存入二维数组。
到这里我和大佬的思路还是一致的，但在递归函数中，我们需要的参数不仅是目前的分型大小，还需要目前的图形的左上角的坐标（我倾向于在函数中计算当前坐标，可能码力不足没调出来）。
Code:

#include<iostream>
#include<cmath>
using namespace std;
int n;
char G[2001][2001];
void f(int x,int y,int g){
    if(g==1){
        G[x][y]='X';
        return;
    }
    int l=pow(3,g-2);
    f(x,y,g-1);
    f(x+2*l,y,g-1);
    f(x,y+2*l,g-1);
    f(x+2*l,y+2*l,g-1);
    f(x+l,y+l,g-1);
}
int main(){
    while(cin>>n && n!=-1){
        f(1,1,n);
        for(int i=1;i<=pow(3,n-1);i++){
            for(int j=1;j<=pow(3,n-1);j++){
                if(G[i][j]!='X') cout<<" ";
                else cout<<"X";
                G[i][j]=' ';
            }
            cout<<endl;
        }
        cout<<"-\n";
    }
    return 0;
}