第十四屆藍橋杯模拟賽第三期
-
- 1. 最小的十六進制
-
- 問題描述
- 答案送出
- 參考答案
- 2. Excel的列
-
- 問題描述
- 答案送出
- 參考答案
- 3. 相等日期
-
- 問題描述
- 答案送出
- 參考答案
- 4. 多少種取法
-
- 問題描述
- 答案送出
- 參考答案
- 5. 最大連通分塊
-
- 問題描述
- 答案送出
- 參考答案
- 6. 哪一天
-
- 問題描述
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 評測用例規模與約定
- 參考答案
- 7. 信号覆寫
-
- 問題描述
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 評測用例規模與約定
- 參考答案
- 8. 清理水草
-
- 問題描述
- 輸入格式
- 輸出格式
- 樣例輸入1
- 樣例輸出1
- 樣例輸入2
- 樣例輸出2
- 評測用例規模與約定
- 參考答案
- 9. 最長滑行
-
- 問題描述
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 樣例說明
- 評測用例規模與約定
- 參考答案
- 10. 區間最小值
-
- 問題描述
- 輸入格式
- 輸出格式
- 樣例輸入
- 樣例輸出
- 評測用例規模與約定
- 參考答案
代碼都是自己敲的，不一定對==
1. 最小的十六進制
問題描述
請找到一個大于 2022 的最小數，這個數轉換成十六進制之後，所有的數位（不含前導 0）都為字母（A 到 F）。
請将這個數的十進制形式作為答案送出。
答案送出
這是一道結果填空的題，你隻需要算出結果後送出即可。本題的結果為一個整數，在送出答案時隻填寫這個整數，填寫多餘的内容将無法得分。
參考答案
2730
#include <iostream>
#include <sstream>
using namespace std;
int main() {
for (int i = 2022;; i++) {
ostringstream ss;
ss << hex << i;
string result(ss.str());
bool flag = true;
for (char j: result) {
if (j < 'a' || j > 'z') {
flag = false;
break;
}
}
if (flag) {
cout << i << endl;
break;
}
}
return 0;
}
2. Excel的列
問題描述
在 Excel 中，列的名稱使用英文字母的組合。前 26 列用一個字母，依次為 A 到 Z，接下來 26*26 列使用兩個字母的組合，依次為 AA 到 ZZ。
請問第 2022 列的名稱是什麼？
答案送出
這是一道結果填空的題，你隻需要算出結果後送出即可。本題的結果為一個由大寫字母組成的字元串，在送出答案時隻填寫這個字元串，填寫多餘的内容将無法得分。
參考答案
BYT
#include <iostream>
#include <sstream>
#include<vector>
#include <algorithm>
using namespace std;
int main() {
vector<string> v;
string temp = "A";
for (int i = 0; i < 26; i++) {
temp[0] = 'A' + i;
v.push_back(temp);
}
temp = "AA";
for (int i = 0; i < 26; i++) {
temp[0] = 'A' + i;
for (int j = 0; j < 26; j++) {
temp[1] = 'A' + j;
v.push_back(temp);
}
}
temp = "AAA";
for (int i = 0; i < 26; i++) {
temp[0] = 'A' + i;
for (int j = 0; j < 26; j++) {
temp[1] = 'A' + j;
for (int k = 0; k < 26; k++) {
temp[2] = 'A' + k;
v.push_back(temp);
}
}
}
cout << v[2021] << endl;
return 0;
}
3. 相等日期
問題描述
對于一個日期，我們可以計算出年份的各個數位上的數字之和，也可以分别計算月和日的各位數字之和。請問從 1900 年 1 月 1 日至 9999 年 12 月 31 日，總共有多少天，年份的數位數字之和等于月的數位數字之和加日的數位數字之和。
例如，2022年11月13日滿足要求，因為 2+0+2+2=(1+1)+(1+3) 。
請送出滿足條件的日期的總數量。
答案送出
這是一道結果填空的題，你隻需要算出結果後送出即可。本題的結果為一個整數，在送出答案時隻填寫這個整數，填寫多餘的内容将無法得分。
參考答案
70910
#include <iostream>
#include <sstream>
#include<vector>
#include <algorithm>
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int days2[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {
int count = 0;
for (int i = 1900; i <= 9999; i++) {
for (int j = 1; j <= 12; j++) {
if (i % 4 == 0 && i % 100 != 0 || i % 400 == 0) {
for (int k = 1; k <= days2[j]; k++) {
string s1 = to_string(i);
string s2 = to_string(j) + to_string(k);
int sum1 = 0, sum2 = 0;
for (char l: s1) sum1 += l - '0';
for (char l: s2) sum2 += l - '0';
if (sum1 == sum2) count++;
}
} else {
for (int k = 1; k <= days[j]; k++) {
string s1 = to_string(i);
string s2 = to_string(j) + to_string(k);
int sum1 = 0, sum2 = 0;
for (char l: s1) sum1 += l - '0';
for (char l: s2) sum2 += l - '0';
if (sum1 == sum2) count++;
}
}
}
}
cout << count << endl;
return 0;
}
4. 多少種取法
問題描述
小藍有 30 個數，分别為：99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。
小藍可以在這些數中取出兩個序号不同的數，共有 30*29/2=435 種取法。
請問這 435 種取法中，有多少種取法取出的兩個數的乘積大于等于 2022 。
答案送出
這是一道結果填空的題，你隻需要算出結果後送出即可。本題的結果為一個整數，在送出答案時隻填寫這個整數，填寫多餘的内容将無法得分。
參考答案
189
#include <iostream>
#include <sstream>
#include<vector>
#include <algorithm>
using namespace std;
int num[30] = {99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77};
int main() {
int count = 0;
for (int i = 0; i < 30; i++) {
for (int j = i + 1; j < 30; j++) {
if (num[i] * num[j] >= 2022) count++;
}
}
cout << count << endl;
return 0;
}
5. 最大連通分塊
問題描述
小藍有一個 30 行 60 列的數字矩陣，矩陣中的每個數都是 0 或 1 。如果從一個标為 1 的位置可以通過上下左右走到另一個标為 1 的位置，則稱兩個位置連通。與某一個标為 1 的位置連通的所有位置（包括自己）組成一個連通分塊。
請問矩陣中最大的連通分塊有多大？
110010000011111110101001001001101010111011011011101001111110
010000000001010001101100000010010110001111100010101100011110
001011101000100011111111111010000010010101010111001000010100
101100001101011101101011011001000110111111010000000110110000
010101100100010000111000100111100110001110111101010011001011
010011011010011110111101111001001001010111110001101000100011
101001011000110100001101011000000110110110100100110111101011
101111000000101000111001100010110000100110001001000101011001
001110111010001011110000001111100001010101001110011010101110
001010101000110001011111001010111111100110000011011111101010
011111100011001110100101001011110011000101011000100111001011
011010001101011110011011111010111110010100101000110111010110
001110000111100100101110001011101010001100010111110111011011
111100001000001100010110101100111001001111100100110000001101
001110010000000111011110000011000010101000111000000110101101
100100011101011111001101001010011111110010111101000010000111
110010100110101100001101111101010011000110101100000110001010
110101101100001110000100010001001010100010110100100001000011
100100000100001101010101001101000101101000000101111110001010
101101011010101000111110110000110100000010011111111100110010
101111000100000100011000010001011111001010010001010110001010
001010001110101010000100010011101001010101101101010111100101
001111110000101100010111111100000100101010000001011101100001
101011110010000010010110000100001010011111100011011000110010
011110010100011101100101111101000001011100001011010001110011
000101000101000010010010110111000010101111001101100110011100
100011100110011111000110011001111100001110110111001001000111
111011000110001000110111011001011110010010010110101000011111
011110011110110110011011001011010000100100101010110000010011
010011110011100101010101111010001001001111101111101110011101
答案送出
這是一道結果填空的題，你隻需要算出結果後送出即可。本題的結果為一個整數，在送出答案時隻填寫這個整數，填寫多餘的内容将無法得分。
參考答案
148
經典問題
#include <iostream>
#include <sstream>
#include<vector>
#include <algorithm>
using namespace std;
string *matrix;
int temp;
void dfs(int x, int y) {
if (x < 0 || y < 0 || x > 29 || y > 59 || matrix[x][y] == '0') return;
matrix[x][y] = '0';
temp++;
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
}
int main() {
freopen("data.txt", "r", stdin);
matrix = new string[30];
for (int i = 0; i < 30; i++) {
cin >> matrix[i];
}
int ans = 0;
for (int i = 0; i < 30; i++) {
for (int j = 0; j < 60; j++) {
if (matrix[i][j] == '1') {
temp = 0;
dfs(i, j);
ans = max(ans, temp);
}
}
}
cout << ans << endl;
return 0;
}
6. 哪一天
問題描述
給定一天是一周中的哪天，請問 n 天後是一周中的哪天？
輸入格式
輸入第一行包含一個整數 w，表示給定的天是一周中的哪天，w 為 1 到 6 分别表示周一到周六，w 為 7 表示周日。
第二行包含一個整數 n。
輸出格式
輸出一行包含一個整數，表示 n 天後是一周中的哪天，1 到 6 分别表示周一到周六，7 表示周日。
樣例輸入
6
10
樣例輸出
2
評測用例規模與約定
對于所有評測用例， 1 < = n < = 1000000 1 <= n <= 1000000 1<=n<=1000000。
參考答案
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
if ((a + b) % 7) {
cout << (a + b) % 7 << endl;
} else {
cout << 7 << endl;
}
return 0;
}
7. 信号覆寫
問題描述
小藍負責一塊區域的信号塔安裝，整塊區域是一個長方形區域，建立坐标軸後，西南角坐标為 (0, 0)， 東南角坐标為 (W, 0)， 西北角坐标為 (0, H)， 東北角坐标為 (W, H)。其中 W, H 都是整數。
他在 n 個位置設定了信号塔，每個信号塔可以覆寫以自己為圓心，半徑為 R 的圓形（包括邊緣）。
為了對信号覆寫的情況進行檢查，小藍打算在區域内的所有橫縱坐标為整數的點進行測試，檢查信号狀态。其中橫坐标範圍為 0 到 W，縱坐标範圍為 0 到 H，總共測試 (W+1) * (H+1) 個點。
給定信号塔的位置，請問這 (W+1)*(H+1) 個點中有多少個點被信号覆寫。
輸入格式
輸入第一行包含四個整數 W, H, n, R，相鄰整數之間使用一個空格分隔。
接下來 n 行，每行包含兩個整數 x, y，表示一個信号塔的坐标。信号塔可能重合，表示兩個信号發射器裝在了同一個位置。
輸出格式
輸出一行包含一個整數，表示答案。
樣例輸入
10 10 2 5
0 0
7 0
樣例輸出
57
評測用例規模與約定
對于所有評測用例，1 <= W, H <= 100，1 <= n <= 100, 1 <= R <= 100, 0 <= x <= W, 0 <= y <= H。
參考答案
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int num[105][105] = {0};
inline double distance(int x1, int y1, int x2, int y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main() {
int W, H, n, R;
cin >> W >> H >> n >> R;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
for (int j = x - R; j <= x + R; j++) {
for (int k = y - R; k <= y + R; k++) {
if (j >= 0 && j <= W && k >= 0 && k <= H && distance(x, y, j, k) <= R) {
num[j][k] = 1;
}
}
}
}
int count = 0;
for (int i = 0; i <= W; i++) {
for (int j = 0; j <= H; j++) {
if (num[i][j] == 1) {
count++;
}
}
}
cout << count << endl;
return 0;
}
8. 清理水草
問題描述
小藍有一個 n * m 大小的矩形水域，小藍将這個水域劃分為 n 行 m 列，行數從 1 到 n 标号，列數從 1 到 m 标号。每行和每列的寬度都是機關 1 。
現在，這個水域長滿了水草，小藍要清理水草。
每次，小藍可以清理一塊矩形的區域，從第 r1 行（含）到第 r2 行（含）的第 c1 列（含）到 c2 列（含）。
經過一段時間清理後，請問還有多少地方沒有被清理過。
輸入格式
輸入第一行包含兩個整數 n, m，用一個空格分隔。
第二行包含一個整數 t ，表示清理的次數。
接下來 t 行，每行四個整數 r1, c1, r2, c2，相鄰整數之間用一個空格分隔，表示一次清理。請注意輸入的順序。
輸出格式
輸出一行包含一個整數，表示沒有被清理過的面積。
樣例輸入1
2 3
2
1 1 1 3
1 2 2 2
樣例輸出1
2
樣例輸入2
30 20
2
5 5 10 15
6 7 15 9
樣例輸出2
519
評測用例規模與約定
對于所有評測用例，1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。
參考答案
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int num[105][105] = {0};
int main() {
int W, H, n;
cin >> W >> H >> n;
int count = 0;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int j = x1; j <= x2; j++) {
for (int k = y1; k <= y2; k++) {
if (num[j][k] == 0) {
num[j][k] = 1;
count++;
}
}
}
}
cout << W * H - count << endl;
return 0;
}
9. 最長滑行
問題描述
小藍準備在一個空曠的場地裡面滑行，這個場地的高度不一，小藍用一個 n 行 m 列的矩陣來表示場地，矩陣中的數值表示場地的高度。
如果小藍在某個位置，而他上、下、左、右中有一個位置的高度（嚴格）低于目前的高度，小藍就可以滑過去，滑動距離為 1 。
如果小藍在某個位置，而他上、下、左、右中所有位置的高度都大于等于目前的高度，小藍的滑行就結束了。
小藍不能滑出矩陣所表示的場地。
小藍可以任意選擇一個位置開始滑行，請問小藍最多能滑行多遠距離。
輸入格式
輸入第一行包含兩個整數 n, m，用一個空格分隔。
接下來 n 行，每行包含 m 個整數，相鄰整數之間用一個空格分隔，依次表示每個位置的高度。
輸出格式
輸出一行包含一個整數，表示答案。
樣例輸入
4 5
1 4 6 3 1
11 8 7 3 1
9 4 5 2 1
1 3 2 2 1
樣例輸出
7
樣例說明
滑行的位置一次為 (2, 1), (2, 2), (2, 3), (3, 3), (3, 2), (4, 2), (4, 3)。
評測用例規模與約定
對于 30 % 30\% 30% 評測用例， 1 < = n < = 20 1 <= n <= 20 1<=n<=20， 1 < = m < = 20 1 <= m <= 20 1<=m<=20， 0 < = 高度 < = 100 0 <= 高度 <= 100 0<=高度<=100。
對于所有評測用例， 1 < = n < = 100 1 <= n <= 100 1<=n<=100， 1 < = m < = 100 1 <= m <= 100 1<=m<=100， 0 < = 高度 < = 10000 0 <= 高度 <= 10000 0<=高度<=10000。
參考答案
經典的記憶化搜尋題，記得學校OJ裡好像有這個題？
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n, m;
int num[105][105] = {0};
int dp[105][105] = {0};
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0},{-1, 0}};
int dfs(int i, int j) {
if (dp[i][j] != -1) return dp[i][j];
int ret = 1;
for (int k = 0; k < 4; k++) {
int x = i + dir[k][0];
int y = j + dir[k][1];
if (x >= 1 && x <= n && y >= 1 && y <= m && num[x][y] < num[i][j]) {
ret = max(ret, dfs(x, y) + 1);
}
}
dp[i][j] = ret;
return dp[i][j];
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> num[i][j];
dp[i][j] = -1;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ans = max(ans, dfs(i, j));
}
}
cout << ans << endl;
return 0;
}
10. 區間最小值
問題描述
小藍有一個序列 a[1], a[2], …, a[n]。
給定一個正整數 k，請問對于每一個 1 到 n 之間的序号 i，a[i-k], a[i-k+1], …, a[i+k] 這 2k+1 個數中的最小值是多少？當某個下标超過 1 到 n 的範圍時，數不存在，求最小值時隻取存在的那些值。
輸入格式
輸入的第一行包含一整數 n。
第二行包含 n 個整數，分别表示 a[1], a[2], …, a[n]。
第三行包含一個整數 k 。
輸出格式
輸出一行，包含 n 個整數，分别表示對于每個序号求得的最小值。
樣例輸入
5
5 2 7 4 3
1
樣例輸出
2 2 2 3 3
評測用例規模與約定
對于 30 % 30\% 30% 的評測用例， 1 < = n < = 1000 1 <= n <= 1000 1<=n<=1000， 1 < = a [ i ] < = 1000 1 <= a[i] <= 1000 1<=a[i]<=1000。
對于 50 % 50\% 50% 的評測用例， 1 < = n < = 10000 1 <= n <= 10000 1<=n<=10000， 1 < = a [ i ] < = 10000 1 <= a[i] <= 10000 1<=a[i]<=10000。
對于所有評測用例， 1 < = n < = 1000000 1 <= n <= 1000000 1<=n<=1000000， 1 < = a [ i ] < = 1000000 1 <= a[i] <= 1000000 1<=a[i]<=1000000。
參考答案
經典闆子題
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e6 + 10, M = 20;
int n, k, t;
int q[N];
int f[N][M];
int query(int l, int r) {
int len = log(r - l + 1) / log(2);
int x = f[l][len], y = f[r - (1 << len) + 1][len];
return q[x] > q[y] ? y : x;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &q[i]);
cin >> k;
t = log(n) / log(2);
for (int j = 0; j <= t; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if (!j) f[i][j] = i;
else {
int l = f[i][j - 1], r = f[i + (1 << (j - 1))][j - 1];
if (q[l] > q[r]) f[i][j] = r;
else f[i][j] = l;
}
}
}
int l, r;
for (int i = 1; i <= n; i++) {
l = max(1, i - k), r = min(n, i + k);
cout << q[query(l, r)] << " ";
}
cout << endl;
return 0;
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)