淘天笔试 淘天笔试题 0507
笔试时间：2025年5月7日
往年笔试合集：
第一题
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
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
