cojR12

Source

commetoj R12

好题:E

D XOR Pair

请先思考后再展开

二进制数相减,不要考虑借位,而是允许-1存在

那么$x \oplus y=n$,考虑每一位,如果是0则x-y这一位是0,否则x-y这一位是1或-1,于是消除了一个限制

那么相当于,原数为-n,现在有若干个可选的位置去$+2^{bit+1}$,最后绝对值不超过m,等价于增量$\Delta \in [n-m,n+m]$,差分求解

然后如果是不可选的位置,x=y=0/1,判一下即可

如果是可以选的位置,选1(x=1,y=0)或0(x=0,y=1),其他位置为0,最后数字不超过R,数位dp即可(注意现在加数、与A和B比较是在pos位,但加数形成的1其实在pos+1位),设$f(pos,topR,topA,topB)$表示三个数在更高位是否都是顶上界的

code

E Ternary String Counting

请先思考后再展开

出题人增强自hdu6578
$$
设f(n,x,y)表示填了n个,与最后颜色不同的另外两种分别最后出现在x、y(x>y) \\
那么相当于每个位置的合法x、y都有上下界限制,每次清掉非法状态 \\
f(n+1,x,n),f(n+1,y,n),f(n+1,x,y) \leftarrow f(n,x,y),O(n^3) \\
考虑将后面两维理解为表格,第三个就是原封不动,前两个就是对行、列求和并放在第n列 \\
合法状态形如矩形,则对于每列而言合法的区间是连续且只变小的,可以存下来,维护好行、列和 \\
枚举列去清空,O(n^2),可能需要注意一些常数
$$
code

F Substring Query

咕咕咕

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