第一题
题面【深搜，搜索有多少个连通区域】：
世界杯球场，能容纳M*N个球迷。官方想统计观众中有多少个球队的球迷群体，最大的群体人数是多少？
球迷群体选座有以下特征：
- 同球队球迷会选择相邻座位，不同球队会选择不相邻的座位。（注解：相邻包括前后左右、斜对角相邻，即8个搜索方向）；
- 在M*N个数中，0代表没人，1代表有人；
输入：
10,10
0,0,0,0,0,0,0,0,0,0
0,0,0,1,1,0,1,0,0,0
0,1,0,0,0,0,0,1,0,1
1,0,0,0,0,0,0,0,1,1
0,0,0,1,1,1,0,0,0,1
0,0,0,0,0,0,1,0,1,1
0,1,1,0,0,0,0,0,0,0
0,0,0,1,0,1,0,0,0,0
0,0,1,0,0,1,0,0,0,0
0,1,0,0,0,0,0,0,0,0
输出：
6, 8
代码：
#include <iostream>
#include <string.h>
#include <algorithm>
#define CLEAR(name, init) memset(name, init, sizeof(name));
const int MAXN = (int) 1e3 + 5;
using namespace std;
int n, m;
int maxSize;
bool square[MAXN][MAXN];
bool vis[MAXN][MAXN];
int size;
int dir[8][2] = {{-1, 0},
{-1, 1},
{-1, -1},
{0, 1},
{0, -1},
{1, 0},
{1, 1},
{1, -1}};
void dfs(int x, int y, int depth) {
if (x < 0 || y < 0 || x >= n || y >= m) return;
if (vis[x][y] || !square[x][y]) return;
vis[x][y] = true;
size++;
maxSize = max(size, maxSize);
for (int i = 0; i < 8; i++) {
dfs(x + dir[i][0], y + dir[i][1], depth + 1);
}
}
int main() {
while (~scanf("%d,%d", &n, &m)) {
CLEAR(vis, 0);
maxSize = 0;
for (int i = 0; i < n; i++) {
char line[MAXN << 1];
scanf("%s", line);
for (int j = 0; line[j]; j++) {
if (line[j] == ',') continue;
if (line[j] == '0') {
square[i][j >> 1] = false;
} else {
square[i][j >> 1] = true;
}
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!vis[i][j] && square[i][j]) {
size = 0;
cnt++;
dfs(i, j, size);
}
}
}
cout << cnt << ',' << maxSize << endl;
}
return 0;
}
第二题
题面【区间合并问题，不知道为什么只通过20%】：
有多个不同区间，区间之间可能存在重叠，求出合并后的区间断。
输入一个整数m，代表有m行输入区间，每行包括数量不定的区间
这题得处理输入数据，因此用Python写更方便一点
输入：
3
1,10;32,45
78,94;5,16
80,100;200,220;16,32
输出：
1,45;78,100;200,220
代码：
# coding=utf-8
import sys
if __name__ == "__main__":
m = int(sys.stdin.readline().strip())
if m < 1:
print(None)
else:
result = []
for i in range(m):
line = sys.stdin.readline().strip().split(';')
for query in line:
tmp = query.split(',')
min_v = min(int(tmp[0]), int(tmp[1]))
max_v = max(int(tmp[0]), int(tmp[1]))
result.append((min_v, max_v))
result.sort()
# print(result)
merge = []
current = [result[0][0], result[0][1]]
for i in range(1, len(result)):
if current[0] <= result[i][0] <= current[1]:
if result[i][1] > current[1]:
current[1] = result[i][1]
else:
merge.append((current[0], current[1]))
current[0] = result[i][0]
current[1] = result[i][1]
merge.append((current[0], current[1]))
print(merge)
第三题
应该是背包问题
第四题
不太会
第五题
题面【贪心活动安排问题】：
- 输入一个n，代表有几个直播节目；
- 输入一个m，代表每天有几个小时；【即现在每天不是24小时，而是m小时】
- 输入每个直播的起始时间、结束时间；
有两点注意事项
- 首先要对数据中主播开始时间大于结束时间的数据进行处理（即处理跨天数据），将跨天数据的结束时间加上m；
- 注意题目中描述的“一天”时间的范围，是从选择的第一个活动的起始时间算起，比如第一个直播开始时间是3点，则题目中的一天指的是今天3点到明天3点，而不是今天0点到明天0点；
输入：
3
10
0 3 3 7 7 0
输出：
3
代码：
#include <iostream>
#include <algorithm>
using namespace std;
struct activity {
int si, ti;
} record[100001];
bool cmp(activity a, activity b) {
return a.ti < b.ti;
}
int main() {
int m, n;
while (cin >> n >> m) {
if (n < 1 || m < 2)
cout << 0 << endl;
else {
for (int i = 0; i < n; ++i) {
cin >> record[i].si >> record[i].ti;
if (record[i].si > record[i].ti)
record[i].ti += m;
}
sort(record, record + n, cmp);
int count = 1;
int last = 0;
int limit = record[last].si + m;
for (int i = 1; i < n; i++) {
if (record[i].si >= record[last].ti && record[i].ti <= limit) {
last = i;
count++;
}
}
cout << count << endl;
}
}
return 0;
}
