第一題
題面【深搜缀踪，搜索有多少個(gè)連通區(qū)域】：
世界杯球場(chǎng)专缠，能容納M*N個(gè)球迷瘪板。官方想統(tǒng)計(jì)觀眾中有多少個(gè)球隊(duì)的球迷群體鹅龄，最大的群體人數(shù)是多少揩慕？
球迷群體選座有以下特征：
- 同球隊(duì)球迷會(huì)選擇相鄰座位，不同球隊(duì)會(huì)選擇不相鄰的座位扮休。（注解：相鄰包括前后左右迎卤、斜對(duì)角相鄰，即8個(gè)搜索方向）玷坠；
- 在M*N個(gè)數(shù)中蜗搔，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;
}
第二題
題面【區(qū)間合并問題樟凄，不知道為什么只通過20%】：
有多個(gè)不同區(qū)間，區(qū)間之間可能存在重疊兄渺，求出合并后的區(qū)間斷不同。
輸入一個(gè)整數(shù)m，代表有m行輸入?yún)^(qū)間溶耘，每行包括數(shù)量不定的區(qū)間
這題得處理輸入數(shù)據(jù)二拐，因此用Python寫更方便一點(diǎn)
輸入：
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)
第三題
應(yīng)該是背包問題
第四題
不太會(huì)
第五題
題面【貪心活動(dòng)安排問題】：
- 輸入一個(gè)n，代表有幾個(gè)直播節(jié)目凳兵；
- 輸入一個(gè)m百新，代表每天有幾個(gè)小時(shí)；【即現(xiàn)在每天不是24小時(shí)庐扫，而是m小時(shí)】
- 輸入每個(gè)直播的起始時(shí)間饭望、結(jié)束時(shí)間仗哨；
有兩點(diǎn)注意事項(xiàng)
- 首先要對(duì)數(shù)據(jù)中主播開始時(shí)間大于結(jié)束時(shí)間的數(shù)據(jù)進(jìn)行處理（即處理跨天數(shù)據(jù)），將跨天數(shù)據(jù)的結(jié)束時(shí)間加上m铅辞；
- 注意題目中描述的“一天”時(shí)間的范圍厌漂，是從選擇的第一個(gè)活動(dòng)的起始時(shí)間算起，比如第一個(gè)直播開始時(shí)間是3點(diǎn)斟珊，則題目中的一天指的是今天3點(diǎn)到明天3點(diǎn)苇倡，而不是今天0點(diǎn)到明天0點(diǎn)；
輸入：
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;
}
