2015程序设计实习实验班免修考试(校内)
「poj1037」decorative fence
用f(i,j)表示长度为i，开头为j，开头为上升的序列
用g(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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int T, n; ll C; ll f[25][25], g[25][25]; int ans[25]; bool vis[25]; void dp() { f[1][1] = g[1][1] = 1; for(int i = 2; i <= 20; i++) for(int j = 1; j <= i; j++) { for(int k = 1; k <= j - 1; k++) g[i][j] += f[i - 1][k]; for(int k = j; k <= i - 1; k++) f[i][j] += g[i - 1][k]; } } int main() { dp(); cin >> T; while(T--) { memset(vis, 0, sizeof(vis)); memset(ans, 0, sizeof(ans)); cin >> n >> C; for(int i = 1; i <= n; i++) { int cnt = 0; for(int j = 1; j <= n; j ++) if(!vis[j]) { ll tmp = C; cnt++; if(i == 1) C -= f[n][cnt] + g[n][cnt]; else if(j > ans[i - 1] && (i == 2 || ans[i - 2] > ans[i - 1]))C -= g[n - i + 1][cnt]; else if(j < ans[i - 1] && (i == 2 || ans[i - 2] < ans[i - 1]))C -= f[n - i + 1][cnt]; if(C <= 0) { ans[i] = j; vis[j] = 1; C = tmp; break; } } } for(int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << endl; } return 0; } |
「poj1011」Sticks
经典的搜索剪枝
1.长度取值范围是木棍的最长长度到长度总和之间。
2.长度总和一定可以整除原来的长度。
3.从大到小排序搜索。
4.某次组合时，如果不能加入某根木棍，同种长度的木棍也不再尝试。
5.如果在组合过程中，当前可选的第一根木棍没用上，返回。
|
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<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 using namespace std; int n, Sum, mx; int a[65]; int sum; bool flag, vis[65]; void dfs(int sel, int len) { if(len == sum) { len = 0; sel++; if(sel == Sum / sum)flag = 1; } if(flag)return; int last = 0; for(int i = 1; i <= n; i++) { if(flag)return; if(!vis[i] && a[i] != last) { last = a[i]; if(len + a[i] <= sum) { vis[i] = 1; dfs(sel, len + a[i]); vis[i] = 0; if(!len)return; } } } } int main() { while(cin >> n) { if(n == 0)break; Sum = 0; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) Sum += a[i]; sort(a + 1, a + n + 1, greater<int>()); flag = 0; for(sum = a[1]; sum <= Sum; sum++) if(Sum % sum == 0) { dfs(0, 0); if(flag) { printf("%d\n", sum); break; } } } return 0; } |
「poj1286」Necklace of Beads
Polya定理，考虑顺时针转i个珠子或按照某个对称轴翻折
|
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 ll long long using namespace std; ll n; ll ans; int main() { while(cin >> n) { if(n == -1)break; ans = 0; for(ll i = 1; i <= n; i++) ans += pow(3, __gcd(n, i)); if(n % 2 == 0) ans += n / 2 * (pow(3, n / 2 + 1) + pow(3, n / 2)); else ans += n * pow(3, n / 2 + 1); ans /= 2 * n; cout << ans << endl; } return 0; } |
「poj1704」Georgia and Bob
阶梯博弈，把棋子按位置升序排列后，从后往前它们两两看成一对。
一对棋子中，如果一方移动前一个，另一方总能对后一个移动相同的步数。
于是只需要考虑同一对的两个棋子之间的空格数，转换为nim问题。
|
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 |
#include <set> #include <map> #include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; int T, n; int p[1005]; int main() { cin >> T; while(T--) { cin >> n; for(int i = 1; i <= n; i++) cin >> p[i]; int ans = 0; sort(p + 1, p + n + 1); for(int i = n; i > 0; i -= 2) ans ^= p[i] - p[i - 1] - 1; if(ans == 0)puts("Bob will win"); else puts("Georgia will win"); } return 0; } |
「poj4105」拯救公主
状压宝石 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 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 |
#include <set> #include <map> #include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; struct data{ int x, y, st, step; }; int mp[205][205][64]; int T, r, c, K; string a[205]; vector<pair<int, int> >portal; queue<data> q; int xx[4] = {0, 0, 1, -1}, yy[4] = {1, -1, 0, 0}; void bfs() { while(!q.empty()) { data t = q.front(); q.pop(); for(int i = 0; i < 4; i++) { int x = t.x + xx[i], y = t.y + yy[i], st = t.st, step = t.step; if(x < 1 || y < 1 || x > r || y > c || a[x][y] == '#')continue; if(a[x][y] >= '0' && a[x][y] <='4') st |= (1 << (a[x][y] - '0')); if(mp[x][y][st] == -1) { mp[x][y][st] = step + 1; q.push((data){x, y, st, step + 1}); if(a[x][y] == '$') for(auto it: portal) { int x = it.first, y = it.second; if(mp[x][y][st] == -1) { mp[x][y][st] = step + 1; q.push((data){x, y, st, step + 1}); } } } } } } int main() { cin >> T; while(T--) { memset(mp, -1, sizeof(mp)); portal.clear(); cin >> r >> c >> K; for(int i = 1; i <= r; i++) { cin >> a[i]; a[i] = " " + a[i]; } int ex, ey; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) if(a[i][j] == '$') portal.push_back(make_pair(i, j)); else if(a[i][j] == 'S') { mp[i][j][0] = 0; q.push((data){i, j, 0, 0}); } else if(a[i][j] == 'E') ex = i, ey = j; bfs(); if(mp[ex][ey][(1 << K) -1] == -1) puts("oop!"); else cout << mp[ex][ey][(1 << K) -1] << endl; } return 0; } |
「poj2528」Mayor’s poster
离散化后线段树染色
|
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 |
#include <set> #include <map> #include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; int T, n; int c[80005], x[10005], y[10005]; bool mark[10005]; vector<int> a; void pushdown(int k) { c[k << 1] = c[k]; c[k << 1|1] = c[k]; c[k] = 0; } void update(int k, int l, int r, int x, int y, int id) { if(c[k] && l != r)pushdown(k); if(l == x && y == r) { c[k] = id; return; } int mid = (l + r) >> 1; if(x <= mid) update(k << 1, l, mid, x, min(y, mid), id); if(y > mid) update(k << 1 | 1, mid + 1, r, max(x, mid + 1), y, id); } int query(int k, int l, int r, int x) { if(c[k] && l != r)pushdown(k); if(l == r)return c[k]; int mid = (l + r) >> 1; if(x <= mid)return query(k << 1, l, mid, x); else return query(k << 1 | 1, mid + 1, r, x); } int main() { cin >> T; while(T--) { a.clear(); memset(mark, 0, sizeof(mark)); memset(c, 0, sizeof(c)); cin >> n; for(int i = 1; i <= n; i++) { scanf("%d%d", &x[i], &y[i]); a.push_back(x[i]); a.push_back(y[i]); } sort(a.begin(), a.end()); for(int i = 1; i <= n; i++) { x[i] = lower_bound(a.begin(), a.end(), x[i]) - a.begin() + 1; y[i] = lower_bound(a.begin(), a.end(), y[i]) - a.begin() + 1; } for(int i = 1; i <= n; i++) update(1, 1, 2 * n, x[i], y[i], i); int ans = 0; mark[0] = 1; for(int i = 1; i <= 2 * n; i++) { int t = query(1, 1, 2 * n, i); if(!mark[t]) mark[t] = 1, ans++; } cout << ans << endl; } return 0; } |
「poj3436」ACM Computer Factory
拆点+最大流
枚举每对机器，判断是否能够传输
|
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 |
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define T (2 * n + 1) using namespace std; int m, n, cnt = 1; int Q[55], h[55], q[55]; int a[55][55], b[55][55], c[55][55]; struct data{ int to, next, v; }e[10005]; int last[55]; void insert(int u, int v, int w) { e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w; e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = 0; } bool bfs() { int head = 0, tail = 1; memset(h, -1, sizeof(h)); q[0] = 0; h[0] = 0; while(head != tail) { int now = q[head]; head++; for(int i = last[now]; i; i = e[i].next) if(h[e[i].to] == -1 && e[i].v) { h[e[i].to] = h[now] + 1; q[tail++] = e[i].to; } } return h[T] != -1; } int dfs(int x, int f) { if(x == T)return f; int w, used = 0; for(int i = last[x]; i; i = e[i].next) if(h[e[i].to] == h[x] + 1) { w = dfs(e[i].to, min(f - used, e[i].v)); used += w; e[i].v -= w; e[i ^ 1].v += w; if(used == f)return f; } if(!used)h[x] = -1; return used; } bool check(int x, int y) { for(int i = 1; i <= m; i++) if(a[y][i] == 1 && b[x][i] == 0) return 0; else if(a[y][i] == 0 && b[x][i] == 1) return 0; return 1; } int main() { cin >> m >> n; for(int i = 1; i <= n; i++) { cin >> Q[i]; bool flag = 0; for(int j = 1; j <= m; j++) { cin >> a[i][j]; if(a[i][j] == 1)flag = 1; } if(!flag)insert(0, i, inf); flag = 1; for(int j = 1; j <= m; j++) { cin >> b[i][j]; flag &= b[i][j]; } if(flag)insert(i + n, T, inf); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j && check(i, j)) { c[i][j] = cnt + 1; insert(i + n, j, inf); } for(int i = 1; i <= n; i++) insert(i, i + n, Q[i]); int ans = 0, ans2 = 0; while(bfs()) ans += dfs(0,inf); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i!=j && e[c[i][j] ^ 1].v) ans2++; cout << ans << ' ' << ans2 << endl; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i!=j && e[c[i][j] ^ 1].v) cout << i << ' ' << j << ' ' << e[c[i][j] ^ 1].v << endl; return 0; } |
计数器 9786055
OI 课件=>
OI 课件=>
/01 /01
对于poj【poj2528】Mayor’s poster这道题…
样例
1
1 10
1 3
6 10
的答案应该是3
(1-3,4-5,6-10)而不是2