Noip 模拟练习5
- 满分300，本人240。修正后300。
- 难度中等。
太空密码
Description
- 人类一直致力于探索地外文明，为此科学家们建造了一个巨大的射电望远镜 用于接收宇宙射线。一天从宇宙深处传来一连串神秘电波，每串电波可以看成是一个三进制 数，即由 0、 1、 2 构成，长度均不超过 40，最特别的是通过对大量有电波分析发现：每串电 波中都没有出现连续的 0。科学家们猜想电波中包含着外星人的密码，为了破译其中的奥秘， 现在请你写一个程序，统计出满足要求的长度为 N 的电波的总数。 例如：当 N=2 时，满足要求的电波有 8 个： 01、 02、 10、 11、 12、 20、 21、 22。 00 不满 足要求，因为出现了连续的 0
Input
- 输入文件 password.in 给出一个不超过 40 的正整数 N，表示电波串的长度。 其中 50%的数据 1≤N≤15。
Output
- 在文件 password.out 给出长度为 N 且没有连续 0 的串的个数。
Sample Input
2
Sample output
8
题解：
dp。
设dp(i, 0/1/2)表示第i个位置上是0/1/2时的方案数，那么所求就是dp(n, 0) + dp(n, 1) + dp(n, 2)。转移也十分简单，见代码。
#include#include #define N 55using namespace std;long long n;long long f[N][4];int main(){ cin >> n; f[1][0] = f[1][1] = f[1][2] = 1; for(int i = 2; i <= n; i++) f[i][0] = f[i - 1][1] + f[i - 1][2], f[i][1] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2], f[i][2] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2]; cout << f[n][0] + f[n][1] + f[n][2]; return 0;}
作业调度方案
题目：
- 有图，转
题解：
- 模拟。
这题难在题目难理解，其实解题方法就在题目中，看懂题目就是一道模拟题。以下为翻译版本：
- 有m台机器加工n个工件，每个工件都有m个工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。现在给你一个“安排顺序”，请你按照“安排顺序”的顺序模拟，最终求出完成这些任务所花费的最短时间。
愣什么，模拟啊！
#include#include #define N 25#define inf 0x7fffffffusing namespace std;struct A {int obj, id, val, las;} a[N * N];struct B {int id, val;} b[N][N];int n, m, ans;int g[N], t[N];int form[N][405];bool check(int id, int l, int r){ for(int i = l; i <= r; i++) if(form[id][i]) return 0; return 1;}void cal(int obj, int id, int val, int las){ if(!las) { for(int i = 1; ; i++) if(check(id, i, i + val - 1)) { for(int j = i; j <= i + val - 1; j++) form[id][j] = obj; t[id] = max(t[id], i + val - 1); break; } return; } int idd = a[las].id, pos; for(int i = t[idd]; i >= 1; i--) if(form[idd][i] == obj) {pos = i; break;} for(int i = pos + 1; ; i++) if(check(id, i, i + val - 1)) { for(int j = i; j <= i + val - 1; j++) form[id][j] = obj; t[id] = max(t[id], i + val - 1); break; }}int main(){ cin >> m >> n; for(int i = 1; i <= m * n; i++) cin >> a[i].obj; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> b[i][j].id; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> b[i][j].val; for(int i = 1; i <= m * n; i++) a[i].id = b[a[i].obj][++g[a[i].obj]].id, a[i].val = b[a[i].obj][g[a[i].obj]].val; for(int i = 1; i <= m * n; i++) { int x = a[i].obj; for(int j = i - 1; j >= 1; j--) if(a[j].obj == x) {a[i].las = j; break;} } for(int i = 1; i <= m * n; i++) cal(a[i].obj, a[i].id, a[i].val, a[i].las); for(int i = 1; i <= m; i++) ans = max(ans, t[i]); cout << ans; return 0;}
引水入城
题目：
- 有图，转
题解：
- bfs + 贪心。
bfs算出每个点所能控制的左边界，右边界。
看看表示能否到达所有干旱区。不能进入第3步，能进入第4步。
扫一遍看看有多少干旱区不可能建有设施，输出答案。进入第5步。
贪心的跑一遍区间覆盖，输出答案。进入第5步。
结束。
- 问题来了，在每个点能控制的左右边界之间的那些干旱区，你怎么知道可以控制呢？换句话说，你怎么知道控制的一定是一段区间呢？
- 这位大大的讲得不错，推荐。
- 最后补充一下，我的代码本地AC，洛谷90pts超时一个点。据说数据加强了要记忆化，那么
我懒我就没有继续修正了。
#include#include #include #include #define N 505#define inf 0x7fffffffusing namespace std;struct E {int l, r;} e[N];struct Node {int x, y, h;};int n, m, last, ans;int a[N][N];bool tag[N];bool vis[N][N];int dx[5] = {0, -1, 1, 0, 0};int dy[5] = {0, 0, 0, -1, 1};int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x *= f;}void bfs(int x, int y, int dfn){ queue que; memset(vis, 0, sizeof(vis)); Node tmp; tmp.x = x, tmp.y = y, tmp.h = a[x][y]; que.push(tmp), vis[x][y] = 1; while(que.size()) { Node now = que.front(); que.pop(); for(int i = 1; i <= 4; i++) { tmp.x = now.x + dx[i], tmp.y = now.y + dy[i], tmp.h = a[tmp.x][tmp.y]; if(now.h > tmp.h && !vis[tmp.x][tmp.y] && tmp.x >= 1 && tmp.x <= n && tmp.y >= 1 && tmp.y <= m) { vis[tmp.x][tmp.y] = 1; que.push(tmp); } } } for(int i = 1; i <= m; i++) if(vis[n][i]) {e[dfn].l = i; break;} for(int i = m; i >= 1; i--) if(vis[n][i]) {e[dfn].r = i; break;} for(int i = e[dfn].l; i <= e[dfn].r; i++) tag[i] = 1;}int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = read(); for(int i = 1; i <= m; i++) bfs(1, i, i); for(int i = 1; i <= m; i++) if(!tag[i]) { cout << 0 << endl; for(int j = 1; j <= m; j++) if(!tag[j]) ans++; cout << ans; return 0; } cout << 1 << endl; int l = 1; while(l <= m) { int r = 0; for(int i = 1; i <= m; i++) if(e[i].l <= l) r = max(r, e[i].r); ans++, l = r + 1; } cout << ans; return 0;}