一個小時兩道題，感覺難度也沒有傳說中的那么大，第二題稍微卡了一會，但是還是做完了
第一題
題意
有一個長度為n的全是小寫字母的字串，有m個要匹配的字串，問一共能匹配多少次，
例如ababa，2個匹配字串ab和aba，共能匹配4次，ab2次，aba兩次，
資料范圍n和m為1e5，匹配字串長度為[2,10]，
分析
因為匹配字串長度很短，因此完全可以計算所有的長度為[2,10]的子串的個數，然后用map來存，然后將m個匹配字串的個數相加即可，
參考代碼
#include <cstdio>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int n, m;
unordered_map<string, int> M;
string s, t;
int main() {
cin >> n >> m;
cin >> s;
int len = s.length();
for (int i=0; i<len; ++i) {
for (int j=2; j<=10 && i+j-1<len; ++j) {
M[s.substr(i, j)]++;
}
}
int ans = 0;
for (int i=0; i<m; ++i) {
cin >> t;
ans += M[t];
}
cout << ans << endl;
return 0;
}
第二題
題意
給一個矩陣，其中值為-1的部分需要替換，如果為-1的部分上下左右相連可以組成連通塊，每個連通塊中的值都應該被替換成這與這個連通塊直接相連的非-1部分的平均值向下取整，
例如：
5 4
0 8 -1 0
0 0 8 0
0 8 8 0
0 8 0 -1
0 -1 -1 0
輸出：
0 8 5 0
0 0 8 0
0 8 8 0
0 8 0 0
0 2 2 0
矩陣中有三個連通塊：
第一個：{(1,3)}，與其直接相連的數有{8, 8, 0}，求平均向下取整為5
第二個：{(4,4)}，與其直接相連的數有{0, 0, 0}，求平均向下取整為0
第三個：{(5,2), {5,3)}，與其直接相連的數有{0, 8, 8, 0}，求平均向下取整為2
分析
第一步肯定是先求連通塊，然后給連通塊編號，然后遍歷每一個非連通塊的值，判斷其是否屬于某一個連通塊，并用sum和num計算每個連通塊周圍非-1的總和，以及個數，
參考代碼
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
int a[1005][1005];
int id[1005][1005];
int vis[1005][1005];
int num[1000005];
int sum[1000005];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool judge(int x, int y) {
if (1<=x && x<=n && 1<=y && y<=m) return true;
return false;
}
void dfs(int x, int y, int _id) {
vis[x][y] = 1;
id[x][y] = _id;
for (int i=0; i<4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (judge(nx, ny) && !vis[nx][ny] && a[nx][ny]==-1) {
dfs(nx, ny, _id);
}
}
}
int main() {
scanf("%d%d", &n, &m);
memset(sum, 0, sizeof(sum));
memset(num, 0, sizeof(num));
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
id[i][j] = vis[i][j] = 0;
scanf("%d", &a[i][j]);
}
}
// 求連通塊，并編號
int __id = 0;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
if (a[i][j]==-1 && !vis[i][j]) {
__id++;
dfs(i, j, __id);
}
}
}
// 計算連通塊周圍非-1的數量以及總和
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
if (a[i][j] != -1) {
int idd[4];
idd[0] = idd[1] = idd[2] = idd[3] = -1;
// 判斷是否屬于上下左右的連通塊，如果屬于則累加和以及個數
// 注意有可能出現上下左右其中幾個是同一個連通塊，需要去重
for (int k=0; k<4; ++k) {
int nx = i + dx[k];
int ny = j + dy[k];
if (judge(nx, ny) && a[nx][ny]==-1) {
bool flag = true;
for (int l=0; l<k; ++l) {
if (idd[l]!=-1 && idd[l]==id[nx][ny]) {
flag = false;
break;
}
}
if (!flag) continue;
idd[k] = id[nx][ny];
sum[id[nx][ny]] += a[i][j];
num[id[nx][ny]]++;
}
}
}
}
}
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
if (a[i][j] == -1) {
if (num[id[i][j]] == 0)
printf("0 ");
else
printf("%d ", sum[id[i][j]] / num[id[i][j]]);
} else {
printf("%d ", a[i][j]);
}
}
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/26946.html
標籤：其他
上一篇：暴力DP背包問題巧解...2020數學建模大賽B題...穿越沙漠
下一篇：Canvas悟空推箱子