奇安信秋招 2023.09.16 编程题目与题解

发表于 2023-09-20 分类于笔试阅读次数：本文字数： 2.4k 阅读时长 ≈ 2 分钟

1、资深彩民的投注方案

纳西姆·塔勒布在著作《随机漫步的傻瓜》中提到过“赌徒谬误”：赌徒谬误的产生是因为人们错误的诠释了“大数法则”的平均律，以为随机序列中一个事件发生的机会率与发生的事件有关，即其发生的机会率会随着之前没有发生该事件的次数而上升。如重复抛一个公平硬币，而连续多次抛出反面朝上，赌徒可能错误地认为，下一次抛出正面的机会会较大。

很遗憾的是，资深彩民小王沉迷于此，现在有一批双色球的往期中奖号码数据，小王想要从其中找到出现次数最少的几个数字进行投注。现在已知双色球每期会有产生\(7\)个中奖号码，号码从\(1\text{-}33\)，不会重复。例如往期某次的中奖号码为： \([5,10,13,20,25,27,30]\)，请帮助小王完成这个分析程序，输入是往期的中奖号码数组，请输出一组符合小王需求的投注方案。

其它要求：

将投注方案中的数字按照从小到大排列。
如果存在多组可能，比如有\(8\)个数字出现次数都是\(0\)，那么把数字最小的\(7\)个数字组成一组投注方案输出。

样例

输入：
[[1,2,3,4,5,6,7],[8,9,10,11,12,13,14],[15,16,17,18,19,20,21],[22,23,24,25,26,27,28]]

输出：
[1,2,29,30,31,32,33]

输入：
[[1,2,3,4,5,6,7],[4,6,7,9,10,12,14]]

输出：
[8,11,13,15,16,17,18]

解答

本题思路比较简单，先统计当前所有中奖号码都出现的次数，然后对\(1\sim 33\)这\(33\)个号码按照以第一关键字为出现频率，升序；第二关键字为数值本身，升序进行排序。最终取排序结果的前\(7\)个号码即可。

取出这\(7\)个号码后，还要对它们进行排序后返回。

代码

class Solution{
public:
    vector<int>solve(vector<vector<int>> &a){
        int n=33;
        vector<int>c(n+1);
        for(auto v:a){
            for(int x:v){
                ++c[x];
            }
        }
        vector<int>num;
        for(int i=1;i<=n;i++)
            num.push_back(i);
        sort(num.begin(),num.end(),[&c](int x,int y){return c[x]<c[y]||c[x]==c[y]&&x<y;});
        vector<int>ans(num.begin(),num.begin()+7);
        sort(ans.begin(),ans.end());
        return ans;
    }
};

2、卡片游戏

小朋友们在玩一款卡片游戏，卡片一共有\(N\)张，每张上印有\(0\)到\(N-1\)的互不重复数字，作为卡片的唯一编号。将\(N\)张卡片按照树形结构排列，提问的小朋友说出一张卡片的编号\(a\)和数字\(b\)，另一个小朋友需要从卡片编号\(a\)到树的根节点路径上找出一张卡片\(c\),该卡片\(c\)的编号与数字\(b\)的异或值最大。

\(\texttt{parents}[i]\)表示卡片编号\(i\)的父节点的卡片编号。如果节点\(x\)是树的根节点，则\(\texttt{parents}[x] = -1\)。

\(\texttt{questions}[i] =[\texttt{node}_i,\texttt{val}_i]\)表示第\(i\)个问题，卡片的编号为\(\texttt{node}_i\)，说出的数字为\(\texttt{node}_i\)，需要找到卡片\(p_i\)，使得\(\texttt{val}_i\)和\(p_i\)的异或值最大，其中\(p_i\)是\(\texttt{node}_i\)到根之间的节点（包含\(\texttt{node}_i\)和根节点），即需要最大化\(\texttt{val}_i\text{ XOR }p_i\)。

请返回数组result ，其中\(\texttt{result}[i]\)是第\(i\)个问题的答案。

说明：\(2\le N\le 10^5,0\le b \le 2\times 10^5\)

输入

第一行为\(\texttt{parents}\)数组，表示树的结构，使用逗号分割的整数。

\(2 \le \texttt{parents.length} \le 10^5\)

对于每个不是根节点的\(i\)，有 \(0 \le \texttt{parents}[i] \le \texttt{parents.length} - 1\)。

之后\(M\)行为数组，每行表示提出的一个问题，包括两个整数\(\texttt{node}_i\)和\(\texttt{val}_i\)，使用逗号分割。

\(1\le \texttt{questions.length}\le 3*10^4\)
\(0 \le \texttt{node}_i \le \texttt{parents.length} - 1\)
\(0 \le \texttt{val}_i \le 2\times10^5\)
\(1\le M\le 3\times10^4\)

输出

\(M\)个用逗号分割的整数，为对应问题的答案。

样例

输入：
1,-1,0,0
3,7
1,19
0,5

输出：
0,1,0

提示：
其中parents = [1,-1,0,0] questions = [[3,7],[1,19],[0,5]]
[3,7]：最大异或的对应节点为0，7 XOR 0 = 7
[1,19]：最大异或的对应节点为1，19 XOR 1 = 18

输入：
2,7,-1,0,3,7,3,2
4,12
1,19
0,5

输出：
3,7,2

提示：
其中parents = [2,7,-1,0,3,7,3,2] questions = [[4,12],[1.19],[0.5]]
[4.12]：最大异或的对应节点为3，12 XOR 3 = 15
[1,19]: 最大异或的对应节点为7，19 XOR 7 = 20
[0,5]: 最大异或的对应节点为2，5 XOR 2 = 7

以下是这两棵树对应的图：

graph TD
    subgraph T1
        A((0));B((1));C((2));D((3));
        B---A;A---C;A---D;
    end
    subgraph T2
        0((0));1((1));2((2));3((3));
        4((4));5((5));6((6));7((7));
        2---7;2---0;7---1;7---5;
        0---3;3---4;3---6;
    end

解答

这题是字典树运用的经典例题。我们首先考虑如下问题：

问题一：给定一个整数集合\(S\)以及多个询问，每次询问给出一个数\(x\)，问\(S\)中和\(x\)异或产生的最大结果是多少？

我们使用字典树解决，对\(S\)中的所有数看成是一个\(M\)比特数，并从高位到地位插入字典树中。询问\(x\)时，假设从高到低遍历到\(x\)的某一比特\(b\)，然后在当前节点查看是否能去到另一侧的节点（也就是由\(1-b\)指向的节点），如果能去，那么当前位对答案会有贡献；否则只能走向当前的节点，无法对答案做出贡献。由于最高位优先，因此产生的是一个最佳答案。

那么现在对问题一加一些操作，得到一个更复杂的问题：

问题二：集合\(S\)可以动态增加/删除元素（且保证询问时非空），如何处理？

我们可以在这棵字典树上对每个节点进行标记，这些标记可以叠加和撤销。在询问时，如果\(1-b\)指向的节点没有标记（或者是不存在），那么说明只能走去另一侧的节点，否则可以走上另一侧的节点。

本问题是问题二的一个特例。使用深度优先搜索遍历到某个节点\(u\)时，将\(u\)这个值插入到集合\(S\)中，此时将和关联节点\(u\)的所有询问完成后，遍历它的所有子节点，最终将\(u\)从\(S\)中删除即可。

剩下的则是一些麻烦的处理输入输出问题，此处不赘述。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
const int N=100004;
const int O=2000004,M=17;
int tr[O][2],c[O],tot=0;
void add(int x,int f){
    int p=0;
    for(int j=M;j>=0;j--){
        int b=x>>j&1;
        if(tr[p][b]==0) tr[p][b]=++tot;
        p=tr[p][b];
        c[p]+=f;
    }
}
int que(int x){
    int p=0,ans=0;
    for(int j=M;j>=0;j--){
        int b=x>>j&1;
        if(tr[p][b^1]!=0&&c[tr[p][b^1]]>0){
            ans|=1<<j;
            p=tr[p][b^1];
        }
        else p=tr[p][b];
    }
    return ans;
}
vector<int>g[N],ans;
vector<pi>q[N];
void dfs(int u){
    add(u,1);
    for(auto [val,id]:q[u]){
        ans[id]=que(val)^val;
    }
    for(int v:g[u]){
        dfs(v);
    }
    add(u,-1);
}
vector<int>solve(vector<int>&parents, vector<vector<int>>&questions){
    int n=parents.size(),rt=-1;
    for(int i=0;i<n;i++){
        if(parents[i]==-1) rt=i;
        else g[parents[i]].push_back(i);
    }
    for(int i=0;i<questions.size();i++){
        q[questions[i][0]].push_back(make_pair(questions[i][1],i));
    }
    ans.resize(questions.size());
    dfs(rt);
    return ans;
}
vector<int>str2vec(string s){
    s+=',';
    vector<int>a;
    int flag=1,val=0;
    for(char ch:s){
        if(ch=='-') flag=-1;
        else if(isdigit(ch)) val=val*10+(ch-'0');
        else{
            a.push_back(flag*val);
            flag=1,val=0;
        }
    }
    return a;
}
string vec2str(vector<int>a){
    string s;
    for(int x:a){
        s+=to_string(x)+',';
    }
    s.pop_back();
    return s;
}

int main(){
    string s;
    cin>>s;
    vector<int>parents=str2vec(s);
    vector<vector<int>>questions;
    while(cin>>s){
        questions.emplace_back(str2vec(s));
    }
    vector<int>ans=solve(parents,questions);
    cout<<vec2str(ans)<<"\n";
}