请选择 进入手机版 | 继续访问电脑版

牛客练习赛44 B.小y的线段(找规律,逆向)

[复制链接]
盛夏丨光年丶 发表于 2020-12-31 18:57:51 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
传送门
一定需要的次数是                              n                      ∗                      (                      n                      −                      1                      )                      /                      2                          n*(n-1)/2               n∗(n−1)/2,剩余的花费就是归零点
在纸上模仿一下,发现归零点都是一连的
换句话说,如果从第                              i                          i               i线段的                              0                          0               0出发,到达第                              k                          k               k条线段刚好不需要归零
那么从                              [                      1                      ,                      i                      −                      1                      ]                          [1,i-1]               [1,i−1]任意线段出发到                              k                          k               k点都需要归零
思量证明其正确性
因为从                              i                          i               i的位置                              0                          0               0出发刚好到第                              k                          k               k条线段
那么从                              i                      −                      1                          i-1               i−1出发一定需要归零
那么从更早的线段出发呢??会不会因为中间归零了反面不需要归零了呢
不会的,因为在                              i                      −                      1                          i-1               i−1之前出发的线段到                              i                      −                      1                          i-1               i−1的线段时,位置一定大于即是                              1                          1               1
所以势必须要归零
所以我们逆向思量,令                              t                      e                      m                      p                      =                      a                      [                      n                      ]                          temp=a[n]               temp=a[n]
然后每往前一条线段令                              t                      e                      m                      p                      −                      −                          temp--               temp−−,同时和                              a                      [                      i                      ]                          a               a取小
当                              t                      e                      m                      p                          temp               temp为零时,说明从点                              i                          i               i出发刚好到                              n                          n               n需要归零
就是说,前面从                              [                      1                      ,                      i                      −                      1                      ]                          [1,i-1]               [1,i−1]出发的线段也一定会在                              n                          n               n位置归零
[code]#include using namespace std;typedef long long ll;unsigned int SA, SB, SC;int n,mod,a[20000009];ll ans,temp;unsigned int Rand(){        SA ^= SA > 5;        SA ^= SA > n >> mod >> SA >> SB >> SC;        for(int i = 1;i 0;i--)        {                temp--;                if( a
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )