23/10/06 模拟赛总结

标签：11 10 06 23 s2 s1 50 times 答案

时间安排

7:35 - 7:45

看题。A 题一眼秒，B C 没思路，D 树形 DP。

7：45 - 7：50

随便过了 A 题。

7:50 - 8:50

写 B 题暴力的时候被卡了，时间复杂度怎么算都会 T 第一档分，也没什么好的处理方法，最后感觉应该跑不满就直接写了纯暴力。

8:50 - 9:30

思考 C，写了爆搜，\(n,m \leq 20\) 想了一个状压做法。

9:30 - 11:20

没想到那个状压那么难写，写到最后发现假了！！

11:20 - 11:37

非常慌，看 D。

11:37 - 11:40

会了链，但是时间显然来不及了。

总结反思

1. 应当在看完题之后把能拿的分列出来，从付出时间及得到的收益两方面考虑最优的拿分策略。
2. 算法题感觉还可以做做，人类智慧题做不了一点。

题解

A.序列划分

pj T2 难度。

B.表达式求值

法 1：将和转为期望算，最后再乘以 \((n-1)!\)。
法 2：区间 DP。设 \(f_{i,j}\) 表示区间 \([l,r]\) 所有可能的答案的和。枚举 \(k \in [l,r)\)，可以将 \(f_{i,k}\) 的可能答案和拆成 \(a_1,a_2,a_3 ... a_{s1}\)，\(f_{k+1,r}\) 的可能答案和拆成 \(b_1,b_2,b_3 ... b_{s2}\)。

1. 乘法操作满足分配率，所以直接乘起来

\[f_{i,j}=\sum_{k=l}^{r-1} f_{l,k} \times f_{k+1,r} \times C_{r-l-1}^{k-l} \]

2. 考虑加法操作， 每个 \(k\) 对答案的贡献为 \((a_1+b_1)+...+(a_1+b_{s2})+(a_2+b_1)+...+(a_2+b_{s2})+ ... +(a_{1}+b_1)+...+(a_{s1}+b_{s2})\)。发现每个 \(a\) 都出现了 \(s2\) 次，每个 \(b\) 都出现了 \(s1\) 次，而 \(s1\) 和 \(s2\) 可以计算出来。

\[f_{i,j}=\sum_{k=l}^{r-1} f_{l,k} \times (r-k-1)! + f_{k+1,r} \times (k-l)! \times C_{r-l-1}^{k-l} \]

3. 减法同理

\[f_{i,j}=\sum_{k=l}^{r-1} f_{l,k} \times (r-k-1)! - f_{k+1,r} \times (k-l)! \times C_{r-l-1}^{k-l} \]

C.放置棋子

人类智慧题。打表发现合法方案要么每一列黑白交替，要么每一行黑白交替，然后为了方便翻转 \((i+j)\) 为偶数的棋子，合法答案就变成了要么每一列同色，要么每一行同色。

D.看电视

发现答案的上界为 \(n+k\)，则连通块数目的上界为 \(\frac{n+k}{k+1}\)。

考虑根号分治，设 \(B\)，对于前半段使用 \(O(nB)\) 的树形 DP ，对于后半段使用 \(O(\frac{n^2}{B})\) 的树形背包。

标签：11,10,06,23,s2,s1,50,times,答案
From： https://www.cnblogs.com/cannotdp/p/17745983.html