2016-5-19模拟测试 bzoj3652 bzoj3653 bzoj3654

  • 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.
上一篇:Android专项面试训练题(一)


下一篇:IE的Cookie目录和临时缓存目录的关系