ACM实训

【碎碎念】继续搞习题学习，今天完成第四套的ABCD，为下一周挤出时间复习，加油

Digit Counting

问题

法希姆喜欢解决数学问题。但有时解决所有的数学问题对他来说是一个挑战。所以有时候他会为了解决数学难题而生气。他拿起一支粉笔，开始写一个从1到N (1 < N < 10000)开始的连续整数序列。之后，他计算每个数字(0到9)在序列中出现的次数。例如，当N = 13时，序列为。

12345678910111213
这个顺序很有趣，对吧?在这个序列中，0(0)出现一次，1(1)出现6次，2(2)出现2次，3(3)出现3次，从4(4)到9(9)的每个数字出现一次。玩了一会儿后，法希姆又觉得无聊了。现在，他想为自己编写一个程序。你的任务是帮助他编写这个程序。

输入
仔细查看输入文件。它由几个数据集组成。输入文件的第一行包含数据集的数量，它是一个不大于20的正整数。下面几行描述了数据集。对于每个测试用例，有一行包含数字N。

输出
现在对于每个单独的测试用例，在一行中顺序地写数字0,1，…用一个空格隔开。

样例输入
2
3
13
样例输出
0 1 1 1 0 0 0 0 0 0
1 6 2 2 1 1 1 1 1 1 1
请注意
您可以使用C/ c++ /Java提交您的解决方案。如果你想用JavaScript提交你的解决方案，那就问志愿者。

思路

把前n（n<=10000)个整数顺次写在一起：123456789101112···数一数0~9各出现多少次（输出10个整数，分别是0，1，···，9出现的次数）。

代码 

#include<stdio.h> 
#include<string.h>
int cnt[10];
int main(){int T;scanf("%d",&T);while(T--){memset(cnt,0,sizeof(cnt));//给数组赋值为0 int n;scanf("%d",&n);for(int i=1;i<=n;i++){//条件不可变 int num=i;while(num){cnt[num%10]++;num/=10;}}for(int i=0;i<10;i++) printf("%d ",cnt[i]);}return 0;
}

Add All

对我来说稍微有一点难，可以先放置

问题

是的! !问题名称反映了你的任务;只要加上一组数字。但是你可能会觉得写一个C/ c++程序只是为了添加一组数字是一种屈尊。这样的问题只会质疑你的学识。所以，让我们加入一些独创性的味道。

加法运算现在需要代价，代价就是这两个相加的和。所以，1加10，需要花费11。如果你想加1 2 3。有几种方法

1 + 2 = 3，成本= 3
3 + 3 = 6，成本= 6
合计= 9

1 + 3 = 4，成本= 4
2 + 4 = 6，成本= 6
总= 10

2 + 3 = 5，成本= 5
1 + 5 = 6，成本= 6
合计= 11

我希望你已经明白你的任务，添加一组整数，使成本最小。
输入
每个测试用例将从一个正数N(2≤N≤5000)开始，然后是N个正整数(均小于100000)。输入以N值为零的情况终止。这个案子不应该处理。
输出
对于每种情况，在单行中打印最小总成本。

思路

代码解析

1. 结构体定义 (struct Num): 定义了一个结构体Num，包含一个成员变量num用于存储数值。通过重载<运算符，使得priority_queue默认按照数值从小到大排序，但实际上我们希望它是最大堆，因此这里的比较逻辑是“当前数大于另一个数”，这样就可以构建最大堆。

2. 主函数(main)逻辑:

   • 读取输入: 使用scanf读取测试用例个数n，当n不为0时继续执行。
   • 循环处理每个测试用例:
     • 初始化总和sum为0。
     • 使用循环读取n个整数，每次读取后创建Num对象并将其压入优先队列Q中。
     • 当优先队列非空时，循环执行以下操作：
       • 从队列顶部弹出两个最大数（由于我们定义的是最大堆，所以这是自动实现的），求和。
       • 将求得的和累加至sum。
       • 若队列中还有其他元素，将求和后的值作为新的元素压入队列。
     • 输出最终的累加和sum。
   • 直到没有更多的测试用例，程序结束。

3. 利用优先队列实现最小累加和：通过持续取出最大两个数相加，并将结果放回队列，确保了每次操作都能最大化减少后续累加过程中的“损失”，从而达到整体最小累加和的目的。

记忆要点

1. 优先队列与堆的应用：理解优先队列（尤其是最大堆）在处理需要频繁访问最大/最小元素的问题中的优势。
2. 结构体与运算符重载：通过自定义结构体和重载比较运算符来适应特定的数据结构需求。
3. 贪心策略：每次选取最大两个数相加，体现了贪心算法的思想，局部最优选择往往能导向全局最优解。
4. 循环终止条件：注意在只剩一个或零个元素时终止循环，避免不必要的操作。
5. 输入输出格式处理：掌握基本的输入输出函数如scanf和printf的使用，注意格式控制。

#include<iostream>
#include<cstdio>      // 包含标准输入输出函数，如scanf/printf
#include<queue>       // 包含队列容器相关的实现，包括优先队列
#include<functional>  // 提供函数对象相关功能，这里用于优先队列自定义排序规则
using namespace std;typedef long long LL;  // 定义长整型别名，方便表示大整数int n;                 // 用于存储输入的整数数量int main(){// 循环读取测试用例，直到输入为0为止while(scanf("%d",&n)==1&&n){LL ans=0;         // 初始化答案变量为0，用于累加计算结果// 定义一个优先队列pq，其中元素类型为int，基于vector容器，使用greater<int>使得队列顶部元素始终是最小的priority_queue<int,vector<int>,greater<int> > pq;// 读取n个整数并压入优先队列for(int i=0;i<n;i++){int x; scanf("%d",&x);pq.push(x);}// 进行n-1轮操作，每轮取出队列顶部的两个最小元素相加，然后将和重新压入队列for(int i=0;i<n-1;i++){int x=pq.top(); pq.pop();    // 取出并删除队列顶部的最小元素xint y=pq.top(); pq.pop();    // 再次取出并删除队列顶部的最小元素yans+=x+y;                  // 将x和y的和累加到答案变量ans中pq.push(x+y);              // 将x+y压回优先队列} // 输出最终计算得到的答案printf("%lld\n",ans);}return 0;           // 程序正常结束，返回0
}

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<functional>
using namespace std;typedef long long LL;
int n;int main(){while(scanf("%d",&n)==1&&n){LL ans=0;priority_queue<int,vector<int>,greater<int> > pq;for(int i=0;i<n;i++){int x; scanf("%d",&x);pq.push(x);}for(int i=0;i<n-1;i++){int x=pq.top(); pq.pop();int y=pq.top(); pq.pop();ans+=x+y;pq.push(x+y);} printf("%lld\n",ans);}return 0;
}

Oil Deposits 

问题

GeoSurvComp地质调查公司负责探测地下油藏。GeoSurvComp每次只处理一个大的矩形区域，并创建一个网格，将土地划分成无数的方形地块。然后，它使用传感设备分别分析每个地块，以确定地块是否含有石油。 含有石油的地块称为口袋。如果两个储层相邻，那么它们就是同一个油藏的一部分。石油蕴藏量很大，可能包含无数的油穴。你的工作是确定在一个网格中有多少不同的石油储藏。.

 

Input 

输入文件包含一个或多个网格。每个网格以包含m和n的行开始，这是网格中的行数和列数，用一个空格分隔。如果m = 0，则表示输入结束。接下来是m行，每行n个字符(不包括行尾字符)。每个字符对应一个情节，“*”代表没有石油，“@”代表有石油的口袋。

 

Output 

对于每个网格，输出不同的石油储量的数量。如果两个不同的袋体在水平、垂直或对角线上相邻，则它们是同一油藏的一部分。一个石油矿床将不超过100个油袋。 

思路

#include <cstdio>      // 包含标准输入输出函数
#include <cstring>     // 包含字符串操作函数
#include <algorithm>   // 包含算法操作函数
using namespace std;int r, c;             // r: 地图的行数，c: 地图的列数
int fx[9] = {0, 0, 1, -1, -1, -1, 1, 1}, fy[9] = {1, -1, 0, 0, -1, 1, -1, 1}; // 方向数组，用于八连通搜索
char mapp[105][105];   // 二维字符数组，用于存储地图信息
int s;                // 计算油桶的总数// 深度优先搜索函数，遍历与当前位置相邻的油桶
void dfs(int x, int y) {mapp[x][y] = '*'; // 标记当前油桶位置为已访问，用'*'代替// 遍历八个方向for (int i = 0; i < 8; i++) {int a = x + fx[i]; // 新的位置行坐标int b = y + fy[i]; // 新的位置列坐标// 检查新位置是否在地图范围内且为未访问的油桶('@')if (a > 0 && a <= r && b > 0 && b <= c && mapp[a][b] == '@') {dfs(a, b); // 递归访问新位置}}
}int main() {// 循环读取测试用例，直到输入的行数为0while (scanf("%d %d", &r, &c) == 2 && r != 0) {s = 0; // 初始化计数器// 读取地图信息for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {scanf(" %c", &mapp[i][j]); // 注意空格，避免读取前导空白字符}}// 遍历地图，对每个油桶发起深度优先搜索for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {if (mapp[i][j] == '@') {dfs(i, j); // 发起搜索s++;       // 搜索完一个油桶集合，计数加一}}}printf("%d\n", s); // 输出当前地图的油桶集合数量}return 0; // 程序结束
}

什么是八连通

八连通（八向连通）是计算机视觉、图像处理和图形学领域中的一个概念，主要应用于分析和处理数字图像中的连通性问题。在处理二值图像时，连通性用来识别和区分不同的目标或区域。具体来说：

八连通意味着在二维空间中，对于每一个像素，如果它与其上下左右以及对角线方向（左上、右上、左下、右下）上的相邻像素具有相同的属性（比如都是白色或者都是黑色），则认为这些像素是八连通的。换句话说，从图像中的任意一个像素出发，如果能够仅通过这八个方向之一到达另一个具有相同属性的像素，那么这两个像素就属于同一个连通区域。

这段代码定义了两个数组fx和fy，它们分别代表了在二维平面上移动时的横坐标（x轴）和纵坐标（y轴）的变化量，用于实现八连通性搜索。八连通意味着从一个点出发，可以向上、下、左、右以及对角线方向（左上、右上、左下、右下）移动并仍然保持在相连的区域内。具体解释如下：

• fx[9] = {0, 0, 1, -1, -1, -1, 1, 1}:

  • fx数组存储了x轴方向的变化量。每个值代表相对于当前位置在x轴上可能移动的方向：
    • 0, 0: 第一个0是占位符，实际上并不使用（因为数组索引从0开始，但实际有效方向从1计数）。
    • 1: 向右移动。
    • -1: 向左移动。
    • -1, -1, 1, 1: 分别对应向上右、上左、下右、下左的对角线移动。

• fy[9] = {1, -1, 0, 0, -1, 1, -1, 1}:

  • fy数组存储了y轴方向的变化量，与fx数组对应的每个方向上的y坐标变化：
    • 1: 向上移动。
    • -1: 向下移动。
    • 0, 0: 同样，前两个0是占位符，实际上代表水平移动时y轴无变化。
    • -1, 1, -1, 1: 对应于对角线方向上y坐标的增减。

 

1.定义dfs函数，运用到八连通

2.扫描地图

3.把有@的数据传到dfs函数中 

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int r, c;
int fx[9] = {0, 0, 1, -1, -1, -1, 1, 1}, fy[9] = {1, -1, 0, 0, -1, 1, -1, 1};
char mapp[105][105];
int s;void dfs(int x, int y) {mapp[x][y] = '*'; // 把等于@的都变成*，因为它们属于同一油桶for (int i = 0; i < 8; i++) {int a = x + fx[i];int b = y + fy[i];if (a > 0 && a <= r && b > 0 && b <= c && mapp[a][b] == '@') {dfs(a, b);}}
}int main() {while (scanf("%d %d", &r, &c) == 2 && r != 0) {s = 0;for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {scanf(" %c", &mapp[i][j]); // 注意增加空格忽略空白字符}}for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {if (mapp[i][j] == '@') {dfs(i, j);s++;}}}printf("%d\n", s);}return 0;
}

Dungeon Master

这道题好难呀QAQ   打算放弃

问题

Description - 题目描述

你进入了一个3D的宝藏地宫中探寻宝藏到了宝藏，你可以找到走出地宫的路带出宝藏，或者使用炉石空手回家。

地宫由立方体单位构成，立方体中不定会充满岩石。向上下前后左右移动一个单位需要一分钟。你不能对角线移动并且地宫四周坚石环绕。
请问你是否可以走出地宫带出宝藏？如果存在，则需要多少时间？

Input - 输入

每个地宫描述的第一行为L，R和C（皆不超过30）。
L表示地宫的层数。
R和C分别表示每层地宫的行与列的大小。
随后L层地宫，每层R行，每行C个字符。
每个字符表示地宫的一个单元。'#'表示岩石单元，'.'表示空白单元。你的起始位置在'S'，出口为'E'。
每层地宫后都有一个空行。L，R和C均为0时输入结束。

Output - 输出

每个地宫对应一行输出。
如果可以带出宝藏，则输出
Escaped in x minute(s).
x为最短脱离时间。
如果无法带出，则输出
Trapped!

思路

感觉这道题是上一道找石油的升级版，由两维升级到三维

代码

#include <iostream>
#include<queue>
#include<string.h> 
using namespace std;struct pp
{
int x;
int y;
int z;
};//定义数据结构pp，用于储存三维坐标queue<pp> s;//创建队列
pp ne, st;//st为起点的坐标，ne为每次朝六个方向探索时的可行坐标
int x, y, z,ans;//xyz为输入的内容，ans记录答案。
const int N = 35;
char a[N][N][N];
int d[N][N][N];//存储到达每个位置所需要的最短步数
int dx[6] = { -1,0,0,1,0,0 }, dy[6] = { 0,-1,0,0,1,0 }, dz[6] = { 0,0,-1,0,0,1 };//上下左右前后六个坐标的延伸int bfs()
{
ans = -1;
memset(d, -1, sizeof d);//将d数组数据全部设置为-1
for (int i = 0; i < z; i++)
for (int j = 0; j < y; j++)
for (int k = 0; k < x; k++)
{
if (a[k][j][i] == 'S')
{
st.x = k, st.y = j, st.z = i;
d[k][j][i] = 0;
s.push(st);
break;
}
}//寻找起点S的位置，然后将起点坐标入队列，该点所在的d设为0
while (s.size())
{
pp temp = s.front();//取出队首元素
s.pop();//弹出队首元素
if (a[temp.x][temp.y][temp.z] == 'E')
{
ans= d[temp.x][temp.y][temp.z];
while (s.size()) s. pop();
break;
}//如果找到终点，终止循环
for (int i = 0; i < 6; i++)
{
int x1 = temp.x + dx[i];
int y1= temp.y + dy[i];
int z1 = temp.z + dz[i];
if (x1 < 0 || x1 >= x || y1 < 0 || y1 >= y || z1 < 0 || z1 >= z || d[x1][y1][z1] != -1 || a[x1][y1][z1] == '#') continue;
if(a[x1][y1][z1]=='.'||a[x1][y1][z1]=='E')
{
ne.x = x1, ne.y = y1, ne.z = z1;
d[x1][y1][z1] = d[temp.x][temp.y][temp.z] + 1;
s.push(ne);
}
}
}//每次朝六个方向延伸，如果该坐标可行则将该点坐标入队列，然后刷线该点所在的d数组的值。
return ans;
}int main()
{
cin.tie(0);
while (cin>>z>>y>>x&&(x!=0||y!=0||z!=0))
{
for (int i = 0; i < z; i++)
for (int j = 0; j < y; j++)
for (int k = 0; k < x; k++)
cin >> a[k][j][i];
if (bfs() != -1) cout << "Escaped in " << bfs() << " minute(s)." << endl;
else cout << "Trapped!" << endl;
}}