期望得分: 61+?+37
实际得分: 61+21+14
A. u
难度评估错误, 放弃去想正解和一闪而过的二维前缀和, 以为很不可打, 于是打了 61 部分分.
然而这是三道题里最简单的.
正解: 差分 + 二维前缀和
考虑如何二维差分, 实际上就是硬凑, 假设并验证所有块的差分前缀和是否正确.
- +1 -1
- +1 -1
- +1 -1
- -1 +1
得到如上.
然后对对角线做差分, 做前缀和转化得到二维差分, 再做二维前缀和得到原矩阵.
妙啊, 秒啊
B. v
考场上不会状压 dp 转移, 正序倒序入度出度一直不能区分.
记忆化搜索, 递归转移, 相当于倒序. 这样式子也很好写.
100% 也是这个思路, 只是优化状态数.
不记录每个位置存不存在, 转而记录球的颜色.
用哈系表可以做到.
注意到:
000101 状态不唯一, 可能是 2B2W,1B2W......
为了区分, 加入轮数的信息.
在最高位打标记 1, 这样每一轮标记的位置不同.
C. w
考试上秒了第一问, 第二问猜了个结论.
一开始没有看见后两个样例 (好几次了啊喂), 码完去盯了一个小时 T2
9 点多看到发现过不去第三个, 把自己 hack 了, 心态爆炸.
正解:
第一问是缩完边后奇数点个数 / 2, 之前的结论 (然而我缩边打炸了)
但用老路子求出第一问对第二问没帮助.
设二元组 f[u][0/1]={c1,c2} 表示 u 向 fa 出不出边, 子树中有 c1 个奇数点, c2 条经过边.
之后进行子树合并 dp, 相当于做背包.
然后对父亲边分类讨论, 更新 f[u][0/1]
背包正确性:
由于没有要求最长链最短之类, 那么哪两条链合并是无所谓的, 我们只要关心有没有合并, 记录有没有多出来的线头.
来源: http://www.bubuko.com/infodetail-3217064.html