- T1
- description
给定正整数\(n\),定义\(f(x) = \max{y \ \mathrm{xor}\ x}(y<n)\)
\(x\)在\([0,n)\)随机取值,求\(f(x)\)的期望。
- solution1
将\(n-1\)插入一棵trie树,则这条链以及他们左边的链是需要考虑的,找到第一个存在右儿子的点,这棵右子树都是可以达到最大的异或值的,那么考虑向左走的这些链,它们对应的\(y\),将会在这棵右子树中朝相反的方向走。在这棵中,如果可以向右走,那么这一位左边的数都可以取,否则会有一半的数走不了,我们不妨把所有数的答案都看作是最大的异或值,然后现在应该把它减掉。在可以向右走的时候,左边又有一些链选择了向左走,那么下面再遇到不能走的情况,就不用考虑这些点了,此时把需要考虑的点数除以2即可。
- solution2
数位dp,本质也是在trie树上走,把具有相同性质的节点用一个状态表示即可,显然本质不同的节点数量是\(O(\log{n})\)的。
- T2
- solution
网上题解很多,我在这之前就看了一篇题解然后写了可持久化线段树。
其实离线+树状数组就可以解决了。
- T3
- description
给你\(n\)个串,每个串可以用任意数量,将它们拼接在一起(不可翻转),问所有结果中最大的回文子串的长度是多少,如果是无穷大输出无穷大。
- solution
如果存在一个回文串,那么答案是无穷大。
否则不存在回文串,那么我们枚举回文中心,对于一个串,如果以这个回文中心的最长回文子串走到了边界上,那么在他左边可以继续拼接,那么可以用\(f(i<n,j<len_i,k=0/1)\)表示当前在第\(i\)个串,在\(j\)这个位置,下次应该往\(k\)这个方向接,枚举下一个接上的串转移即可。
转移时可以使用记忆化搜索,在这个转移图上发现环则输出INF.