阿里0325笔试

今天得空review了一下昨晚的笔试，AI研发方向的，整体上有一定的难度，感觉自己答得还可以吧，期待给个面试机会

20 道选择 + 3 道编程 + 1 道 Prompt，T1 签到，T2 贪心一眼秒，T3 是个数位 DP 有点东西，T4 Prompt 题考的是让 AI 算出租车费。

选择题概览

选择题一半 AI 一半 CS 基础，AI 方向的占比还是挺高的。

AI/Agent 相关的大概考了这些：Transformer 的 teacher forcing 训练推理差异、MHA/MQA/GQA 注意力机制对比、LangChain 和 LangGraph 的关系、ReAct 的机制边界、multi-agent vs 单 agent 的适用场景、Agent 长期记忆方案设计、tool use 参数出错的排查、多任务混合 RL 训练的问题、提示词注入防御，还有一道 MCP 里 tool 和 resource 的区别。说实话做大模型方向的应该还好，但有几道涉及 Agent 工程细节的确实得有实操经验才好选。

CS 基础那边考的比较杂：排序算法（基本有序数组选什么排序最快）、TCP 流量控制和拥塞控制的区别、SQL 查询（GROUP BY + HAVING）、操作系统内存分区的 Best Fit、互斥锁和信号量、博弈论取数游戏的 DP 思路、并发系统的数据结构设计、HTTPS/TLS 安全机制、数据库全表扫描的触发条件，还有一道优化动作是改善真实性能还是纸面指标的。这些算是比较经典的八股了。

T1. 分糖果

知识点：数学

签到题。对于每种糖果 $i$ ，每个小朋友分到 $\lfloor c_i/k \rfloor$ 或 $\lceil c_i/k \rceil$ ，而且不同种类的分配是独立的。所以我们完全可以让某个小朋友对每种都拿 $\lfloor c_i/k \rfloor$ ，也可以让他对每种都拿 $\lceil c_i/k \rceil$ 。最小值就是 $\sum \lfloor c_i/k \rfloor$ ，最大值就是 $\sum \lceil c_i/k \rceil$ 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--){
        int n,k,i;
        cin>>n>>k;
        int mi=0,ma=0;
        for(i=0;i<n;i++){
            int c;
            cin>>c;
            mi+=c/k;
            ma+=(c+k-1)/k;
        }
        cout<<mi<<" "<<ma<<"\n";
    }
}

T2. 最大子序列

知识点：贪心

要字典序最大，那第一个元素肯定越大越好。从 $n$ 到 $1$ 枚举值 $v$ ，如果 $v$ 在 $p$ 和 $q$ 中的位置都在之前选的元素后面，就选它。因为 $v$ 比任何更小的值都大，选上一定不亏，不选反而可能错过。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[202020],b[202020];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,i,x;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>x;
        a[x]=i;
    }
    for(i=1;i<=n;i++){
        cin>>x;
        b[x]=i;
    }
    int la=0,lb=0;
    vector<int>res;
    for(i=n;i>=1;i--){
        if(a[i]>la&&b[i]>lb){
            res.push_back(i);
            la=a[i];
            lb=b[i];
        }
    }
    cout<<res.size()<<"\n";
    for(i=0;i<(int)res.size();i++){
        if(i)cout<<" ";
        cout<<res[i];
    }
    cout<<"\n";
}

T3. 挑食

知识点：数位DP、二分

$k$ 到 $10^{18}$ ，显然不能枚举。经典套路：二分答案 $x$ ，数位 DP 算 $[1,x]$ 里有多少个数满足「不含数字 3 且不被 3 整除」。

考场上第一反应就是二分答案 + 数位 DP 算 $[1,x]$ 里有多少个合法数。写了个递归记搜的版本，状态是（位置，数位和 mod 3，是否贴上界，是否开始），每次二分都 memset 一遍 dp 数组重跑。单测没问题，但这题 $t$ 到 $10^4$ ，每组二分 60 多次，每次 memset + 递归，直接 T 了只过了不到一半。

后来发现合法数字 $\{0,1,2,4,5,6,7,8,9\}$ 在 mod 3 下刚好均匀分布（每种余数恰好 3 个），所以 $d$ 位的合法序列里每种余数的个数都是 $9^d/3$ 。有了这个性质就不需要记搜了，预处理 $9$ 的幂，逐位迭代就能算：位数 $< n$ 的部分直接公式（1 位 6 个， $len$ 位 $48 \times 9^{len-2}$ 个），位数 $= n$ 的部分从高位往低位扫，枚举比当前位小的合法数字，剩下的位用公式一步到位。遇到 3 直接 break。

注意答案可能超 long long（题目提示第 $10^{18}+1$ 项约 $1.1 \times 10^{19}$ ），要用 unsigned long long。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

ull pw[21];

ull f(ull x){
    if(!x)return 0;
    int d[21],n=0;
    ull t=x;
    while(t)d[n++]=t%10,t/=10;
    for(int i=0;i<n/2;i++)swap(d[i],d[n-1-i]);
    ull res=0;
    // 位数 < n 的合法数：1位有6个，len位(len>=2)有 48*9^(len-2) 个
    if(n>1)res+=6;
    for(int i=2;i<n;i++)res+=48*pw[i-2];
    // 位数 = n 且 <= x 的合法数
    int cm=0;
    bool brk=0;
    for(int i=0;i<n;i++){
        for(int v=(i?0:1);v<d[i];v++){
            if(v==3)continue;
            int nm=(cm+v)%3,rem=n-i-1;
            if(!rem){
                if(nm)res++;
            }else{
                res+=pw[rem]-pw[rem]/3;
            }
        }
        if(d[i]==3){brk=1;break;}
        cm=(cm+d[i])%3;
    }
    if(!brk&&cm)res++;
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    pw[0]=1;
    for(int i=1;i<=20;i++)pw[i]=pw[i-1]*9;
    int _;
    cin>>_;
    while(_--){
        ull k;
        cin>>k;
        ull lo=1,hi=18000000000000000000ULL;
        while(lo<hi){
            ull mid=lo+(hi-lo)/2;
            if(f(mid)>=k)hi=mid;
            else lo=mid+1;
        }
        cout<<lo<<"\n";
    }
}

T4. 出租车计费器

这道是 Prompt 题，给了出租车的计费规则，要你写提示词让 AI 正确算费用。规则不复杂但细节不少：起步价 3km 10 元，3-15km 每公里 3 元，超 15km 每公里 4 元（不足 1km 向上取整），等候费每满 5 分钟 2 元，夜间 23:00（含）至次日 5:00（不含）车费加收 20% 向上取整，大件行李每件 5 元不参与夜间加收。

这道题模型用的是 qwen3.5-flash，调 prompt 的时候踩了不少坑，在另一位牛友评论区评论的答题过了50%，但是今天又凭着回忆修正了一版

参考 Prompt：

# Role
你是高德出租车计费系统。用户用自然语言描述行程，你提取信息并计算费用，只输出JSON。

# 信息提取
从用户描述中提取：行驶距离（公里）、等候时间（分钟）、是否夜间、大件行李数量。
未提及的默认为0，时间未提及默认白天。
夜间指上车时间在23:00（含）到次日05:00（不含）之间。

# 计算过程

## 第一步：基础车费 base_fare
起步价10元，包含前3公里（含3公里）。
超过3公里的部分，不足1公里按1公里算（向上取整到整数公里）：
- 总距离在3到15公里（含15公里）：超出部分每公里3元
- 总距离超过15公里：超出3公里的前12公里每公里3元，再超出的部分每公里4元

## 第二步：夜间加收
夜间：车费 = base_fare × 1.2，有小数则进1取整（例如19.2进为20），night_surcharge = true
非夜间：车费 = base_fare，night_surcharge = false
注意：等候费和行李费不参与夜间加收。

## 第三步：等候费
只按完整的5分钟计费，剩余不足5分钟的部分不收。
等候费 = (等候分钟数 减去 余数后 再除以5) × 2
比如24分钟：24减去余数4得20，20÷5=4段，等候费=4×2=8元

## 第四步：行李费
每件大件行李5元。

## 第五步：总费用
fare = 车费 + 等候费 + 行李费

# 输出
只输出一个JSON，不要输出任何其他内容。按顺序填入以下字段：
{
  "thinking": "用自然语言写出完整的逐步计算过程，包括每一步的数字代入和结果",
  "base_fare": 基础车费（整数元）,
  "night_surcharge": 是否夜间（true/false）,
  "fare": 总费用（整数元）
}
所有费用为整数，单位元。