第十届蓝桥杯题解(个人向)
第一题 平方和
算$1 $到$2019$中含有$2,0,1,9$的数的平方和。
1 |
|
第二题 数列求值
求类似斐波那契数列$f[i] = f[i-1] + f[i-2] + f[i-3]$ ,求$f[20190324]\%10000$。
1 |
|
第三题 最大降雨量
答案34.贪心即可。注意中位数的中位数
第四题 迷宫
第九题 糖果
题意
有n袋糖,里面有m种糖,每袋糖有k个,问至少取几包才能攒够所有种类的糖。
$n \leq 100;m,k\leq 20$
题解
状压dp。我场上直接上暴力了。但是场下经过队友提示,发现就是个简单的状压dp。
因为他的$m$低于20所以我们可以用二进制位来表示。总的复杂度$O(2^m *n)$
状态转移方程 $dp[S|i] = min(dp[S|i],dp[i]+1)$
可能ac的代码
1 |
|