专注都难不倒 (2)

PART1:Zipper

Problem

Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order. For example, consider forming “tcraete” from “cat” and “tree”: String A: cat String B: tree String C: tcraete As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming “catrtee” from “cat” and “tree”: String A: cat String B: tree String C: catrtee Finally, notice that it is impossible to form “cttaree” from “cat” and “tree”.

Input

The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line. For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive.

Output

For each data set, print: Data set n: yes if the third string can be formed from the first two, or Data set n: no if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.

Sample Input

3
cat tree tcraete
cat tree catrtee
cat tree cttaree

Sample Output

Data set 1: yes
Data set 2: yes
Data set 3: no

[tip] 使用动态规划。因为很多时候会需要重复判断（这也是 DP 提出来的缘故），使用 int flag[i][j] 来表示第一个字符串 str1[i..end] 和 str2[j..end] 能否组成第三个字符串（0 表示不确定，1 表示可以，-1 表示不可以）[/tip]

整套代码如下:

#define bits 201
 
#include<iostream>
using namespace std;
 
int flag[bits][bits];//0表示不确定，1表示可以，-1表示不可以
 
bool match(char* first,int lenfirst, char* second,int lensecond, char* third)
{
	if(flag[lenfirst][lensecond]==1)//对以前情况（已经搜索过）的判断
		return true;
	else if(flag[lenfirst][lensecond]==-1)
		return false;
	else
	{
		int i=0,j=0,k=0;
		while(i<lenfirst||j<lensecond)
		{
			if(first[i]!=second[j])//左右字符不等的时候必然只能从其中一个取
			{
				if(third[k]==first[i])
				{
					i++;
					k++;
				}
				else if(third[k]==second[j])
				{
					j++;
					k++;
				}
				else
				{
					flag[lenfirst][lensecond]=-1;//左右字符不等且都不等于第三个字符串，判定取法失败
					return false;
				}
			}
			else//但是左右字符相等的时候可以尝试两张不同的取法
			{
				bool flag1=match(&first[1],lenfirst-1,second,lensecond,&third[1]);
				if(flag1==true)
				{
					flag[lenfirst][lensecond]=1;
					return true;
				}
				bool flag2=match(first,lenfirst,&second[1],lensecond-1,&third[1]);
				if(flag2==true)
				{
					flag[lenfirst][lensecond]=1;
					return true;
				}
				else
				{
					flag[lenfirst][lensecond]=-1;
					return false;
				}
 
			}
		}
		flag[lenfirst][lensecond]=1;
		return true;
	}
}
 
int main()
{
	int n;
	char first[201],second[201],third[401];
	scanf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}s{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}s{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}s",first,second,third);
		memset(flag,0,bits*bits*sizeof(int));//记得初始化flag数组
		bool flag1=match(first,strlen(first),second,strlen(second),third);
		if(flag1==true)
			printf("Data set {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d: yesn",i);
		else
			printf("Data set {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d: non",i);
	}
	return 0;
}

PART2: Lenny’s Lucky Lotto

Problem

Lenny likes to play the game of lotto. In the lotto game, he picks a list of N unique numbers in the range from 1 to M. If his list matches the list of numbers that are drawn, he wins the big prize.

Lenny has a scheme that he thinks is likely to be lucky. He likes to choose his list so that each number in it is at least twice as large as the one before it. So, for example, if N = 4 and M = 10, then the possible lucky lists Lenny could like are:

1 2 4 8

1 2 4 9

1 2 4 10

1 2 5 10

Thus Lenny has four lists from which to choose.

Your job, given N and M, is to determine from how many lucky lists Lenny can choose.

Input

There will be multiple cases to consider from input. The first input will be a number C (0 < C <= 50) indicating how many cases with which you will deal. Following this number will be pairs of integers giving values for N and M, in that order. You are guaranteed that 1 <= N <= 10, 1 <= M <= 2000, and N <= M. Each N M pair will occur on a line of its own. N and M will be separated by a single space.

Output

For each case display a line containing the case number (starting with 1 and increasing sequentially), the input values for N and M, and the number of lucky lists meeting Lenny’s requirements. The desired format is illustrated in the sample shown below.

Sample Input

3
4 10
2 20
2 200

Sample Output

Case 1: n = 4, m = 10, # lists = 4
Case 2: n = 2, m = 20, # lists = 100
Case 3: n = 2, m = 200, # lists = 10000

因为比较简单，就不用 tips 了，直接上代码+注释

#define bits 2001
#include
using namespace std;
 
int N,M;
double path[bits][12];     //path[i][j]保存由数字i开始到最后，步长为j的路径数目
 
double makeup(int N,int M)
{
	memset(path,0,sizeof(double)*bits*12);
	for(int i=M;i&gt;0;i--)
	{
		path[i][1]=1;//1步的话（也就是只包括数字自己本身）只有1
	}
	for(int i=M/2;i&gt;0;i--)
	{
		path[i][2]=M-i*2+1;
		for(int j=3;j&lt;=N;j++)
		{
			for(int k=i*2;k&lt;=M;k++)
			{
				if(path[k][j-1]&gt;0)
					path[i][j]+=path[k][j-1];//这一步是关键
				else
					break;
			}
		}
	}
	double total=0;
	for(int i=1;i&lt;=M;i++)
	{
		total+=path[i][N];//将所有步长为N的数字都加起来就得到总数
	}
	return total;
}
 
int main()
{
	int C;
	scanf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d",&amp;C);
	for(int i=1;i&lt;=C;i++)
	{
		scanf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d",&amp;N,&amp;M);
		printf("Case {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d: n = {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d, m = {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d, # lists = {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}.0lfn",i,N,M,makeup(N,M));  //输出double时要作为整数输出{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}.0lf
	}
}

2 评论

留下评论取消回复