饿了么笔试饿了么秋招 0919

笔试时间：2025年9月19日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：有趣的数字

TK的朋友给了他一个长度为n、仅由1和2构成的数组A，TK对这个数组很感兴趣，他将对数组进行m次操作。每次操作给出三个整数x、y、z，含义如下：

先将A[x]修改为y（其中y∈{1,2}）；
修改之后，TK想知道是否可以将整个数组划分为恰好z个连续且非空的段，使得这z段的乘积均相同。

对于每次操作，请输出结果：若可以，输出Yes；否则输出No。

注意：每次修改会影响数组的当前状态，并用于后续操作。

【名词解释】划分z段：选择z-1个切分点，将数组分成z个连续且非空的段，覆盖整个数组且两两不交。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数T（1≤T≤5）代表数据组数，每组测试数据描述如下：

第一行输入两个整数n、m，分别表示数组长度与操作次数；
第二行输入n个整数A[1],A[2],...,A[n]；
接下来m行，每行输入三个整数x、y、z（1≤x≤n，y∈{1,2}，1≤z≤n）表示一次操作。

除此之外，保证单个测试文件的∑n之和、∑m之和均不超过2×10^5。

输出描述

对于每组测试数据，输出m行，对每次操作，若可以完成所需划分，输出Yes；否则输出No。

样例输入

2

4 4

1 2 1 2

2 1 2

1 1 1

2 2 2

4 2 3

3 3

1 1 1

2 1 2

1 2 2

3 2 1

样例输出

Yes

No

Yes

No

Yes

No

Yes

样例说明

对于第一组数据，初始数组为[1,2,1,2]。

第一次操作后数组变为[1,1,1,2]，可以分割为[1,1]和[1,2]，满足条件输出Yes。
第二次操作后数组为[1,1,1,2]，无法分割为两个乘积相同子段。

参考题解

解题思路：

题目问数组能不能划分成z段乘积相同，其实乘积只和2的个数有关系。进一步说，2的个数是z的倍数时，一定能划分。那么只需要统计每次操作后2的个数即可。

C++：

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        
        int cnt2 = 0;
        for (int x : a) {
            if (x == 2) {
                cnt2++;
            }
        }
        
        while (m--) {
            int x, y, z;
            cin >> x >> y >> z;
            x--;
            if (a[x] == 2) cnt2--;
            a[x] = y;
            if (y == 2) cnt2++;
            
            if (cnt2 % z == 0) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] a = new int[n];
            
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            
            int cnt2 = 0;
            for (int x : a) {
                if (x == 2) {
                    cnt2++;
                }
            }
            
            while (m-- > 0) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int z = sc.nextInt();
                x--;
                
                if (a[x] == 2) cnt2--;
                a[x] = y;
                if (y == 2) cnt2++;
                
                if (cnt2 % z == 0) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
            }
        }
    }
}

Python：

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    
    cnt2 = sum(1 for x in a if x == 2)
    
    for _ in range(m):
        x, y, z = map(int, input().split())
        x -= 1
        
        if a[x] == 2:
            cnt2 -= 1
        a[x] = y
        if y == 2:
            cnt2 += 1
        
        if cnt2 % z == 0:
            print("Yes")
        else:
            print("No")