首页 > 地斗主
开通博客写题解
头像 lifehappy
发表于 2020-08-12 22:55:27
地斗主 思路 看到这非常大，感觉一定是个结论公式题，但是感觉又不像是排列组合，于是可以考虑矩阵快速幂了，所以关键就是得得到递推公式了。 我们将棋盘分成两部分我们假定显然对分别有种分法，对应到原来一整块的部分上也就是,并且后面的变化是由不断循环下去的，所以我们只要将即可得到递推式 接下来就是这么一个简 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 zzugzx
发表于 2020-08-12 14:02:43
题目链接 题意：题解：AC代码 /* Author : zzugzx Lang : C++ Blog : blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #def 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-08-14 15:09:55
题意：给你一个4 * n的矩阵，让你用1 * 2的矩阵填满，求有多少种方法？ 思路：n=1时有1种n=2时有5种n=3时有11种n=4时有36种由官方题解可知dp[i]=dp[i-1]+5d[i-2]+dp[i-3]-dp[i-4].所以我们可以用矩阵快速幂求结果。为了防止产生负数，所以-1可以等价 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 blowhail
发表于 2020-08-16 20:02:08
推出前几项为1,5,11,36 ，直接用oeis找出规律(:з」∠)a(n) = a(n-1) + 5*a(n-2) + a(n-3) - a(n-4)因此，可以用矩阵快速幂来算[a(5),a(4),a(3),a(2)] = [a(4),a(3),a(2),a(1)] * #include &l 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 鞠永全
发表于 2020-08-12 17:16:57
题意：用1 X 2的矩形填充4 X n的矩形，共有多少种不同方法。 思路：原来写过一个2*n的，递推推公式就行。如果n-1行填满的话，第n行只有一种情况，如果n-2行填满的话，有4种情况； 如果n-3行填满的话，有2种情况； 如果n-4行填满的话，有3种情况； 如果n-5行填满的话，有2种情况； 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 horz
发表于 2020-08-13 10:23:29
题意 用 的骨牌去填充 的矩阵，问有几种方法。 分析 手算一下前五项，可以得到这么一个序列：1,5，11，36，95 设 表示拼完前 i 列的方案数。这时考虑 OEIS 。可以得到递推式： 然后利用矩阵快速幂就可以解决了。 #include <bits/stdc++.h> usin 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunsetcolors
发表于 2020-08-12 13:27:10
地斗主 题目地址： https://ac.nowcoder.com/acm/problem/19833 基本思路： 我们看到对于的数据,所以很明显这题应该能推出公式,因此,我们手推或者打表出前几项，然后我们用我们睿智的头脑,和锐利眼光去观察(使用oeis),就能得到如下递推式： . 然后我们 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”