9.8集训

Posted on Edited on In

火柴排队一题 - 离散化的时候

\(a[i] = f[i].rank\)这才是离散化

  • 求逆序对用树状数组

两种写法，一种是先插入后查询，统计答案的时候不需要加加减减

另一种是先查询，后插入，不过需要\(i - query(a[i]) -1\)

货车运输一题

是真tm恶心，真tm细节

  • 求lca的时候，无论是中途return还是最后的return都必须返回权值，返回结点编号是没有用的
  • 什么时候用fa，必定会伴随着w的出现
  • 在最小生成树里面，加边的时候，应该是对结构体伴随着的点加边，而不是后来find到的
  • dfs里面的for要从1开始而不是0
  • 先取min再跳

推荐例题：click

货车运输的即视感

与货车运输相反的一个题

修改点：

  • min变为max
  • 比较符号修改
  • res不要初始化为INF了

今天做了dp

有简单的有难的

第一道Coloring Brackets

是一个区间dp

  • 碰到括号就想栈
  • 第一道大法师与动规结合的题目

状态：\(f[l][r][i][j]\)表示在l与r之间，且l为i颜色，r为j颜色时候所能获得的最大价值

规定用0表示没有颜色，1是红色，2是蓝色

  • 考虑三种情况

\(l+1=r\)这是边界\(f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1\)

\(mch[l]=r\)接下来\(dfs(l+1,r-1)\)既然两边匹配了，考虑进一步往里边缩

\(if (j != 1) (f[l][r][0][1] += f[l + 1][r - 1][i][j]) \%= mod;\) \(if (j != 2) (f[l][r][0][2] += f[l + 1][r - 1][i][j]) \%= mod;\) \(if (i != 1) (f[l][r][1][0] += f[l + 1][r - 1][i][j]) \%= mod;\) \(if (i != 2) (f[l][r][2][0] += f[l + 1][r - 1][i][j]) \%= mod;\)

啥也不是，\(dfs(l,mch[l])\;and\;dfs(mch[l]+1,r)\)

\(if ((j == 1\) && \(p == 1) || (j == 2\) && \(p == 2)) continue;\) \((f[l][r][i][q] += f[l][mch[l]][i][j] * f[mch[l] + 1][r][p][q]) \%= mod\)

因为两个相邻的颜色不能一样，所以要特判

第二道是[IOI1998]Polygon

也是一个区间dp

乘积最大的即视感

  • 考虑断环成链
  • 初始化先大面再i=i
  • 考虑dp

记录f数组为最大的贡献，g数组为最小的贡献

因为涉及到负负得正的情况，加法转移一眼就出来了

乘法转移就很冗杂：

\(q = f[i][k] * f[k + 1][j], w = g[i][k] * g[k + 1][j]\) \(e = f[i][k] * g[k + 1][j], r = g[i][k] * f[k + 1][j]\) \(q = max(q, w), e = max(e, r)\) \(q = max(q, w)\) \(f[i][j] = max(f[i][j], q);\)

左边最大\(\times\)右边最大，左边最大\(\times\)右边最小

左边最小\(\times\)右边最大，左边最小\(\times\)右边最小

g数组同理

  • 输出答案时候顺着扫一遍就可

  • 输入时候，考虑多\(getchar\)因为有空格，并且不要用快读，碰到要一起读字符和数字的题目就不要用快读了

第三道是时态同步

是一个树形dp

\(f[] show\;the\;longest\;distance\;form "the" tree's Root\;to\;its\;sons.\)

就是当前以x为根的子树中的最长链的长度，然后答案统计的时候

\(res+=f[x] -(f[y]+edge(x,y))\)

第四道是一个完全背包

考虑完全背包与01背包的区别

  • 完全背包是正着扫，因为你现在用的状态可能就是原来已经买过一件的，你可以选择多次用这同一件来填充价值
  • 而01背包是每次只能用一个，因此倒着扫，保证不会用到原来的状态

！！！！！！01背包也可以AC

第五道是最长公共子序列 q[x] = y,表示x在A中出现在了B哪个地方（将A序列的数字在B序列中的位置表示出来——）

我们要求这个数组的最长上升子序列即为这两个序列的最长公共子序列，我不会证明，但是我知道这么做是对的

\(n^2\)复杂度过不去啊，所以我们只能借用STL的lower_bound来log优化一下

mp数组其实是一个不断覆盖的过程

我们保证mp一定是一个递增的序列，因此我们可以直接用res去更新pos