笔试时间：2025年5月7日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

Tk有一个长度为n的数组 {a1, a2, ..., an}，他希望将数组分割为 {a1, a2, ..., ax} 和 {ax+1, ax+2, ..., an} 两个部分（显然，x需要满足≤ x < n），使得下式的答案达到最大： ∑(i = 1到x) ∑(j = x + 1到n) ai × aj 你并不需要告诉他具体分割位置，只需要告诉他最终结果即可。由于答案可能很大，请将答案对998244353取模后输出。

输入描述

第一行输入一个正整数n (2 ≤ n ≤ 2 × 10^5) 表示数组大小。

第二行输入n个整数a1, a2, ..., an (1 ≤ ai ≤ 10^4) 代表数组中的元素。

输出描述

输出一个值表示上式的最大值。由于答案可能很大，请将答案对998244353取模后输出。

样例输入

5

3 2 4 1 5

样例输出

54

解释： 分割最终区间为 [1, 3], [4, 5] 可以得到最大值54

参考题解

先用一次遍历算出全数组元素和 T = ∑ a[i]。 再维护一个前缀和 S=∑_{i=1}^x a[i]，那么后缀和就是 T−S。 每向右移动一个分割点 x，更新 S，计算当前交叉乘积和 S*(T−S)，在所有 x 中取最大值。 最后对 998244353 取模输出即可。

C++：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

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

    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    ll t = 0;
    for(ll x : a) t += x;

    ll s = 0, b = 0;
    for(int i = 0; i + 1 < n; i++){
        s += a[i];
        ll v = s * (t - s);
        if (v > b) b = v;
    }

    cout << (b % MOD) << "\n";
    return 0;
}

Java：

// Java 版本
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static final long MOD = 998244353L;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }
        
        long t = 0;
        for (long x : a) {
            t += x;
        }
        
        long s = 0, b = 0;
        for (int i = 0; i + 1 < n; i++) {
            s += a[i];
            long v = s * (t - s);
            if (v > b) {
                b = v;
            }
        }
        
        System.out.println(b % MOD);
    }
}

Python：

# Python 版本
import sys
input = sys.stdin.readline

MOD = 998244353

def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    t = sum(a)
    
    s = 0
    b = 0
    for i in range(n - 1):
        s += a[i]
        v = s * (t - s)
        if v > b:
            b = v
    
    print(b % MOD)

if __name__ == "__main__":
    main()

第二题

小红有a个1×1和b个2×2的正方形，她想知道能不能刚好用这a + b个拼成一个大正方形，使得这个正方形的每个位置都属于其中一块小正方形，且大正方形的每个位置不存在小正方形的重叠。

输入描述

第一行一个整数T(1 ≤ T ≤ 100)，表示数据组数。

接下来T行，每行两个整数a, b(1 ≤ a, b ≤ 10^9)，表示两种小正方形的个数。

输出描述

输出共T行，每行一个字符串，若能拼成大正方形输出"YES"，否则输出"NO"。

样例输入

2

5 1

1 2

样例输出

YES

NO

参考题解

大正方形的面积必然是 A = a·1 + b·4。要拼出一个边长为 L 的正方形，必须有 L^2 = A。 先检查 A 是否为完全平方数 L^2； 再检查在这样边长的正方形内部，能否用恰好 b 个 2×2 方块填满所有“2×2”格子——也就是看 b == (L/2)^2（当且仅当 L 为偶数时才可能）。 两个条件同时满足则输出 “YES”，否则 “NO”。

C++：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int T;
    cin >> T;
    while(T--){
        ll a, b;
        cin >> a >> b;
        ll tot = a + 4LL * b;

        ll s = floor(sqrt((long double)tot));
        while ((s+1)*(s+1) <= tot) s++;
        while (s*s > tot) s--;
        if (s*s != tot || b != (s/2)*(s/2)) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
    return 0;
}

Java：

// Java 版本

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            long tot = a + 4L * b;

            // 计算向下取整的平方根
            long s = (l