Violence enumeration~

Statistical square

Statistical block
Examination site ：
Looking for a regular + Loop enumeration

In fact, this problem has nothing to do with violence enumeration , The key is to find the rules .

Simulate several cases , Find out from (1,1) Start enumerating each point （ The first point is (0,0))

 Number of squares  = min(i, j)
 Number of rectangles  = i * j -  Number of squares 

Add up the number of squares of all the points to get the answer .

ac Code ：

#include <iostream>

using namespace std;

int main()
{
    
	long long n, m, sqr = 0, all = 0;
	cin >> n >> m;
	for(int i = 1; i <= n ; i++)
		for(int j = 1; j <= m; j++)
		{
    
			sqr += min(i, j);
			all += i * j;
		}
	
	cout << sqr << ' ' << all - sqr;
}

Roast Chicken

Roast Chicken
Examination site ： Loop enumeration

notes ： You can not open this array , Just enumerate the violence .
Complexity is 3^10 Power , You can receive .

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

int res[55000][10];
int main()
{
    
	int n, ans = 0;
	cin >> n;
	if(n < 10 || n > 30) cout << 0 << endl;
	else
	{
    
		for(int a = 1; a <= 3; a++)
			for(int b = 1; b <= 3; b++)
				for(int c = 1; c <= 3; c++)
					for(int d = 1; d <= 3; d++)
						for(int e = 1; e <= 3; e++)
							for(int f = 1; f <= 3; f++)
								for(int g = 1; g <= 3; g++)
									for(int h = 1; h <= 3; h++)
										for(int i = 1; i <= 3; i++)
											for(int j = 1; j <= 3; j++)
												if(a + b + c + d + e + f + g + h + i + j == n)
												{
    
													res[ans][0] = a;
													res[ans][1] = b;
													res[ans][2] = c;
													res[ans][3] = d;
													res[ans][4] = e;
													res[ans][5] = f;
													res[ans][6] = g;
													res[ans][7] = h;
													res[ans][8] = i;
													res[ans][9] = j;
													ans++;
												}
		cout << ans << endl;
		for(int i = 0; i < ans; i++)
		{
    
			for(int j = 0; j < 10; j++)
				cout << res[i][j] << ' ';
			puts("");
		}
	}
}

Three strikes in a row

Three strikes in a row

Examination site ： Permutation enumeration
Ideas ：
take 1-9 Full Permutation , And then it's made up of 3 Number , Let's see if these three figures are in proportion , If it meets the requirements, it will output .

Examination site ：
next_permutation

next_permutation： Arrange the contents of the array in dictionary order . After the arrangement, it will return to 0, Suitable for use do while To manipulate this function .

ac Code ：

#include <iostream>
#include <algorithm>
using namespace std;

int num[9] = {
    1,2,3,4,5,6,7,8,9};

int main()
{
    
	double a, b, c;
	int flag = 0;
	cin >> a >> b >>c;
	do
	{
    
		double x = num[0] * 100 + num[1] * 10 + num[2];
		double y = num[3] * 100 + num[4] * 10 + num[5];
		double z = num[6] * 100 + num[7] * 10 + num[8]; 
		if(x / y == a / b && x / z == a / c && y / z == b / c) flag = 1,cout << x << ' ' << y << ' ' << z << endl;
	}while(next_permutation(num, num + 9));
	if(flag == 0) cout << "No!!!";
}

Selection

Selection

Examination site ： Composite enumeration

Combined enumeration templates ：
Remember the idea and you can write this template .
thought ： Take the number from the first position , After taking it , Go to the next position to get , And take a number （ Don't take it again ）.
The subscript problem is not fixed , Specific analysis of specific problems , Ideas matter most

#include <iostream>

using namespace std;

const int N = 1010;
int n,m;
int path[N];

void dfs(int u,int start)
{
    
    if(u == m)
    {
    
        for(int i = 0; i < m; i++) printf("%d ",path[i]);
        printf("\n");
        return;
    }
    
    for(int i = start; i <= n; i++)
    {
    
        path[u] = i;
        dfs(u+1,i+1);// Can not write start+1, Draw a recursive search tree 
        path[u] = 0;
    }
}

int main()
{
    
    cin>>n>>m;;
    dfs(0,1);
}

ac Code

#include <iostream>

using namespace std;


const int N = 30;
int n, m;
int a[N];
int b[N];
int ans;

bool check(int x)
{
    
	for(int i = 2; i <= x / i; i++)
		if(x % i == 0) 
			return false;
	return true;
}

void dfs(int u, int start)
{
    
	if(u == m)
	{
    
		int res = 0;
		for(int i = 0; i < m; i++) res += b[i];
		if(check(res)) ans++;
		return;
	}
	
	for(int i = start; i < n; i++)
	{
    
		b[u] = a[i];
		dfs(u + 1, i + 1);
		b[u] = 0;
	}
}

int main()
{
    
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin>>a[i];
	dfs(0, 0);
	cout << ans;
}

Combined output

Combined output

This problem is the template problem of combinatorial enumeration .

ac Code ：

#include <iostream>

using namespace std;

const int N = 25;
int n, m;
int a[N];

void dfs(int u, int start)
{
    
	if(u == m)
	{
    
		for(int i = 0; i < m; i++) printf("%3d", a[i]);
		puts("");
		return;
	}
	
	for(int i = start; i < n; i++)
	{
    
		a[u] = i + 1;
		dfs(u + 1, i + 1);
		a[u] = 0;
	}
}

int main()
{
    
	cin >> n >> m;
	dfs(0, 0);
}

Full Permutation

Direct use next_permutation Just fine . Refer to the three combos above . It's simple .

ac Code ：

#include <iostream>
#include <algorithm>

using namespace std;

int a[10];

int main()
{
    
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) a[i] = i + 1;
	do
	{
    
		for(int i = 0; i < n; i++) printf("%5d", a[i]);
		puts("");
	}while(next_permutation(a, a + n));
	
}

Martian

I have written an explanation before , Direct use next_permutation that will do
https://blog.csdn.net/m0_51641706/article/details/121986470