OD题库
2026/4/9大约 21 分钟
OD题库
题库表
1.斗地主之顺子(双指针)
题目描述
在斗地主只扑克牌游戏中，扑克牌由小到大的顺序为:3.4,5.6,7.8,9,10.J,Q.K.A.2，玩家可以出的扑克牌阵型有:单张、对子、顺子、飞机、炸弹等。
其中顺子的出牌规则为:由至少5张由小到大连续递增的 扑克牌只 组成，且不能包含2。例如:(3.4,5,6,7}、(3.4,5,6,7,8,9,10,J,Q,K,A}都是有效的顺子;而{,Q,K,A,2}、(2,3,4,5,6}、(3,4,5,6}、(3,4,5.6,8)等都不是顺子给定一个包含 13 张牌的数组，如果有满足出牌规则的顺子，请输出顺子。
如果存在多个顺子，请每行输出一个顺子，且需要按顺子的第一张牌的大小(必须从小到大)依次输出。
如果没有满足出牌规则的顺子，请输出NO。
输入描述：
13张任意顺序的扑克牌，每张扑克牌数字用空格隔开，每张扑克牌的数字都是合法的，并且不包括大小王:2 9 J 2 3 4 K A 7 9 A 5 6不需要考虑输入为异常字符的情况
输出描述：
组成的顺子，每张扑克牌数字用空格隔开:3 4 5 6 7示例1
输入
2 9 J 2 3 4 K A 7 9 A 5 6
输出
3 4 5 6 7
说明
13张牌中，可以组成的顺子只有1组:3 4 5 6 7.
示例2
输入
2 9 J 10 3 4 K A 7 Q A 5 6
输出
3 4 5 6 7
9 10 J Q K A说明
13张牌中，可以组成2组顺子，从小到大分别为:3 4 5 6 7和9 10 J Q K A
示例3
输入
2 9 9 9 3 4 K A 10 Q A 5 6
输出
No
说明
13张牌中，无法组成顺子。
题目分析：
- 扑克牌按从小到大的顺序排列为：3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A。牌 2 不能用于顺子。
- 顺子的规则是：至少由5张连续递增的牌组成，例如 (3, 4, 5, 6, 7)。
- 需要找出所有可能的顺子组合，每个顺子中的牌不能重复使用。
解题思路
1、输入准备:
- 从输入中读取13张扑克牌，存储在一个列表或数组中。
2、数据转换:
- 将扑克牌的字符表示（如 "J", "Q", "K", "A"）转换为对应的数字值，以便于排序和比较。
- 排除不能用于顺子的牌 2。
3、排序:
- 对转换后的牌进行排序，以便更容易查找连续递增的序列。
4、查找顺子:
- 初始化数据结构：创建一个布尔数组（或列表）used，初始化为false，- 用于跟踪每张牌是否已经被用作某个顺子的一部分。
- 遍历牌序列：使用两层循环：
- 外层循环从每一张未使用的牌作为起点开始。
- 内层循环尝试构建一个顺子：
- 如果下一张牌与当前顺子的最后一张牌连续且未被使用，添加到当前顺子中并标记为已使用。
- 如果不连续或已被使用，终止当前顺子的构建。
- 验证顺子长度：检查构建的顺子是否至少包含5张牌：
- 如果是，将该顺子保存起来。
- 如果不是，重置used数组中与当前顺子相关的牌的标记，使它们可以用于后续的顺子构建。
5、输出结果:
- 如果找到一个或多个顺子，按顺序输出它们。
- 如果没有找到任何顺子，输出 "NO"。
代码
*C++源代码：*
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
// 将扑克牌转换为对应的数字值
int cardValue(const string &card) {
if (card == "3") return 3;
if (card == "4") return 4;
if (card == "5") return 5;
if (card == "6") return 6;
if (card == "7") return 7;
if (card == "8") return 8;
if (card == "9") return 9;
if (card == "10") return 10;
if (card == "J") return 11;
if (card == "Q") return 12;
if (card == "K") return 13;
if (card == "A") return 14;
return 0; // 忽略 '2'
}
int main() {
vector<string> cards(13);
for (int i = 0; i < 13; ++i) {
cin >> cards[i];
}
// 转换并排序卡片，排除 '2'
vector<int> cardNumbers;
for (const auto &card : cards) {
int value = cardValue(card);
if (value != 0) { // 跳过 '2'
cardNumbers.push_back(value);
}
}
sort(cardNumbers.begin(), cardNumbers.end());
vector<vector<int>> sequences;
vector<bool> used(cardNumbers.size(), false); // 记录每张牌是否已被使用
// 查找所有可能的顺子
for (int i = 0; i < cardNumbers.size(); ++i) {
if (used[i]) continue; // 已使用的牌跳过
vector<int> currentSequence;
currentSequence.push_back(cardNumbers[i]);
used[i] = true; // 标记当前牌已使用
for (int j = i + 1; j < cardNumbers.size(); ++j) {
if (used[j]) continue; // 跳过已使用的牌
if (cardNumbers[j] == currentSequence.back() + 1) {
currentSequence.push_back(cardNumbers[j]);
used[j] = true; // 标记当前牌已使用
} else if (cardNumbers[j] > currentSequence.back() + 1) {
break; // 不再连续，结束当前顺子的查找
}
}
if (currentSequence.size() >= 5) {
sequences.push_back(currentSequence);
} else {
// 如果当前顺子不满足要求，重置已使用标记
for (int k = 0; k < currentSequence.size(); ++k) {
auto it = find(cardNumbers.begin(), cardNumbers.end(), currentSequence[k]);
if (it != cardNumbers.end()) {
used[it - cardNumbers.begin()] = false;
}
}
}
}
// 输出结果
if (sequences.empty()) {
cout << "No" << endl;
} else {
for (const auto &seq : sequences) {
for (int i = 0; i < seq.size(); ++i) {
if (i > 0) cout << " ";
cout << (seq[i] > 10 ? (seq[i] == 11 ? "J" : seq[i] == 12 ? "Q" : seq[i] == 13 ? "K" : "A") : to_string(seq[i]));
}
cout << endl;
}
}
return 0;
}JAVA源代码：
import java.util.*;
public class Main {
// 将扑克牌转换为对应的数字值
private static int cardValue(String card) {
switch (card) {
case "3": return 3;
case "4": return 4;
case "5": return 5;
case "6": return 6;
case "7": return 7;
case "8": return 8;
case "9": return 9;
case "10": return 10;
case "J": return 11;
case "Q": return 12;
case "K": return 13;
case "A": return 14;
default: return 0; // 忽略 '2'
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] inputCards = new String[13];
for (int i = 0; i < 13; i++) {
inputCards[i] = scanner.next();
}
scanner.close();
// 转换并排序卡片，排除 '2'
List<Integer> cardNumbers = new ArrayList<>();
for (String card : inputCards) {
int value = cardValue(card);
if (value != 0) { // 跳过 '2'
cardNumbers.add(value);
}
}
Collections.sort(cardNumbers);
List<List<Integer>> sequences = new ArrayList<>();
boolean[] used = new boolean[cardNumbers.size()]; // 记录每张牌是否已被使用
// 查找所有可能的顺子
for (int i = 0; i < cardNumbers.size(); i++) {
if (used[i]) continue; // 已使用的牌跳过
List<Integer> currentSequence = new ArrayList<>();
currentSequence.add(cardNumbers.get(i));
used[i] = true; // 标记当前牌已使用
for (int j = i + 1; j < cardNumbers.size(); j++) {
if (used[j]) continue; // 跳过已使用的牌
if (cardNumbers.get(j) == currentSequence.get(currentSequence.size() - 1) + 1) {
currentSequence.add(cardNumbers.get(j));
used[j] = true; // 标记当前牌已使用
} else if (cardNumbers.get(j) > currentSequence.get(currentSequence.size() - 1) + 1) {
break; // 不再连续，结束当前顺子的查找
}
}
if (currentSequence.size() >= 5) {
sequences.add(new ArrayList<>(currentSequence));
} else {
// 如果当前顺子不满足要求，重置已使用标记
for (Integer num : currentSequence) {
used[cardNumbers.indexOf(num)] = false;
}
}
}
// 输出结果
if (sequences.isEmpty()) {
System.out.println("No");
} else {
for (List<Integer> seq : sequences) {
for (int i = 0; i < seq.size(); i++) {
if (i > 0) System.out.print(" ");
int value = seq.get(i);
if (value == 11) System.out.print("J");
else if (value == 12) System.out.print("Q");
else if (value == 13) System.out.print("K");
else if (value == 14) System.out.print("A");
else System.out.print(value);
}
System.out.println();
}
}
}
}2.AI处理器组合(模拟)
题目描述：
某公司研发了一款高性能AI处理器。每台物理设备具备8颗AI处理器，编号分别为0、1、2、3、4、5、6、7。编号0-3的处理器处于同一个链路中，编号4-7的处理器处于另外一个链路中，不通链路中的处理器不能通信，如下图所示。现给定服务器可用的处理器编号数组array，以及任务申请的处理器数量num，找出符合下列亲和性调度原则的芯片组合。如果不存在符合要求的组合，则返回空列表。
亲和性调度原则：
- 如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。
- 如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。
- 如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。
- 如果申请处理器个数为8，则申请节点所有8个处理器。
提示：
\1. 任务申请的处理器数量只能是1、2、4、8
\2. 编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。
\3. 处理器编号唯一，且不存在相同编号处理器
入描述：
输入包含可用的处理器编号数组array，以及任务申请的处理器数量num两个部分。
第一行为array，第二行为num。例如：
[0, 1, 4, 5, 6, 7]
1
表示当前编号为0、1、4、5、6、7的处理器可用。任务申请1个处理器。
0<= array.length <= 8
0<= array[i] <= 7
num in [1, 2, 4, 8]
输出描述：
输出为组合列表，当array=[0, 1, 4, 5, 6, 7] ，num=1时，输出为[[0], [1]]
示例1
输入：
[0, 1, 4, 5, 6, 7] 1输出：
[[0], [1]]说明：
根据第一条亲和性调度原则，在剩余两个处理器的链路（0,1,2,3）中选择处理器。由于只有0和1可用，则返回任意一颗处理器即可
示例2
输入：
[0, 1, 4, 5, 6, 7] 4输出：
[[4, 5, 6, 7]]说明：
根据第三条亲和性调度原则，必须选择同一链路剩余可用的处理器数量为4个的环。
代码
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
vector<int> arr1,arr2;
int num;
string str;
getline(cin,str);
for(int i=0;i<str.length();++i){
if (str.at(i) >= '0' && str.at(i) <= '3'){
arr1.push_back(str.at(i) - '0');
} else if (str.at(i) >= '4' && str.at(i) <= '7'){
arr2.push_back(str.at(i) - '0');
} else continue;
}
cin>>num;
switch(num){
case 1:
{
bool flag =false;
if (arr1.size() == 1) {
cout<<"[["<<arr1[0]<<"]";
flag = true;
}
if (arr2.size() == 1) {
if (flag) cout<<", ["<<arr2[0]<<"]]";
else {cout<<"[["<<arr2[0]<<"]";flag = true;}
}
if(flag) {cout<<"]";break;}
if (arr1.size() == 3) {
cout<<"[["<<arr1[0]<<"]"<<", ["<<arr1[1]<<"]"<<", ["<<arr1[2]<<"]";
flag =true;
}
if (arr2.size() == 3) {
if (flag) cout<<", ["<<arr2[0]<<"]"<<", ["<<arr2[1]<<"]"<<", ["<<arr2[2]<<"]";
else {cout<<"[["<<arr2[0]<<"]"<<", ["<<arr2[1]<<"]"<<", ["<<arr2[2]<<"]";flag=true;}
}
if(flag) {cout<<"]";break;}
if (arr1.size() == 2) {
cout<<"[["<<arr1[0]<<"]"<<", ["<<arr1[1]<<"]";
flag =true;
}
if (arr2.size() == 2) {
if (flag) cout<<", ["<<arr2[0]<<"]"<<", ["<<arr2[1]<<"]";
else {cout<<"[["<<arr2[0]<<"]"<<", ["<<arr2[1]<<"]";flag =true;}
}
if(flag) {cout<<"]";break;}
if (arr1.size() == 4) {
cout<<"[["<<arr1[0]<<"]"<<", ["<<arr1[1]<<"]"<<", ["<<arr1[2]<<"]"<<", ["<<arr1[3]<<"]";
flag =true;
}
if (arr2.size() == 4) {
if (flag) cout<<", ["<<arr2[0]<<"]"<<", ["<<arr2[1]<<"]"<<", ["<<arr2[2]<<"]"<<", ["<<arr2[3]<<"]";
else {cout<<"[["<<arr2[0]<<"]"<<", ["<<arr2[1]<<"]"<<", ["<<arr2[2]<<"]"<<", ["<<arr2[3]<<"]";flag =true;}
}
if(flag) {cout<<"]";break;}
}
case 2:
{
bool flag = false;
if (arr1.size() == 2) {
cout<<"[["<<arr1[0]<<", "<<arr1[1]<<"]";
flag =true;
}
if (arr2.size() == 2) {
if (flag) cout<<", ["<<arr2[0]<<", "<<arr2[1]<<"]";
else {cout<<"[["<<arr2[0]<<", "<<arr2[1]<<"]";flag =true;}
}
if(flag) {cout<<"]";break;}
if (arr1.size() == 4) {
cout<<"[["<<arr1[0]<<", "<<arr1[1]<<"]";
cout<<", ["<<arr1[0]<<", "<<arr1[2]<<"]";
cout<<", ["<<arr1[0]<<", "<<arr1[3]<<"]";
cout<<", ["<<arr1[1]<<", "<<arr1[2]<<"]";
cout<<", ["<<arr1[1]<<", "<<arr1[3]<<"]";
cout<<", ["<<arr1[2]<<", "<<arr1[3]<<"]";
flag =true;
}
if (arr2.size() == 4) {
if (flag) {
cout<<", ["<<arr2[0]<<", "<<arr2[1]<<"]";
cout<<", ["<<arr2[0]<<", "<<arr2[2]<<"]";
cout<<", ["<<arr2[0]<<", "<<arr2[3]<<"]";
cout<<", ["<<arr2[1]<<", "<<arr2[2]<<"]";
cout<<", ["<<arr2[1]<<", "<<arr2[3]<<"]";
cout<<", ["<<arr2[2]<<", "<<arr2[3]<<"]";
} else {
cout<<"[["<<arr2[0]<<", "<<arr2[1]<<"]";
cout<<", ["<<arr2[0]<<", "<<arr2[2]<<"]";
cout<<", ["<<arr2[0]<<", "<<arr2[3]<<"]";
cout<<", ["<<arr2[1]<<", "<<arr2[2]<<"]";
cout<<", ["<<arr2[1]<<", "<<arr2[3]<<"]";
cout<<", ["<<arr2[2]<<", "<<arr2[3]<<"]";
flag =true;
}
}
if(flag) {cout<<"]";break;}
if (arr1.size() == 3) {
cout<<"[["<<arr1[0]<<", "<<arr1[1]<<"]";
cout<<", ["<<arr1[0]<<", "<<arr1[2]<<"]";
cout<<", ["<<arr1[1]<<", "<<arr1[2]<<"]";
flag =true;
}
if (arr2.size() == 3) {
if (flag) {
cout<<", ["<<arr2[0]<<", "<<arr2[1]<<"]";
cout<<", ["<<arr2[0]<<", "<<arr2[2]<<"]";
cout<<", ["<<arr2[1]<<", "<<arr2[2]<<"]";
} else {
cout<<"[["<<arr2[0]<<", "<<arr2[1]<<"]";
cout<<", ["<<arr2[0]<<", "<<arr2[2]<<"]";
cout<<", ["<<arr2[1]<<", "<<arr2[2]<<"]";
flag =true;
}
}
if(flag) {cout<<"]";break;}
}
case 4:
{
bool flag = false;
if (arr1.size() == 4) {
cout<<"[["<<arr1[0]<<", "<<arr1[1]<<", "<<arr1[2]<<", "<<arr1[3]<<"]";
flag = true;
}
if (arr2.size() == 4) {
if (flag) {
cout<<", ["<<arr2[0]<<", "<<arr2[1]<<", "<<arr2[2]<<", "<<arr2[3]<<"]";
} else {
cout<<"[["<<arr2[0]<<", "<<arr2[1]<<", "<<arr2[2]<<", "<<arr2[3]<<"]";
flag =true;
}
}
if(flag) {cout<<"]";break;}
}
case 8:
{
if (arr1.size() == 4 && arr2.size() ==4) {
cout<<"[["<<arr1[0]<<", "<<arr1[1]<<", "<<arr1[2]<<", "<<arr1[3]
<<", "<<arr2[0]<<", "<<arr2[1]<<", "<<arr2[2]<<", "<<arr2[3]<<"]]";
}
break;
}
}
}java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Integer[] arr =
Arrays.stream(sc.nextLine().split("[\\[\\]\\,\\s]"))
.filter(str -> !"".equals(str))
.map(Integer::parseInt)
.toArray(Integer[]::new);
String num = sc.next();
System.out.println(getResult(arr, num));
}
public static String getResult(Integer[] arr, String num) {
ArrayList<Integer> link1 = new ArrayList<>();
ArrayList<Integer> link2 = new ArrayList<>();
Arrays.sort(arr, (a, b) -> a - b);
for (Integer e : arr) {
if (e < 4) {
link1.add(e);
} else {
link2.add(e);
}
}
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
int len1 = link1.size();
int len2 = link2.size();
switch (num) {
case "1":
if (len1 == 1 || len2 == 1) {
if (len1 == 1) dfs(link1, 0, 1, new ArrayList<>(), ans);
if (len2 == 1) dfs(link2, 0, 1, new ArrayList<>(), ans);
} else if (len1 == 3 || len2 == 3) {
if (len1 == 3) dfs(link1, 0, 1, new ArrayList<>(), ans);
if (len2 == 3) dfs(link2, 0, 1, new ArrayList<>(), ans);
} else if (len1 == 2 || len2 == 2) {
if (len1 == 2) dfs(link1, 0, 1, new ArrayList<>(), ans);
if (len2 == 2) dfs(link2, 0, 1, new ArrayList<>(), ans);
} else if (len1 == 4 || len2 == 4) {
if (len1 == 4) dfs(link1, 0, 1, new ArrayList<>(), ans);
if (len2 == 4) dfs(link2, 0, 1, new ArrayList<>(), ans);
}
break;
case "2":
if (len1 == 2 || len2 == 2) {
if (len1 == 2) dfs(link1, 0, 2, new ArrayList<>(), ans);
if (len2 == 2) dfs(link2, 0, 2, new ArrayList<>(), ans);
} else if (len1 == 4 || len2 == 4) {
if (len1 == 4) dfs(link1, 0, 2, new ArrayList<>(), ans);
if (len2 == 4) dfs(link2, 0, 2, new ArrayList<>(), ans);
} else if (len1 == 3 || len2 == 3) {
if (len1 == 3) dfs(link1, 0, 2, new ArrayList<>(), ans);
if (len2 == 3) dfs(link2, 0, 2, new ArrayList<>(), ans);
}
break;
case "4":
if (len1 == 4 || len2 == 4) {
if (len1 == 4) ans.add(link1);
if (len2 == 4) ans.add(link2);
}
break;
case "8":
if (len1 == 4 && len2 == 4) {
ans.add(
Stream.concat(link1.stream(), link2.stream())
.collect(Collectors.toCollection(ArrayList<Integer>::new)));
}
break;
}
return ans.toString();
}
public static void dfs(
ArrayList<Integer> arr,
int index,
int level,
ArrayList<Integer> path,
ArrayList<ArrayList<Integer>> res) {
if (path.size() == level) {
res.add(new ArrayList<>(path));
return;
}
for (int i = index; i < arr.size(); i++) {
path.add(arr.get(i));
dfs(arr, i + 1, level, path, res);
path.remove(path.size() - 1);
}
}
}3.Boss的收入(拓扑排序)
*题目描述**：*
一个XX产品行销总公司，只有一个boss，其有若千一级分销，一级分销又有若干二级分销，每个分错只有唯一的上级分销。规定，每个月，下级分销需要将自己的总收入(自已的+下级上交的)每满100元上交15元给自己的上级现给出一组分销的关系，和每个分销的收入，请找出boss并计算出这个boss的收入。
比如:
·收入100元，上交15元:
·收入199元(99元不够100)，上交15元:。
收入200元，上交30元。
输入:
分销关系和收入:[[分销id上级分销id收入]，[分销id上级分销id收入]，[分销id 上级分销id 收入]]
·分销ID范围:0..65535
·收入范围:0..65535，单位元
提示:
输入的数据只存在1个boss，不存在环路
输出:
[boss的ID，总收入]
输入描述
第一行输入关系的总数量N
第二行开始，输入关系信息，格式:
分销ID上级分销ID收入
比如:
5 1 0 100 2 0 199 3 0 200 4 0 200 5 0 200*输出描述**：*
输出:
boss的ID总收入
0 120
比如:
0120
说明
给定的输入数据都是合法的,不存在环路,重复的
输入：
5 1 0 100 2 0 199 3 0 200 4 0 200 5 0 200输出：
0 120
解题思路：
本质上这个图就是一棵树结构，我们先利用叶子节点和根节点的特性，去找到他们。然后从叶子节点开始，一层一层计算收入即可。但是由于题目给图的方式，无法第一时间构建树结构，所以用处理拓扑图的方式处理。
算法步骤：
利用邻接表的形式存储图
使用数组记录每个节点的入度和收入
手动计算节点数量 n
通过队列 q 来进行拓扑排序
将所有入度为 0 的节点入队，并依次处理队列中的节点
确定最终的 boss 节点，输出答案
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6+5;
vector<int> g[maxn];
int du[maxn], val[maxn];
signed main()
{
int m, n=0;
cin>>m;
while (m--)
{
int u, v, w;
cin>>u>>v>>w;
n = max(n, max(u, v)); // 手动计算 n 值
g[u].push_back(v); // 建图
du[v]++; // 记录每个点的入度
val[u] += w; // 记录收入
}
queue<int> q;
// 将入度为 0 的点入队
for (int i=0; i<=n; i++)
{
if (du[i]==0)
q.push(i);
}
while (q.size())
{
int u = q.front();
q.pop();
for (int v:g[u])
{
du[v]--; // 入度-1
val[v] += val[u] / 100 * 15; // 计算收入
if (du[v]==0) // 入度为 0 的点入队
q.push(v);
}
// 最后剩下的点一定是 boss
if (q.size() == 0)
cout<<u<<" "<<val[u]<<endl;
}
}java
import java.util.*;
public class Main {
static List<List<Integer>> g;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
final int N = (int)1e6 + 5;
g = new ArrayList<>();
for (int i=0; i<N; i++)
g.add(new ArrayList<>());
int[] du = new int[N], val = new int[N];
int n=0, m=in.nextInt();
while (m-- > 0)
{
int u = in.nextInt(), v = in.nextInt(), w = in.nextInt();
n = Math.max(n, Math.max(u, v)); // 手动计算 n 值
g.get(u).add(v); // 建图
du[v]++; // 记录每个点的入度
val[u] += w; // 记录收入
}
Deque<Integer> q = new ArrayDeque<>();
// 将入度为 0 的点入队
for (int i=0; i<=n; i++)
{
if (du[i] == 0)
q.add(i);
}
// 拓扑排序
while (q.size() > 0)
{
int u = q.poll();
for (int v : g.get(u))
{
du[v]--; // 入度-1
val[v] += val[u] / 100 * 15; // 计算收入
if (du[v] == 0) // 入度为 0 的点入队
q.add(v);
}
// 最后剩下的点一定是 boss
if (q.size() == 0)
System.out.println(u + " " + val[u]);
}
}
}4.光伏场地建设规划(二维前缀和)
*题目描述*
祖国西北部有一片大片荒地，其中零星的分布着一些湖泊，保护区，矿区:整体上常年光照良好，但是也有一些地区光照不太好。
某电力公司希望在这里建设多个光伏电站，生产清洁能源对每平方公里的土地进行了发电评估，其中不能建设的区域发电量为0kw，可以发电的区域根据光照，地形等给出了每平方公里年发电量x千瓦。
我们希望能够找到其中集中的矩形区域建设电站，能够获得良好的收益
*输入描述*
第一行输入为调研的地区长，宽，以及准备建设的电站【长宽相等，为正方形】的边长，最低要求的发电量，之后每行为调研区域每平方公里的发电量。
例如，输入为:
2526
13458
23671
表示调研的区域大小为长2宽5的矩形，我们要建设的电站的边长为 2，建设电站最低发电量为 6
*输出描述*
输出为这样的区域有多少个?
上述输入长度为 2 的正方形满足发电量大于等于6的区域有 4 个。则输出为:
备注
其中被调研的区域的长宽均大于等于 1，建设电站的边长大于等于 1，任何区域的发电量大于等于0
*示例1*
输入
2 5 2 6 1 3 4 5 8 2 3 6 7 1输出
4说明
输入长为2，宽为5的场地，建设的场地为正方形场地边长为2，要求场地的发电量大于等于6
*示例2*
2 5 1 6 1 3 4 5 8 2 3 6 7 1输出
3说明
输入长为2，宽为5的场地，建设的场地为正方形场地，边长为1，要求场地的发电量大于等于6
*示例3*
2 5 1 0 1 3 4 5 8 2 3 6 7 1输出
10说明
输入长为2，宽为5的场地，建设的场地为正方形场地，边长为1，要求场地的发电量大于等于0
解题思路
1、理解问题:
- 给定一个矩形区域的尺寸（长和宽）和一个正方形电站的边长，计算在这个矩形区域内所有可能的正方形子区域的总发电量。
判断这些正方形子区域中有多少个满足最低发电量要求。
2、前缀和的概念:
- 前缀和是一种预处理技术，用于快速计算矩阵中任意子矩阵的和。
通过构建一个前缀和矩阵，我们可以在常数时间内查询任何子矩阵的和。
3、构建前缀和矩阵:
- 创建一个与输入矩阵大小相同的前缀和矩阵prefixSum，其中prefixSum[i][j]表示从左上角 (0,0) 到 (i,j) 的所有元素之和。
计算公式：
prefixSum[i][j] = [matrix][i][j]
+ prefixSum[i-1][j]
+ prefixSum[i][j-1]
- prefixSum[i-1][j-1]4、计算每个正方形子区域的发电量:
- 遍历每一个可能的正方形子区域的左上角坐标 (i, j)。
- 计算每个正方形区域的总发电量，使用前缀和矩阵快速查询：
totalPower = prefixSum[x2][y2]
- prefixSum[x1-1][y2]
- prefixSum[x2][y1-1]
+ prefixSum[x1-1][y1-1]其中 (x1, y1) 是正方形的左上角坐标，(x2, y2) 是右下角坐标。通过这种方式，可以快速计算任意子矩阵的和。
5、判断和计数:
- 对于每个正方形子区域，计算其总发电量并判断是否满足最低发电量要求。
6、输出结果:
- 输出满足条件的正方形子区域的数量。
代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int regionLength, regionWidth, squareSide, minPower;
cin >> regionLength >> regionWidth >> squareSide >> minPower;
vector<vector<int>> powerGrid(regionLength, vector<int>(regionWidth));
// 读取每个位置的发电量
for (int i = 0; i < regionLength; ++i) {
for (int j = 0; j < regionWidth; ++j) {
cin >> powerGrid[i][j];
}
}
// 构建前缀和矩阵
vector<vector<int>> prefix(regionLength + 1, vector<int>(regionWidth + 1, 0));
for (int i = 1; i <= regionLength; ++i) {
for (int j = 1; j <= regionWidth; ++j) {
prefix[i][j] = powerGrid[i - 1][j - 1]
+ prefix[i - 1][j]
+ prefix[i][j - 1]
- prefix[i - 1][j - 1];
}
}
int count = 0; // 满足条件的区域数量
// 遍历所有可能的正方形子区域的左上角坐标 (i, j)
for (int i = 0; i <= regionLength - squareSide; ++i) {
for (int j = 0; j <= regionWidth - squareSide; ++j) {
// 子矩阵的右下角坐标
int x2 = i + squareSide;
int y2 = j + squareSide;
// 计算子矩阵的总发电量
int totalPower = prefix[x2][y2]
- prefix[i][y2]
- prefix[x2][j]
+ prefix[i][j];
// 检查总发电量是否满足条件
if (totalPower >= minPower) {
count++;
}
}
}
// 输出满足条件的区域数量
cout << count << endl;
return 0;
}java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入矩阵的长、宽、电站的边长和最低发电量要求
int regionLength = scanner.nextInt();
int regionWidth = scanner.nextInt();
int squareSide = scanner.nextInt();
int minPower = scanner.nextInt();
int[][] powerGrid = new int[regionLength + 1][regionWidth + 1]; // 增加1行1列用于前缀和计算简化
// 读取每个位置的发电量
for (int i = 1; i <= regionLength; i++) {
for (int j = 1; j <= regionWidth; j++) {
powerGrid[i][j] = scanner.nextInt();
}
}
// 构建前缀和矩阵直接在原始矩阵上，从1开始避免越界和多余的判断
for (int i = 1; i <= regionLength; i++) {
for (int j = 1; j <= regionWidth; j++) {
powerGrid[i][j] += powerGrid[i - 1][j] + powerGrid[i][j - 1] - powerGrid[i - 1][j - 1];
}
}
int count = 0; // 满足条件的区域数量
// 遍历所有可能的正方形子区域的左上角坐标 (i, j)
for (int i = 1; i <= regionLength - squareSide + 1; i++) {
for (int j = 1; j <= regionWidth - squareSide + 1; j++) {
// 子矩阵的右下角坐标
int x2 = i + squareSide - 1;
int y2 = j + squareSide - 1;
// 计算子矩阵的总发电量
int totalPower = powerGrid[x2][y2] - powerGrid[i - 1][y2] - powerGrid[x2][j - 1] + powerGrid[i - 1][j - 1];
// 检查总发电量是否满足条件
if (totalPower >= minPower) {
count++;
}
}
}
// 输出满足条件的区域数量
System.out.println(count);
scanner.close();
}
}