又见彩票事件（含米哈游算法变形题）

站长

2024年03月11日 12:35 · 阅读数 5

又见彩票事件

1月17日，中国体彩最新开奖结果出炉，其中“排列3”和“排列5”均出现罕见的“连5”组合。

体彩“排列3”的开奖号码为“555”，“排列5”的开奖号码为“55555”。

5亿奖池被清空。

开奖后第二天就有同学问我怎么看。

我 ... 我能怎么看？

2.2 亿的时候我已经看过了，也把结论分享过给大家了。

果然，1月18号这事儿上热搜之后，我们又一次的迎来最具"说服力"的回应：

1月18日，相关话题冲上微博热搜，有网友质疑开奖号码过于罕见和特殊，是否存在内幕。对此，中国体彩客服回应记者称，“开奖全流程有网络直播，也有两名工作人员的监督，号码是随机摇出来的，不存在内幕和故障，开奖是真实有效的。”

这里面的重点，也是在普通人常识里最有说服力，最能实现逻辑自洽的，是「监督」二字。

...

其实也难怪大家来问我看法。

虽然我已经在 1月10号的推文中详细说过彩票问题，但文章似乎被平台精准限流了。

在我近期的发文中，那篇文章的阅读是倒数第一。

如果是和「前一天」及「后一天」的推文去比较，则更是突兀到不行。

又见彩票事件（含米哈游算法变形题）

我十分好奇这里面到底存在什么玄学因素。

于是，我萌生了把这些“似乎有风险“，会被公众号推荐系统标记的内容重发一遍。

直接对那天的推文中的「彩票」部分内容进行截图贴出，我估计是可以绕过某些机制，让阅读回归到正常水准的。

但，那又有什么意思呢？

我就是要看看，对于一些无法反驳的事实，简中网是如何让文章不被看到的。

以下看到的内容，是对 1月10号推文中「锐评时事」部分的完全复制。

...

本来今天不打算更新闻的了，中午的时候看到「花10万中2.2亿彩票事件调查进展」上热搜。

原以为总算和"融创"来了点不一样的了。

又见彩票事件（含米哈游算法变形题）

结果调查结果是暂无结果，调查进展是没有进展。

一则报道，没有实际的信息增量，但有广泛的群众记忆和讨论基础。

使得报道发出之后，话题稳坐热搜榜的第二名。

又见彩票事件（含米哈游算法变形题）

只要能骂能喷，能对外输出情绪，群众从不在意这是新闻还是旧闻，有意义还是没意义。

如果你问我，如何理解彩票事件。

能问出这样的问题，那么大概率你对福利彩票的认识存在较大盲区。

嗯，是盲区，而不是误区。

我这里简单列举一些基本信息：

彩票中心的博彩专营权是由国务院给予的，主要目的是通过发售彩票，来增加财政收入
目前福利彩票的开奖过程，都是有公证人在场的
公证人来自于公证机构，公证机构的公证权是由国家直接下放，即不存在自由经济市场产生的公证企业，必须是国家司法证明机构，才能行使公证权

看到这里，一切正常，逻辑闭环。

也符合普罗大众对彩票事业的理解。

可能大家印象中的细节没有这么足，但结论肯定是大差不差：彩票的公平性由国家直接或间接保证。

但稍微深究就可以发现当中的不合理关系，我补充一些大家可能不知道的信息：

公证机构虽然是由国家直接下放公证权，但不属于公务员体系，是自收自支的事业单位
开奖过程的公证人在场，并非规定的条例，而是彩票中心为了自身形象，多卖彩票，花钱从公证机构请的。主要作用不得而知，但个人猜想，如果现场有公证人，那么开奖过程中，增加一个公证人宣誓的环节，会在观众心理上增加许多正面作用

现场公证员的拿着背靠国家的公证权，但位于自收自支的事业单位，可能会有对权力进行变现的局部压力，彩票中心作为现场公证人的甲方，可能也会影响公证人员的立场。

这里也有必要声明一下，上述只是基于现有规则进行的动机猜测，不代表事实本身。

任何有独立思考能力的人都会有自己的想法。

但彩票的本质终归不是数学。

搞清楚这些之后，你可能要推翻以前对福利彩票的认识了。

但普通人接受到这些信息之后，可能只够在一段时间内，认识到「彩票不是一个概率游戏」，长期还是会落入「用数量对抗随机性」的不切实际幻想中。

归根到底，是这些利害关系不足以产生画面感。

无法与报道刊登的「xxx 中 xxxx 万元」形成对立效果。

因此，我有必要提供一个具体的场景，断了大家通过彩票致富的念想。

你可以把这游戏看作是一场特殊「剪刀石头布」：赢了得 500w，输了赔 2 元，但永远是对方后出。如果对方一时间头脑发热出错了，他有权判定无效，重开一盘。

好，现在我已经将一个画面深深植入你的脑海。

大概率足够你对现有的体制下的游戏产生免疫效果。

...

好，复述完毕。

如果本推文达到了阅读的平均水准，那么很好，之前没被传播出去的东西，现在有了二次机会。

如果本推文没有达到阅读的平均水准，那么至少你和我都见证了某些无形的东西，亦具意义。

...

回归主线。

过去一周，大家对米哈游（原神）的一面算法题十分感兴趣，但那道题毕竟太裸（太模板）了。

所以这次，我给大家安排了一道「变形题」试试。

题目描述

平台：LeetCode

题号：1035

在两条独立的水平线上按给定的顺序写下 s1 和 s2 中的整数。

现在，可以绘制一些连接两个数字 s1[i]s1[i]s1[i] 和 s2[j]s2[j]s2[j] 的直线，这些直线需要同时满足满足：

s1[i]=s2[j]s1[i] = s2[j]s1[i]=s2[j]
且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：又见彩票事件（含米哈游算法变形题）

输入：s1 = [1,4,2], s2 = [1,2,4]

输出：2

解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 s1[1]=4 到 s2[2]=4 的直线将与从 s1[2]=2 到 s2[1]=2 的直线相交。

示例 2：

输入：s1 = [2,5,1,2,5], s2 = [10,5,2,1,5,2]

输出：3

示例 3：

输入：s1 = [1,3,7,1,7,5], s2 = [1,9,2,5,1]

输出：2

提示：

1<=s1.length<=5001 <= s1.length <= 5001<=s1.length<=500
1<=s2.length<=5001 <= s2.length <= 5001<=s2.length<=500
1<=s1[i],s2[i]<=20001 <= s1[i], s2[i] <= 20001<=s1[i],s2[i]<=2000

动态规划

这是一道「最长公共子序列（LCS）」的轻度变形题。

对于这类题都使用如下「状态定义」即可：

f[i][j]f[i][j]f[i][j] 代表考虑 s1s1s1 的前 iii 个字符、考虑 s2s2s2 的前 jjj 的字符，形成的最长公共子序列长度。

然后不失一般性的考虑 f[i][j]f[i][j]f[i][j] 如何转移。

由于我们的「状态定义」只是说「考虑前 iii 个和考虑前 jjj 个字符」，并没有说「一定要包含第 iii 个或者第 jjj 个字符」（这也是「最长公共子序列 LCS」与「最长上升子序列 LIS」状态定义上的最大不同）。

我们需要考虑「不包含 s1[i]s1[i]s1[i]，不包含 s2[j]s2[j]s2[j]」、「不包含 s1[i]s1[i]s1[i]，包含 s2[j]s2[j]s2[j]」「包含 s1[i]s1[i]s1[i]，不包含 s2[j]s2[j]s2[j]」、「包含 s1[i]s1[i]s1[i]，包含 s2[j]s2[j]s2[j]」四种情况：

不包含 s1[i]s1[i]s1[i]，不包含 s2[j]s2[j]s2[j]：结合状态定义，可以使用 f[i−1][j−1]f[i - 1][j - 1]f[i−1][j−1] 进行精确表示。
包含 s1[i]s1[i]s1[i]，包含 s2[j]s2[j]s2[j]：前提是 s1[i]=s2[j]s1[i] = s2[j]s1[i]=s2[j]，可以使用 f[i−1][j−1]+1f[i - 1][j - 1] + 1f[i−1][j−1]+1 进行精确表示。
不包含 s1[i]s1[i]s1[i]，包含 s2[j]s2[j]s2[j]：结合状态定义，我们无法直接将该情况表示出来。

注意 f[i−1][j]f[i - 1][j]f[i−1][j] 只是表示「必然不包含 s1[i]s1[i]s1[i]，但可能包含s2[j]s2[j]s2[j]」的情况，也就是说 f[i−1][j]f[i - 1][j]f[i−1][j] 其实是该情况与情况 111 的合集。

但是由于我们求的是「最大值」，只需要确保「不漏」即可保证答案的正确（某些情况被重复参与比较不影响正确性），因此这里直接使用 f[i−1][j]f[i - 1][j]f[i−1][j] 进行表示没有问题。
包含 s1[i]s1[i]s1[i]，不包含 s2[j]s2[j]s2[j]：与情况 333 同理，直接使用 f[i][j−1]f[i][j - 1]f[i][j−1] 表示没有问题。

f[i][j]f[i][j]f[i][j] 就是在上述所有情况中取 maxmaxmax 而来，由于情况 111 被情况 333 和情况 444 所包含，因此我们只需要考虑 f[i−1][j]f[i - 1][j]f[i−1][j]、f[i][j−1]f[i][j -1]f[i][j−1] 和 f[i−1][j−1]+1f[i - 1][j - 1] + 1f[i−1][j−1]+1 三种状态即可，其中最后一种状态需要满足 s1[i]=s2[j]s1[i] = s2[j]s1[i]=s2[j] 前提条件。

因此我们最后的状态转移方程为：

f[i][j]={max⁡(f[i−1][j],f[i][j−1],f[i−1][j−1]+1)s1[i]=s2[j]max⁡(f[i−1][j],f[i][j−1])s1[i]≠s2[j]f[i][j]=\begin{cases} \max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1) & s1[i] = s2[j] \\ \max(f[i - 1][j], f[i][j - 1]) & s1[i] \neq s2[j] \\ \end{cases}f[i][j]={max(f[i−1][j],f[i][j−1],f[i−1][j−1]+1)max(f[i−1][j],f[i][j−1])s1[i]=s2[j]s1[i]=s2[j]

上述分析过程建议加深理解，估计很多同学能 AC 但其实并不知道 LCS 问题的状态转移是包含了「重复状态比较」的。

Java 代码：

class Solution {
    public int maxUncrossedLines(int[] s1, int[] s2) {
        int n = s1.length, m = s2.length;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (s1[i - 1] == s2[j - 1]) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }
        return f[n][m];
    }
}

C++ 代码：

class Solution {
public:
    int maxUncrossedLines(vector<int>& s1, vector<int>& s2) {
        int n = s1.size(), m = s2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (s1[i - 1] == s2[j - 1]) {
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }
        return f[n][m];
    }
};

Python 代码：

class Solution:
    def maxUncrossedLines(self, s1: List[int], s2: List[int]) -> int:
        n, m = len(s1), len(s2)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                f[i][j] = max(f[i - 1][j], f[i][j - 1])
                if s1[i - 1] == s2[j - 1]:
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)
        return f[n][m]

TypeScript 代码：

function maxUncrossedLines(s1: number[], s2: number[]): number {
    const n = s1.length, m = s2.length;
    const f = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
    for (let i = 1; i <= n; ++i) {
        for (let j = 1; j <= m; ++j) {
            f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
            if (s1[i - 1] === s2[j - 1]) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    return f[n][m];
};

时间复杂度：O(n×m)O(n \times m)O(n×m)
空间复杂度：O(n×m)O(n \times m)O(n×m)

我是宫水三叶，每天都会分享算法题解，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地 🎉🎉