2012年台州学院第六届“星峰杯”大学生程序设计竞赛解题报告

2012台州学院第五届“星峰杯”大学生程序设计竞赛-by logx

D:涂鸦方格图

题目意思是有一个m1*n1大方格和一个m2*n2的小方格,从大方格中选m2行n2列使得重组的方格和小方格一模一样,

本题总的思想是深搜,用两个深搜选出行和列,用row[i],col[i]标记该行有没选:

首先我们要选取m1行中一行,进行深搜,和小方格的第一行进行匹配(选出来的是列),能选的列标记col[i]=1,假如从n1个数中能选出n2个数能按顺序匹配的话,再进行列的深搜从n1列中选取一列,与小方格的第一列匹配(选出的是行),同理标记选出的行row[i]=1,最后提取出选出来的小方块和目标方块比较看看是否相等。

E:校赛题目

题目刚开始看着有点晕,感觉提示这有点错误,第二个逗号后面的“可以为1或2的有1道题目”应改为“可以为2或3的有1道题目”。

题目中a[i]是难度系数为i的题数,难度系数可以为i也可以为i+1的有b[i]题。

本题总的思想就是DP,数据有点大的样子就直接都开了int64位的三个数组:

dp1[i]记录前i题,选难到度系数i的并且选a[i]的总的选法;

dp2[i]记录前i题,选到难度系数i的并且选b[i-1]的总的选法;

dp3[i]记录前i题,选到难度系数i的并且选b[i]的总的选法;

对难度系数为1的要进行初始化话;

对于第i个难度系数有以下递推方程:

1、选a[i]时,难度系数i-1可以选a[i-1] ,b[i-2],b[i-1]所以:

      dp1[i]=a[i]*(dp1[i-1]+dp2[i-1]+dp3[i-1]);

2、选b[i-1]时要注意下,难度系数i-1选a[i-1],b[i-2]都没问题,就是b[i-1]里被取了两个,那么:

      dp2[i]=b[i-1]*(dp1[i-1]+dp2[i-1])+(b[i-1]-1)*dp3[i-1];

3、选b[i]和选a[i]一样,难度系数i-1可以选a[i-1] ,b[i-2],b[i-1],所以:

      dp3[i]=b[i]*(dp1[i-1]+dp2[i-1]+dp3[i-1]);

最后所有过程记得取余就好了。
 


 

 


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.