Luogu 2467 [SDOI2010]地精部落
挺有意思的题。
优质题解: https://www.luogu.org/blog/user55639/solution-p2467
题意为求长度为n,取值为$[1, n]$的波动序列的个数。
首先需要三个性质:
性质1:在一个波动序列中,如果数字$i$与数字$i - 1$不相邻,那么把$i$与$i - 1$交换之后也会构成一个波动序列
性质2:如果已经构造好了一个波动序列,那么把这个序列中的每一个数$a_{i}$全部变成$(n + 1 - a_{i})$也是一个波动序列,且山谷和山峰的位置相反
性质3:一个波动序列倒过来也是一个合法的波动序列
首先根据性质3,我们只要算出以山峰开头的波动序列的个数,然后乘以二就是最终的答案了。
我们设$f_{i, j}$表示选用区间$[1, i]$中的数,且数字$j$开头为山峰的方案数。
考虑转移: $f_{i, j} = f_{i, j - 1} + f_{i - 1, i - j + 1}$ $(2\leq j\leq i )$
解释一下这个转移方程,由于性质1,当数字$j$与数字$j - 1$不相邻的时候,我们直接交换数字$j$和数字$j - 1$可以构造出合法的波动序列
考虑数字$j$与数字$j - 1$相邻的情况,这时候我们构造的序列相当于这样
$(j), (j - 1), ..., ..., ...$
因为$j$一定是一个山峰的位置,那么$j - 1$一定是一个山谷的位置,那么相当于我们要加上数字取值在$[1, j - 1] \cup [j + 1, i]$且以数字$j - 1$开头的山谷的数量
我们的状态设计并不能拆分区间,但是我们可以考虑把$[j + 1, i]$区间的数字全部都向左平移一位,这样并不会改变构造的波动序列的合法性
由于性质2,我们所求的这一段答案就是$f_{i - 1, (i - 1) + 1 - (j - 1) = i - j + 1}$。
考虑到1开头作山峰的时候没有合法的波动序列,所以初态从2开始。
滚掉第一维即可。
时间复杂度$O(n ^ {2})$
思维量和码量的差距还是很大的。
Code:
#include <cstdio>
using namespace std; const int N = ; int n, P, f[][N]; int main() {
scanf("%d%d", &n, &P);
f[][] = ;
for(int i = ; i <= n; i++)
for(int j = ; j <= i; j++)
f[i & ][j] = (f[i & ][j - ] + f[(i - ) & ][i - j + ]) % P; int ans = ;
for(int i = ; i <= n; i++)
ans = (ans + f[n & ][i]) % P; printf("%d\n", ans * % P);
return ;
}
我真的不会数数呜呜呜……
最新文章
- 安装生物信息学软件-R
- xshell5 启动显示 mfc110.dll msvcp110.dll 未找到问题 解决办法
- 在Unity中使用贝塞尔曲线(转)
- 创建ORACLE JOB
- Git教程之分支管理之二
- cisco通过控制口或者通过远程配置交换机
- Python读取Excel数据
- 算法起步之A星算法
- TCP中ECN的工作原理分析二(摘自:RFC3168)
- 201521123071 《JAVA程序设计》第二周学习总结
- java.sql.SQLException: Incorrect string value: &#39;\xE5\xBC\xA0\xE9\x9B\xB7&#39; for column &#39;content&#39; at row 1
- OSPFv3与OSPF的配置
- UVa 10382 - Watering Grass 贪心,水题,爆int 难度: 0
- C# 使用 iTextSharp 将 PDF 转换成 TXT 文本
- inux下C中怎么让才干安全关闭线程
- C字符串
- 使用webpy创建一个简单的restful风格的webservice应用
- 部署 Flask 应用时,为什么会需要 gunicorn 或 uWSGI?
- git常用命令简集
- ZT 用gdb调试core dump文件
热门文章
- @angular/cli项目构建--httpClient
- Codeforces Round #263 (Div. 2)C(贪心,联想到huffman算法)
- 1.mysql优化---优化入门之MySQL的优化介绍及执行步骤
- 1110. Complete Binary Tree (25)
- QString的拼接
- object.observe数据绑定
- BZOJ2002:[HNOI2010]弹飞绵羊
- Pix mesa 自动化测试
- idea debug的时候 启动起来超级慢
- 环形缓冲区的应用ringbuffer