Common enumeration forms

Enumeration form	General traversal method
polynomial	Recurrence
index	Recursion, bit operation
array	Recursion, c++ next_permutation
combination	Recursion + pruning

Implement exponential enumeration

DFS (I)

The idea is to output in the form of increasing along the path.

#include <iostream>
#include <stdio.h>
#include <cstring>

using namespace std;

int n;
int path[100000];

void dfs(int stp, int k) {
	for (int i = 0; i < k; ++i)
		printf("%d ", path[i]);
	putchar('\n');
	if (stp > n)
		return ;
	for (int i = stp; i <= n; ++i) {
		path[k++] = i; //choice
		dfs(i + 1, k); 
		k -- ; //Backtracking, no selection
	}
}

int  main() {
	scanf("%d", &n);
	dfs(1, 0);
	return 0;
}

DFS (II)

void calc(int x){
    if(x == n+1)
    {
        for(int i =0;i<chosen.size();++i)
        printf("%d ",chosen[i]);
        putchar('\n');
        return ;
    }
    //Two options
    calc(x+1); //Not selected
    chosen.push_back(x); // choose
    calc(x+1);
    chosen.pop_back(); // to flash back
}

Bit operation (I)

// Every number can be selected or not, so it is the n-th power of 2
for (int i = 0; i < (1 << n); ++i) { 
	for (int j = 0; j < n; ++j)
		if ((i >> j) & 1) //Judge whether the j of i is selected
			cout << j + 1 << " ";
				cout << '\n';
}

Bit operation (2)

void dfs(int u,int state){
  if(u == n){
    for(int i=0;i<n;++i)
        if(state>>i &1)
            cout<<i+1<<" ";
        cout<<endl;
        return ;
    }
    dfs(u+1,state);
    dfs(u+1,state|1<<u);//Set the u position of state to 1
   
}

Implement composite enumeration

DFS + pruning

#include <iostream>
#include <stdio.h>
#include <cstring>

using namespace std;

int n,m;
int path[100000];

void dfs(int stp, int k) {
    if(k == m){ // Check whether the number of elements placed reaches m
    for (int i = 0; i < k; ++i)
        printf("%d ", path[i]);
    putchar('\n');
    }
    // prune
    //The number of selected elements has exceeded m, or even if the remaining elements are selected, the number is not enough
    if(k >= m || (k+n-stp+1)<m)
    return ;
    if (stp > n)
        return ;
    for (int i = stp; i <= n; ++i) {
        path[k++] = i;
        dfs(i + 1, k);
        k -- ;
    }
}

int  main() {
    scanf("%d%d", &n,&m);
    dfs(1, 0);
    return 0;
}

Author: multivariate function
 Link: https://www.acwing.com/activity/content/code/content/1963737/
Source: AcWing
 The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

Implement permutation enumeration

DFS

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;

int n;
bool vis[10];
int path[10];

void dfs(int sp){
    if(sp == n+1){
        for(int i=1;i<=n;++i)
        printf("%d ",path[i]);
        putchar('\n');
        return ;
    }
    for(int i=1;i<=n;++i){
        if(!vis[i]){ // Use a bool array to record the used value of a path to avoid repetition
            vis[i] = 1;
            path[sp] = i; //Because here SP is the position corresponding to sp, a number should be inserted
            dfs(sp+1);
            vis[i] = 0; // to flash back
        }
    }
}

int main(){
    scanf("%d",&n);
    memset(vis,0,sizeof(vis));
    dfs(1);
    return 0;
}

Puzzling switch

Title Link

Difficulties:

After enumerating all the states in the first row, how to change the original idea is to change and count the number of bits with 1. Because the change will change the original state, you need to use an array to save the original state and restore it after the change. After determining the first line, you can recurs the following lines. The lines range from 0 to 4. If it is 0, it will change. Then check whether the last line is 1.

skill:

For the original 0 character becomes 1, and the 1 character becomes 0. You can use the XOR 1 method.

g[xx][yy]  ^= 1;

code:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
const int INF = 987654321;
using namespace std;

char g[20][20];
int ans;
int dx[5] = {0,1,-1,0,0},dy[5] ={0,0,0,1,-1};

void turn(int x,int y){
    for(int i = 0;i<5;++i){
        int xx = x+dx[i],yy = y+dy[i];
        if(xx>=0&&xx<5&&yy>=0&&yy<5){
            g[xx][yy]  ^= 1;
        }
    }
}


int work(){
    for(int k=0;k<(1<<5);++k){
        int res = 0;
        char barcup[20][20];
        memcpy(barcup,g,sizeof g);
        for(int i=0;i<5;++i)
            if(k>>i &1){ // A position of 1 indicates a change in the lamp at that position
            res++; //So count every step
            turn(0,i);
            }
        for(int i =0;i<4;++i)
        for(int j=0;j<5;++j){
            if(g[i][j] == '0'){
                res++;
                turn(i+1,j);
            }
        }
        bool istrue = true;
        for(int i=0;i<5;++i)
        if(g[4][i] == '0')
        {
            istrue = 0;
            break;
        }
        if(istrue) ans = min(ans,res);
        memcpy(g,barcup,sizeof g);
    }
    if(ans>6)return -1;
    return ans;
}


int  main(){
    int t;
    scanf("%d",&t);
    while(t--){
        for(int  i=0;i<5;++i)cin>>g[i];
        ans = INF;
       ans =  work();
       printf("%d\n",ans);
    }
    
    return 0;
}

Strange tower of Hanoi

Original question link

code:

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;

const int INF = 98765431;
int n;
int d[100],f[200];

int main(){
    n = 12;
    d[1] = 1;
    for(int i=2;i<=n;++i) // Recursively calculate three plates
        d[i] = 2*d[i-1] + 1;
    memset(f,0x3f,sizeof f);
    f[0]  = 0;
    for(int i=1;i<=n;++i)
        for(int j=0;j<i;++j)
        // f[j] when there are four towers, move the first j towers to one.
        // Then you have to move back, so it's * 2
        // After that, when the remaining i-j are moved, there are only 3, so it is d[i-j]
            f[i] = min(f[i],2*f[j]+d[i-j]);
    for(int i =1;i<=n;++i)
        printf("%d\n",f[i]);
    return 0;
}

Fractal City

Title Link

Recursion + divide and conquer + mathematical coordinate system formula + law finding
Recursion + divide and conquer makes it easy to understand, because the most remarkable feature of this topic is that it constantly repeats rotation and replication, that is, NN level cities, which can be constructed by 44 N − 1N − 1 level cities. Therefore, we can constantly fractal N − 1N − 1 level cities every time and continuously narrow the scope of the problem
In fact, there are two mathematical coordinate formulas for this problem. One is the mathematical function of high school, rotation, which is a difficulty. In fact, it can be solved by finding the law. The second formula is the Euclidean distance formula. (x1−x2)2−(y1−y2)2−−−−−−−−−−−−−−−−−−√(x1−x2)2−(y1−y2)2
The most difficult thing is how to rotate the square to find the law.
Generally speaking, this topic has a lot of mathematical knowledge. It can give you a favorable foot in NOIP by investigating the drawing ability, natural solution and data cancer.

• Upper left corner: we can find that the N − 1N − 1-level matrix in the upper left corner is actually N − 1N − 1, that is, the previous matrix, rotated 90 ° 90 ° clockwise. In that case, we can synthesize the formula given by yxc teacher in class (supplement: i.e. rotation matrix, which belongs to the linear algebra of the University) to obtain the coordinates of a point in the transferred matrix from (x,y)(x,y) becomes (y,x)(y,x)
• Lower left corner: the same as the upper left corner, it rotates 90 ° counterclockwise and turns horizontally, that is, it is symmetrical along the xx axis. Originally, it is (y, − x)(y, − x) after counterclockwise, and then it should be symmetrical. The xx coordinate remains unchanged and the yy coordinate is reversed, so the coordinates are (− y, − x) (− y, − x), which is the so-called (2) × len−1−y,len−1−x)(2 × Len − 1 − y, len − 1 − x) the most difficult coordinates, which can be understood by drawing
• Upper right corner and lower right corner: it is found through the N=2N=2 level graph that it is actually the same as N=1N=1. There is no rotation but only translation, so the coordinates of the upper right corner are (x,y+len)(x,y+len), and the coordinates of the lower right corner are (x+len,y+len)(x+len,y+len)

In general, the above four transfers can be understood by drawing
There is also the data cancer of this problem. It is best to round double, and the integer type must be long long, otherwise it is easy to WA!

Source of the problem: https://www.acwing.com/solution/content/814/

Tips:
The coordinate formula obtained by rotating the coordinate (x,y) clockwise for a certain number of degrees is:
∣ cos ⁡ θ sin ⁡ θ − sin ⁡ θ cos ⁡ θ ∣ \left| \begin{matrix} \cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \\ \end{matrix} \right| ∣∣∣∣​cosθ−sinθ​sinθcosθ​∣∣∣∣​

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
#define PLL pair<ll,ll>
PLL calc(ll n,ll m)
{
    if (n==0)
        return make_pair(0,0);
    ll len=1LL<<(n-1),cnt=1LL<<(2*n-2);
    PLL pos=calc(n-1,m%cnt);
    ll x=pos.first,y=pos.second;
    ll z=m/cnt;
    if (z==0)
        return make_pair(y,x);
    if (z==1)
        return make_pair(x,y+len);
    if (z==2)
        return make_pair(x+len,y+len);
    return make_pair(2*len-1-y,len-1-x);
}
int main()
{
    //ios::sync_with_stdio(false);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,a,b;
        scanf("%lld%lld%lld",&n,&a,&b);
        PLL x=calc(n,a-1);
        PLL y=calc(n,b-1);
        ll dx=x.first-y.first,dy=x.second-y.second;
        double ans=(sqrt(double(dx*dx+dy*dy))*10);
        printf("%0.lf\n",ans);
    }
    return 0;
}