程序设计实习实验班2017作业(算法 作业1, 5)
bfs的时候多一维记录查克拉
|
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 |
#include <iostream> using namespace std; int n, m, T; string a[205]; struct data{ int x, y, step, energy; }q[400005]; int xx[4] = {0, 0, 1, -1}, yy[4] = {1, -1, 0, 0}; bool mp[205][205][15]; int bfs() { int head = 0, tail = 1; while(head != tail) { data now = q[head]; head++; for(int i = 0; i < 4; i++) { int x = now.x + xx[i], y = now.y + yy[i], energy = now.energy, step = now.step + 1; if(x < 0 || y < 0 || x == n || y == m)continue; if(a[x][y] == '#')energy --; if(energy < 0)continue; if(a[x][y] == '+')return step; if(!mp[x][y][energy]) { mp[x][y][energy] = 1; q[tail++] = (data){x, y, step, energy}; } } } return -1; } int main() { cin >> n >> m >> T; q[0].energy = T; for(int i = 0; i < n; i++) { cin >> a[i]; for(int j = 0; j < m; j++) if(a[i][j] == '@') q[0].x = i, q[0].y = j; } cout << bfs() << endl; return 0; } |
「poj1190」生日蛋糕/泰国佛塔
从下往上一层一层搜索，每一层枚举半径和高度（注意范围）
根据每一层半径和高度严格递减，进行一些剪枝：
1、剩下的若干层都放最小的圆柱，体积也不够
2、剩下的若干层都放最小的圆柱，得出的表面积比当前最优解劣
3、剩下的体积所需的最小表面积加上当前表面积比当前最优解劣
|
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 |
#include <map> #include <cmath> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int n, m, ans; int sv[25], ss[25]; void dfs(int v, int dep, int R, int H, int tot) { if(dep == 0) { if(v == 0 && tot < ans) ans = tot; return; } if(v < sv[dep] || tot + ss[dep] >= ans || tot + v / R * 2 >= ans) return; for(int r = R - 1; r >= dep; r--) for(int h = min(H - 1, (v - sv[dep - 1])/ r / r); h >= dep; h--) { int tmp = tot + 2 * r * h; if(dep == m)tmp += r * r; if(v - r * r * h >= 0) dfs(v - r * r * h, dep - 1, r, h, tmp); } } int main() { for(int i = 1; i <= 20; i++) { sv[i] = sv[i - 1] + i * i * i; ss[i] = ss[i - 1] + 2 * i * i; } while(cin >> n >> m) { ans = inf; dfs(n, m, sqrt(n) + 1, n + 1, 0); if(ans == inf)puts("0"); else cout << ans << endl; } return 0; } |
「Bailian4119」复杂的整数划分问题
令F1(i, j)为把i划分成j个正整数的方案数
1.划分出一个1,\(F1(i+1, j+1) += F1(i,j)\)
2.将当前所有划分加1,\(F1(i+j,j) += F1(i,j)\)
令F2(i, j)为把i划分成j个不同正整数的方案数
1.将当前所有划分加1，并划分出一个1,\(F2(i+j+1, j+1) += F2(i,j)\)
2.将当前所有划分加1,\(F2(i+j,j) += F2(i,j)\)
令F3(i, j)为把i划分成j个奇正整数的方案数
1.划分出一个1,\(F3(i+1, j+1) += F3(i,j)\)
2.将当前所有划分加2,\(F3(i+j+j,j) += F3(i,j)\)
|
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 |
#include <iostream> using namespace std; int n, m; int f1[55][55], f2[55][55], f3[55][55]; int main() { f1[0][0] = 1; for(int i = 0; i <= 50; i++) for(int j = 0; j <= i; j++) { if(i + j <= 50 && j != 0)f1[i + j][j] += f1[i][j]; if(i + 1 <= 50)f1[i + 1][j + 1] += f1[i][j]; } f2[0][0] = 1; for(int i = 0; i <= 50; i++) for(int j = 0; j <= i; j++) { if(i + j <= 50 && j != 0)f2[i + j][j] += f2[i][j]; if(i + j + 1 <= 50)f2[i + j + 1][j + 1] += f2[i][j]; } f3[0][0] = 1; for(int i = 0; i <= 50; i++) for(int j = 0; j <= i; j++) { if(i + j * 2 <= 50 && j != 0)f3[i + j * 2][j] += f3[i][j]; if(i + 1 <= 50)f3[i + 1][j + 1] += f3[i][j]; } while(cin >> n >> m) { int ans2 = 0, ans3 = 0; for(int i = 1; i <= n; i++) { ans2 += f2[n][i]; ans3 += f2[n][i]; } cout << f1[n][m] << endl; cout << ans2 << endl; cout << ans3 << endl; } return 0; } |
热血格斗场
经典set的应用
|
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<set> #include<cstdio> #include<iostream> using namespace std; int n; int main() { set<pair<int, int> >st; st.insert(make_pair(1000000000,1)); st.insert(make_pair(-1000000000,-1)); cin >> n; for(int i = 1; i <= n; i++) { int id, x; cin >> id >> x; set<pair<int, int> >::iterator l = st.lower_bound(make_pair(x, id)); set<pair<int, int> >::iterator r = l; l--; if(x - (l-> first) <= (r -> first) - x) cout << id <<' '<< l-> second << endl; else cout << id <<' '<< r-> second << endl; st.insert(make_pair(x, id)); } return 0; } |
「poj1290」Blocks
先将相邻的同色块合并，记忆化搜索
F(l, r, len)表示将l到r消去的最大得分，此时r之后有一段长为len的方块与r同色
转移1：将r和len一起消除
转移2：在l到r-1中枚举一个和r同色的段i，那么i到r之间的就内部解决，即\(F(i + 1, r – 1, 0)\)，和另一段\(F(l, i, num_r + len)\)
|
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 <map> #include <cstdio> #include <vector> #include <iomanip> #include <cstring> #include <iostream> using namespace std; int T; int n, m; int a[205], num[205]; int f[205][205][205]; int dp(int l, int r, int len) { if(f[l][r][len] != -1) return f[l][r][len]; int res = (len + num[r]); res = res * res; if(l == r) return res; if(l > r) return 0; res += dp(l, r - 1, 0); for(int i = l; i <= r - 1; i++) if(a[i] == a[r]) res = max(res, dp(l, i, num[r] + len) + dp(i + 1, r - 1, 0)); return f[l][r][len] = res; } int main() { cin >> T; for(int cas = 1; cas <= T; cas++) { cout << "Case " << cas << ": "; memset(num, 0, sizeof(num)); memset(f, -1, sizeof(f)); m = 0; cin >> n; int x; for(int i = 1; i <= n; i++) { cin >> x; if(i == 1 || x != a[m]) { m++; a[m] = x; num[m]++; } else num[m]++; } cout << dp(1, m, 0) << endl; } return 0; } |
「poj1191」棋盘分割
维护二维前缀和，记忆化搜索
|
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 |
#include <map> #include <cmath> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int n; int a[10][10], sum[10][10]; int dp[20][10][10][10][10]; int S2(int x1, int y1, int x2, int y2) { x1--; y1--; int S = sum[x2][y2] + sum[x1][y1] - sum[x1][y2] - sum[x2][y1]; return S * S; } int f(int k, int x1, int y1, int x2, int y2) { if(k == 0) return S2(x1, y1, x2, y2); if(dp[k][x1][y1][x2][y2] != -1) return dp[k][x1][y1][x2][y2]; int mn = inf; for(int x = x1; x < x2; x++) { mn = min(mn, f(k - 1, x1, y1, x, y2) + S2(x + 1, y1, x2, y2)); mn = min(mn, S2(x1, y1, x, y2) + f(k - 1, x + 1, y1, x2, y2)); } for(int y = y1; y < y2; y++) { mn = min(mn, f(k - 1, x1, y1, x2, y) + S2(x1, y + 1, x2, y2)); mn = min(mn, S2(x1, y1, x2, y) + f(k - 1, x1, y + 1, x2, y2)); } dp[k][x1][y1][x2][y2] = mn; return mn; } int main() { memset(dp, -1, sizeof(dp)); cin >> n; for(int i = 1; i <= 8; i++) for(int j = 1; j <= 8; j++) { cin >> a[i][j]; sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]; } double S = sum[8][8], ans = f(n - 1, 1, 1, 8, 8); ans = sqrt((ans - S * S / n) / n); printf("%.3lf\n", ans); return 0; } |
「poj1724」ROADS
用F(i,j)表示花费为i，走到点j的最短路
按照花费分层转移即可
|
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 |
#include <map> #include <cmath> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #define inf 1000000000 using namespace std; int K, n, m, cnt; int last[105]; int f[10005][105]; struct edge{ int to, next, w, c; }e[10005]; void insert(int u, int v, int w, int c) { e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].w = w; e[cnt].c = c; } int main() { memset(f, 127 / 3, sizeof(f)); cin >> K >> n >> m; for(int i = 1; i <= m; i++) { int u, v, w, c; cin >> u >> v >> w >> c; insert(u, v, w, c); } f[0][1] = 0; int ans = inf; for(int i = 0; i <= 10000; i++) { if(f[i][n] <= K) { ans = i; break; } for(int j = 1; j <= n; j++) if(f[i][j] <= K) for(int x = last[j]; x; x = e[x].next) if(i + e[x].w <= 10000) f[i + e[x].w][e[x].to] = min(f[i + e[x].w][e[x].to], f[i][j] + e[x].c); } if(ans == inf)puts("-1"); else cout << ans << endl; return 0; } |
01:List
|
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 |
#include <map> #include <list> #include <iostream> using namespace std; int n; map<int, list<int> >mp; int main() { cin >> n; string opt; int id1, id2; for(int i = 1; i <= n; i++) { cin >> opt >> id1; if(opt == "new") mp[id1] = list<int>{}; if(opt == "add") { cin >> id2; mp[id1].push_back(id2); } if(opt == "merge") { cin >> id2; mp[id1].merge(mp[id2]); } if(opt == "unique") { mp[id1].sort(); mp[id1].unique(); } if(opt == "out") { mp[id1].sort(); for(auto j: mp[id1]) cout << j << ' '; cout << endl; } } return 0; } |
02:RPN Calculator
|
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 |
#include <queue> #include <cmath> #include <cstring> #include <iostream> using namespace std; int n; priority_queue<double, vector<double>, greater<double> >q; vector<double> st; void pop(double val) { q.pop(); q.push(val); printf("%e\n", val); } void cal(char c) { double b = st.back(); st.pop_back(); if(c == '=') { pop(b); return; } double a = st.back(); st.pop_back(); if(c == '+') st.push_back(a + b); if(c == '-') st.push_back(a - b); if(c == '*') st.push_back(a * b); if(c == '/') st.push_back(a / b); if(c == '^') st.push_back(pow(a, b)); } int main() { scanf("%d", &n); double x; for(int i = 1; i <= n; i++) { scanf("%lf", &x); q.push(x); } char ch[20]; while(scanf("%s", ch) != EOF) { if((ch[0] >= '0' && ch[0] <= '9') || (ch[0] == '-' && strlen(ch) != 1)) st.push_back(atof(ch)); else cal(ch[0]); } puts(""); for(int i = 1; i <= n; i++) { printf("%e ", q.top()); if(i % 10 == 0)puts(""); q.pop(); } return 0; } |
03:Set
|
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 |
#include <set> #include <map> #include <iostream> using namespace std; int n; multiset<int>st; map<int, bool>mp; int main() { cin >> n; string opt; int x; for(int i = 1; i <= n; i++) { cin >> opt >> x; if(opt == "add") { st.insert(x); mp[x] = 1; cout << st.count(x) << endl; } if(opt == "del") { cout << st.count(x) << endl; st.erase(st.lower_bound(x), st.upper_bound(x)); } if(opt == "ask") cout << mp[x] << ' ' << st.count(x) << endl; } return 0; } |
04:字符串操作
每次读入一个词之后，判断末尾的若干个词是否是一次操作，处理操作压栈
check 用于判断某个单词是否是操作
count 用于找到离末尾最近的一个操作
|
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include <queue> #include <cmath> #include <cstring> #include <iostream> using namespace std; string str[25]; string st[10005]; int n, m; string copy(int N, int X, int L) { string tmp = ""; for(int i = 0; i < L; i++) tmp += str[N][X + i]; return tmp; } int s2i(string x) { int val = 0; for(int i = 0; i < x.length(); i++) if('0' <= x[i] && x[i] <= '9') val = val * 10 + (x[i] - '0'); else return -1; return val; } string Opt[] = {"copy", "add", "find", "rfind", "insert", "reset", "print", "printall"}; bool check(string opt) { for(int i = 0; i < 8; i++) if(opt == Opt[i])return 1; return 0; } int count() { for(int i = 1; i <= m; i++) if(check(st[m - i + 1])) return i; return 0; } bool solve() { string tmp; if(count() == 4) { if(st[m - 3] == "copy") { tmp = copy(s2i(st[m - 2]), s2i(st[m - 1]), s2i(st[m])); m -= 4; st[++m] = tmp; return 1; } if(st[m - 3] == "insert") { int X = s2i(st[m]), N = s2i(st[m - 1]); str[N].insert(X, st[m - 2]); m -= 3; return 1; } } if(count() == 3) { if(st[m - 2] == "add") { int b = s2i(st[m]), a = s2i(st[m - 1]); if(0 <= a && a <= 99999 && 0 <= b && b <= 99999) tmp = to_string(a + b); else tmp = st[m - 1] + st[m]; m -= 3; st[++m] = tmp; return 1; } if(st[m - 2] == "find") { int N = s2i(st[m]); int pos = str[N].find(st[m - 1]); if(pos == -1)pos = str[N].length(); tmp = to_string(pos); m -= 3; st[++m] = tmp; return 1; } if(st[m - 2] == "rfind") { int N = s2i(st[m]); int pos = str[N].rfind(st[m - 1]); if(pos == -1)pos = str[N].length(); tmp = to_string(pos); m -= 3; st[++m] = tmp; return 1; } if(st[m - 2] == "reset") { int N = s2i(st[m]); str[N] = st[m - 1]; m -= 2; return 1; } } if(count() == 2 && st[m - 1] == "print") { int N = s2i(st[m]); cout << str[N] << endl; m -= 2; return 1; } if(count() == 1 && st[m] == "printall") { for(int i = 1; i <= n; i++) cout << str[i] << endl; m--; return 1; } return 0; } int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> str[i]; string x; while(cin >> x) { if(x == "over")break; else st[++m] = x; while(solve()); } return 0; } |
05:热血格斗场
|
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 <set> #include <cstdio> #include <iostream> using namespace std; int n; int id[100005],v[100005]; set<pair<int, int> >st; int main() { scanf("%d", &n); st.insert(make_pair(1000000000,1)); st.insert(make_pair(-1000000000,1)); for(int i = 1; i <= n; i++) { scanf("%d%d", &id[i], &v[i]); auto l = st.lower_bound(make_pair(v[i], id[i])), r = l; l--; if(v[i] - (l->first) <= (r->first) - v[i]) printf("%d %d\n", id[i], l->second); else printf("%d %d\n", id[i], r->second); st.insert(make_pair(v[i], id[i])); } return 0; } |
06:冷血格斗场
|
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 <set> #include <cstdio> #include <iostream> using namespace std; int n; int id[100005],v[100005]; set<pair<int, int> >st; int main() { scanf("%d", &n); st.insert(make_pair(1000000000,1)); st.insert(make_pair(-1000000000,1)); for(int i = 1; i <= n; i++) { scanf("%d%d", &id[i], &v[i]); auto l = st.lower_bound(make_pair(v[i], id[i])), r = l; l--; l = st.lower_bound(make_pair(l->first, 0)); if(make_pair(v[i] - l->first, l->second) < make_pair(r->first - v[i], r->second)) printf("%d %d\n", id[i], l->second); else printf("%d %d\n", id[i], r->second); st.insert(make_pair(v[i], id[i])); } return 0; } |
07:priority queue练习题
|
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 |
#include <queue> #include <cstdio> #include <iostream> using namespace std; int n, cnt; int pri[10000005], num[10000005]; bool mark[10000005]; void pre() { for(int i = 2; i <= 10000000; i++) { if(!mark[i]) { pri[++cnt] = i; num[i] = 1; } for(int j = 1; pri[j] * i <= 10000000 && j <= cnt; j++) { mark[pri[j] * i] = 1; if(i % pri[j] == 0) { num[pri[j] * i] = num[i]; break; } else num[pri[j] * i] = num[i] + 1; } } for(int i = 2; i <= 10000000; i++) if(!mark[i])num[i]--; } struct cmp1{ bool operator()(const int &a, const int &b){ if(num[a] == num[b])return a < b; return num[a] < num[b]; } }; struct cmp2{ bool operator()(const int &a, const int &b){ if(num[a] == num[b])return a > b; return num[a] > num[b]; } }; priority_queue<int, vector<int>, cmp1> q1; priority_queue<int, vector<int>, cmp2> q2; int main() { pre(); cin >> n; while(n--) { int x; for(int i = 1; i <= 10; i++) { cin >> x; q1.push(x); q2.push(x); } cout << q1.top() << ' ' << q2.top() << endl; q1.pop(); q2.pop(); } 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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <string> #include <map> #include <iterator> #include <algorithm> using namespace std; template <class T1, class T2, class T3 = greater<T1> > class MyMultimap: public multimap<T1, T2, T3>{ public: void Set(T1 a, T2 b){ for(auto it = this->find(a); it->first == a; it++) it->second = b; } }; template <typename T1,typename T2> ostream& operator <<(ostream& os, pair<T1, T2> p){ os << '(' << p.first << ',' << p.second << ')'; return os; } struct Student { string name; int score; }; template <class T> void Print(T first,T last) { for(;first!= last; ++ first) cout << * first << ","; cout << endl; } int main() { Student s[] = { {"Tom",80},{"Jack",70}, {"Jone",90},{"Tom",70},{"Alice",100} }; MyMultimap<string,int> mp; for(int i = 0; i<5; ++ i) mp.insert(make_pair(s[i].name,s[i].score)); Print(mp.begin(),mp.end()); //按姓名从大到小输出 mp.Set("Tom",78); //把所有名为"Tom"的学生的成绩都设置为78 Print(mp.begin(),mp.end()); MyMultimap<int,string,less<int> > mp2; for(int i = 0; i<5; ++ i) mp2.insert(make_pair(s[i].score,s[i].name)); Print(mp2.begin(),mp2.end()); //按成绩从小到大输出 mp2.Set(70,"Error"); //把所有成绩为70的学生，名字都改为"Error" Print(mp2.begin(),mp2.end()); cout << "******" << endl; mp.clear(); string name; string cmd; int score; while(cin >> cmd ) { if( cmd == "A") { cin >> name >> score; if(mp.find(name) != mp.end() ) { cout << "erroe" << endl; } mp.insert(make_pair(name,score)); } else if(cmd == "Q") { cin >> name; MyMultimap<string,int>::iterator p = mp.find(name); if( p!= mp.end()) { cout << p->second << endl; } else { cout << "Not Found" << endl; } } } return 0; } |
计数器 9528826
OI 课件=>
OI 课件=>
黄学长，能详细解释一下字符串操作的代码吗 实在看不懂 Orz
已经添加
非常感谢ヾ(≧▽≦*)o
学长，这些题目您在高中就已经会做，为什么上大学还要学这个
OwO 复习复习丫