泛做

Educational Codeforces Round 45 的 B 和 C 不错 (CF #996)

B. Micro-World

给一列数

每个a[i]可以覆盖[a[i] + 1 .. a[i] + k] 这个区间

如果有a[j]在这个区间里,那么称i可以被j吃掉,问最后最少剩几个

这个区间描述的关系是被吃的指向吃的,所以应该反过来,用a[j]引出[a[j] - k, a[j] - 1]这个区间,这时的含义是j可以吃覆盖的区间里的。答案就是没有被覆盖的a[i]的个数

把每个区间起点打标记+1,终点后一个位置-1,求个前缀和。如果一个位置是0那么就是没被覆盖过的

C. Bracket Sequences Concatenation Problem

给一堆括号序列,问有多少二元组,拼起来之后算是合法的

核心在于如何求一个括号序列左侧需要补多少左括号和右侧需要补多少右括号才合法

尝试过程略去,说一下结论

1
2
3
4
5
6
7
8
f(i, 0, n) if (buf[i] == '(') {
++r[idx];
} else {
if (r[idx]) --r[idx];
// 这里是需要不减成负的
// 如果会变成负的,那多出来的右括号是留给左侧,左侧用左括号补上的
// 就不需要右侧管了,所以要保证计数器不减成0
}

POJ 1191 棋盘分割

方差的式子可以拆开

\begin{align}
S & = \sum_{i=1}^n(x_i - \bar x)^2 \\
& = \sum(x_i^2-2x_i\bar{x}+\bar{x}^2) \\
& = \sum{x_i^2} - \sum{2x_i\bar{x}} + n{\bar{x}^2} \\
& = \sum{x_i^2} - 2n\bar{X} + n\bar{x}^2 \\
& = \sum{x_i^2} - n\bar{X}
\end{align}

dp[n][x1][y1][x2][y2]表示这块区域切n

记忆化搜索,前缀和预处理

张三丰的传人

后三种剪枝其实是在说一件事,题目要求分组,但是组内不要求顺序。

但是dfs肯定是有设定了顺序的,所以剪枝方案说:第一个如果不行,换了也不行,直接减掉;最后一个如果不行,换了也不行;

当然我们从长到短枚举就人为给了数据一个顺序,这样的话就可以避免了重复枚举,不会在已知不可能的情况多次尝试、浪费时间

康拓展开

可以用来求排列的序号,比如问1..5的第16个排列是哪一个

也可以对给出的一组排列问它在所有的排列里排第几

https://algorithm.yuanbin.me/zh-hans/exhaustive_search/permutation_index.html

$ans = \sum_{i=1}^{n}{(a[i]右侧比a[i]小的数的个数) * (n - i)!)}$

逆向就是每次除以一个阶乘,余数继续。每次的商就是会有多少个数比这一位的数要小。可选的数字集合每次在变

用线段树搞一下就是nlogn查询了吧 (没写)

思考:如果允许元素重复呢? 换言之,并不是严格意义上的排列

https://algorithm.yuanbin.me/zh-hans/exhaustive_search/permutation_index_ii.html

后面乘的阶乘除以重复那部分 $\frac{(\sum{a_i})!}{\Pi{(a_i!)}}$ 这样的

POJ 1037: A decorative fence

c[i][k][0/1] 是前i个木棒中以第k短的开头,然后这一个是 下降/上升 的方案数

边界:c[1][1][0] = c[1][1][1] = 1

后面还要计算第C个方案是啥,类似于排列计数

依次假设第x短的木棒放在那,然后看此时的方案数是否>= c

如果否,就用第x + 1短的木棒

LIS 计数 http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1376

http://www.cnblogs.com/dirge/p/5958808.html

考虑一个$O(n^2)$的算法

a[i]表示原数组,l[i]表示以i结尾的LIS长度,dp[i]表示最长的这个的个数

我们每次处理a[i]如果它可以接在a[j]后面,那么l[i] = max(l[j]) + 1

然后我们同时可以发现,如果l[i] > l[j] + 1,那么,dp[i] = dp[j],因为最长的长度更新了,要重新计数;
如果l[i] == l[j] + 1,那么更新进去,dp[i] += dp[j].

用树状数组维护每一块的(用块里的数结尾的)LIS长度和对应个数

树上第i个位置代表的是以值i结尾的LIS的最长长度和对应个数

处理a[i]的时候,先看之前的用小于a[i]的数结尾的(这里是二维偏序)LIS的长度和对应个数

然后把长度更新

再插回树状数组里。

https://github.com/Ir1d/Fantasy/blob/master/51NOD/1376.cpp

POJ 1390 方盒游戏

就是考虑最右侧的块,有两种选择,要么直接消了,要么把它左边消了,等着合并。

注意第二种方案不是和左边一起直接消了,而应该递归进入子问题

所以dp[i][j]并不够用,要加一维,用dp[i][j][len],表示把[i .. j]这段,和与a[j]相等且长度为len的一块合并的最大得分

左边的同色大块可能有很多个,到底和哪个合并最好,不知道,只能枚举

upd: 细节是要先游程编码,然后对编码之后的序列搜能方便一些。程设2018考了个类似的,死活没调出来

HDU 1423 LCIS

https://www.cnblogs.com/Howe-Young/p/5082611.html

dp[i][j]表示str1和str2分别以i和j结尾的LCIS,第一维空间可以省掉

如果s1[i] == s2[j]更新一下答案,用什么更新呢?

就是先预处理出来s1[i]对应的,s2[j] < s1[i]且让dp[j]最大的j

由于i在外层固定,所以循环的时候按顺序记一下这个j就好了