A bunch of recursion problems

A Bunch of Recursion Problems#

——From Yizhong OJ and contests of Yizhong OJ

P1367【Training Problem】Climbing Stairs[2]#

Description#

Teacher He climbs stairs, and he can take 1, 2, or 3 steps at a time. Given the number of steps in the staircase, calculate the number of different ways to climb. For example, if there are 3 steps, he can take one step each time, or take one step first and then two steps, or take two steps first and then one step, or take three steps at once, resulting in a total of 4 methods.

Unfortunately, some steps are broken, and Teacher He cannot step on these steps. Now given the total number of steps N and the K broken steps, please calculate the total number of ways he can climb the stairs.

Input#

The first line: N, K. The second line: K integers h[i], indicating the broken steps (1<=h[i]<=N).

Output#

The number of different ways to climb, which may be a very large number, so output the final answer mod 1234567.

Input Example 1#

5 2
2 4

Output Example 1#

Hint#

1 <= N <= 1000 0 <= k < N

Idea#

Set the number of ways for all broken steps to 0 during the recursion process.

Note that there may also be broken steps at the beginning.

So use 0 as a boundary.

Check for out-of-bounds during the process.

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

const int MAXN=1005;

int f[MAXN];
bool h[MAXN];

int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=k;++i){
		int t;
		cin>>t;
		h[t]=1;
	}
	f[0]=1;
//	f[1]=1;
	for(int i=1;i<=n;++i){
		if(h[i]){
			f[i]=0;
			continue;
		}
		else if(!f[i]){
			if(i-1>=0)f[i]+=f[i-1];
			if(i-2>=0)f[i]+=f[i-2];
			if(i-3>=0)f[i]+=f[i-3];
			f[i]%=1234567;
		}
	}
	cout<<f[n]<<endl;
	return 0;
}

Tiling#

Description#

Use red 1×1 and black 2×2 tiles to completely cover an n×3 surface without overlapping, and find out how many different tiling schemes there are.

Input#

A single integer n, 0<n<1000.

Output#

A single integer, the number of tiling schemes mod 12345.

Input Example 1#

Output Example 1#

Idea#

There is one way to fill from the previous cell.

There are 3 ways to fill from the previous two cells.

However, using all 1x1 tiles is included in the filling from the previous cell.

So f[i]=f[i-1]+f[i-2]*2

f[0]=f[1]=1;

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

int f[1005];

int main(){
	int n;
	cin>>n;
	f[0]=f[1]=1;
	//f[2]=3;
	for(int i=2;i<=n;++i){
		f[i]=f[i-1]+f[i-2]*2;
		f[i]%=12345;
	}
	cout<<f[n]<<endl;
	return 0;
}

City Path#

Description#

There are n cities on the map, and a cow wants to start from city 1 and pass through these cities in order, finally reaching city n. However, the cow finds this too boring, so it decides to skip one of the cities (but cannot skip city 1 and city n), in order to minimize the total distance traveled from city 1 to city n. Assume each city i has coordinates (x i ,y i), the distance between city 1 at (x 1 ,y 1) and city 2 at (x 2 ,y 2) is | x 1 -x 2 | + | y 1 -y 2 |.

Input#

The first line contains a positive integer n, indicating the number of cities. The next n lines each contain 2 numbers x i and y i, indicating the coordinates of city i.

Output#

A single number, which is the minimum total distance traveled from city 1, skipping one city, to reach city n.

Input Example 1#

Output Example 1#

Hint#

The example indicates skipping city 2. 【Data scale】 For 40% of the data, n≤1000. For 100% of the data, 3≤n≤100000, -1000≤x i ,y i ≤1000.

Idea#

Some problems appear to be recursion problems, but can actually be solved by simulation.
? ——Lu Xun

This is greedy.

? ——~~hqx~~perisino

Compare the impact on the distance of deleting each point, and choose the shortest after deletion.

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;

const int MAXN=1e5+5;

struct zb{
	int x,y;
} city[MAXN];
int n;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&city[i].x,&city[i].y);
	}
	int maxs=0,maxi=0;
	int he=0;
	
	for(int i=2;i<n;++i){
		int tmp=
			abs(city[i+1].x-city[i].x)+abs(city[i+1].y-city[i].y)
			+abs(city[i-1].x-city[i].x)+abs(city[i-1].y-city[i].y);
		tmp-=abs(city[i+1].x-city[i-1].x)+abs(city[i+1].y-city[i-1].y);
		if(tmp>maxs){
			maxi=i;
			maxs=tmp;
		}
		he+=abs(city[i-1].x-city[i].x)+abs(city[i-1].y-city[i].y);
	}
	he+=abs(city[n-1].x-city[n].x)+abs(city[n-1].y-city[n].y);
	he-=maxs;
	printf("%d\n",he);
	return 0;
}

Ribbon#

Description#

For the 90th anniversary celebration, Xiaolin plans to use some white, blue, and red ribbons to decorate the school supermarket's window. He hopes to meet the following two conditions:

(1) Ribbons of the same color cannot be placed in adjacent positions;

(2) A blue ribbon must be placed between a white ribbon and a red ribbon.

Now, he wants to know how many different arrangements of ribbons satisfy the requirements.

For example, as shown in Figure 9.4-1, there are 4 arrangements for a window width of n=3.

Input#

A single integer n, indicating the width of the window (or the number of ribbons).

Output#

A single integer, indicating the number of arrangements of ribbons to decorate the window.

Input Example 1#

Output Example 1#

Hint#

For 30% of the data, 1≤n≤15. For 100% of the data, 1≤n≤45.

Idea#

This problem is thanks to perisino for the guidance.

f[i] represents the number of arrangements when there are i ribbons.

Note that the last ribbon cannot be blue.

When

The (i-1)th ribbon is red or white: Since the last ribbon cannot be blue, there is one case.
The (i-1)th ribbon is blue: The ith ribbon must be of a different color than the (i-2)th ribbon, which gives one case.
~~The previous big guy wrote the second (i-1) as (i-2) and I almost didn't understand it.~~

So f[i]=f[i-1]+f[i-2]

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

const int MAXN=50;

int f[MAXN];
int n;

int main(){
	f[1]=2;
	f[2]=2;
	cin>>n;
	for(int i=3;i<=n;++i){
		f[i]=f[i-1]+f[i-2];
	}
	cout<<f[n]<<endl;
	return 0;
}

Fibonacci Sum of the First N Terms#

Description#

Calculate the sum of the first n terms of the Fibonacci sequence modulo m.

Input#

A single line with two integers n m.

Output#

Output the sum of the first n terms modulo m.

Input Example 1#

5 1000

Output Example 1#

Hint#

1<=n<=2*10^9 1<=m<=1000000010

Idea#

It is the sum of the first n terms, not the nth term.

The data range is very large, use matrices.

~~I forgot matrix exponentiation, how embarrassing.~~

Matrix A: 1x3

? Content: f(i-1),f(i-2),g(i-1)

? Where f(i) represents the ith term of the Fibonacci sequence, and g(i) represents the sum of the first i terms.

Matrix B: 3x3

? Content:

		1 1 1
		1 0 1
		0 0 1

Then $f(n)=A\cdot B^{(n-2)}$

Make sure to use long long.

#include<cstdio>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;

const LL MAXN=5;

LL n,m;

struct matrix{
	private:
		LL v[MAXN][MAXN];
		LL h,l;
		
		void print(void){
			for(LL i=1;i<=h;++i){
				for(LL j=1;j<=l;++j){
					cout<<v[i][j]<<' ';
				}
				cout<<'\n';
			}
		}
	
	public:
		matrix(LL he,LL le){
			memset(v,0,sizeof(v));
			h=he,l=le;
		}
		
		friend matrix operator *(matrix a,matrix b){
			matrix c(a.h,b.l);
			for(LL i=1;i<=a.h;++i){
				for(LL j=1;j<=b.l;++j){
					 for(LL k=1;k<=a.l;++k){
					 	c.v[i][j]+=(a.v[i][k]*b.v[k][j]%m);
					 	c.v[i][j]%=m;
					 }
				}
			}
			return c;
		}
		
		friend matrix operator ^(matrix a,LL b){
			
			matrix ret(a.h,a.l),sum=a;
			for(LL i=1;i<=a.h;++i){
				ret.v[i][i]=1;
			}
			while(b){
				if(b&1){
					ret=ret*sum;
				}
				sum=sum*sum;
				b>>=1;
			}
//			ret.print();
			return ret;
		}
		
		void writeV(LL x,LL y,LL val) {
			v[x][y]=val;
		}
		
		LL callV(LL x,LL y){
			return v[x][y];
		}
};

	matrix a(1,3),b(3,3);
int main(void){
	cin>>n>>m;
	a.writeV(1,1,1);
	a.writeV(1,2,1);
	a.writeV(1,3,2);
	
	b.writeV(1,1,1);
	b.writeV(1,2,1);
	b.writeV(1,3,1);
	b.writeV(2,1,1);
	b.writeV(2,2,0);
	b.writeV(2,3,1);
	b.writeV(3,1,0);
	b.writeV(3,2,0);
	b.writeV(3,3,1);
	
	matrix c=a*(b^(n-2));
	cout<<c.callV(1,3)<<endl;
	
	return 0;
}

Even Number of 3s#

Description#

Write a program to find out how many n-digit numbers have an even number of the digit 3.

Input#

A single line with a positive integer n, 0<n<1000.

Output#

A single line with a positive integer, indicating how many n-digit numbers have an even number of 3s. The final answer is mod 12345.

Input Example 1#

Output Example 1#

Idea#

This is a difficult problem!

Looking at the big guy's table, I found the pattern and got AC, and my eyes were moist.

Then I also did a DFS to create a table.

However, I couldn't find any pattern.

Finally, I looked at the big guy's pattern and solution...

~~I found that I might never find this pattern in my life...~~

~~This is the gap between me and the big guy.~~

The big guy here refers to (wyx) [https://wuyanxi.top] and (perisino) [https://cnblogs.com/perisino].

Ignore the above part.

The main solution is to use f[i][0] to represent the number of i-digit numbers with an even number of 3s.

? Use f[i][1] to represent the number of i-digit numbers with an odd number of 3s.

If an (i-1) digit number has an even number of 3s, to make the i-digit number have an even number of 3s,

you can append 1,2,4,5,6,7,8,9,0.

If it has an odd number, you can append a 3.

Thus we have

f[i][0]=f[i-1][0]*9+f[i-1][1];
f[i][1]=f[i-1][1]*9+f[i-1][0];

Palindrome Partitioning#

Description#

For a positive integer K, find all the partitions of K and count the number of palindrome sequences among them. A palindrome sequence is one where all numbers in the sequence are the same when read from left to right or from right to left. For example:

When K=4, the following partitions exist:

4=1+1+1+1 (palindrome sequence 1)

=1+1+2

=1+2+1 (palindrome sequence 2)

=2+1+1

=2+2 (palindrome sequence 3)

=1+3

=3+1

There are a total of 3 palindrome sequences.

Input#

A single line with a positive integer K, 1<=K<=26.

Output#

A single positive integer, indicating the number of palindrome sequences.

Input Example 1#

Output Example 1#

Idea#

~~Some problems appear in recursion contests, but they are actually recursion problems.~~

? ~~——Lu Xun~~

I wrote a DFS to see how many points I could pass, and unexpectedly got AC.

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

int f[30];

void dfs(int step,int tot);
int k,cnt;

int main(){
	cin>>k;
	dfs(1,0);
	cout<<cnt<<endl;
	return 0;
}

void dfs(int step,int tot){
	if(tot>k)return;
	if(tot==k){
		bool flag=1;
		for(int i=1;i<=(step-1)/2;++i){
			if(f[i]!=f[step-i]){
				flag=0;
				break;
			}
		}
		if(flag){
			++cnt;
//			for(int i=1;i<step;++i){
//				cout<<f[i]<<' ';
//			}
//			cout<<'\n';
		}
	}
	for(int i=1;i<=k-tot&&i<k;++i){
		f[step]=i;
		dfs(step+1,tot+i);
	}
}

Seeing that I was 400+ms while others were 2, 3ms, I felt very embarrassed.

So I created a table.

for(int i=1;i<=26;++i){
    cnt=0;
    memset(f,0,sizeof(f));
    k=i;
    dfs(1,0);
    cout<<i<<' '<<cnt<<endl;
}

I got

Table Result

This is $(2^n-1)$, right?

So I AC'd again.

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

int qkpow(int x,int y);

int main(void){
	int k;
	cin>>k;
	cout<<qkpow(2,k/2)-1<<endl;
	return 0;
}

int qkpow(int x,int y){
	if(y==0){
		return 1;
	}
	int ret=1,sum=x;
	while(y){
		if(y&1){
			ret*=sum;
		}
		sum*=sum;
		y>>=1;
	}
	return ret;
}

Well, ~~

Then I looked for the correct solution.

Each number must be divided into 3 parts.

For 4: 4=1+2+1, we find that the middle number can only be even, i.e., 2 and 0, when it is 2 there is 1 sequence, when it is 0 there are 2 sequences.

For 6, when it is 4 there is 1 sequence, when it is 2 there are 2 sequences, when it is 0 there are 4 sequences.

Finally, for 5, the situation is very similar to 4, except that the middle number can only be odd.

Thus, let f[i] be the number of possible partitions of i, if i is odd, f[i]=f[i-1], if i is even, f[i]=f[i-1]*2.

Wow, %%%