本文共 6274 字，大约阅读时间需要 20 分钟。
T1: 排序与输出
#include #include using namespace std;const int maxN = 100000 + 5;int a[maxN];int main() { freopen("carpet.in", "r", stdin); freopen("carpet.out", "w", stdout); int n; cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n, greater<>()); cout << a[0] * a[1]; return 0;}
T2: 比赛得分计算
#include #include using namespace std;int main() { freopen("volleyball.in", "r", stdin); freopen("volleyball.out", "w", stdout); char ch; int scoreA = 0, scoreB = 0; int round = 1; int cntA = 0, cntB = 0; while(cin >> ch) { if(ch == 'E') break; if(ch == 'A') scoreA++; else if(ch == 'B') scoreB++; if(round == 5) { if(scoreA >= 15 && scoreA - scoreB >= 2) { cntA++; break; } else if(scoreB >= 15 && scoreB - scoreA >= 2) { cntB++; break; } } else { if(scoreA >= 25 && scoreA - scoreB >= 2) { cntA++; scoreA = 0; scoreB = 0; round++; } else if(scoreB >= 25 && scoreB - scoreA >= 2) { cntB++; scoreA = 0; scoreB = 0; round++; } } } cout << cntA << ":" << cntB; return 0;}
T3: 石头问题
#include #include using namespace std;const int maxN = 105;int a[maxN];int f[maxN];int main() { freopen("stonehenge.in", "r", stdin); freopen("stonehenge.out", "w", stdout); int n; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } f[1] = a[1]; for(int i = 2; i <= n; i++) { if(f[i-2] + a[i] > f[i-1]) { f[i] = f[i-2] + a[i]; } else { f[i] = f[i-1]; } } cout << f[n]; return 0;}
T4: 最短路径问题
深度优先搜索解法
#include #include using namespace std;const int maxN = 105;char a[maxN][maxN];bool vis[maxN][maxN];int ans = INT_MAX;int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};int n;void dfs(int curRow, int curCol, int step) { if(n == curRow && n == curCol) { ans = min(ans, step); return; } for(int i = 0; i < 4; i++) { int nextRow = curRow + dir[i][0]; int nextCol = curCol + dir[i][1]; if(nextRow >= 1 && nextRow <= n && nextCol >= 1 && nextCol <= n && !vis[nextRow][nextCol] && a[nextRow][nextCol] != '#') { vis[nextRow][nextCol] = true; dfs(nextRow, nextCol, step + 1); vis[nextRow][nextCol] = false; } }}int main() { freopen("record.in", "r", stdin); freopen("record.out", "w", stdout); int p, q; cin >> n >> p >> q; for(int row = 1; row <= n; row++) { for(int col = 1; col <= n; col++) { a[row][col] = '.'; } } for(int i = 1; i <= p; i++) { int x, y; cin >> x >> y; a[x][y] = '#'; } vis[1][1] = true; dfs(1, 1, 1); if(ans == INT_MAX) { cout << -1; } else { cout << ans; } return 0;}
广度优先搜索解法
#include #include using namespace std;const int maxN = 105;bool notGo[maxN][maxN];vector > friCity[maxN][maxN];const int maxDays = 40005;vector > step[maxDays];int dis[maxN][maxN];int mv[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};int n, p, q;bool checkMin(int &x, int y) { return x > y ? x = y, true : false;}bool check(pair u) { return u.first >= 1 && u.first <= n && u.second >= 1 && u.second <= n && !notGo[u.first][u.second];}int main() { cin >> n >> p >> q; for(int i = 1; i <= p; i++) { int x, y; cin >> x >> y; notGo[x][y] = true; } for(int i = 1; i <= q; i++) { int a, b, c, d; cin >> a >> b >> c >> d; friCity[a][b].push_back(make_pair(c, d)); } step[1].push_back(make_pair(1, 1)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { dis[i][j] = maxDays; } } dis[1][1] = 1; int ans = -1; for(int i = 1; i < maxDays; i++) { for(auto v : step[i]) { if(dis[v.first][v.second] != i) continue; if(v.first == n && v.second == n) { ans = i; } for(int t = 0; t < 4; t++) { pair grid = make_pair(v.first + mv[t][0], v.second + mv[t][1]); if(!check(grid)) continue; int day = dis[v.first][v.second] + 1; if(checkMin(dis[grid.first][grid.second], day)) { step[day].push_back(grid); } } } } if(dis[n][n] == maxDays) { cout << -1; } else { cout << dis[n][n]; } return 0;}
迪杰特斯拉算法解法
#include #include using namespace std;const int maxN = 105;int dis[maxN][maxN];bool vis[maxN][maxN];bool notGo[maxN][maxN];int friCity[maxN][maxN];int N;int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int flyTo[maxN][2];struct node { int x; int y; int dist; node(int _x = 0, int _y = 0, int _dist = 0) : x(_x), y(_y), dist(_dist) {}};bool operator<(node a, node b) { return a.dist > b.dist;}void dijkstra() { for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { dis[i][j] = INT_MAX; } } priority_queue q; dis[1][1] = 1; q.push(node(1, 1, 1)); while(!q.empty()) { node p = q.top(); q.pop(); if(vis[p.x][p.y]) continue; vis[p.x][p.y] = true; for(int i = 0; i < 4; i++) { int vx = p.x + dir[i][0]; int vy = p.y + dir[i][1]; if(vx < 1 || vx > N || vy < 1 || vy > N || notGo[vx][vy]) continue; if(dis[p.x][p.y] + 1 < dis[vx][vy]) { dis[vx][vy] = dis[p.x][p.y] + 1; q.push(node(vx, vy, dis[vx][vy])); } } if(friCity[p.x][p.y] > 0) { int vx = flyTo[friCity[p.x][p.y]][0]; int vy = flyTo[friCity[p.x][p.y]][1]; if(dis[p.x][p.y] + 4 < dis[vx][vy]) { dis[vx][vy] = dis[p.x][p.y] + 4; q.push(node(vx, vy, dis[vx][vy])); } } }}int main() { freopen("record.in", "r", stdin); freopen("record.out", "w", stdout); int P, Q; cin >> N >> P >> Q; for(int i = 1; i <= P; i++) { int x, y; cin >> x >> y; notGo[x][y] = true; } for(int i = 1; i <= Q; i++) { int x, y, xx, yy; cin >> x >> y >> xx >> yy; friCity[x][y] = i; flyTo[i][0] = xx; flyTo[i][1] = yy; } dijkstra(); if(dis[N][N] == INT_MAX) { cout << -1; } else { cout << dis[N][N]; } return 0;}
转载地址：http://vfvk.baihongyu.com/