京东-27届秋招题目8.29

第1题 第几条明暗交错子序列

题目描述

给定一个长度为的二进制字符串。从中选择一组严格递增的下标，可以得到一个子序列；也允许一个下标都不选，此时得到空串。

如果中任意两个相邻字符都不相同，则称它为明暗交错子序列。

不同的下标选择方案要分别计数，即使它们得到的字符串完全相同，也视为不同方案。把所有合法方案得到的字符串放在一起，按照以下规则排序：

空串也参与排序。请输出排序后的第个字符串；如果总方案数不足个，则输出 -1。题目保证第个字符串不会是空串。

输入描述

第一行输入两个整数：

第二行输入一个长度为的二进制字符串。

输出描述

输出排序后的第个明暗交错子序列；若不存在，则输出 -1。

样例1

输入：

3 4110

输出：

1

样例2

输入：

4 20101

输出：

0

样例3

输入：

1 50

输出：

-1

解题思路

这道题最关键的观察是：交错串一旦确定了长度和首字符，整条字符串就随之确定。

例如长度为时，只有 01010 和 10101 两种可能。因此，我们不需要真的枚举所有字符串，只需统计：

从右向左扫描原串。令 cnt[c][L] 表示当前后缀中，长度为且以字符开头的交错子序列数量。

处理当前字符时：

由于，所有计数超过后都可以直接截断，既能避免无意义的大整数增长，也不会影响名次判断。

统计完成后，先扣除排在最前面的空串，再按长度从小到大寻找第个方案所在的长度。固定长度内，以 0 开头的交错串字典序更小，因此先判断名次是否落在这一组；否则答案就是以 1 开头的那一种交错串。

复杂度分析

更加详细解题思路和 CPP、Java 代码加我微信获取：jackwwang8

import sysLIMIT = 10**15def solve(m, q, bits):    # cnt[first][length]：以 first 开头、长度为 length 的方案数    cnt = [[0] * (m + 1) for _ in range(2)]    for char in reversed(bits):        first = ord(char) - ord("0")        other = first ^ 1        cnt[first][1] = min(LIMIT, cnt[first][1] + 1)        for length in range(2, m + 1):            value = cnt[first][length] + cnt[other][length - 1]            cnt[first][length] = min(LIMIT, value)    # 空串位于第 1 名，因此在非空方案中寻找第 q-1 名    rank = q - 1    answer_length = -1    for length in range(1, m + 1):        total = min(LIMIT, cnt[0][length] + cnt[1][length])        if rank > total:            rank -= total        else:            answer_length = length            break    if answer_length == -1:        return "-1"    if rank <= cnt[0][answer_length]:        first = 0    else:        first = 1    return "".join(        str(first ^ (index & 1)) for index in range(answer_length)    )def main():    data = sys.stdin.read().split()    m = int(data[0])    q = int(data[1])    bits = data[2]    print(solve(m, q, bits))if __name__ == "__main__":    main()

第2题 货位好坏线性判别

题目描述

仓储质检系统需要按照指定流程训练一个线性分类器，并判断测试货位是否合格。

每条训练记录由特征向量和标签组成，其中 0 表示不合格，1 表示合格。训练前先把标签转换为：

在特征向量前补上常数项，得到：

权向量初始全部为，学习率固定为，严格按照训练数据的原始顺序训练轮。

对每个样本，先计算：

其中内积大于等于时，；否则。若预测错误，则执行更新：

训练结束后，用同样的判定规则预测测试集，并将映射回 1、映射回 0。

输入描述

标准输入是一段 JSON，包含两个字段：

输出描述

输出一行 JSON 数组，依次给出每条测试数据的预测标签。

样例1

输入：

{"train":[[[0],0],[[1],0],[[4],1],[[5],1]],"test":[[0],[1],[2],[3],[4],[5]]}

输出：

[0, 0, 1, 1, 1, 1]

样例2

输入：

{"train":[[[0,0],0],[[2,0],1]],"test":[[0,0],[2,0],[1,0]]}

输出：

[0, 1, 1]

解题思路

本题不是选择最优分类模型，而是完整复现题目指定的感知机训练过程。因此，训练轮数、样本顺序、零点的符号判定以及更新时机都不能改变。

先根据第一条训练样本确定特征维数，并创建多一个元素的权向量，其中 weights[0] 对应偏置项。随后执行轮训练：

预测测试集时不再修改权重，只计算内积并把符号转换回 0/1 标签。输入输出均为 JSON，使用标准库 json 即可完成解析和序列化。

复杂度分析

设训练样本数为，测试样本数为，特征维数为。

更加详细解题思路和 CPP、Java 代码加我微信获取：jackwwang8

import jsonimport sysdef dot(weights, features):    score = weights[0]    for index, value in enumerate(features, start=1):        score += weights[index] * value    return scoredef train_perceptron(train_data):    dimension = len(train_data[0][0])    weights = [0.0] * (dimension + 1)    for _ in range(10):        for features, label in train_data:            target = 1 if label == 1 else -1            prediction = 1 if dot(weights, features) >= 0 else -1            if prediction != target:                weights[0] += target                for index, value in enumerate(features, start=1):                    weights[index] += target * value    return weightsdef solve(data):    weights = train_perceptron(data["train"])    answer = []    for features in data["test"]:        label = 1 if dot(weights, features) >= 0 else 0        answer.append(label)    return answerdef main():    data = json.loads(sys.stdin.read())    result = solve(data)    print(json.dumps(result, ensure_ascii=False))if __name__ == "__main__":    main()