2024-09-03发表2024-09-10更新牛客 / 刷题11 分钟读完 (大约1638个字)

牛客刷题-2

1.小美的平衡矩阵

1.

小美的平衡矩阵

小美拿到了一个

n*n

的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个

i*i

的完美矩形区域。你需要回答

1\leq i \leq n

的所有答案。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入一个正整数，代表矩阵大小。
接下来的行，每行输入一个长度为的 01 串，用来表示矩阵。

输出描述：

输出行，第行输出的完美矩形区域的数量。

示例1

输入例子：

输出例子：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> preSum(n, vector<int>(n+1));
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++) {
            preSum[i][j+1] = preSum[i][j] + (s[j] - '0');
        }
    }
    for(int window = 1; window <= n; window++) {
        if(window & 1) {
            cout << "0\n";
            continue;
        }
        int perfect = 0;
        for(int j = 0; j <= n - window; j++) {
            int sum = 0;
            for(int i = 0; i < window; i++) {
                sum += preSum[i][window + j] - preSum[i][j];
            }
            if(sum * 2 == window * window) {
                perfect++;
            }
            for(int i = window; i < n; i++) {
                sum -= preSum[i - window][window + j] - preSum[i - window][j];
                sum += preSum[i][window + j] - preSum[i][j];
                if(sum * 2 == window * window) {
                    perfect++;
                }
            }
        }
        cout << perfect << "\n";
    }
}

2.小美的数组询问

2.

小美的数组询问

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间

[l,r]

范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？
共有

q

次询问。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入两个正整数，代表数组大小和询问次数。
第二行输入个整数，其中如果输入的为 0，那么说明是未知的。
接下来的行，每行输入两个正整数，代表一次询问。

输出描述：

输出行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

示例1

输入例子：

输出例子：

5 6
8 8

例子说明：

只有第二个元素是未知的。
第一次询问，数组最小的和是 1+1+3=5，最大的和是 1+2+3=6。
第二次询问，显然数组的元素和必然为 8。

#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    long long sum = 0;
    long long zeroCnt = 0;
    for(int i = 0; i < n; i++) {
        int ai;
        cin >> ai;
        zeroCnt += (ai == 0 ? 1 : 0);
        sum += ai;
    }
    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << sum + zeroCnt*l << " " << sum + zeroCnt*r << "\n";
    }
}

2024-03-27发表2024-04-23更新牛客 / 刷题25 分钟读完 (大约3755个字)

牛客刷题-1

小米2019秋招安卓开发笔试题（B）

21. 最少立方数之和

给出一个数字N（0<N<1000000）,将N写成立方数和的形式，求出需要的最少立方数个数。
例如N=17，1+8+8 = 17，最少需要3个立方数，则输出3。
N= 28,1+1+1+1+8+8+8=28, 需要7个立方数，1+27=28,需要2个立方数，所以最少立方数为2，则输出2。

import java.util.*;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static final List<Integer> cubs;
    private static final int cubNum;
    static {
        cubs = new ArrayList<Integer>();
        for(int i = 1; i*i*i <= 1000000; i++) {
            cubs.add(i*i*i);
        }
        cubNum = cubs.size();
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int index = Collections.binarySearch(cubs, n);
            if(index < 0) {
                index = -index - 2;
            }
            if(index < 0) {
                throw new RuntimeException("unreachable");
            }
            int[] dp = new int[n+1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            for(int j = 1; j <= index+1; j++) {
                for(int i = cubs.get(j-1); i <= n; i++) {
                    dp[i] = Math.min(dp[i], dp[i - cubs.get(j-1)] + 1);
                }
            }
            System.out.println(dp[n]);
        }
    }
}

完全背包，从所有立方数里选数，取数目最小的情况

资产包打包