彩票游戏礼品计算代码优化：如何消除循环实现O(1)查询？

游戏规则与原代码 #

这是一款彩票游戏，规则如下：

• 每位顾客可持有一张或多张彩票，每张彩票为6位数字序列，每位数字范围为0-9。
• 存在幸运号码，顾客根据彩票与幸运号码的对应位置匹配数获取礼品，礼品奖励规则：
  • 6位全匹配：奖励100
  • 5位匹配：奖励50
  • 4位匹配：奖励40
  • 3位匹配：奖励10
  • 匹配数小于3：无奖励

原代码实现如下：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    vector<string> customerTickets;
    string luckyTicket;
    int totalNumberOfTickets;

    cin>>totalNumberOfTickets;

    for(int i=0; i<totalNumberOfTickets; ++i) {
        string s;
        cin>>s; // 6 digit long string

        customerTickets.push_back(s);
    }

    cin>>luckyTicket;

    int totalGiftAmount = 0;

    for(int i=0; i<totalNumberOfTickets; ++i) {
        int match = 0;
        for(int j=0; j<6; ++j) {
            if(customerTickets[i][j] == luckyTicket[j]) match++;
        }

        if(match==6) totalGiftAmount+=100;
        else if(match==5) totalGiftAmount+=50;
        else if(match==4) totalGiftAmount+=40;
        else if(match==3) totalGiftAmount+=10;
    }

    cout<<totalGiftAmount;
}

用户需求 #

当前需处理数千个幸运号码的礼品金额计算，希望消除代码中的循环，询问是否可实现O(1)时间复杂度的总礼品金额计算？

解决方案：可以实现O(1)时间计算（单幸运号码） #

要实现单个幸运号码的O(1)计算，核心是预先对所有顾客彩票做统计预处理，之后每个幸运号码的计算仅需固定次数的操作（与顾客彩票总数N无关）。

预处理步骤（O(N)时间，N为彩票总数） #

构建一个6维数组freq，大小为10×10×10×10×10×10，用来统计每个6位彩票的出现次数：

• 数组的每个维度对应彩票的一位数字（0-9）
• freq[d0][d1][d2][d3][d4][d5]表示彩票d0d1d2d3d4d5的出现次数

预处理时，遍历所有顾客彩票，将每个彩票的每一位转为整数后，对应数组位置的计数加1。

单幸运号码的O(1)计算步骤 #

假设幸运号码为l = l0l1l2l3l4l5（每位转为整数），按以下步骤计算各匹配数的彩票数量：

1. 6位全匹配的数量：直接取 match6 = freq[l0][l1][l2][l3][l4][l5]
2. 恰好5位匹配的数量：
   • 遍历6个位置，对每个位置i，计算其余5位固定为l对应位时的总彩票数，减去6位全匹配的数量；将6个位置的结果求和
   • 最终 match5 = 总和 - 6 * match6（每个全匹配彩票被重复统计了6次，需去重）
3. 恰好4位匹配的数量：
   • 遍历所有C(6,2)=15种位置组合，计算对应4位固定为l对应位时的总彩票数，再通过容斥原理减去重复统计的5位匹配、6位匹配的数量
4. 恰好3位匹配的数量：
   • 可通过总彩票数减去匹配数为0、1、2、4、5、6的数量得到，或用容斥原理直接计算

得到各匹配数的数量后，总礼品金额为：

total = match6 * 100 + match5 * 50 + match4 * 40 + match3 * 10

关键说明 #

因为彩票位数固定为6，所有计算步骤的操作次数都是固定的（比如计算match5仅需循环6次），完全与顾客彩票总数N无关，因此单个幸运号码的计算时间为O(1)。

内容的提问来源于stack exchange，提问作者Sajib Saha