这次的主题根据周围同学的反应普遍很难,但是仔细看看主题其实并不难。 因为不涉及复杂的算法。 但是,这次的主题都很复杂,写起来很花时间。
主题说明:众所周知有很多人排成m行n列。 (M,n都在10以上1000以下),现在从这些人中选出几个人。 在这个m行n列的队伍中,每个人对应一个坐标,从最左上的(0,0 )到右下的) M-1,N-1。 他们也按蜗牛壳一样形状的顺时针方向从外轮像内圈一样数数,数的1位为7、10位为奇数的人出来后,按照数的顺序计算输出他们坐标的数。
例如,如下图所示,是5行5列的队伍,按照顺时针顺序从外向里计数。 其中17个满足条件,因此需要输出17个坐标(1,1 )。
输入格式和输出格式:
输入行数m和列数n
10 10输出满足条件的坐标:
请注意[ 7,9 ]、[ 1,1 ]、[ 8,2 ]、[ 7,5 ]、[ 4,4 ] ]输出时存在孔。 在前一组的输出坐标之后输出逗号分隔符号,在最后一组的坐标之后不输出逗号。 因此,必须找到满足最后一个条件的坐标,以防止在输出时输出逗号。
第一个问题的想法很明确。 首先创建一个m行n列的纯0数组,按此顺时针顺序走一遍,然后为每个坐标位置赋值。 然后,输出满足所列条件的申报数的坐标即可。 按顺序走的时候,需要按以下顺序走。
如果坐标的左边和上面的位置已经计数,右边的位置还没有计数,则该位置计数后继续向右计数。 如果坐标的右边和上面的位置已经计数,下面的位置还没有计数,则在该位置计数后继续向下计数。 如果坐标的右下位置已经计数,而左下位置尚未计数,则该位置将在计数后继续向下计数。 如果坐标的左边和下边的位置已经计数,而上边的位置还没有计数,则该位置在计数后继续向上计数。
上面的报数的意思其实是给二维数组赋值的过程。 首先需要注意数完最外周的报数。 这是因为,在进行判断时,会检查这些坐标的相邻外周要素的状态。 如果不先计算最外周的报数,在以后访问时数组会越界。 第一题代码# includeiostreamusingnamespacestd; int main () { int M,n; cin M N; int sum0=M*N; //从后向前查找符合条件的最后计数。 while(sum00 ) { int r1=sum0 % 100; int x1=r1 % 10; r1=r1/10; int x2=r1; if(x1==7x2%2==1) break; sum0--; //sum0此时满足条件的最后计数} int a[M][N]; for(intI0=0; i0米; i0 ) for(intJ0=0; j0 N; j0 ) a[i0][j0]=0; int count=1; int i=0,j=0; cout '[; while(a[I][j]==0) {a[i][j]=count; 出局; int s0=a[i][j]; int r0=s00; 除以//100的馀数为后2位,用r0记录。 int y1=r0 % 10; //y1为一位r0=r0/10; int y2=r0; //y2是10位if(y1==7y2%2==1) ) /以满足条件的计数输出(cout ) () I )、(j ) ); if(a ) I ) j )!=sum0)//输出最后复合条件的件数时,无逗号单独处理。 cout ','; (if ) I==0jn-1 )//先在最外环进行报告数j; ELSEif(I==0j==n-1 ) I; ELSEif(Im-1j==n-1 ) I; ELSEif(I==m-1j==n-1 ) j----; ELSEif(I==m-1j0 ) j----; ELSEif(I==m-1j==0) I----; ELSEif(I1j==0) I----; elseif(I==1j==0) j; //开始申报内圈的else if (a [ I-1 ] [ j ] 0a [ I ] [ j-1 ] 0a [ I ] [ j ]
1] == 0)j++;else if (a[i - 1][j]>0 && a[i][j + 1]>0 && a[i + 1][j] == 0)i++;else if (a[i + 1][j]>0 && a[i][j + 1]>0 && a[i][j - 1] == 0)j--;else if (a[i +1][j]>0 && a[i][j - 1]>0 && a[i - 1][j] == 0)i--;} cout << ']'; return 0;}运行结果:
调试过程中记录队伍报数编号的矩阵:
给定二叉树每个节点的深度,计算多少种满足条件的二叉树。根节点深度为0.
输入描述:
第一行为一个整数N,表示二叉树节点的数量,在1到1000之间。
第二行为N个整数,d1,d2,……dN表示每个节点的深度。
输出描述:
输出为满足条件的二叉树数量。由于结果可能非常大,因此输出为实际结果除以(10^9+7)之后的余数。
例:
输入:
输出:
2例子解读:
上面的输入表示深度为1的节点有一个,深度为0的节点有一个,深度为2的节点有两个。对应的两种二叉树的形状如下图所示:由答案为2可以知道该题目不区分元素的不同,只根据二叉树的形状进行分类。如果考虑元素分布的话,下图中D2-1和D2-2交换位置则又多了一倍的种类,因此此题目只考虑多少种形状的二叉树即可,即只考虑组合不考虑排列。
该题如果高中排列组合学的比较好的话应该比较容易想到思路,理清了数学关系这道题目就很简单了。
首先要根据输入把二叉树每层多少个节点数目统计好。例如D0,D1,D2……DN分别表示第0层,1层,……N层的节点数目。对于第i层,该层有Di个节点,则第i+1层有2Di个位置,因此需要从2Di个位置中选D(i+1)个位置进行放置,则放置方法有
种。然后把所有层的放置方法数全部乘起来就得到最后总的不同形状二叉树数量。
如上面的例子:第0 1 2层的节点数为1 1 2.因此对于第一层,有2个位置选一个有2种选取方法,对于第2层,从2个位置选两个有1种选择方法,因此总方法有2*1=2种方法,也就是两种不同形状的二叉树。
运行结果:
俄罗斯方块,输入有两个字符串,第一个frame表示当前底座状态,第二个brick表示下落方块的状态,下落的方块只能左右移动不会旋转。方块落下后如果一行全部充满则会消失,最后求最少还剩多少行。输入的底座和方块都不超过9列,即最大只有9列。
例如:
输入为:
底座和方块状态如下图所示:其中2122表示当前底座状态,都是底对齐的,而121表示下落方块的状态,都是顶对齐的,即2的位置的突出是往下凸而不是往上凸。下图运行结果为1,下图中方块左右移动有两种下落方式,一种如下图所示,下落后会消去两行最后剩余1行。另外一种下落方式是向又移动一格然后再下落,最后消去一行剩余3行,因此最少的结果是剩余1行,输出为1
输出为:
该题思路非常简单,把方块从左到右依次落下并记录剩余的行数,取行数最小的输出。但写起来较为繁琐,关键是如何表示方块。可以用一个二维数组来表示。如上面的例子,共有两种下落方法,一种是靠左边,此时将各列相加可得到3332.
12121223332注意方块下落所在的三列,高度都为3,和方块的顶对齐保持一致。说明这些列下方没有空格。如下图所示:
而靠右边下落的情况,将各列相加得2243。
注意方块下落所在的三列高度分别为243,不满足方块的顶部对齐条件。因此除了高度最高的那列之外,剩下的俩列都有空格,高度为2的有两个空格,高度为3的有一个空格。如下图所示:在处理中需要特别注意。另外输入的是字符串,需要把每个单独转化为数字处理。
运行结果: