Global Round 5

Global Round 5

好题:F

CF1237E Balanced Binary Search Trees

请先思考后再展开

明明很接近了……拼14的时候一开始以为可以,草稿纸略乱,后来发现不行后忘记划掉了,然后后面就懵逼了……而且思考的时候没有从最大节点深度去分层思考,直接讨论节点个数来思考转移区间,所以不是很明显

首先知道转移的条件是从上一层选a、b,奇偶性要求$rt(a)=(a+1) \oplus 1,rt(b)=0$,然后你会发现每层只有两个

code

CF1237F Balanced Domino Placements

请先思考后再展开

先考虑空棋盘怎么放,随便想想发现如果现在在某行放了个横,那么会分割成两个相互影响的部分,如果直接看做一部分需要把【有竖跨过这行】去掉,不太好搞,但注意到现在的矛盾是横与竖之间的,这启发我们分开考虑竖和横

设有i个竖,j个横,设$f(n,cnt)=长度为n的表格,放若干不重叠骨牌方案数$,则$ans=竖f(n,i)*横f(m,j)*P_{m-2j}^i*P_{n-2i}^j$

空棋盘的f随便dp,不空其实也随便dp,求答案中排列数的下标改成剩下可选的行、列即可,$O(n^2)$,code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6536cd98.html
转载请注明出处,谢谢!