首页 > 其他 > 详细

牛客 2018NOIP 模你赛2 T2 分糖果 解题报告

时间:2018-09-21 00:18:46      阅读:76      评论:0      收藏:0      [点我收藏+]

标签:视频   -a   单调栈优化   con   要求   现在   表示   回来   tps   

分糖果

链接:https://www.nowcoder.com/acm/contest/173/B
来源:牛客网

题目描述

\(N\) 个小朋友围成一圈,你有无穷个糖果,想把其中一些分给他们。
从某个小朋友开始,我们顺时针给他们标号为\(1\) ~ \(N\)。第 \(i\) 个小朋友可以得到至多 \(a[i]\),至少 \(1\) 个糖果。
问,有多少种分配方案使得每一对相邻的小朋友拿到的糖果数不同。答案对 \(10^9 + 7\) 取模。

输入描述:

第一行一个整数 \(N\)
接下来一行 \(N\) 个整数,第 \(i\) 个数表示 \(a[i]\)

输出描述:

一行一个整数,表示答案。

说明:

对全部的测试数据,\(n <= 10^6, a_i <= 10^9\)

  • \(10\) 分的数据,\(n <= 4\)
  • \(10\) 分的数据,\(n <= 100,a_i <= 20\)
  • \(20\) 分的数据,\(n <= 100,a_i <= 100\)
  • \(10\) 分的数据,\(n <= 10^5,a_i\) 全部相等
  • \(30\) 分的数据,\(n <= 10^5,a_i\) 为随机生成
  • \(20\) 分的数据,\(n <= 10^6\).

当时讲得视频本蒟蒻死活听不懂,回来花了好几天的语文课总算是能够自己理解了,和视频里面讲得并不太一样,也许是我理解麻烦了说不定

40pts的普通区间DP就不说了,不过吐槽一下没有\(N^2\)的档,事实上不用容斥是可以做到\(N^2\)的,只需要一些断环的技巧

下面正题

  • 大致分为三个步骤:
    1 链上答案的统计
    2 拆环为链
    3 单调栈优化

现在仅考虑为链的情况
先回归一下问题的本质,我们可以这样描述这个问题,我们要填满一个长度为\(n\)的数组,要求每两个相邻的位置填的数不能相等,每个位置的可填集合为\(1\)-\(n\)的正整数。(这看起来有变吗??

行吧,根据正难则反,换成容斥的话,先不管条件,求总方案,然后按照填了几个相等的数作为容斥系数,直接统计?听起来好像非常有道理,然而一点也说不到重点

这里直接给出状态转移方程进行分析了(事实上文字描述说起来不清楚,还容易产生误导

\(dp_i\)表示前\(i\)个位置构成的合法的方案数

\(dp_i=\sum_{i=0}^{i-1} dp_j \times min_{k=j+1}^i a_k \times (-1)^{i-j-1}\)

\(dp_0=1\)

先睡了,明儿再写了、、

牛客 2018NOIP 模你赛2 T2 分糖果 解题报告

标签:视频   -a   单调栈优化   con   要求   现在   表示   回来   tps   

原文:https://www.cnblogs.com/ppprseter/p/9684035.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号