欢迎光临散文网 会员登陆 & 注册

[ARC153C] ± Increasing Sequence

2023-03-14 14:52 作者:BNU_ACM  | 我要投稿
  • 构造严格递增的X序列,通过差分,可变为构造全为正的Y(首项除外)。

  • 推公式可知,Y需要满足与B的内积为0,其中B是A的后缀和。

  • 因A取值特殊,故B有一定性质。其中:若B有正有负,则一定有+1和-1。


  • 先考虑B有正有负的情况:

  • 先让Y全部为1,再看B的和 tot,+1的点可补偿tot<0情况,-1的点可补偿tot>0情况。


  • 再考虑B无正整、或无负数情况:

  • 因B不可能全0,所以一定需要补偿,而只有无约束的Y[1]能起到补偿的作用,

  • 若B[1]为零,Y[1]不能发挥作用,无解,输出"No"。

  • 若B[1]非零,则设Y[2...n]都为B[1]的绝对值,再安排Y[1]来补偿所有。


[ARC153C] ± Increasing Sequence的评论 (共 条)

分享到微博请遵守国家法律