写在前面

大厂笔试AI Coding练习:CodeFun2000.com/aicoder-gym

第1题-质检加权评分

题目内容

外观工位把每件样品分成两类：有疵点写成 ，完好写成 。检测模型对同一批样品给出取值相同的判定。质检组不看整体对错比例，只给正类（有疵点）打分。该分数由精确率  与召回率  按系数  合成， 越大，漏掉疵点的分量越重。

记模型与人工都标成  的件数为 ，模型标成  而人工标成  的件数为 ，模型标成  而人工标成  的件数为 。

，当  时令 。

，当  时令 。

分数

当上式分母为  时，令 。

 按四舍五入保留  位小数。正类固定为 。

解题思路

1. 这是二分类里的  分数，也就是精确率与召回率的加权调和平均。正类固定为 （有疵点），完好为 。系数  对应公式里的 ： 越大，漏检（召回率）占得越重。
2. 从左到右同时看模型判定和人工标注，只计三类件数：（两边都是 ）、（模型为 、人工为 ）、（模型为 、人工为 ）。两边都是  的样品不进入分子分母。
3. 精确率 ，召回率 ；某一项分母为  时该项记 。分数。 当  时分子为 ，或整个分母为 ，都令 。 时可用等价闭式， 避免先做两次除法再乘回去。
4. 用十进制把  四舍五入到  位小数。程序自己从标准输入读入三行，再把结果打印成一行。

复杂度分析

设样品数为 。一遍扫描即可得到 、、，时间复杂度 。除输入数组外只用常数个计数器，额外空间复杂度 。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

from decimal import Decimal, ROUND_HALF_UPimport astdefscore(weight, pred, gold):# 正类固定为 1，只累计命中、误报、漏检    tp = 0    fp = 0    fn = 0for mark, label in zip(pred, gold):if label == 1and mark == 1:            tp += 1elif label == 0and mark == 1:            fp += 1elif label == 1and mark == 0:            fn += 1# 没有正类命中时，加权调和平均的分子为 0，或分母为 0，分数记 0if tp == 0:return0.0# 闭式与定义等价，用十进制做除法，再四舍五入到 3 位    w = Decimal(str(weight))    ww = w * w    num = (Decimal(1) + ww) * Decimal(tp)    den = ww * Decimal(tp + fn) + Decimal(tp + fp)    value = (num / den).quantize(Decimal("0.001"), rounding=ROUND_HALF_UP)return float(value)defmain():# 第一行是系数，第二行是模型判定，第三行是人工标注    weight = float(input())    pred = ast.literal_eval(input())    gold = ast.literal_eval(input())# 小数点后恰好 3 位    print(f"{score(weight, pred, gold):.3f}")main()

第2题-分批均方下降

题目内容

车间要用一组系数去拟合样品读数。第  件样品的自变量是一行数，读数是一个标量。预测值是这一行与系数的内积，没有另外的偏置项。

误差用残差平方的均值来衡量。设当前这一刀有  行，预测减去读数得到残差 ，则系数的梯度是

每走一步都做 。 是步长。

一共有三种走法，行序都不打乱：

1. ：每一轮把全部  行当成一刀，只更新一次。
2. ：每一轮按行号从  到 ，每次只拿一行更新。
3. ：每一轮按行号切成连续的刀，每刀最多  行；最后一刀不足  行也要更新。

轮数记为 。每一轮都会把全部样品走完，而不是只更新一次就结束。

解题思路

沿残差平方均值的负梯度更新系数，也就是批量、随机、小批量三种梯度下降。预测是自变量行与系数的内积，没有单独的偏置。

1. 当前这一刀有  行。残差  是预测减去读数，梯度 ，然后 。少乘  或把残差方向写反，走出来的系数都会偏。
2.  每一轮只切一刀，这一刀就是全部  行。
3.  每一轮按行号从  走到 ，每刀只有一行，一行更新一次。
4.  每一轮也按行号切，每刀最多  行。最后一刀不足  行仍然要更新，不能丢掉。
5.  是来回走的轮数。每一轮都把样品走完。三种走法都不打乱行序。
6. 最终系数每个数保留  位小数，放在一对方括号里，中间一个空格。

复杂度分析

• 时间复杂度：。每一轮每个元素只参与常数次乘加， 与  也只是把同一批乘法拆开。
• 空间复杂度：。主要存放自变量表；系数和每一刀的残差都更小。

 不超过 ， 不超过 ， 不超过 。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

import astimport numpy as npdefdescend(table, reading, theta, step, rounds, block, kind):# 自变量表、读数、系数都按 float64 计算，避免整型把梯度截成 0    table = np.asarray(table, dtype=np.float64)    reading = np.asarray(reading, dtype=np.float64)    theta = np.array(theta, dtype=np.float64)    rows = table.shape[0]for _ in range(rounds):# 每一轮都把全部行走完；三种走法只是一刀里有几行if kind == "full":            cuts = [(0, rows)]elif kind == "point":            cuts = [(i, i + 1) for i in range(rows)]else:            cuts = []            start = 0while start < rows:                end = min(start + block, rows)                cuts.append((start, end))                start = endfor start, end in cuts:            piece = table[start:end]            target = reading[start:end]            width = end - start# 残差 = 预测 - 读数；梯度带上 2/b，对应残差平方均值            residual = piece @ theta - target            grad = (2.0 / width) * (piece.T @ residual)            theta = theta - step * gradreturn thetadefmain():# 七行依次是走法、步长、轮数、每刀行数、初始系数、读数、自变量表    kind = ast.literal_eval(input())    step = float(input())    rounds = int(input())    block = int(input())    theta = ast.literal_eval(input())    reading = ast.literal_eval(input())    table = ast.literal_eval(input())    ans = descend(table, reading, theta, step, rounds, block, kind)    print("[" + " ".join(f"{value:.8f}"for value in ans) + "]")main()

第3题-双档连喷计数

题目内容

装配车间的打标枪只有两档。黑点写成 ，白点写成 。扣住某一档不松手，喷头就沿工件一直打出同色的点；松手再换档，才再记一次扣动。

一段点列最少要扣几次，等于它被切成的单色段个数。单色段是从左往右尽量延长、颜色保持不变的那一截。

整条工件上的点列记为 ，另外给出正整数 。请统计有多少个连续片段恰好要扣  次才能喷完。片段按起止位置区分：位置不同就各算一次，颜色序列相同也不合并。片段最短是一个点，最长可以盖住整条 。

解题思路

扣住同一档不松手，喷出来的是一段颜色不变的点。松手再换档才多计一次。所以一个连续片段要扣的次数，就是它内部的单色段个数。题目要的是单色段个数恰好等于  的片段数，位置不同的片段分开计数。

1. 从左到右扫描点列 ，把相邻同色的点并成一段，得到长度数组 。
2. 若 ，片段不能跨段。第  段内部的片段数是 。各段相加即可。这里起点和终点落在同一段，不能写成 。
3. 若 ，枚举片段覆盖的第一段下标 ，最后一段就是 。这段下标没有越界时，中间  段必须整段保留，两端各自至少留一个点，贡献是 。
4.  大于段数  时没有合法片段，答案是 。全部片段数不超过 ，乘积要放进  位整数。

复杂度分析

• 时间复杂度：。压缩单色段扫一遍点列，再按段数扫一遍。
• 空间复杂度：。最坏每个点单独成段，长度数组与点列同阶。

 与  都不超过 。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

# 双档连喷计数：统计恰好含 t 段单色的连续片段个数defcount_exact(c, t):# 空串没有片段；t 小于 1 时按题面不会出现，直接返回 0ifnot c or t <= 0:return0    lens = []    prev = ""for ch in c:# 颜色变了就新开一段，否则当前段长度加一if lens and ch == prev:            lens[-1] += 1else:            lens.append(1)            prev = ch    runs = len(lens)# 段数不够 t 时，任何片段都喷不出恰好 t 次if t > runs:return0    ans = 0if t == 1:for length in lens:# 同一段里起点和终点绑在一起，个数是三角数而不是 length*length            ans += length * (length + 1) // 2return ans# 恰好盖住连续 t 段：两端可以截短，中间必须整段留下    last = t - 1for i in range(runs - last):        ans += lens[i] * lens[i + last]return ansdefmain():# 第一行有时只有扣动次数，自测样例里也可能是「长度 扣动次数」    parts = input().split()if len(parts) == 1:        t = int(parts[0])else:        t = int(parts[1])# 第二行才是整条点列    c = input()    print(count_exact(c, t))if __name__ == "__main__":    main()

第4题-红中对桌收子

题目内容

活动室里，甲、乙用一小套麻将子做收子练习。这一套只有十三种，每种记号如下： 到  是一筒到九筒， 是东， 是白， 是发， 是红中。甲先从牌墙顶上取一张，之后两人交替各取一张，取到的子依次排进自己面前的队列，队首就是接下来要打出的那张。牌墙必须全部取完。

取完后由甲先打。每次只能打出自己的队首，不能挑子，也不能把队列倒过来。打出的子按先后落在桌面上。

出现下面两种情况时，刚打出这张的人把指定的子全部收回，按打出顺序的逆序接到自己队尾，然后立刻再打一张：

1. 刚打出的记号在桌面上已经有过。从桌面上最近的那张相同记号算起，一直到刚打出的这张，全部收回。
2. 刚打出的是红中 ，而且桌面上已经有子。桌面上的子连同这张红中一起收回。

如果打出红中时桌面是空的，这张红中就留在桌面上，当作第一张，换对方出牌。

谁在打完一张、又没有收回新子之后手里空了，谁就结束。另一人获胜。若某人打出最后一张后又收回了子，练习继续。

样例1

输入

42p 1p 2p 7z

输出

jia | 2p

说明

甲拿到 ，乙拿到 。

甲打出 ，桌面为 。乙打出 ，桌面为 。甲再打出 ，从桌面上那张  起整段收回，逆序接回后手里是 。甲继续打出队首 。乙打出红中 ，桌面不空，把桌面和红中一起收回，逆序后手里是 。乙再打红中时桌面已空，红中留下。之后甲打出 ，乙打出 ，乙的队列空了。甲获胜，手里剩下 。

样例2

输入

27z 1p

输出

yi | 1p

说明

甲只有一张红中 ，乙只有一张 。甲打出红中时桌面是空的，红中留在桌面，甲的队列随之变空。乙获胜，手里仍是 。

解题思路

甲先从牌墙顶上取子，也先出牌。双方面前都是队列，只能打队首。桌面按打出顺序保留。 是红中。

1. 从左到右把  张子交替分给甲和乙。甲拿第  张。
2. 打出普通记号时，从桌面右端找最近的相同记号。找到就把那一张直到刚打出的子整段收回，按打出顺序的逆序接到队尾，这个人马上再打。找不到就把这张留在桌面，换对方。
3. 打出红中时，桌面不空就把桌面和红中一起逆序收回，并继续出牌。桌面是空的，红中留下，换对方。
4. 某人打完一张却没有收回任何子，手里又空了，另一人获胜。输出时  表示甲， 表示乙，队列从队首写到队尾。

复杂度分析

• 时间复杂度：出牌次数不超过 ，每次在桌面上找相同记号最多扫  张，，合计 。
• 空间复杂度：。只保存双方队列和桌面。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

# 红中对桌收子：两个队列模拟轮流打出、同面子收回，红中钓走整桌defparse_concat(text):# 旧题面把牌粘成一串，10 占两个字符    cards = []    i = 0while i < len(text):if text[i:i + 2] == "10":            cards.append("10")            i += 2else:            cards.append(text[i])            i += 1return cardsdefis_hook(card):# 新题面里 7z 是红中；旧的一行粘连样例里仍用 Jreturn card == "7z"or card == "J"defsimulate(cards):# 下标 0 是甲，先摸先打；下标 1 是乙    hands = [[], []]for i, card in enumerate(cards):        hands[i % 2].append(card)    table = []    cur = 0for _ in range(10000):# 轮到的人手里已经空了，另一人获胜ifnot hands[cur]:return1 - cur, hands[1 - cur]        card = hands[cur].pop(0)        got = Falseif is_hook(card):ifnot table:# 桌面是空的，红中钓不到，这张留下，本轮不再收回                table.append(card)else:# 桌面从先到后，再接上这张红中；逆序入队，最后打出的排在前面                taken = table + [card]                table = []                hands[cur].extend(reversed(taken))                got = Trueelse:            idx = Nonefor i in range(len(table) - 1, -1, -1):if table[i] == card:                    idx = ibreakif idx isnotNone:                taken = table[idx:] + [card]                table = table[:idx]                hands[cur].extend(reversed(taken))                got = Trueelse:                table.append(card)if got:# 收回牌的人立刻再打一张continueifnot hands[cur]:return1 - cur, hands[1 - cur]        cur = 1 - curreturn0, hands[0]defmain():    first = input()try:        second = input()except EOFError:        second = Noneif second isNone:# 只有一行、牌面粘在一起时，按旧样例读入并沿用旧的两行输出        cards = parse_concat(first.strip())        winner, hand = simulate(cards)        print("sanqiu"if winner == 0else"xiran")        print(" ".join(hand))return# 新题面：第一行是张数，第二行用空格分开每张麻将子    cards = second.split()    winner, hand = simulate(cards)    name = "jia"if winner == 0else"yi"if hand:        print(name + " | " + " ".join(hand))else:        print(name + " |")if __name__ == "__main__":    main()