SUST_ACM_2019届暑期ACM集训热身赛题解
生活随笔
收集整理的這篇文章主要介紹了
SUST_ACM_2019届暑期ACM集训热身赛题解
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
問題A:Hello SUST!
知識點：基本輸入輸出
C/C++：
1 #include <stdio.h>2 3 int main() {4 int n;5 scanf("%d", &n);6 while(n --) {7 printf("Hello SUST!\n");8 }9 return 0; 10 }View Code
問題B:計算A+B
知識點：基本輸入輸出
C/C++：
1 #include <cstdio> 2 3 int main() { 4 int a, b; 5 while(~scanf("%d %d", &a, &b)) { 6 printf("%d\n", a + b); 7 } 8 return 0; 9 }View Code
問題C:
知識點：基本輸入輸出
C/C++：
1 #include <cstdio> 2 3 int main() { 4 int n; 5 while(scanf("%d", &n) && n) { 6 printf("%d\n", n * (n + 1) / 2); 7 } 8 return 0; 9 }View Code
問題D:
知識點：遞推
C/C++：
1 #include <cstdio> 2 using namespace std; 3 4 const int maxn = 20 + 5; 5 typedef long long ll; 6 ll ans[maxn]; 7 int t, n; 8 9 int main() { 10 ans[0] = ans[1] = 1; 11 for(int i = 2; i < maxn; i ++) { 12 ans[i] = ans[i - 1] + ans[i - 2]; 13 } 14 scanf("%d", &t); 15 while(t --) { 16 scanf("%d", &n); 17 printf("%lld\n", ans[n]); 18 } 19 return 0; 20 }View Code
問題E:
知識點：排序
C/C++：
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 10 + 5; 6 double score[maxn]; 7 8 bool cmp(const double &a, const double &b) { 9 return a > b; 10 } 11 12 int main() { 13 int t, n, m; 14 scanf("%d", &t); 15 while(t --) { 16 scanf("%d %d", &n, &m); 17 for(int i = 0; i < n; i ++) scanf("%lf", &score[i]); 18 // sort(score, score + n, cmp);//可用冒泡排序代替 19 // /* 20 for(int i = 0; i < n - 1; i ++) { 21 for(int j = 0; j < n - 1 - i; j ++) { 22 if(score[j + 1] > score[j]) { 23 double temp = score[j]; 24 score[j] = score[j + 1]; 25 score[j + 1] = temp; 26 } 27 } 28 } 29 // */ 30 double ans = 0.0; 31 for(int i = 0; i < m; i ++) { 32 ans += score[i]; 33 } 34 printf("%.2f\n", ans / m * 1.0); 35 } 36 return 0; 37 }View Code
問題F:
知識點：循環語句和判斷語句
C/C++：
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 5 char G[3][3]; 6 bool ans; 7 8 int main() { 9 int t, flag; 10 scanf("%d", &t); 11 while(t --) { 12 ans = false; 13 for(int i = 0; i < 3; i ++) { 14 scanf("%s", G[i]); 15 } 16 if((G[0][0] == '0' && G[1][1] == '0' && G[2][2] == '0') || (G[0][2] == '0' && G[1][1] == '0' && G[2][0] == '0')) 17 ans = true;//檢查斜向true 18 if(!ans) { 19 for(int i = 0; i < 3; i ++) { 20 flag = 0; 21 for(int j = 0; j < 3; j ++) { 22 if(G[i][j] == '0') flag ++; 23 } 24 if(flag == 3) { 25 ans = true; 26 break; 27 }//檢查橫向 28 flag = 0; 29 for(int j = 0; j < 3; j ++) { 30 if(G[j][i] == '0') flag ++; 31 }//檢查縱向 32 if(flag == 3) { 33 ans = true; 34 break; 35 } 36 } 37 } 38 if(ans) printf("Yes\n"); 39 else printf("No\n"); 40 } 41 return 0; 42 }View Code
問題G:
知識點：字符串存儲
C/C++：
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 5 char str[8][20] = { 6 "Monday", 7 "Tuesday", 8 "Wednesday", 9 "Thursday", 10 "Friday", 11 "Saturday", 12 "Sunday" 13 }; 14 15 int main() { 16 int n; 17 while(scanf("%d", &n) && n) { 18 if(n <= 7) 19 printf("%s\n", str[n - 1]); 20 } 21 return 0; 22 }View Code
問題H:
知識點：循環語句
C/C++：
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 5 const int maxn = 100; 6 int value[4] = {2, 3, 5, 10}; 7 bool vis[maxn]; 8 9 int main() { 10 int n; 11 for(int i = 0; i <= 2; i ++) { 12 for(int j = 0; j <= 2; j ++) { 13 for(int k = 0; k <= 2; k ++) { 14 for(int p = 0; p <= 2; p ++) { 15 vis[i * value[0] + j * value[1] + k * value[2] + p * value[3]] = true; 16 } 17 } 18 } 19 } 20 while(scanf("%d", &n) && n) { 21 if(vis[n]) printf("Y\n"); 22 else printf("N\n"); 23 } 24 return 0; 25 }View Code
問題I:
知識點：題目要判斷三維空間內四個點是否共面，則只需知道由四個點組成的三個向量是否共面即可知道答案。
我們知道兩個向量a, b,?的向量積等于垂直于他們所在平面的空間向量c,如果c與另一個向量d垂直，那我們就可以證明a，b，c三向量共面。
我們可以利用矩陣(行列式)計算出c向量，再與d進行點乘，判定結果是否為零即可(兩向量平行，內積為零)。
C/C++：
1 #include <cstdio> 2 #include <cstdlib> 3 using namespace std; 4 5 struct node{ 6 int x, y, z; 7 } a[4], b[3]; 8 9 bool plane() { 10 bool ret = false; 11 if(b[0].x * (b[1].y * b[2].z - b[1].z * b[2].y) - b[1].x * (b[0].y * b[2].z - b[0].z * b[2].y) + b[2].x * (b[0].y * b[1].z - b[0].z * b[1].y) == 0) 12 ret = true; 13 return ret; 14 } 15 16 int main() 17 { 18 int T, day = 1; 19 scanf("%d", &T); 20 while(T--) { 21 for(int i = 0; i < 4; i ++) { 22 scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z); 23 } 24 for(int i = 0; i < 3; i ++) { 25 b[i].x = a[i + 1].x - a[i].x; 26 b[i].y = a[i + 1].y - a[i].y; 27 b[i].z = a[i + 1].z - a[i].z; 28 } 29 if(plane()) 30 printf("Day #%d: Yes\n", day); 31 else 32 printf("Day #%d: No\n", day); 33 day ++; 34 } 35 return 0; 36 }View Code
問題J:
題意：
從L走到C的最短路dist是否小于k？小于k的話從L到C路徑長度等于dist的不全重復的路徑有幾條？
思路：
由于DFS求解最短路之緩慢，所以我們可以先用BFS算出最短路，判斷可行之后再用DFS求出滿足條件的條數即可。在執行DFS時，我們先從起點出發，任意選擇其中一條路并且一直走到不滿足題解的狀態時我們回退到上一個可以繼續往前走的狀態繼續往前走，往前走的時候記得標記走過的路，往回走的時候記得取消標記，這樣可以保證所有路都被找到并且沒有重復，實現起來也比較簡便。
C/C++：
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <cmath> 5 using namespace std; 6 7 typedef pair<int, int> pii; 8 const int maxn = 1e3 + 5; 9 int n, m, k, step, ans, Dist; 10 char G[maxn][maxn]; 11 int dist[maxn][maxn]; 12 bool vis[maxn][maxn]; 13 pii B, E, now, Next; 14 /* 15 這里的pair完全可以用結構體代替 16 17 pair<int, int> 可以看作是一個類似于結構體的寄存器 18 比如 struct P { 19 int first, second; 20 }now; 21 可以用now.first, now.second訪問這個變量的兩個值。 22 也可以申明pair<int, int>類型的數組，也就相當于struct P array[size]; 23 */ 24 int bfs(int x, int y) { 25 memset(vis, false, sizeof vis); 26 memset(dist, 0, sizeof dist); 27 queue <pii> Q; 28 Q.push(make_pair(x, y)); 29 dist[x][y] = 0; 30 while(!Q.empty()) { 31 pii now = Q.front(); 32 Q.pop(); 33 if(now.first == E.first && now.second == E.second) return dist[now.first][now.second]; 34 for(int dx = -1; dx <= 1; dx ++) { 35 for(int dy = -1; dy <= 1; dy ++) { 36 if(abs(dx - dy) == 1) { 37 Next.first = now.first + dx; 38 Next.second = now.second + dy; 39 if(!vis[Next.first][Next.second] && Next.first >= 0 && Next.first < n && Next.second >= 0 && Next.second < m && G[Next.first][Next.second] != '#') { 40 dist[Next.first][Next.second] = dist[now.first][now.second] + 1; 41 Q.push(make_pair(Next.first, Next.second)); 42 vis[Next.first][Next.second] = true; 43 } 44 } 45 } 46 } 47 } 48 return -1; 49 } 50 51 void dfs(pii B, pii E, int D) { 52 if(B.first == E.first && B.second == E.second) { 53 if(D == ans) step ++;//如果當前訪問的結點為終點且到起點的距離為最短路則step++ 54 } 55 if(D > ans) return;//如果當前路徑在D步內不能到達終點則回退，換下一條路 56 for(int i = -1; i <= 1; i ++) { 57 for(int j = -1; j <= 1; j ++) { 58 if(abs(i - j) == 1) {//由于只能從上下左右四個方向走，所以可以找出這樣的關系式，讀者可以自行在草稿紙上進行驗證 59 if(B.first + i >= 0 && B.first + i < n && B.second + j >= 0 && B.second + j < m) {//不越界 60 if(G[B.first + i][B.second + j] != '#' && !vis[B.first + i][B.second + j]) {//判斷是否沒有訪問過且不為石頭 61 vis[B.first + i][B.second + j] = true; 62 dfs(make_pair(B.first + i, B.second + j), E, D + 1);//遞歸走下一步 63 vis[B.first + i][B.second + j] = false;//記得修復狀態 64 } 65 } 66 } 67 } 68 } 69 } 70 71 int main() { 72 int t, Case = 0; 73 scanf("%d", &t); 74 while(t --) { 75 step = 0; 76 Dist = 0x3f3f3f3f; 77 scanf("%d %d %d", &n, &m, &k); 78 for(int i = 0; i < n; i ++) scanf("%s", G[i]); 79 for(int i = 0; i < n; i ++) { 80 for(int j = 0; j < m; j ++) { 81 if(G[i][j] == 'L') B = make_pair(i, j); 82 if(G[i][j] == 'C') E = make_pair(i, j); 83 } 84 } 85 ans = bfs(B.first, B.second); 86 if(ans > k) ans = -1; 87 printf("Case #%d: %d ", ++Case, ans); 88 if(ans != -1) { 89 memset(vis, false, sizeof vis); 90 dfs(B, E, 0); 91 printf("%d", step); 92 } 93 printf("\n"); 94 } 95 return 0; 96 }View Code
?
轉載于:https://www.cnblogs.com/bianjunting/p/11164316.html
總結
以上是生活随笔為你收集整理的SUST_ACM_2019届暑期ACM集训热身赛题解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 你知道dos和cmd之间的关系以及区别吗
- 下一篇： 求一个好听的红茶名字！