CH1602:The XOR Largest Pair 题解

主要思路

如何找到一对异或值最大的数字呢?我们先从二进制计算(位运算)本身讲起,如果我们要保证\(Xor\)值更大,那么我们就需要尽可能多的\(1\),除此之外,\(1\)的位置也非常重要,在一些情况下靠前更好。我们可以考虑从最高位为起点向最低位建立一个 Trie 树。我们记\(num[i]\)表示第\(i\)位的\(0或1\)状态。建立 Trie 树之后,我们计算出每个数所对应的异或值最大的值。我们的策略是:

继续阅读CH1602:The XOR Largest Pair 题解

POJ1961:Period 题解

主要思路

这道题要求在一个循环前缀中求出最小周期长度和最大频率。我们可以用 KMP 的 next 数组来解这个问题。我们先来回顾一下 next 数组的含义。\(next[i]\)代表在区间\(str[1,i]\)中前缀后缀的最长公共部分。如果区间长度是\(next[i]\)的倍数,那么其中就有循环节。详细见代码。

继续阅读POJ1961:Period 题解

P2110:欢总喊楼记题解

神仙做法

我看题解之后非常心塞,竟然不用数位 DP !我们先来考虑部分解。当\(num<10\)时,答案就是\(num\)。如果\(num \geq 10\),那么答案就是\(9+\frac{x}{10}\)。我们来看,考虑一个数\(1921\)的答案,我们可以考虑\(192-\)部分里有\(\lfloor \frac{1920}{10} \rfloor\)对首尾相同的数。然后再加上位数为一时的答案。

继续阅读P2110:欢总喊楼记题解

CH1401:兔子与兔子题解与字符串哈希

字符串哈希

我们先来简述一下字符串哈希。首先我们把字符串中的字符转换为数值,比如我们使用以下函数来搞定:

\[toNum(character) = character – numberOf(‘a’) + 1\]

然后,我们来定义一个值\(bitNum\)来作为进位值。所以,我们的前缀哈希函数有一个递推式如下:

\[Hash(i) = Hash(i-1)*bitNum + toNum(S[i])\]

我们可以来探寻这个前缀哈希函数的相减线性性。我们设\(|S|,|T|\)为这两个字符串的长度。我们得出:

\[Hash(|T|) = Hash(|S+T|) – Hash(|S|)*bitNum^{|T|}(1.1)\]

继续阅读CH1401:兔子与兔子题解与字符串哈希