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]);
最后所有过程记得取余就好了。