四季读书网
四季读书网

3月15日蚂蚁算法岗真题解析

四季读书网 3 0
3月15日蚂蚁算法岗真题解析
3月15日蚂蚁算法岗真题解析 第1张

🔗刷题网址: bishipass.com

蚂蚁-2026.03.15-算法岗

这一套前后层次很清楚：第 1 题是纯判断型热身，关键只是别被“大整数”三个字吓到；第 2 题虽然披着图学习外壳，但本质是按题面公式做一次聚合和小规模线性代数实现，属于整场最容易在细节上丢分的题；第 3 题回到经典字符串比较，真正难点是把“两端删字符”改写成固定长度窗口的最小字典序比较。

题目一：祝福乘积校验

这题本质是整除判定，不需要真的把两个超长整数乘出来。把字符串逐位对  取模后再相乘即可，做法非常直接。最容易错的地方是想当然上大整数库，结果把一个热身题写重了。

难度：简单

题目二：单层节点分类器

题面看着像机器学习，实际完全是实现题：无向图一跳均值聚合、岭回归闭式解、再接一次 sigmoid 判类。真正卡人的地方在于“自己也参与平均”“孤立点保持原向量”“浮点输出按题意保留到小数点后 6 位”这些工程细节。只要流程没有读错，这题并不需要任何额外模型知识。

难度：中等偏难

题目三：裁边后的最小片段

把左右删掉恰好  个字符后，剩下的一定是原串里的一个长度为  的连续子串，所以题目马上转成若干固定长度窗口的字典序最小值。难点不在贪心，而在怎么高效比较两个候选窗口；这里用双模哈希加二分 LCP 就够了。实现时最容易写炸的是比较函数边界和哈希下标。

难度：中等

1. 祝福乘积校验

问题描述

LYA 在生日当天收到了很多朋友发来的祝福消息。第  位朋友会给出两个十进制大整数 。

LYA 约定：如果  是  的倍数，就认为这份祝福通过了校验。

现在请对每位朋友分别判断，这份祝福是否通过校验。

输入格式

每个测试文件均包含多组测试数据。

第一行输入一个整数 ，表示朋友的数量。

接下来  行，每行输入两个由数字字符构成、且不含前导零的整数 。

输出格式

对于每位朋友，单独输出一行结果：

  • >
    如果  是  的倍数，输出 Yes。
  • >
    否则输出 No。

输出大小写必须与样例一致。

样例输入

5
2 3
6 11
22 9
25 44
121 132

样例输出

No
Yes
Yes
No
Yes

数据范围

  • >
  • >
  • >
    单个测试文件内，所有  与  的位数之和不超过 

题解

这题的核心不是“大整数乘法”，而是“整除判定”。

因为只需要判断  是否是  的倍数，所以根本没有必要真的把两个超长整数乘出来。只要保留模  的结果就够了。

设：

  • >
  • >

那么：

于是只要判断：

就能得到答案。

#怎么求超长整数对  取模

把数字当成字符串逐位读入。

如果当前已经处理出的前缀模值是 cur，读到新的一位数字 d 之后，新模值就是：

整段字符串扫完，就得到了这个大整数对  的模。

#复杂度分析

设某组数据中两个字符串长度之和为 。

逐位取模只需要线性扫描，因此这一组的复杂度是 。

整份测试文件中，所有数字总位数不超过 ，所以总复杂度就是 总位数，额外空间复杂度为 。

参考代码

  • >
    Python
import sys

input = lambda: sys.stdin.readline().strip()


defmod66(s: str) -> int:
    val = 0
for ch in s:
        val = (val * 10 + ord(ch) - 48) % 66
return val


defsolve() -> None:
    t = int(input())
    out = []
for _ in range(t):
        x, y = input().split()
        ok = mod66(x) * mod66(y) % 66 == 0
        out.append("Yes"if ok else"No")
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

intmod66(conststring& s){
int val = 0;
for (char ch : s) {
        val = (val * 10 + (ch - '0')) % 66;
    }
return val;
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
string x, y;
cin >> x >> y;
bool ok = 1LL * mod66(x) * mod66(y) % 66 == 0;
cout << (ok ? "Yes" : "No") << '\n';
    }
return0;
}
  • >
    Java
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.StringJoiner;

publicclassMain{
staticintmod66(String s){
int val = 0;
for (int i = 0; i < s.length(); i++) {
            val = (val * 10 + s.charAt(i) - '0') % 66;
        }
return val;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);
int t = fs.nextInt();
        StringBuilder sb = new StringBuilder();
for (int cs = 0; cs < t; cs++) {
            String x = fs.next();
            String y = fs.next();
boolean ok = (long) mod66(x) * mod66(y) % 66 == 0;
            sb.append(ok ? "Yes" : "No").append('\n');
        }
        System.out.print(sb);
    }

staticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = new BufferedInputStream(is);
        }

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

String next()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);
            StringBuilder sb = new StringBuilder();
while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
return sb.toString();
        }

intnextInt()throws IOException {
return Integer.parseInt(next());
        }
    }
}

2. 单层节点分类器

问题描述

LYA 正在整理一张无向关系网络。图中共有  个节点，节点编号为 ，每个节点都带有一个长度为  的原始特征向量。

现在需要按照下面这套固定流程，实现一个单层 GraphSAGE-Mean 节点分类器：

  1. 图是无向图，没有自环，输入给出邻接边 edges。
  2. 原始特征矩阵记为 。
  3. 先做一跳平均聚合，得到新特征矩阵 。对于节点 ：

如果节点  的度数为 ，那么直接有 。

  1. 只在训练节点上已知标签 。设训练节点对应的特征矩阵是 ，标签向量是 ，并固定 ，训练目标为：

其闭式解为：

  1. 对任意节点 ，预测概率为：

其中 。阈值取 ，若  则预测标签为 ，否则为 。

请输出权重向量、测试点的预测概率，以及测试点的预测标签。

输入格式

输入只有一行，是一个 JSON 对象：

{
"nodes": [[...], [...], ...],
"edges": [[u1, v1], [u2, v2], ...],
"train_idx": [i1, i2, ...],
"train_y": [0, 1, ...],
"test_idx": [j1, j2, ...]
}

其中：

  • >
    nodes 表示原始特征矩阵；
  • >
    edges 表示无向边；
  • >
    train_idx 表示训练节点下标；
  • >
    train_y 表示训练节点标签；
  • >
    test_idx 表示需要预测的节点下标。

输出格式

输出一行 JSON：

{
"weights": [...],
"test_proba": [...],
"test_pred": [...]
}

要求：

  • >
    weights 长度为 ；
  • >
    test_proba 长度等于 test_idx 的长度；
  • >
    所有浮点数都按照 round(x, 6) 的规则保留到小数点后  位。

样例输入

{"nodes":[[0,0],[0.2,0.1],[0.1,-0.1],[4,4],[4.2,3.9]],"edges":[[0,1],[0,2],[3,4]],"train_idx":[0,3],"train_y":[0,1],"test_idx":[1,4]}

样例输出

{"weights":[0.085354,0.164463],"test_proba":[0.50419,0.730977],"test_pred":[1,1]}

数据范围

  • >
  • >
  • >
  • >
  • >

题解

这题本质上是一道按固定公式实现的题，关键是不要把流程理解错。

#第一步：做一跳均值聚合

先按无向图建邻接表。

然后对每个节点 ，把自己和所有一跳邻居的特征向量加起来，再除以 ，就得到新的特征向量 。

这里有两个容易错的点：

  • >
    这一步是自己也要参与平均，不是只平均邻居。
  • >
    图是无向图，所以每条边要双向加入。

#第二步：只在训练节点上做岭回归

题目已经把目标函数和闭式解都写出来了，所以不需要再去训练什么神经网络，也不需要自己迭代梯度下降。

把训练节点对应的那些行抽出来，记成矩阵 ，再把标签写成列向量 。

接着计算：

问题就变成了解线性方程：

由于 ，直接用高斯消元就够了。

#第三步：算概率并判类

拿到  以后，对测试节点  计算：

如果 ，预测标签就是 ，否则是 。

#为什么这样做是对的

因为题目已经明确规定了：

  1. 特征如何聚合；
  2. 训练目标函数是什么；
  3. 闭式解怎么写；
  4. 预测时如何从线性结果映射到概率。

所以只要严格按这套流程实现，得到的结果就是题目要求的标准答案。

#复杂度分析

设节点数为 ，特征维度为 ，边数为 。

  • >
    建图和聚合的复杂度是 。
  • >
    计算  与  的复杂度是 。
  • >
    解一个  的线性方程组，复杂度是 。

由于本题  都很小，所以整体代价非常低。

参考代码

  • >
    Python
import json
import math
import sys

input = lambda: sys.stdin.readline().strip()
LAMBDA = 0.01


defsigmoid(x: float) -> float:
if x >= 0:
        e = math.exp(-x)
return1.0 / (1.0 + e)
    e = math.exp(x)
return e / (1.0 + e)


defgauss(a, b):
    n = len(a)
for col in range(n):
        pivot = col
for row in range(col, n):
if abs(a[row][col]) > abs(a[pivot][col]):
                pivot = row
        a[col], a[pivot] = a[pivot], a[col]
        b[col], b[pivot] = b[pivot], b[col]

        base = a[col][col]
for j in range(col, n):
            a[col][j] /= base
        b[col] /= base

for row in range(n):
if row == col:
continue
            fac = a[row][col]
if abs(fac) < 1e-12:
continue
for j in range(col, n):
                a[row][j] -= fac * a[col][j]
            b[row] -= fac * b[col]
return b


defsolve() -> None:
    data = json.loads(input())
    nodes = data["nodes"]
    edges = data["edges"]
    train_idx = data["train_idx"]
    train_y = data["train_y"]
    test_idx = data["test_idx"]

    n = len(nodes)
    d = len(nodes[0])
    g = [[] for _ in range(n)]
for u, v in edges:
        g[u].append(v)
        g[v].append(u)

    h = [[0.0] * d for _ in range(n)]
for i in range(n):
        cnt = len(g[i]) + 1
for k in range(d):
            cur = nodes[i][k]
for v in g[i]:
                cur += nodes[v][k]
            h[i][k] = cur / cnt

    a = [[0.0] * d for _ in range(d)]
    b = [0.0] * d
for idx, y in zip(train_idx, train_y):
        row = h[idx]
for i in range(d):
            b[i] += row[i] * y
for j in range(d):
                a[i][j] += row[i] * row[j]
for i in range(d):
        a[i][i] += LAMBDA

    w = gauss(a, b)
    proba = []
    pred = []
for idx in test_idx:
        z = 0.0
for i in range(d):
            z += h[idx][i] * w[i]
        p = sigmoid(z)
        proba.append(round(p, 6))
        pred.append(1if p >= 0.5else0)

    ans = {
"weights": [round(x, 6) for x in w],
"test_proba": proba,
"test_pred": pred,
    }
    sys.stdout.write(json.dumps(ans, ensure_ascii=False, separators=(",", ":")))


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

constdouble LAMBDA = 0.01;

structParser {
string s;
int p = 0;

explicitParser(string str) : s(std::move(str)){}

voidskip(){
while (p < (int)s.size() && isspace((unsignedchar)s[p])) {
            ++p;
        }
    }

voidexpect(char c){
        skip();
if (p >= (int)s.size() || s[p] != c) {
throw runtime_error("parse error");
        }
        ++p;
    }

booleat(char c){
        skip();
if (p < (int)s.size() && s[p] == c) {
            ++p;
returntrue;
        }
returnfalse;
    }

stringparseString(){
        skip();
        expect('"');
string res;
while (p < (int)s.size() && s[p] != '"') {
            res.push_back(s[p++]);
        }
        expect('"');
return res;
    }

doubleparseNumber(){
        skip();
int st = p;
if (s[p] == '-') {
            ++p;
        }
while (p < (int)s.size() && isdigit((unsignedchar)s[p])) {
            ++p;
        }
if (p < (int)s.size() && s[p] == '.') {
            ++p;
while (p < (int)s.size() && isdigit((unsignedchar)s[p])) {
                ++p;
            }
        }
return stod(s.substr(st, p - st));
    }

vector<double> parseDoubleArray(){
vector<double> res;
        expect('[');
if (eat(']')) {
return res;
        }
while (true) {
            res.push_back(parseNumber());
if (eat(']')) {
break;
            }
            expect(',');
        }
return res;
    }

vector<int> parseIntArray(){
vector<int> res;
        expect('[');
if (eat(']')) {
return res;
        }
while (true) {
            res.push_back((int)llround(parseNumber()));
if (eat(']')) {
break;
            }
            expect(',');
        }
return res;
    }

vector<vector<double>> parseDoubleMatrix(){
vector<vector<double>> res;
        expect('[');
if (eat(']')) {
return res;
        }
while (true) {
            res.push_back(parseDoubleArray());
if (eat(']')) {
break;
            }
            expect(',');
        }
return res;
    }

vector<vector<int>> parseIntMatrix(){
vector<vector<int>> res;
        expect('[');
if (eat(']')) {
return res;
        }
while (true) {
            res.push_back(parseIntArray());
if (eat(']')) {
break;
            }
            expect(',');
        }
return res;
    }
};

doublesigmoid(double x){
if (x >= 0) {
double e = exp(-x);
return1.0 / (1.0 + e);
    }
double e = exp(x);
return e / (1.0 + e);
}

vector<double> gauss(vector<vector<double>> a, vector<double> b){
int n = (int)a.size();
for (int col = 0; col < n; ++col) {
int pivot = col;
for (int row = col; row < n; ++row) {
if (fabs(a[row][col]) > fabs(a[pivot][col])) {
                pivot = row;
            }
        }
        swap(a[col], a[pivot]);
        swap(b[col], b[pivot]);

double base = a[col][col];
for (int j = col; j < n; ++j) {
            a[col][j] /= base;
        }
        b[col] /= base;

for (int row = 0; row < n; ++row) {
if (row == col) {
continue;
            }
double fac = a[row][col];
if (fabs(fac) < 1e-12) {
continue;
            }
for (int j = col; j < n; ++j) {
                a[row][j] -= fac * a[col][j];
            }
            b[row] -= fac * b[col];
        }
    }
return b;
}

stringfmt(double x){
double y = round(x * 1e6) / 1e6;
if (fabs(y) < 5e-13) {
        y = 0.0;
    }
ostringstream oss;
    oss << fixed << setprecision(6) << y;
string s = oss.str();
while (!s.empty() && s.back() == '0') {
        s.pop_back();
    }
if (!s.empty() && s.back() == '.') {
        s += '0';
    }
if (s.empty() || s == "-0") {
        s = "0.0";
    }
if (s.find('.') == string::npos) {
        s += ".0";
    }
return s;
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

string line, tmp;
while (getline(cin, tmp)) {
        line += tmp;
    }

Parser ps(line);
vector<vector<double>> nodes;
vector<vector<int>> edges;
vector<int> trainIdx, trainY, testIdx;

    ps.expect('{');
while (true) {
string key = ps.parseString();
        ps.expect(':');
if (key == "nodes") {
            nodes = ps.parseDoubleMatrix();
        } elseif (key == "edges") {
            edges = ps.parseIntMatrix();
        } elseif (key == "train_idx") {
            trainIdx = ps.parseIntArray();
        } elseif (key == "train_y") {
            trainY = ps.parseIntArray();
        } elseif (key == "test_idx") {
            testIdx = ps.parseIntArray();
        }
if (ps.eat('}')) {
break;
        }
        ps.expect(',');
    }

int n = (int)nodes.size();
int d = (int)nodes[0].size();
vector<vector<int>> g(n);
for (auto &e : edges) {
int u = e[0], v = e[1];
        g[u].push_back(v);
        g[v].push_back(u);
    }

vector<vector<double>> h(n, vector<double>(d, 0.0));
for (int i = 0; i < n; ++i) {
int cnt = (int)g[i].size() + 1;
for (int k = 0; k < d; ++k) {
double cur = nodes[i][k];
for (int v : g[i]) {
                cur += nodes[v][k];
            }
            h[i][k] = cur / cnt;
        }
    }

vector<vector<double>> a(d, vector<double>(d, 0.0));
vector<double> b(d, 0.0);
for (int t = 0; t < (int)trainIdx.size(); ++t) {
int idx = trainIdx[t];
int y = trainY[t];
for (int i = 0; i < d; ++i) {
            b[i] += h[idx][i] * y;
for (int j = 0; j < d; ++j) {
                a[i][j] += h[idx][i] * h[idx][j];
            }
        }
    }
for (int i = 0; i < d; ++i) {
        a[i][i] += LAMBDA;
    }

vector<double> w = gauss(a, b);
vector<double> prob;
vector<int> pred;
for (int idx : testIdx) {
double z = 0.0;
for (int i = 0; i < d; ++i) {
            z += h[idx][i] * w[i];
        }
double p = sigmoid(z);
        prob.push_back(p);
        pred.push_back(p >= 0.5 ? 1 : 0);
    }

cout << "{\"weights\":[";
for (int i = 0; i < d; ++i) {
if (i) cout << ',';
cout << fmt(w[i]);
    }
cout << "],\"test_proba\":[";
for (int i = 0; i < (int)prob.size(); ++i) {
if (i) cout << ',';
cout << fmt(prob[i]);
    }
cout << "],\"test_pred\":[";
for (int i = 0; i < (int)pred.size(); ++i) {
if (i) cout << ',';
cout << pred[i];
    }
cout << "]}";
return0;
}
  • >
    Java
import java.io.BufferedInputStream;
import java.io.ByteArrayOutputStream;
import java.io.InputStream;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;

publicclassMain{
staticfinaldouble LAMBDA = 0.01;

staticclassParser{
char[] s;
int p = 0;

        Parser(String str) {
            s = str.toCharArray();
        }

voidskip(){
while (p < s.length && Character.isWhitespace(s[p])) {
                p++;
            }
        }

voidexpect(char c){
            skip();
if (p >= s.length || s[p] != c) {
thrownew RuntimeException("parse error");
            }
            p++;
        }

booleaneat(char c){
            skip();
if (p < s.length && s[p] == c) {
                p++;
returntrue;
            }
returnfalse;
        }

String parseString(){
            skip();
            expect('"');
            StringBuilder sb = new StringBuilder();
while (p < s.length && s[p] != '"') {
                sb.append(s[p++]);
            }
            expect('"');
return sb.toString();
        }

doubleparseNumber(){
            skip();
int st = p;
if (s[p] == '-') {
                p++;
            }
while (p < s.length && Character.isDigit(s[p])) {
                p++;
            }
if (p < s.length && s[p] == '.') {
                p++;
while (p < s.length && Character.isDigit(s[p])) {
                    p++;
                }
            }
return Double.parseDouble(new String(s, st, p - st));
        }

double[] parseDoubleArray() {
            List<Double> list = new ArrayList<>();
            expect('[');
if (eat(']')) {
returnnewdouble[0];
            }
while (true) {
                list.add(parseNumber());
if (eat(']')) {
break;
                }
                expect(',');
            }
double[] arr = newdouble[list.size()];
for (int i = 0; i < arr.length; i++) {
                arr[i] = list.get(i);
            }
return arr;
        }

int[] parseIntArray() {
            List<Integer> list = new ArrayList<>();
            expect('[');
if (eat(']')) {
returnnewint[0];
            }
while (true) {
                list.add((int) Math.round(parseNumber()));
if (eat(']')) {
break;
                }
                expect(',');
            }
int[] arr = newint[list.size()];
for (int i = 0; i < arr.length; i++) {
                arr[i] = list.get(i);
            }
return arr;
        }

double[][] parseDoubleMatrix() {
            List<double[]> list = new ArrayList<>();
            expect('[');
if (eat(']')) {
returnnewdouble[0][];
            }
while (true) {
                list.add(parseDoubleArray());
if (eat(']')) {
break;
                }
                expect(',');
            }
return list.toArray(newdouble[0][]);
        }

int[][] parseIntMatrix() {
            List<int[]> list = new ArrayList<>();
            expect('[');
if (eat(']')) {
returnnewint[0][];
            }
while (true) {
                list.add(parseIntArray());
if (eat(']')) {
break;
                }
                expect(',');
            }
return list.toArray(newint[0][]);
        }
    }

staticdoublesigmoid(double x){
if (x >= 0) {
double e = Math.exp(-x);
return1.0 / (1.0 + e);
        }
double e = Math.exp(x);
return e / (1.0 + e);
    }

staticdouble[] gauss(double[][] a, double[] b) {
int n = a.length;
for (int col = 0; col < n; col++) {
int pivot = col;
for (int row = col; row < n; row++) {
if (Math.abs(a[row][col]) > Math.abs(a[pivot][col])) {
                    pivot = row;
                }
            }
double[] tmpRow = a[col];
            a[col] = a[pivot];
            a[pivot] = tmpRow;
double tmp = b[col];
            b[col] = b[pivot];
            b[pivot] = tmp;

double base = a[col][col];
for (int j = col; j < n; j++) {
                a[col][j] /= base;
            }
            b[col] /= base;

for (int row = 0; row < n; row++) {
if (row == col) {
continue;
                }
double fac = a[row][col];
if (Math.abs(fac) < 1e-12) {
continue;
                }
for (int j = col; j < n; j++) {
                    a[row][j] -= fac * a[col][j];
                }
                b[row] -= fac * b[col];
            }
        }
return b;
    }

static String fmt(double x){
double y = Math.round(x * 1_000_000.0) / 1_000_000.0;
if (Math.abs(y) < 5e-13) {
            y = 0.0;
        }
        BigDecimal bd = BigDecimal.valueOf(y).setScale(6, RoundingMode.HALF_UP).stripTrailingZeros();
        String s = bd.toPlainString();
if (s.equals("-0")) {
return"0.0";
        }
if (!s.contains(".") && !s.contains("E")) {
            s += ".0";
        }
return s;
    }

publicstaticvoidmain(String[] args)throws Exception {
        String text = readAll(System.in);
        Parser ps = new Parser(text);
double[][] nodes = null;
int[][] edges = null;
int[] trainIdx = null, trainY = null, testIdx = null;

        ps.expect('{');
while (true) {
            String key = ps.parseString();
            ps.expect(':');
switch (key) {
case"nodes":
                    nodes = ps.parseDoubleMatrix();
break;
case"edges":
                    edges = ps.parseIntMatrix();
break;
case"train_idx":
                    trainIdx = ps.parseIntArray();
break;
case"train_y":
                    trainY = ps.parseIntArray();
break;
case"test_idx":
                    testIdx = ps.parseIntArray();
break;
default:
thrownew RuntimeException("unknown key");
            }
if (ps.eat('}')) {
break;
            }
            ps.expect(',');
        }

int n = nodes.length;
int d = nodes[0].length;
        List<Integer>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }

double[][] h = newdouble[n][d];
for (int i = 0; i < n; i++) {
int cnt = g[i].size() + 1;
for (int k = 0; k < d; k++) {
double cur = nodes[i][k];
for (int v : g[i]) {
                    cur += nodes[v][k];
                }
                h[i][k] = cur / cnt;
            }
        }

double[][] a = newdouble[d][d];
double[] b = newdouble[d];
for (int t = 0; t < trainIdx.length; t++) {
int idx = trainIdx[t];
int y = trainY[t];
for (int i = 0; i < d; i++) {
                b[i] += h[idx][i] * y;
for (int j = 0; j < d; j++) {
                    a[i][j] += h[idx][i] * h[idx][j];
                }
            }
        }
for (int i = 0; i < d; i++) {
            a[i][i] += LAMBDA;
        }

double[] w = gauss(a, b);
        StringBuilder sb = new StringBuilder();
        sb.append("{\"weights\":[");
for (int i = 0; i < d; i++) {
if (i > 0) {
                sb.append(',');
            }
            sb.append(fmt(w[i]));
        }
        sb.append("],\"test_proba\":[");

int[] pred = newint[testIdx.length];
double[] prob = newdouble[testIdx.length];
for (int t = 0; t < testIdx.length; t++) {
int idx = testIdx[t];
double z = 0.0;
for (int i = 0; i < d; i++) {
                z += h[idx][i] * w[i];
            }
            prob[t] = sigmoid(z);
            pred[t] = prob[t] >= 0.5 ? 1 : 0;
if (t > 0) {
                sb.append(',');
            }
            sb.append(fmt(prob[t]));
        }
        sb.append("],\"test_pred\":[");
for (int i = 0; i < pred.length; i++) {
if (i > 0) {
                sb.append(',');
            }
            sb.append(pred[i]);
        }
        sb.append("]}");
        System.out.print(sb);
    }

static String readAll(InputStream in)throws Exception {
        BufferedInputStream bis = new BufferedInputStream(in);
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
byte[] buf = newbyte[1 << 15];
int len;
while ((len = bis.read(buf)) != -1) {
            bos.write(buf, 0, len);
        }
return bos.toString(StandardCharsets.UTF_8);
    }
}

3. 裁边后的最小片段

问题描述

LYA 手里有一个长度为  的小写字母字符串 。

现在允许从字符串的两端合计删掉恰好  个字符。也就是说，可以先从左边删掉  个字符，再从右边删掉  个字符，其中：

最后得到的字符串长度固定为 。

请在所有可能得到的结果中，找出字典序最小的那个字符串。

输入格式

每个测试文件均包含多组测试数据。

第一行输入一个整数 ，表示数据组数。

对于每组数据：

  • >
    第一行输入两个整数 ；
  • >
    第二行输入一个长度为  的字符串 ，只包含小写字母。

输出格式

对于每组测试数据，输出一行一个字符串，表示所有可能结果中字典序最小的那个。

样例输入

3
5 2
cbada
4 0
baca
6 3
zzxyyx

样例输出

ada
baca
xyy

数据范围

  • >
  • >
  • >
  • >
    所有测试数据中， 的总和不超过 

题解

这题最容易误判成“删掉任意  个字符后求最小子序列”，但实际上不是。

因为题目要求只能从两端删除，所以最后留下来的部分一定是一个连续子串。

设保留下来的长度是：

如果从左边删掉  个字符，那么最终保留下来的就是：

其中  的取值范围正好是 。

所以问题被转化成了：

在所有起点属于  的长度为  的子串中，找出字典序最小的那个。

#直接比较为什么不行

候选子串一共有  个。

如果直接把每两个候选子串按字符一位一位比较，最坏会退化到平方级，显然撑不住总长度  的数据范围。

#用哈希比较两个候选子串

设当前最优起点是 best，现在要和新起点 i 对应的子串比较。

两个候选串长度都等于 ，只需要找到它们的最长公共前缀长度 lcp：

  • >
    如果 lcp = L，说明两个子串完全相同；
  • >
    否则比较下一位字符，较小的那个子串字典序更小。

为了快速得到 lcp，可以对原串做双模多项式哈希，然后二分 lcp。

这样比较两个候选子串的代价就是 。

把所有起点  扫一遍，总复杂度为：

在本题范围内是可以通过的。

#复杂度分析

设当前测试用例字符串长度为 ，保留长度为 。

  • >
    预处理哈希数组的复杂度是 ；
  • >
    枚举所有候选起点并二分比较，复杂度是 。

因此单组复杂度是 ，空间复杂度是 。

参考代码

  • >
    Python
import sys

input = lambda: sys.stdin.readline().strip()

MOD1 = 1_000_000_007
MOD2 = 1_000_000_009
BASE = 911_382_323


defsolve_one(n: int, k: int, s: str) -> str:
if k == 0:
return s

    keep = n - k
    a = [ord(ch) - 96for ch in s]

    p1 = [1] * (n + 1)
    p2 = [1] * (n + 1)
    h1 = [0] * (n + 1)
    h2 = [0] * (n + 1)

for i, x in enumerate(a, 1):
        p1[i] = p1[i - 1] * BASE % MOD1
        p2[i] = p2[i - 1] * BASE % MOD2
        h1[i] = (h1[i - 1] * BASE + x) % MOD1
        h2[i] = (h2[i - 1] * BASE + x) % MOD2

defget_hash(l: int, r: int):
        x1 = (h1[r] - h1[l] * p1[r - l]) % MOD1
        x2 = (h2[r] - h2[l] * p2[r - l]) % MOD2
return x1, x2

    best = 0
for i in range(1, k + 1):
        lo, hi = 0, keep
while lo < hi:
            mid = (lo + hi + 1) >> 1
if get_hash(best, best + mid) == get_hash(i, i + mid):
                lo = mid
else:
                hi = mid - 1
        lcp = lo
if lcp == keep:
continue
if s[i + lcp] < s[best + lcp]:
            best = i

return s[best:best + keep]


defsolve() -> None:
    t = int(input())
    out = []
for _ in range(t):
        n, k = map(int, input().split())
        s = input()
        out.append(solve_one(n, k, s))
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<bits/stdc++.h>
usingnamespacestd;

constlonglong MOD1 = 1000000007LL;
constlonglong MOD2 = 1000000009LL;
constlonglong BASE = 911382323LL;

stringsolveOne(int n, int k, conststring& s){
if (k == 0) {
return s;
    }

int keep = n - k;
vector<longlong> p1(n + 1, 1), p2(n + 1, 1);
vector<longlong> h1(n + 1, 0), h2(n + 1, 0);

for (int i = 1; i <= n; ++i) {
int x = s[i - 1] - 'a' + 1;
        p1[i] = p1[i - 1] * BASE % MOD1;
        p2[i] = p2[i - 1] * BASE % MOD2;
        h1[i] = (h1[i - 1] * BASE + x) % MOD1;
        h2[i] = (h2[i - 1] * BASE + x) % MOD2;
    }

auto getHash = [&](int l, int r) {
longlong x1 = (h1[r] - h1[l] * p1[r - l]) % MOD1;
longlong x2 = (h2[r] - h2[l] * p2[r - l]) % MOD2;
if (x1 < 0) x1 += MOD1;
if (x2 < 0) x2 += MOD2;
return pair<longlong, longlong>(x1, x2);
    };

int best = 0;
for (int i = 1; i <= k; ++i) {
int lo = 0, hi = keep;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (getHash(best, best + mid) == getHash(i, i + mid)) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
int lcp = lo;
if (lcp == keep) {
continue;
        }
if (s[i + lcp] < s[best + lcp]) {
            best = i;
        }
    }

return s.substr(best, keep);
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
int n, k;
string s;
cin >> n >> k >> s;
cout << solveOne(n, k, s) << '\n';
    }
return0;
}
  • >
    Java
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;

publicclassMain{
staticfinallong MOD1 = 1_000_000_007L;
staticfinallong MOD2 = 1_000_000_009L;
staticfinallong BASE = 911_382_323L;

static String solveOne(int n, int k, String s){
if (k == 0) {
return s;
        }

int keep = n - k;
long[] p1 = newlong[n + 1];
long[] p2 = newlong[n + 1];
long[] h1 = newlong[n + 1];
long[] h2 = newlong[n + 1];
        p1[0] = 1;
        p2[0] = 1;

for (int i = 1; i <= n; i++) {
int x = s.charAt(i - 1) - 'a' + 1;
            p1[i] = p1[i - 1] * BASE % MOD1;
            p2[i] = p2[i - 1] * BASE % MOD2;
            h1[i] = (h1[i - 1] * BASE + x) % MOD1;
            h2[i] = (h2[i - 1] * BASE + x) % MOD2;
        }

int best = 0;
for (int i = 1; i <= k; i++) {
int lo = 0, hi = keep;
while (lo < hi) {
int mid = (lo + hi + 1) >>> 1;
if (same(best, i, mid, h1, h2, p1, p2)) {
                    lo = mid;
                } else {
                    hi = mid - 1;
                }
            }
int lcp = lo;
if (lcp == keep) {
continue;
            }
if (s.charAt(i + lcp) < s.charAt(best + lcp)) {
                best = i;
            }
        }
return s.substring(best, best + keep);
    }

staticbooleansame(int a, int b, int len, long[] h1, long[] h2, long[] p1, long[] p2){
long x1 = (h1[a + len] - h1[a] * p1[len]) % MOD1;
long y1 = (h1[b + len] - h1[b] * p1[len]) % MOD1;
long x2 = (h2[a + len] - h2[a] * p2[len]) % MOD2;
long y2 = (h2[b + len] - h2[b] * p2[len]) % MOD2;
if (x1 < 0) x1 += MOD1;
if (y1 < 0) y1 += MOD1;
if (x2 < 0) x2 += MOD2;
if (y2 < 0) y2 += MOD2;
return x1 == y1 && x2 == y2;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);
int t = fs.nextInt();
        StringBuilder sb = new StringBuilder();
for (int cs = 0; cs < t; cs++) {
int n = fs.nextInt();
int k = fs.nextInt();
            String s = fs.next();
            sb.append(solveOne(n, k, s)).append('\n');
        }
        System.out.print(sb);
    }

staticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = new BufferedInputStream(is);
        }

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

String next()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);
            StringBuilder sb = new StringBuilder();
while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
return sb.toString();
        }

intnextInt()throws IOException {
return Integer.parseInt(next());
        }
    }
}

✨ 写在最后：

网站最近上线了八股和选额的功能啦。

最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。

3月15日蚂蚁算法岗真题解析 第2张
3月15日蚂蚁算法岗真题解析 第3张
3月15日蚂蚁算法岗真题解析 第4张
3月15日蚂蚁算法岗真题解析 第5张

文章来源： 四季读书网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！

上一个中考物理冲刺技巧

下一个吹响冲锋号,共筑青春梦——910蛟龙班中考百日誓师主题班会纪实

相关文章

抱歉，评论功能暂时关闭!