2015程序设计实习之上机练习题
01:浮点数求高精度幂
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <cstdio> #include <cstring> #include <iostream> using namespace std; string R; int n; class D{ int l, pos; int a[1005]; public: D(){ l = 1; pos = 0; memset(a, 0, sizeof(a)); } D(string x){ l = pos = 0; for(int i = x.length() - 1; i >= 0; i--) if(x[i] == '.')pos = x.length() - i - 1; else a[++l] = x[i] - '0'; } int& operator [](int x){ return a[x]; } friend D operator *(D a, D b){ D c; for(int i = 1; i <= a.l; i++) for(int j = 1; j <= b.l; j++) c[i + j - 1] += a[i] * b[j]; c.l = a.l + b.l - 1; for(int i = 1; i <= c.l; i++) if(c[i] >= 10) { c[i + 1] += c[i] / 10; c[i] %= 10; if(i == c.l)c.l++; } c.pos = a.pos + b.pos; return c; } D operator ^(int n){ D ans = D("1"); while(n--) ans = ans * (*this); return ans; } friend ostream& operator <<(ostream& os, D a){ string ans = ""; bool zero = 1; for(int i = a.l; i; i--) { ans = ans + char(a[i] + '0'); if(a[i])zero = 0; if(i - 1 == a.pos) { ans += '.'; if(zero)ans = "."; } } int l = a.l; while(ans[l] == '0') { ans.erase(l); l--; } if(ans[l] == '.') { ans.erase(l); l--; } cout << ans; return os; } }; int main() { while(cin >> R >> n) cout << (D(R) ^ n) << endl; return 0; } |
02:Integer Inquiry
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <cstdio> #include <cstring> #include <iostream> using namespace std; struct Int{ int l; int a[1005]; public: Int(){ l = 1; memset(a, 0, sizeof(a)); } Int(string x){ l = x.size(); memset(a, 0, sizeof(a)); for(int i = l - 1; i >= 0; i--) a[l - i] = x[i] - '0'; } int& operator [](int x){ return a[x]; } friend ostream& operator << (ostream& os, Int a){ for(int i = a.l; i; i--) cout << a[i]; return os; } friend Int operator +(Int a, Int b){ Int c; c.l = max(a.l, b.l); for(int i = 1; i <= c.l; i++) c[i] = a[i] + b[i]; for(int i = 1; i <= c.l; i++) if(c[i] >= 10) { if(i == c.l)c.l++; c[i + 1] += c[i] / 10; c[i] %= 10; } return c; } }ans; int main() { string str; ans = Int("0"); while(cin >> str) { if(str == "0")break; ans = ans + Int(str); } cout << ans << endl; return 0; } |
03:Communication System
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int t, n; int m[105], b[105][105], p[105][105]; double ans; double cal(int x) { int sum = 0; for(int i = 1; i <= n; i++) { int mn = inf; for(int j = 1; j <= m[i]; j++) if(b[i][j] >= x) mn = min(mn, p[i][j]); if(mn == inf)return 0; sum += mn; } return (double)x / sum; } int main() { cin >> t; while(t--) { cin >> n; for(int i = 1; i <= n; i++) { cin >> m[i]; for(int j = 1; j <= m[i]; j++) cin >> b[i][j] >> p[i][j]; } ans = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m[i]; j++) ans = max(ans, cal(b[i][j])); printf("%.3lf\n", ans); } return 0; } |
04:判断闰年
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int n; int main() { cin >> n; if(!(n % 400) || ((n % 100) && !(n % 4)))puts("Y"); else puts("N"); return 0; } |
05:生理周期
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int p, e, I, d; int main() { cin >> p >> e >> I >> d; for(int i = d + 1; ; i++) if(i % 23 == p % 23 && i % 28 == e % 28 && i % 33 == I % 33) { cout << i - d << endl; break; } return 0; } |
06:完美立方
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int n; int p[105]; int main() { cin >> n; for(int i = 1; i <= 100; i++) p[i] = i * i * i; for(int a = 2; a <= n; a++) for(int b = 2; b <= a; b++) for(int c = b; c <= a; c++) for(int d = c; d <= a; d++) if(p[a] == p[b] + p[c] + p[d]) printf("Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d); return 0; } |
07:画家问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 #define dfsnxt(x, y, num) y == n? dfs(x + 1, 1, num): dfs(x, y + 1, num) using namespace std; bool c[15][15]; int n, ans = inf; string a[15]; void print(int x, int y) { c[x][y] ^= 1; if(x > 1)c[x - 1][y] ^= 1; if(x < n)c[x + 1][y] ^= 1; if(y > 1)c[x][y - 1] ^= 1; if(y < n)c[x][y + 1] ^= 1; } void dfs(int x, int y, int num) { if(num >= ans)return; if(x == 1) { dfsnxt(x, y, num); print(x, y); dfsnxt(x, y, num + 1); print(x, y); } else if(x == n + 1) { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(!c[i][j])return; ans = num; } else { if(!c[x - 1][y]) { print(x, y); dfsnxt(x, y, num + 1); print(x, y); } else dfsnxt(x, y, num); } } int main() { cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(a[i - 1][j - 1] == 'w') c[i][j] = 0; else c[i][j] = 1; dfs(1, 1, 0); if(ans == inf )puts("inf"); else cout << ans <<endl; return 0; } |
08:恼人的青蛙
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; int r, c, n; struct data{ int x, y; }p[5005]; bool a[5005][5005]; bool operator<(data a, data b) { if(a.x == b.x)return a.y < b.y; return a.x < b.x; } inline bool check(int x, int y) { if(x < 1 || y < 1 || x > r || y > c)return 0; return 1; } int main() { cin >> r >> c >> n; for(int i = 1; i <= n; i++) { scanf("%d%d", &p[i].x, &p[i].y); a[p[i].x][p[i].y] = 1; } int ans = 0; sort(p + 1, p + n + 1); for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) { int x = p[i].x, y = p[i].y; int dx = p[j].x - x, dy = p[j].y - y; if(x + dx * ans > r)break; if(check(x - dx, y - dy))continue; if(check(x + dx * ans, y + dy * ans)) { int cnt = 0, flag = 1; while(1) { x += dx; y += dy; if(!check(x, y))break; else if(a[x][y])cnt++; else { flag = 0; break; } } if(flag)ans = max(ans, cnt); } } if(ans <= 2)puts("0"); else cout << ans + 1 << endl; return 0; } |
09:放苹果
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; int t; int m, n, f[25][25]; void dp() { for(int i = 0; i <= 10; i++) for(int j = 1; j <= 10; j++) if(i == 0 || j == 1)f[i][j] = 1; else if(i >= j)f[i][j] = f[i][j - 1] + f[i - j][j]; else f[i][j] = f[i][j - 1]; } int main() { dp(); cin >> t; while(t--) { cin >> m >> n; cout << f[m][n] << endl; } return 0; } |
10:古代密码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; string a, b; int mp1[30], mp2[30]; int main() { cin >> a >> b; for(int i = 0; i < a.size(); i++) mp1[a[i] - 'A']++; for(int i = 0; i < b.size(); i++) mp2[b[i] - 'A']++; sort(mp1, mp1 + 26); sort(mp2, mp2 + 26); bool equ = 1; for(int i = 0; i < 26; i++) if(mp1[i] != mp2[i])equ = 0; if(equ)puts("YES"); else puts("NO"); return 0; } |
11:棋盘问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 #define dfsnxt(x, y, k) y == n - 1? dfs(x + 1, 0, k): dfs(x, y + 1, k) using namespace std; int n, K, ans; string a[10]; bool r[10], c[10]; void dfs(int x, int y, int k) { if(k == K) { ans++; return; } if(x == n)return; dfsnxt(x, y, k); if(a[x][y] == '#' && !r[x] && !c[y]) { r[x] = c[y] = 1; dfsnxt(x, y, k + 1); r[x] = c[y] = 0; } } int main() { while(cin >> n >> K) { if(n == -1)break; for(int i = 0; i < n; i++) cin >> a[i]; ans = 0; dfs(0, 0, 0); cout << ans <<endl; } return 0; } |
12:求平均年龄
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; int n; int main() { cin >> n; double x, ave = 0; for(int i = 1; i <= n; i++) { cin >> x; ave += x; } printf("%.2lf\n", ave / n); return 0; } |
13:拦截导弹
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; int n, a[30], f[30]; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; int ans = 0; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) if(a[j] <= a[i]) f[j] = max(f[j], f[i] + 1); ans = max(ans, f[i]); } cout << ans + 1 << endl; return 0; } |
14:Flip Game
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 #define dfsnxt(x, y, num) y == 4? dfs(x + 1, 1, num): dfs(x, y + 1, num) using namespace std; bool c[5][5]; int ans = inf; string a[5]; void print(int x, int y) { c[x][y] ^= 1; if(x > 1)c[x - 1][y] ^= 1; if(x < 4)c[x + 1][y] ^= 1; if(y > 1)c[x][y - 1] ^= 1; if(y < 4)c[x][y + 1] ^= 1; } void dfs(int x, int y, int num) { if(num >= ans)return; if(x == 5) { for(int i = 1; i <= 4; i++) for(int j = 1; j <= 4; j++) if(c[i][j] != c[1][1])return; ans = num; } else { dfsnxt(x, y, num); print(x, y); dfsnxt(x, y, num + 1); print(x, y); } } int main() { for(int i = 0; i < 4; i++) cin >> a[i]; for(int i = 1; i <= 4; i++) for(int j = 1; j <= 4; j++) if(a[i - 1][j - 1] == 'w') c[i][j] = 0; else c[i][j] = 1; dfs(1, 1, 0); if(ans == inf )puts("Impossible"); else cout << ans <<endl; return 0; } |
15:最大子矩阵
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int n, a[105][105], s[105][105]; int main() { cin >> n; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { cin >> a[i][j]; s[i][j] = s[i][j - 1] + a[i][j]; } int ans = -inf; for(int l = 1; l <= n; l++) for(int r = l; r <= n; r++) { int sum = 0; for(int k = 1; k <= n; k++) { sum += s[k][r] - s[k][l - 1]; ans = max(ans, sum); if(sum < 0)sum = 0; } } cout << ans << endl; return 0; } |
16:Tour
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int n; double f[55][55]; struct data{ int x, y; }p[55]; double dis(data a, data b) { return sqrt((a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y)); } int main() { while(cin >> n) { for(int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y; memset(f, 127, sizeof(f)); f[1][1] = 0; for(int i = 1; i <= n; i++) for(int j = 1; j < i; j++) { f[i][j] = min(f[i][j], f[i - 1][j] + dis(p[i - 1], p[i])); f[i][i - 1] = min(f[i][i - 1], f[i - 1][j] + dis(p[j], p[i])); } printf("%.2lf\n", f[n][n-1] + dis(p[n-1], p[n])); } return 0; } |
17:石头剪刀布
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int n, na, nb; int cnt; int a[105], b[105]; int cmp(int a, int b) { if(a == b)return 0; if(a == 0 && b == 2)return 1; if(a == 2 && b == 5)return 1; if(a == 5 && b == 0)return 1; return -1; } int main() { cin >> n >> na >> nb; for(int i = 0; i < na; i++) cin >> a[i]; for(int i = 0; i < nb; i++) cin >> b[i]; for(int i = 0; i < n; i++) cnt += cmp(a[i % na], b[i % nb]); if(cnt < 0)puts("B"); else if(cnt > 0)puts("A"); else puts("draw"); return 0; } |
18:Eight
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <map> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; struct data{ int x, y; string a, ans; }q[1000005]; int head = 0, tail = 1; map<string, bool> mp; bool check(data x) { for(int i = 0; i < 8; i++) if(x.a[i] != (i + '1')) return 0; return 1; } void move(data a, int x, int y, int _x, int _y, char dir) { if(_x < 0 || _y < 0 || _x > 2 || _y > 2)return; data c = a; c.x = _x; c.y = _y; c.ans += dir; swap(c.a[x * 3 + y], c.a[_x * 3 + _y]); if(!mp[c.a]) { mp[c.a] = 1, q[tail++] = c; } } void bfs() { while(head != tail) { if(check(q[head])) { cout << q[head].ans << endl; return; } int x = q[head].x, y = q[head].y; move(q[head], x, y, x - 1, y, 'u'); move(q[head], x, y, x + 1, y, 'd'); move(q[head], x, y, x, y - 1, 'l'); move(q[head], x, y, x, y + 1, 'r'); head++; } } int main() { string str; for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) { cin >> str; q[0].a += str[0]; if(str[0] == 'x') q[0].x = i, q[0].y = j; } bfs(); return 0; } |
19:滑雪
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int r, c, ans; int h[105][105], f[105][105]; int xx[4] = {0, 0, 1, -1}, yy[4] = {1, -1, 0, 0}; int dfs(int x, int y) { if(x < 1 || y < 1 || x > r || y > c)return 0; if(f[x][y] != -1)return f[x][y]; f[x][y] = 1; for(int i = 0; i < 4; i++) { int tx = x + xx[i], ty = y + yy[i]; if(h[tx][ty] < h[x][y]) f[x][y] = max(f[x][y], dfs(tx,ty) + 1); } return f[x][y]; } int main() { memset(f, -1, sizeof(f)); cin >> r >> c; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) cin >> h[i][j]; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) if(f[i][j] == -1) ans=max(ans, dfs(i, j)); printf("%d\n", ans); return 0; } |
20:买房子
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; double tot, price; double n, K; int main() { cin >> n >> K; price = 200; tot = n; for(int i = 1; i <= 20; i++) if(tot >= price) { cout << i << endl; return 0; } else { tot += n; price = price * (1 + K / 100); } puts("Impossible"); return 0; } |
Subscribe
计数器 9794830
OI 课件=>
OI 课件=>