9.9集训

Posted on Edited on In

今天做了三个题 第一个是一个数位dp

吉哥系列故事——恨7不成妻 HDU - 4507

考虑三个条件

  • 整数某一位是7

简单，直接continue

  • 整数的每一位加起来的和是7的整数倍

维护一个sum即可

  • 这个整数是7的整数倍

当前枚举的数i，是第pos位，那么对求和的贡献就是\(i*10^{pos}\)

则对于一个pos位的与7无关的数X有\(X=( A\times10 ^ {pos}+B)^2\),A是你当前pos位枚举的值，B是一个子问题，展开得到\(A \times A \times 10 ^ 2 \times pos+2 \times A \times 10 ^{pos} \times B+B^2\)

第二个是壮压dp

P2704 [NOI2001]炮兵阵地

  • 空间不够

需要用滚动数组，因为是状态压缩两行，所以我们\(i\%3\)

  • 预处理

  • 考虑能放的条件

\(j\)&\((j<<1\;or\;2)\)

1位是左边一格子，2位是左边两格子

\(dp[L][S][i]\)表示当前状态是 S，上一行的状态是 L，当前考虑到了第 i 行

\(dp[L][S][i]=max(dp[L][S][i],dp[FL][L][i-1]+Sum[S])\) 这里 FL 表示上上行的状态，Sum[S] 表示当前状态 S 里面包含几个 1

  • 判断每个位置是不是山丘

只要把每一行的输入都转成一个二进制数(平原是 0，山丘是1)，然后直接跟待判断的状态做一次位运算即可，就是 S&a[i]，如果位运算结果不是零，说明有些位置放在了山丘上，也就是说当前状态不合法

第三个题是区间dp

P5336 [THUSC2016]成绩单

设\(f[l][r][x][y]\)表示区间\([l,r]\)没取走的当中最大的是y,最小的是x的最小代价

考虑转移：

  • 从\([l,r-1]\)转移，就是把这个归为上一个的那一砣
  • 考虑枚举一个k，\(f[l][r][x][y] = min(f[l][r][x][y], f[l][k][x][y] + g[k + 1][r])\)
  • \(g[k+1][r]\)表示\(min(f[k+1][r][x][y])\)

还有个坑点：离散化

闲散时间D昨天树剖的bug

找到漏洞：

  • query函数没写return
  • 跳的时候是top数组
  • 两个dfs的名字不要互相引用
  • 读入字符和数字都有的时候，不能用快读！！！
  • 取最大值的时候，一定要给res赋极小值

如果出题人卡你负数，就凉了

Seating G

考虑down的时候

如果tag为0就要return