阿里笔试 阿里笔试题 0426
笔试时间：2025年04月26日
历史笔试传送门：
第一题
题目
电影院共有 n 行，m 列座位。部分座位已被陌生人提前购买，剩余座位为空闲。你和你的 k 位朋友希望一起观影，选座时有以下要求：只能选择空闲座位；全部 k 个人的选座需要位于同一行，且保持连续；对于选中的每一个位置，其上下左右相邻的位置要么不存在，要么为空闲，要么同样为你们选中的位置。现在，给出电影院的座位示意图，以及多次询问，每次询问给出 k 个整数，表示你们希望一起观影的人数，请计算对于每次询问，有多少种不同的选座方案满足上述要求。两个方案不同当且仅当至少有一个人与之前的位置不同。若不存在任何合法方案，输出 0。由于答案可能很大，请将答案对 998244353 取模后输出
输入描述
第一行输入三个整数n,m,q（1 ≤ n,m,q ≤ 100），表示电影院座位的行数、列数、询问次数。
此后 n 行，每行输入 m 个整数aᵢⱼ（0 ≤ aᵢⱼ ≤ 1），其中aᵢⱼ表示电影院第 i 行第 j 列的座位状态，aᵢⱼ = 0表示空闲，aᵢⱼ = 1 表示已被购买。
第 n + 2 行输入 q 个整数 k₁,k₂, …, k_q（1 ≤ kᵢ ≤ n × m），表示每次询问中，你们希望一起观影的人数。
输出描述
对于每次询问，在一行上连续的输出一个整数，表示不同的选座方案数。由于答案可能很大，请将答案对 998244353 取模后输出。
样例输入
1 3 4
0 0 0
0 1 2 3
样例输出
0 3 4 6
参考题解
标记“可用”座位: 我们需要先标记哪些空闲座位是有效的。有效座位是那些不仅是空闲座位，而且其上下左右相邻的座位要么不存在，要么也是空闲的。滑动窗口: 对于每个询问的 k，我们需要在每一行中找到满足条件的连续 k个座位。这可以通过滑动窗口技术来实现。我们检查每一行中的所有可能的连续子数组，并判断它们是否满足条件。预处理阶乘: 对于每个询问，我们还需要对每种 k计算结果时，将结果乘上 k!。为了高效地计算阶乘，我们可以预处理阶乘值。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
usingnamespacestd;
staticconstint MOD = 998244353;
int add(int a,int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
int mul(long long a,long long b){ returnint(a*b%MOD); }
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,q;
cin>>n>>m>>q;
vector<vector<int>> a(n, vector<int>(m));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
// 标记“可用”座位
vector<vector<char>> good(n, vector<char>(m, 0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]==0){
bool ok = true;
if(i>0 && a[i-1][j]==1) ok = false;
if(i+1<n && a[i+1][j]==1) ok = false;
if(ok) good[i][j]=1;
}
}
}
// 读入所有 k，找出最大值用于预处理阶乘
vector<int> ks(q);
int Kmax = 0;
for(int i=0;i<q;i++){
cin>>ks[i];
Kmax = max(Kmax, ks[i]);
}
// 阶乘预处理到 Kmax
vector<int> fact(Kmax+1,1);
for(int i=1;i<=Kmax;i++){
fact[i] = mul(fact[i-1], i);
}
// 对每个不同的 k 只算一次
unordered_map<int,int> ansk;
ansk.reserve(q*2);
for(int k: ks){
if(ansk.count(k)) continue;
if(k<=0 || k>m){
ansk[k]=0;
continue;
}
longlong windows = 0;
for(int i=0;i<n;i++){
// 在第 i 行滑窗
for(int j=0;j+k<=m;j++){
// 检查 [j..j+k-1] 全部 good
bool ok = true;
for(int p=j;p<j+k;p++){
if(!good[i][p]){
ok=false; break;
}
}
if(!ok) continue;
// 检查左右邻接
if(j>0 && a[i][j-1]==1) continue;
if(j+k<m && a[i][j+k]==1) continue;
windows++;
}
}
// 乘上 k! 并取模
ansk[k] = mul(windows % MOD, fact[k]);
}
// 按输入顺序输出
for(int i=0;i<q;i++){
if(i) cout<<' ';
cout<<ansk[ks[i]];
}
cout<<"\n";
return0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
static final int MOD = 998244353;
static int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
static int mul(long a, long b) {
return (int) (a * b % MOD);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int q = scanner.nextInt();
int[][] a = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = scanner.nextInt();
}
}
boolean[][] good = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 0) {
boolean ok = true;
if (i > 0 && a[i - 1][j] == 1) ok = false;
if (i + 1 < n && a[i + 1][j] == 1) ok = false;
good[i][j] = ok;
}
}
}
int[] ks = new int[q];
int Kmax = 0;
for (int i = 0; i < q; i++) {
ks[i] = scanner.nextInt();
Kmax = Math.max(Kmax, ks[i]);
}
int[] fact = new int[Kmax + 1];
fact[0] = 1;
for (int i = 1; i <= Kmax; i++) {
fact[i] = mul(fact[i - 1], i);
}
Map<Integer, Integer> ansk = new HashMap<>();
for (int k : ks) {
if (ansk.containsKey(k)) continue;
if (k <= 0 || k > m) {
ansk.put(k, 0);
continue;
}
long windows = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j + k <= m; j++) {
boolean ok = true;
for (int p = j; p < j + k; p++) {
if (!good[i][p]) {
ok = false;
break;
}
}
if (!ok) continue;
if (j > 0 && a[i][j - 1] == 1) continue;
if (j + k < m && a[i][j + k] == 1) continue;
windows++;
}
}
ansk.put(k, mul((int) (windows % MOD), fact[k]));
}
for (int i = 0; i < q; i++) {
if (i > 0) System.out.print(' ');
System.out.print(ansk.get(ks[i]));
}
System.out.println();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
MOD = 998244353
def add(a, b):
a += b
if a >= MOD:
a -= MOD
return a
def mul(a, b):
return (a * b) % MOD
n, m, q = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
good = [[False for _ in range(m)] for __ in range(n)]
for i in range(n):
for j in range(m):
if a[i][j] == 0:
ok = True
if i > 0 and a[i-1][j] == 1:
ok = False
if i+1 < n and a[i+1][j] == 1:
ok = False
good[i][j] = ok
ks = list(map(int, input().split()))
Kmax = max(ks) if ks else 0
fact = [1] * (Kmax + 1)
for i in range(1, Kmax + 1):
fact[i] = mul(fact[i-1], i)
ansk = {}
for k in ks:
if k in ansk:
continue
if k <= 0 or k > m:
ansk[k] = 0
continue
windows = 0
for i in range(n):
for j in range(m - k + 1):
ok = True
for p in range(j, j + k):
if not good[i][p]:
ok = False
break
if not ok
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
投递京东等公司10个岗位