Time Warp

Problem 2048. Next Greater Numerically Balanced Number Analysis 这是上周周赛的一道题，早该写了。 根据题意，111 要么不出现，要么只能出现 111 次，222 同理只能出现 000 或 222 次，则 iii 的出现次数记为 xix_ixi​ 的话，就有 xi∈{0,i}x_i \in \{0, i\}xi​∈{0,i}。 我们不妨记一个 balanced number 的数位有 mmm 个，显然这 mmm 个数字只能从集合 {1,2,...,m}\{1,2,...,m\}{1,2,...,m} 里面取，因为如果你取了 m+1m+1m+1，则根据规则它必须出现 m+1m+1m+1 次，我们只有 mmm 个数位，显然放不开，至于 0。它只能出现 0 次，直接没法用。 既然知道了每个数位的取值集合，那我们就可以考察集合内每个元素在 mmm 个数位中的出现次数，不妨记数字 iii 出现了 xix_ixi​ 次，其中 i∈{1,2,...,m},xi∈{0,i}i \in \{1,2,...,m\}, x_i \in \{0, ...

Problem 31. Next Permutation Proof 这个题目有个很绝妙的算法，在这里有介绍，文章里给出了直觉上的认识，通俗易懂但是不够严格，我这里再证明一下。先把原图搬过来。想偷懒的原文其实可以不看，只看这张图就能知道这算法干了什么。 我们主要关心这个算法的正确性如何。不妨令数组为nums，把第2步中的pivot记为i，则数组被分为nums[0:i]和nums[i+1, n-1]两部分，算法会确保后者是非递增的。那么这么个操作流程下来，最终生成的排列PPP到底是不是 第一个 比原排列OOO大的排列呢，我们用反证法，先假设如下命题为真： 存在一个更优的解——排列QQQ，它比这个排列PPP更小，且比原排列OOO更大 首先注意到P和原排列O的nums[0:i-1]位完全一致，即有P[0:i−1]=Q[0:i−1]P[0:i-1] = Q[0:i-1]P[0:i−1]=Q[0:i−1]，而Q的大小在他们之间，所以毫无疑问P[0:i−1]=O[0:i−1]=Q[0:i−1]P[0:i-1] = O[0:i-1] = Q[0:i-1]P[0:i−1]=O[0:i−1]=Q[0: ...

这个证明思路是昨晚洗澡时想好的，现在写下来。 Problem 41. First Missing Positive Proof 首先有如下引理： 如果第一个缺失的正数是 a，那么 [1, a-1] 区间上的每一个数一定是数组内的元素。 我们先用反证法证明这个引理。 设立两个简单命题，并组成复合命题： 简单命题 p:p:p: 第一个缺失的正数是 a 简单命题 q:q:q: ∃b∈[1,a−1],b∉array\exists b \in [1, a-1], b \notin array∃b∈[1,a−1],b∈/array 复合命题 P:P:P: p⇒qp \Rightarrow qp⇒q 命题 ppp 是我们的基本设定，值为真，命题 q 是我们要考察的命题，暂时不知道真假。 我们首先假设命题 PPP 成立，又因为 ppp 为真，所以推出 qqq 也为真。又因为 b∈[1,a−1]b \in [1, a-1]b∈[1,a−1] 即 b<ab < ab<a，那么就有 (b<a)∧(b∉array)\left (b < a\right ) \wedge \ ...

这篇证明当初做完题就该写了，我太懒了，留了个坑，两周了才来补全。 Problem 189. Rotate Array Proof 把数组元素个数记为 nnn，旋转数目记为 kkk，我们对这个题目的思路是可以先把位置 iii 的元素放入到 (i+k) mod n(i+k) \bmod n(i+k)modn 的位置，这样此位置的原元素会被逐出，我们再把逐出的元素放到它该去的位置即 ((i+k) mod n+k) mod n((i+k) \bmod n + k) \bmod n((i+k)modn+k)modn 下标处。这样一直进行下去，最终会不会绕一圈即目标位置刚好是 iii 呢。这是肯定的。我们把这期间经历的步数记为 mmm。则有： n∑j=1mcoeffj=mk(1)n\sum_{j=1}^{m}coeff_{j}=mk \tag{1} nj=1∑m​coeffj​=mk(1) 这玩意儿咋得来的。其实很简单，下标 iii 的元素其目标位置是 (i+k) mod n(i+k) \bmod n(i+k)modn，(i+k) mod n(i+k) \bmod n(i+k)modn 元素的目标 ...