胡一个不是打表的做法,求完善
  • 板块P1662 数7
  • 楼主Ranya
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/10/14 11:25
  • 上次更新2023/10/27 07:36:57
查看原帖
胡一个不是打表的做法,求完善
365706
Ranya楼主2022/10/14 11:25

假如 n = 20。考虑报数过程中哪些数会是序列取反:7,14,17

如果我们先不取反,复原序列的过程会是:now = 20 表示第 20 个人报出 20 这个树。然后考虑 17 取反,以 17 为对称中心,即 17=(now+now)/217 = (now + now') / 2now=17×2nownow' = 17 \times 2 - now 所以更新 now = 17 * 2 - 20 = 14。

然后考虑 14 取反,now = 14

考虑 7 取反,now = 0。又因为总人数是 1337,所以 now=1337。

此时求得答案 当 n = 20,报出的人是 1337

aia_i 表示第 i 个需要取反的数,满足 aia_i 是七的倍数或含 7。

每个 aia_i 贡献为:如果 i 是奇数,a[i]2a[i] * 2,偶数,a[i]2-a[i]*2

然后如果 a 的个数为奇数,答案 n-n,否则 +n+n

至于如何求得 a 数组, 不会了。dp ?或者打表(

2022/10/14 11:25
加载中...