专栏文章

最古遗迹（贡献延迟）

____Dice___
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min4eszl
此快照首次捕获于
2025/12/01 20:23
3 个月前
此快照最后确认于
2025/12/01 20:23
3 个月前
查看原文
最古遗迹
考虑设 fi,jf_{i,j} 表示倒着考虑到 ii，≤j\leq j 的数都填了，剩下的所有数字都 >j+1>j+1，只考虑 ≤j\leq j 的数字的贡献。
考虑 fi,jf_{i,j} 去更新 i−1i-1 的填的什么。
p为必须死的人数，q为必须活的人数
  • i−1i-1 必须死，那有 fi,j×(j−p)→fi−1,jf_{i,j} \times (j-p) \to f_{i-1,j}
  • i−1i-1 必须活。
  1. 若 i−1i-1 填 >j+1>j+1，fi,j→fi−1,jf_{i,j} \to f_{i-1,j}（忽略 i−1i-1 的贡献）。
  2. 否则 i−1i-1 填 =j+1=j+1。
设 j′j' 为填了 j+1j+1 之后的到达的值。
  • i−1i-1 自身的贡献，他的初始值必须 >j>j，并且 j+2∼j′j+2 \sim j' 都必须填。
可以算出来贡献是有多余的名额是 2×(j′−j)2\times (j'-j)，i−1i-1 之后要用的名额是 j′−j−1j'-j-1，所以还剩下 2j′−2j−j′+j+1=j′−j+12j'-2j-j'+j+1=j'-j+1 个。
接下来考虑剩下的 j+1,j+2...,j′j+1,j+2...,j' 这其中每个数字都有 22 个，但是我之从其中选出来 n−(i−2)n-(i-2) 个。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...