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值為零的情況終止。這個案子不應該處理。
輸出
對于每種情況，在單行中打印最小總成本。

思路

代碼解析

結構體定義 (struct Num): 定義了一個結構體Num，包含一個成員變量num用于存儲數值。通過重載<運算符，使得priority_queue默認按照數值從小到大排序，但實際上我們希望它是最大堆，因此這里的比較邏輯是“當前數大于另一個數”，這樣就可以構建最大堆。
主函數(main)邏輯:
- 讀取輸入: 使用scanf讀取測試用例個數n，當n不為0時繼續執行。
- 循環處理每個測試用例:
  - 初始化總和sum為0。
  - 使用循環讀取n個整數，每次讀取后創建Num對象并將其壓入優先隊列Q中。
  - 當優先隊列非空時，循環執行以下操作：
    - 從隊列頂部彈出兩個最大數（由于我們定義的是最大堆，所以這是自動實現的），求和。
    - 將求得的和累加至sum。
    - 若隊列中還有其他元素，將求和后的值作為新的元素壓入隊列。
  - 輸出最終的累加和sum。
- 直到沒有更多的測試用例，程序結束。
利用優先隊列實現最小累加和：通過持續取出最大兩個數相加，并將結果放回隊列，確保了每次操作都能最大化減少后續累加過程中的“損失”，從而達到整體最小累加和的目的。

記憶要點

優先隊列與堆的應用：理解優先隊列（尤其是最大堆）在處理需要頻繁訪問最大/最小元素的問題中的優勢。
結構體與運算符重載：通過自定義結構體和重載比較運算符來適應特定的數據結構需求。
貪心策略：每次選取最大兩個數相加，體現了貪心算法的思想，局部最優選擇往往能導向全局最優解。
循環終止條件：注意在只剩一個或零個元素時終止循環，避免不必要的操作。
輸入輸出格式處理：掌握基本的輸入輸出函數如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;
}}