SCOI2010 六题题解

首先爆搜出所有的幸运数字,然后把倍数去重。这样还剩 943 个。

对于一个数字 x[A,B] 中的倍数的个数是 \lfloor \frac{B}{x} \rfloor - \lceil \frac{A}{x} \rceil +1

然后直接 DFS 跑容斥,将所有数字按照从大到小的顺序排序,选 1 个号码的答案 -2 个号码的 \text{lcm} 的答案 +3 个号码的 \text{lcm} 的答案……

将数字按照从大到小的顺序排序,使得 \text{lcm} 能够更快地超越上界。

考虑二分图匹配。左面一排点代表属性,右面一排点代表装备。意义是如果发挥当前的属性的装备被用过了,那用那个装备的属性就换一种。匈牙利即可。

设计状态 dp[i][j] 表示第 i 天持有 j 支股票的答案。

转移分为三种:

  • 从 dp[i-1][j] 转移
  • 从 dp[i-w-1][k] 转移(买入)
  • 从 dp[i-w-1][k] 转移(卖出)

考虑后两个的转移式子:

\text{dp}\left[ i \right] \left[ j \right] =\max \left\{ \text{dp}\left[ i-w-1 \right] \left[ k \right] -\text{ap}\left[ i \right] \times \left( j-k \right) \right\}

 

\text{dp}\left[ i \right] \left[ j \right] =\max \left\{ \text{dp}\left[ i-w-1 \right] \left[ k \right] +\text{bp}\left[ i \right] \times \left( k-j \right) \right\}

把后面的 y \times (j-k) 那部分展开,发现后两种转移是个滑动窗口,上单调队列。

经典套路,二维正交坐标系把 1 看做向右走,把 0 看做向上走,答案为不跨越直线 y=x (在下半部分走)到达点 (n,m) 的方案数。

也即不触碰直线 y=x+1 到达的方案数。以 y=x+1 为对称轴做 (n,m) 的对称点为 (m-1,n+1)

答案为 C_{n+m}^n - C_{n+m}^{m-1}

三分套三分。设在 AB 上从 A \rightarrow E ,在 CD 上从 F \rightarrow D ,那么中间就是 E \rightarrow F

然后对 E 三分,固定 E 的位置三分 F 的位置。

 [Scoi2010]序列操作

直接上线段树硬搞。维护最左端 0/1 最右端 0/1 和整段的 0/1 即可。

合并的时候讨论一下。

下推的时候覆盖标记消翻转标记,翻转标记优先翻转覆盖标记,再更新自己。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据