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#

Mr. He is climbing 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 it. For example, if there are 3 steps, he can take one step at a time, or take one step then two steps, or take two steps then one step, or take all three steps at once, resulting in a total of 4 methods.

Unfortunately, some steps are broken, and Mr. He cannot step on these. 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 to climb the broken steps to 0 during the recursion process.

Note that there may be broken steps at the very 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. Calculate how many different tiling schemes there are.

Input#

A single line with an integer n, 0<n<1000.

Output#

A single line with an integer, representing the number of tiling schemes mod 12345.

Input Example 1#

Output Example 1#

Idea#

There is one way to fill from the previous square.

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

However, all using 1x1 are included in the way of filling from the previous square.

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 a 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 city (but cannot skip city 1 and city n), making the total distance from city 1 to city n as small as possible. Assume each city i has coordinates (x i, y i), the distance from city 1 at (x 1, y 1) to 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, indicating the minimum total distance from city 1, skipping one city, to 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 effect of deleting each point on the distance, 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 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 ways there are to arrange the ribbons according to these requirements.

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

Input#

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

Output#

A single line with an integer, indicating the number of arrangements for decorating the window with ribbons.

Input Example 1#

Output Example 1#

Hint#

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

Idea#

Thanks to perisino for the guidance.

f[i] represents the number of arrangements for 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 a different color from 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 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)}$

Use long long, use long long, 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 printLL(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.printLL();
			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 taken mod 12345.

Input Example 1#

Output Example 1#

Idea#

This is a difficult problem!

Looking at the big guy's table to find the pattern made me emotional.

Then I also used 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 this pattern might be something I could never discover in my lifetime...~~

~~This is probably the gap between me and the big guys.~~

The big guys here refer 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,

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

If it has an odd number, we 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 Splitting#

Description#

For a positive integer K, find all the splits 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 right to left. For example:

When K=4, the following splits 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, 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 are 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 made me feel awkward.

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 results

Isn't this $(2^n-1)$...?

So I AC'd it 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 went to find the correct answer.

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, when it is 2 there are 2, when it is 0 there are 4.

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 possible cases for i, if i is odd, f[i]=f[i-1], if i is even, f[i]=f[i-1]*2.

Wow, %%%