2016程序设计实习实验班免修考试(算法)
02:热血格斗场
|
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; } |
05:MPI Maelstrom
|
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 |
#include <set> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; int read() { int x = 0; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == 'x')return -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();} return x; } int n, m; int dis[105][105]; int main() { scanf("%d", &n); memset(dis, 127/3, sizeof(dis)); for(int i = 2; i <= n; i++) for(int j = 1; j < i; j++) { int x = read(); if(x != -1)dis[i][j] = dis[j][i] = x; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]); int ans = 0; for(int i = 1; i <= n; i++) ans = max(ans, dis[1][i]); cout << ans << endl; return 0; } |
06:Ultra-QuickSort
|
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 |
#include <set> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n; int a[500005], b[500005], t[500005]; vector<int>ve; void add(int x) { for(int i = x; i <= n; i += i&(-i)) t[i]++; } int query(int x) { int ans = 0; for(int i = x; i; i -= i&(-i)) ans += t[i]; return ans; } int main() { while(scanf("%d", &n)) { if(n == 0)break; ve.clear(); memset(t, 0 , sizeof(t)); for(int i = 1; i <= n; i++) { int x; scanf("%d", &a[i]); ve.push_back(a[i]); } sort(ve.begin(), ve.end()); for(int i = 1; i <= n; i++) b[i] = lower_bound(ve.begin(), ve.end(), a[i]) - ve.begin() + 1; long long ans = 0; for(int i = 1; i <= n; i++) { add(b[i]); ans += i - query(b[i]); } cout << ans << endl; } return 0; } |
08:Drainage Ditches
|
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 |
#include <set> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; int n, m, cnt; int h[205], last[205], q[205]; struct edge{ int to, next, v; }e[1005]; void insert(int u, int v, int w) { e[++cnt] = (edge){v, last[u], w}; last[u] = cnt; e[++cnt] = (edge){u, last[v], 0}; last[v] = cnt; } bool bfs() { int head = 0, tail = 1; memset(h, -1, sizeof(h)); q[0] = 1; h[1] = 0; while(head != tail) { int now = q[head]; head++; for(int i = last[now]; i; i = e[i].next) if(e[i].v && h[e[i].to] == -1) { h[e[i].to] = h[now] + 1; q[tail++] = e[i].to; } } return h[m] != -1; } int dfs(int x, int f) { int w, used = 0; if(x == m)return f; for(int i = last[x]; i; i = e[i].next) if(h[e[i].to] == h[x] + 1) { w = dfs(e[i].to, min(e[i].v, f - used)); used += w; e[i].v -= w; e[i ^ 1].v += w; if(used == f)return used; } if(!used)h[x] = -1; return used; } int main() { while(scanf("%d%d", &n ,&m) != EOF) { memset(last, 0, sizeof(last)); cnt = 1; for(int i = 1; i <= n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); insert(u, v, w); } int ans = 0; while(bfs()) ans += dfs(1, inf); cout << ans << endl; } return 0; } |
Subscribe