一个小时两道题，感觉难度也没有传说中的那么大，第二题稍微卡了一会，但是还是做完了

第一题

题意

有一个长度为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;
}