Recursive implementation of exponential enumeration (AcWing 92)

Link Title: Recursive implementation of exponential enumeration
That is, given a n, all the combination schemes in output 1~n
① Binary state compression scheme can be adopted
Let a=0, a < 1 < < n, then in the process of adding a to 1 < < n-1 each time, each combination scheme can be represented by the bit with binary 1 of A.
AC Code:

Click to view the code

# include<bits/stdc++.h>
using namespace std;
const int N=20;
int n;
int main()
{
    cin>>n;
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        if(i>>j&1)  cout<<j+1<<" ";
        cout<<endl;
    }
}

② Recursion is adopted.
AC Code:

Click to view the code

# include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,a[N];
void dfs(int n,int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++)
            if(a[i])    cout<<i<<" ";
        cout<<endl;
        return ;
    }
    dfs(n,u+1);
    a[u]=1;
    dfs(n,u+1);
    a[u]=0;
}
int main()
{
    cin>>n;
    dfs(n,1);
}

Recursive implementation of composite enumeration (AcWing 93)

Link Title: Recursive implementation of combinatorial enumeration
Select all combination schemes with m numbers in output 1~n.
Use depth first search (DFS)
AC Code:

Click to view the code

# include<bits/stdc++.h>
using namespace std;
const int N=30;
int a[N];
int n,m;
void dfs(int n,int m,int u,int k)
{
    if(n-k+1+u<m)   return ;
    if(u>=m)
    {
        for(int i=1;i<=n;i++)
            if(a[i])    cout<<i<<" ";
        cout<<endl;
        return ;
    }
    a[k]=1;
    dfs(n,m,u+1,k+1);
    a[k]=0;
    dfs(n,m,u,k+1);
}
int main()
{
    cin>>n>>m;
    dfs(n,m,0,1);
}

Recursive implementation of permutation enumeration (AcWing 94)

Link Title: Recursive implementation of arranged enumeration
All permutations of output 1~n can use DFS algorithm
AC Code:

Click to view the code

# include<bits/stdc++.h>
using namespace std;
const int N=10;
int a[N];
bool st[N];
void dfs(int n,int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            a[u]=i;
            st[i]=true;
            dfs(n,u+1);
            st[i]=false;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    dfs(n,1);
}

Puzzling switch (AcWing 95)

Link Title: Puzzling switch
Change the state of line i-1 from line i. finally, if there is still 0 in line n, it indicates that the method is not available, so the state of the first line determines the global state. Therefore, it is necessary to enumerate 32 states of the first line first;

Click to view the code

# include<bits/stdc++.h>
using namespace std;
const int N=7;
int p[N][N],a[N][N];
int dx[]={0,0,1,0,-1};
int dy[]={0,1,0,-1,0};
void turn(int a,int b)
{
    for(int i=0;i<5;i++)
    {
        int x=a+dx[i];
        int y=b+dy[i];
        if(p[x][y]==0)  p[x][y]=1;
        else    p[x][y]=0;
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        for(int i=1;i<=5;i++)
        {
            string s;
            cin>>s;
            for(int j=1;j<=5;j++)
                a[i][j]=s[j-1]-'0';
        }
        int res=7;
        for(int k=0;k<32;k++)
        {
            int t=0;
            bool flag=true;
            memcpy(p,a,sizeof a);
            for(int i=0;i<5;i++)
            {
                if(k>>i&1)
                {
                    t++;
                    turn(1,i+1);
                }
            }
            for(int i=2;i<=5;i++)
            {
                for(int j=1;j<=5;j++)
                    if(p[i-1][j]==0)
                    {
                        turn(i,j);
                        t++;
                    }
            }
            for(int i=1;i<=5;i++)
            {
                if(p[5][i]==0)
                {
                    flag=false;
                    break;
                }
            }
            if(flag&&t<=6)
                res=min(t,res);
        }
        if(res>6)   cout<<"-1"<<endl;
        else    cout<<res<<endl;
    }
    return 0;
}

Strange tower of Hanoi (AcWing 96)

Link Title: Strange tower of Hanoi
Every time you move n, you need to put the nth on D, indicating that the first n-1 is on B and C. my understanding is to put the first k on B and k+1 to n-1 on C. in this way, the Hanoi Tower on B is equivalent to four towers and the Hanoi Tower on C is equivalent to three towers. Then enumerate k to get the answer.
Two arrays are set. Array a represents the number of times the Hanoi Tower of three towers moves + 1, and array p represents the number of times the Hanoi Tower of four towers moves.
AC Code:

Click to view the code

# include<bits/stdc++.h>
using namespace std;
int a[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
int p[13];
//Move the first i-j to B, p[i-j];
//Move j to C, a[j]-1;
//Move n to D, 1;
//Move j to D, a[j]-1;
//Move i to D, p[i-j];
int main()
{
    p[1]=1;
    //Calculate p[i+1];
    cout<<p[1]<<endl;
    for(int i=1;i<12;i++)
    {
        int k=INT_MAX;
        for(int j=0;j<=i;j++)
            k=min(k,2*p[i-j]+2*a[j]-1);
        p[i+1]=k;
        cout<<p[i+1]<<endl;
    }
}

Sum of divisors (AcWing 97)

Link Title: Sum of divisors
I haven't learned it yet. Take the pit first.

Fractal City (AcWing 98)

Link Title: Fractal City
No, zhankeng.