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

不敲代码的意念刷题计划

[复制链接]
孤单 发表于 2021-1-3 11:56:11 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
CF504E Misha and LCP on Tree

题:给出一棵                              n                          n               n结点的树,每个结点上有一个字符,                              (                      x                      ,                      y                      )                          (x,y)               (x,y)表现从点                              x                          x               x到点                              y                          y               y路径上字符组成的字符串。有                              q                          q               q个查询,每个查询给出                              a                      ,                      b                      ,                      c                      ,                      d                          a,b,c,d               a,b,c,d,求                              (                      a                      ,                      b                      )                          (a,b)               (a,b)和                              (                      c                      ,                      d                      )                          (c,d)               (c,d)的最长公共前缀。(                              n                      ,                      q                      ≤                      300000                          n,q\le300000               n,q≤300000)。
解:界说串                              s                          s               s的哈希函数为                                   h                         s                         (                         s                         )                         =                                   ∑                                       i                               =                               1                                      n                                  (                                   s                            i                                            −                            ′                                            0                            ′                                  +                         1                         )                         ∗                         b                         a                         s                                   e                            i                                       hs(s)=\sum\limits_{i=1}^n(s_i-'0'+1)*base^i                  hs(s)=i=1∑n​(si​−′0′+1)∗basei
界说                              f                      (                      x                      ,                      y                      )                          f(x,y)               f(x,y)为                              (                      x                      ,                      y                      )                          (x,y)               (x,y)的哈希值。对于每一个结点                              u                          u               u,纪录                              f                      (                      1                      ,                      u                      )                          f(1,u)               f(1,u)和                              f                      (                      u                      ,                      1                      )                          f(u,1)               f(u,1)。设点                              s                          s               s为                              t                          t               t的祖先,则                                   f                         (                         s                         ,                         t                         )                         =                         (                         f                         (                         1                         ,                         t                         )                         −                         f                         (                         1                         ,                         f                                   a                            s                                  )                         )                         ∗                         i                         n                         v                         (                         b                         a                         s                                   e                                       d                               e                                           p                                  s                                          −                               1                                            )                              f(s,t)=(f(1,t)-f(1,fa_s))*inv(base^{dep_s-1})                  f(s,t)=(f(1,t)−f(1,fas​))∗inv(basedeps​−1)                                   f                         (                         t                         ,                         s                         )                         =                         f                         (                         t                         ,                         1                         )                         −                         b                         a                         s                                   e                                       d                               e                                           p                                  t                                          −                               d                               e                                           p                                  s                                                       ∗                         f                         (                         s                         ,                         1                         )                              f(t,s)=f(t,1)-base^{dep_t-dep_s}*f(s,1)                  f(t,s)=f(t,1)−basedept​−deps​∗f(s,1)同时,若                              s                          s               s和                              t                          t               t互不为祖先,求出其                              l                      c                      a                          lca               lca拆分出两条路径并采取,仍然可用上述方法                              O                      (                      1                      )                          O(1)               O(1)求出哈希值。
从而,对于每个查询,求出                              l                      c                      a                      (                      a                      ,                      b                      )                          lca(a,b)               lca(a,b)和                              l                      c                      a                      (                      c                      ,                      d                      )                          lca(c,d)               lca(c,d),二分                              (                      a                      ,                      b                      )                          (a,b)               (a,b)和                              (                      c                      ,                      d                      )                          (c,d)               (c,d)最长公共前缀的长度,长链剖分求                              b                          b               b和                              d                          d               d的                              k                          k               k级祖先,判定哈希值是否相等即可,时间复杂度                              O                      (                      n                      l                      o                      g                      n                      )                          O(nlogn)               O(nlogn)。
CF505E Mr. Kitayuta vs. Bamboos

有                              n                          n               n朵花,第                              i                          i               i朵花最初高度为                                       h                         i                                  h_i               hi​,天天晚上长高                                       a                         i                                  a_i               ai​。天天白天可以使用                              k                          k               k次邪术,邪术选择一朵花                              i                          i               i,将其高度变为                              m                      a                      x                      (                      0                      ,                               h                         i                              −                      p                      )                          max(0,h_i-p)               max(0,hi​−p)。                              m                          m               m天后所有花中的最大高度最小是多少?
                               n                      ≤                      100000                      ;                      m                      ≤                      5000                      ;                      k                      ≤                      10                      ;                      p                      ,                               a                         i                              ,                               h                         i                              ≤                      1                      e                      9                          n\le100000;m\le5000;k\le10;p,a_i,h_i\le1e9               n≤100000;m≤5000;k≤10;p,ai​,hi​≤1e9
二分                              m                          m               m天后花的最大高度                              H                          H               H,判定                              m                          m               m天后花的高度是否都                              ≤                      H                          \le H               ≤H。由                                       h                         i                              =                      m                      a                      x                      (                      0                      ,                               h                         i                              −                      p                      )                          h_i=max(0,h_i-p)               hi​=max(0,hi​−p)的限制,在                                       h                         i                              ≤                      p                          h_i\le p               hi​≤p时,会浪费                              p                      −                               h                         i                                  p-h_i               p−hi​的长度,因此需要思量尽大概少的浪费长度。
问题转换:有                              n                          n               n朵花,第                              i                          i               i朵花最初高度为                              H                          H               H,天天白天长矮                                       a                         i                                  a_i               ai​。天天晚上可以使用                              k                          k               k次邪术,邪术选择一朵花                              i                          i               i,将其高度增加                              p                          p               p。                              m                          m               m天后花的高度是否大于                                       h                         i                                  h_i               hi​?过程中花的高度要                              ≥                      0                          \ge0               ≥0。每次贪心选择最快会长矮为负数的花使用邪术长高即可。
                               −                      过                      程                      中                      花                      的                      高                      度                      ≥                      0                      的                      条                      件                      仍                      然                      充                      满                      疑                      问                      中                      −                          -过程中花的高度\ge0的条件仍然布满疑问中-               −过程中花的高度≥0的条件仍然充满疑问中−
arc110F

给定                              0                      ,                      1                      ,                      .                      .                      .                      ,                      n                      −                      1                          0,1,...,n-1               0,1,...,n−1的分列                                       P                         0                                       P                         1                              .                      .                      .                               P                                   n                            −                            1                                           P_0P_1...P_{n-1}               P0​P1​...Pn−1​。执行交换                                       p                         i                                  p_i               pi​和                                       p                                   (                            i                            +                                       p                               i                                      )                                        m                               o                               d                                       n                                           p_{(i+p_i)\bmod n}               p(i+pi​)modn​最多                              200000                          200000               200000次,使得分列升序。
解:先不绝执行                                       p                         i                              =                      1                          p_i=1               pi​=1将                              0                          0               0交换到位置                              n                      −                      1                          n-1               n−1,然后把                              1                      ,                      2                      ,                      .                      .                      .                      ,                      n                      −                      1                          1,2,...,n-1               1,2,...,n−1逐个交换到位置                              n                      −                      2                      ,                      n                      −                      3                      ,                      .                      .                      .                      ,                      0                          n-2,n-3,...,0               n−2,n−3,...,0(重复交换一个位置,总是得到差别的数,但由于                              0                      ,                      1                      ,                      2                      ,                      .                      .                      .                      ,                      x                          0,1,2,...,x               0,1,2,...,x被排在交换位置的                              1                                             x                      +                      1                          1~x+1               1 x+1步中,故当                                       a                                   n                            −                            x                            −                            i                                       =                      x                          a_{n-x-i}=x               an−x−i​=x之前不会打乱顺序)。最后,将得到一个                              n                      −                      1                      ,                      n                      −                      2                      ,                      .                      .                      .                      ,                      2                      ,                      1                      ,                      0                          n-1,n-2,...,2,1,0               n−1,n−2,...,2,1,0的降序分列,此时,因为                              1                          1               1可以自由移动,因此对于                              2                      ,                      3                      ,                      4                      ,                      .                      .                      .                      ,                      n                      −                      1                          2,3,4,...,n-1               2,3,4,...,n−1先把                              1                          1               1移动到对应要交换的位置,然后再举行交换。
arc109D


首先,把一个格子分成四块,每一块格子可以唯一表现一个                              L                          L               L形。

其次,观察                              L                          L               L形的移动,一个重心可以向其周围                              7                          7               7个位置移动(除了重心格子角的那边)。

于是可以将问题转换为重心的移动,将                              L                          L               L形转换为新棋盘中重心的坐标。观察上述移动计谋可以发现,若重心坐标为                              x                      ,                      y                          x,y               x,y且                              x                      ≠                      y                          x\neq y               x​=y,则答案为                              m                      a                      x                      (                      ∣                      x                      ∣                      ,                      ∣                      y                      ∣                      )                          max(|x|,|y|)               max(∣x∣,∣y∣),否则为                              ∣                      x                      ∣                      +                      1                          |x|+1               ∣x∣+1。
[code]#includeusing namespace std;struct node{    int x,y;    bool operator=1,a=a*a%mod)        if(n&1) ans=ans*a%mod;    return ans;}int main(){    scanf("%d",&n);    if(n==1) printf("%d\n",qpow(2,mod-2));    else    {        ll sum=qpow(2,n),isum=qpow(sum,mod-2);        for(int i=1;i
回复

使用道具 举报

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

本版积分规则

发布主题

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

18768367769

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

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

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