Noip 模拟练习7
- 满分300，本人20分。修正后300分。
- 难度：简单。
- 总结：基本功要扎实，简单的题不能丢分。
人均AK QAQ。麻烦您写细节时长点心吧艹！
胖子机械师
Description
大家都知道胖子是一名机械工程师，他很胖，然而最近遇到了一件烦心事，
这件事是如此的烦心，以至于他的体重锐减 20%！
烦心事来自一位设计师瘦子给胖子的机器 3D 设计图纸，瘦子是如此的没有
力气，以至于将图纸画得模糊不清，而且这个方形机器中居然没有除工件外的空
位，胖子 800 度的视力受到严重考验，于是他终日食之不得下咽。
胖子终于无法忍受，决定求助于最新科技——电脑，他买来一台联想电脑，
借助它进行图纸辨别，但是电脑上没有这样的软件，于是胖子以 1 斤肉作为奖励，
希望你帮他设计一个软件。
胖子说：“我的图纸是三维的（先进吧），用坐标系分了网格，每个工件包含
相邻的一些网格部分，由于万恶的瘦子很愚蠢，我不得不认为模糊程度相差在一
定范围的相邻两格是同一工件，你就帮我看看总共有多少个工件吧”。
Input
第一行 3 个整数 l,w,h (l,w,h<=50) 表示三维图纸的长宽高；
第二行 1 个整数 m(0<=m<=255)表示模糊程度的最大允许差值；
后面有一行 lwh 个 0~255 的非负整数，按照空间坐标从小到大给出瘦子画每一
格的模糊程度(坐标大小比较，按长，宽，高的优先顺序)。
Output
- 一个整数，工件个数。
Sample Input
2 2 2
0
1 1 1 1 2 2 2 2
Sample output
2
题解：
- 搜索。
- 三维搜索找联通块。
#include#include #include #define N 55using namespace std;int x, y, z, avg, ans;int a[N][N][N]; //第一维是横切()，第二维是竖切，第三维是立切bool vis[N][N][N];int dx[7] = {0, 0, 0, 0, 0, -1, 1};int dy[7] = {0, 0, 0, -1, 1, 0, 0};int dz[7] = {0, 1, -1, 0, 0, 0, 0};int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}void dfs(int v1, int v2, int v3){ for(int i = 1; i <= 6; i++) { int xx = v1 + dx[i], yy = v2 + dy[i], zz = v3 + dz[i]; if(xx < 1 || xx > x || yy < 1 || yy > y || zz < 1 || zz > z) continue; if(vis[xx][yy][zz]) continue; if(abs(a[xx][yy][zz] - a[v1][v2][v3]) <= avg) { vis[xx][yy][zz] = 1; dfs(xx, yy, zz); } }}int main(){ cin >> x >> y >> z >> avg; for(int i = 1; i <= x; i++) for(int j = 1; j <= y; j++) for(int k = 1; k <= z; k++) a[i][j][k] = read(); for(int i = 1; i <= x; i++) for(int j = 1; j <= y; j++) for(int k = 1; k <= z; k++) if(!vis[i][j][k]) { ans++; vis[i][j][k] = 1; dfs(i, j, k); } cout << ans; return 0;}
棋盘覆盖
Description
用 1 1 和 1 2 两种骨牌去覆盖由 2 * N 个方格构成的棋盘，可以有多种方
案，下图给出 N=1 和 N=2 时两个棋盘的覆盖方案，“■”表示 1 1 的骨牌，“ ■■”表示 1 *
2 骨牌,可以看出，2 * 1 的棋盘有两种覆盖方法，而 2 * 2 的棋盘有七种覆盖方法。
Input
输入文件 chess.in 仅有一行，给出正整数 N 的值， 1≤N≤30, 其中 50%的数据
1≤N≤15。
Output
输出文件 chess.out 也仅有一行，给出用 1 1 和 1 2 两种骨牌覆盖 2 N 的棋
盘的方案总数。
Sample Input
2
Sample output
7
题解：
- dp。
欸这题我还真没去想正解。主要因为一看到这题就想起的噩梦。貌似是原题于是跳过了… …
- 其实这题认真想想就是个普通的dp啊！！！
- 考虑新加一列怎么操作，有如下4种情况：
- 前一列是平的
- 前一列的第一行凸出来了，第二行是平的
- 前一列的第二行凸出来了，第一行是平的
- 前一列的两行都凸出来了
那么一个for循环，里面算出dp(i)(1/2/3/4)。转移很好想：
- 箭头所指是当前行。那么考虑第一种情况，要使箭头所指变成平的，可以从第一种情况转移，填一个竖着的1 * 2或者两个1 * 1，那么dp(i, 1) += dp(i - 1, 1) * 2。可以从第二种情况转移，在第二行填一个1 * 1就平了，那么dp(i, 1) += dp(i - 1, 2)。可以从第三种情况转移，理由同上，dp(i, 1) += dp(i - 1, 3)。可以从第四种情况转移，嘛都不用填，因为本来就平了。总结：dp(i, 1) = dp(i - 1, 1) * 2 + dp(i - 1, 2) + dp(i - 1, 3) + dp(i - 1, 4)。
- 考虑第二种情况，要使当前列的第一行凸出去，第二行平的。那么可以从第一、三种情况转移。总结：dp(i, 2) = dp(i - 1, 1) + dp(i - 1, 3)。为什么不能从2或4情况转移，因为只考虑上一行与这一行的关系！
- 第三、四种情况理由同上，不推了。那么最终dp(n, 1)即为所求。
#include#include #define int unsigned long longusing namespace std;int n;int f[35][5];signed main(){ cin >> n; f[0][1] = 1; for(int i = 1; i <= n; i++) { f[i][1] = f[i - 1][1] * 2 + f[i - 1][2] + f[i - 1][3] + f[i - 1][4]; f[i][2] = f[i - 1][1] + f[i - 1][3]; f[i][3] = f[i - 1][1] + f[i - 1][2]; f[i][4] = f[i - 1][1]; } cout << f[n][1]; return 0;}
积存降水
题目：
- 有图，转
题解：
- 搜索 / 并查集。
- 爆搜容易超时，但这题数据范围咋那么小。我的思路是直接计算，用并查集优化。复杂度是O(nm + V)，比搜索快很多。
- 对于此题，我们考虑每一层能装多少水。这样从第0层枚举到最高的那一层的sum之和就是答案。那每一层的答案怎么算呢？我们知道，假设当前层数(高度)是h，那么如果一个点高度 <= h且与边界联通，那么这个点肯定要不得。所以对于枚举的每个高度，找到这个高度的点所在位置，向四周拓展。如果周围点的高度 <= h，那么将此点与当前点并起来。（和边界合并可视为跟0合并。最终这一层的答案就是访问到的节点个数 - size[getFat(0)]。
#include#include #include #define N 105using namespace std;struct Node {int x, y;};vector a[N * N];int n, m, tot, h, ans;int fat[N * N], size[N * N];int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};bool vis[N][N];int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}int getFat(int x){ if(fat[x] == x) return x; return fat[x] = getFat(fat[x]);}void merge(int x, int y){ int fx = getFat(x), fy = getFat(y); if(fx == fy) return; if(size[fx] > size[fy]) swap(fx, fy); size[fy] += size[fx], fat[fx] = fy;}int cal(int x, int y){ if(x < 1 || x > n || y < 1 || y > m) return 0; return (x - 1) * m + y;}int main(){ freopen("water.in", "r", stdin); freopen("water.out", "w", stdout); cin >> n >> m; for(int i = 1; i <= n * m; i++) fat[i] = i, size[i] = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { int val = read(); h = max(h, val); a[val].push_back((Node){i, j}); } /** * 这种一层一层看的思路就是我原先的思路，然后我写挂了。（爆搜 * 但我没想到用并查集。枚举每一层高度，已知只要 <= 当前高度且与边界相连的点肯定 会流走。所以用遍历到的点个数 - 这种类型的点个数就是当前层的答案。那么“这种 类型”的点可以用并查集维护。 */ for(int i = 0; i <= h; i++) //这里必须要每个高度枚举到，因为这也是“一层水” { for(int j = 0; j < a[i].size(); j++) { int x = a[i][j].x, y = a[i][j].y; vis[x][y] = 1, tot++; for(int k = 1; k <= 4; k++) { int xx = x + dx[k], yy = y + dy[k]; if(xx < 1 || xx > n || yy < 1 || yy > m) merge(cal(x, y), cal(xx, yy)); if(vis[xx][yy]) merge(cal(x, y), cal(xx, yy)); } } ans += tot - size[getFat(0)]; } cout << ans; return 0;}