太仓建设工程信息网站,绘制网站地图,wnmp搭建后怎么做网站,东城免费做网站文章目录 一、日志统计 1、1 题目描述 1、2 题解关键思路与解答 二、献给阿尔吉侬的花束 2、1 题目描述 2、2 题解关键思路与解答 三、红与黑 3、1 题目描述 3、2 题解关键思路与解答 3、2、1 dfs题解代码 3、2、2 bfs题解答案 四、交换瓶子 4、1 题目描述 4、2 题解关键思路与… 文章目录 一、日志统计 1、1 题目描述 1、2 题解关键思路与解答 二、献给阿尔吉侬的花束 2、1 题目描述 2、2 题解关键思路与解答 三、红与黑 3、1 题目描述 3、2 题解关键思路与解答 3、2、1 dfs题解代码 3、2、2 bfs题解答案 四、交换瓶子 4、1 题目描述 4、2 题解关键思路与解答 本篇文章针对蓝桥杯比赛的考点列出双指针、BFS和DFS与图论的相关习题以及知识点的解释。希望本篇文章会对你有所帮助。 一、日志统计
1、1 题目描述 题目来源第九届蓝桥杯省赛CB组,第九届蓝桥杯省赛JAVAB组 题目难度简单 题目描述小明维护着一个程序员论坛。现在他收集了一份”点赞”日志日志共有 N 行。 其中每一行的格式是 ts id 表示在 ts 时刻编号 id 的帖子收到一个”赞”。现在小明想统计有哪些帖子曾经是”热帖”。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞小明就认为这个帖子曾是”热帖”。 具体来说如果存在某个时刻 T 满足该帖在 [T,TD) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞该帖就曾是”热帖”。给定日志请你帮助小明统计出所有曾是”热帖”的帖子编号。 输入格式 第一行包含三个整数 N,D,K。 以下 N 行每行一条日志包含两个整数 ts 和 id。 输出格式 按从小到大的顺序输出热帖 id。 每个 id 占一行。 数据范围 1≤K≤N≤1e5, 0≤ts,id≤1e5, 1≤D≤10000。 输入样例 7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3输出样例 1
3 1、2 题解关键思路与解答 我们大概叙述一下题目的意思在一段时间内某个帖子的赞达到一定数量就被称为热帖。这道题中关键的就去维护一段时间段看这个时间段内该帖子是否达到一定能够赞数。这个时候我们就需要两个指针并不是真正的指针是指变量来维护这个时间段的区间了。我们先去要对输入的时间进行一个排序然后再去维护这个区间开一个记录状态的数组去看是否有达到热帖的。我们结合着代码一起理解一下 #includeiostream
#includecstring
#includealgorithm
#includecstdio#define x first
#define y secondusing namespace std;typedef pairint,int PII;const int N1e510;PII q[N];
int cnt[N];
bool st[N];int n,d,k;
int main()
{scanf(%d%d%d, n, d, k);for(int i0;in;i)scanf(%d%d,q[i].x,q[i].y);sort(q,qn);for(int i0,j0;in;i){int idq[i].y;cnt[id];//时间段区间while(q[i].x-q[j].xd){cnt[q[j].y]--;j;}if(cnt[id]k)st[id]true;}for(int i0;iN;i)if(st[i])printf(%d\n,i);return 0;
}
二、献给阿尔吉侬的花束
2、1 题目描述 题目来源《信息学奥赛一本通》 题目难度简单 题目描述阿尔吉侬是一只聪明又慵懒的小白鼠它最擅长的就是走各种各样的迷宫。 今天它要挑战一个非常大的迷宫研究员们为了鼓励阿尔吉侬尽快到达终点就在终点放了一块阿尔吉侬最喜欢的奶酪。 现在研究员们想知道如果阿尔吉侬足够聪明它最少需要多少时间就能吃到奶酪。 迷宫用一个 R×C的字符矩阵来表示。 字符 S 表示阿尔吉侬所在的位置字符 E 表示奶酪所在的位置字符 # 表示墙壁字符 . 表示可以通行。 阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置但不能走出地图边界。 输入格式 第一行是一个正整数 T表示一共有 T 组数据。 每一组数据的第一行包含了两个用空格分开的正整数 R 和 C表示地图是一个 R×C 的矩阵。 接下来的 R 行描述了地图的具体内容每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。 输出格式: 对于每一组数据输出阿尔吉侬吃到奶酪的最少单位时间。 若阿尔吉侬无法吃到奶酪则输出“oop!”只输出引号里面的内容不输出引号。 每组数据的输出结果占一行。 数据范围: 1T≤10, 2≤R,C≤200。 输入样例 3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.输出样例 5
1
oop! 2、2 题解关键思路与解答 首先我们要住注意的是本题的输入格式要注意的是输入 0 0 时结束。我们要找到开始的位置和奶酪的位置。我们需要从开始位置出发且是最小路径到达奶酪位置。这时我们可以想到洪水灌溉法Flood Fill。洪水灌溉法是指dfs深度优先搜索和 bfs宽度优先搜索。dfs是采用递归的方法不断实现覆盖。dfs与bfs又有所不同dfs写起来代码简单bfs可以求出最短路径各有优势。宽度优先是一层一层进行遍历的。是用队列进行维护实现的。队列是先进先出的原则。我们先把第一个数据入队。然后再循环进行维护。除去对头入队与对头相关的点直到队列为空。bfs有固定模板通过本题我们可以进行记一下。我们结合代码理解一下 #includeiostream
#includealgorithm
#includecstring
#includecstdio
#includequeueusing namespace std;#define x first
#define y secondtypedef pairint,int PII;const int N210;int n,m;int dist[N][N];
char g[N][N];int bfs(PII start,PII end)
{queuePII q;memset(dist,-1,sizeof dist); //初始dsit为-1表示为没有走过该点dist[start.x][start.y]0;q.push(start);while(q.size()){PII tq.front();q.pop();int dx[4]{-1,1,0,0},dy[4]{0,0,-1,1};for(int i0;i4;i){int xt.xdx[i],yt.ydy[i];if(x0 ||xn || y0 || ym)continue;if(g[x][y]#)continue;if(dist[x][y]!-1)continue;dist[x][y]dist[t.x][t.y]1;if(g[x][y]E)return dist[x][y];q.push({x,y});}}return -1;
}
int main()
{int T;cinT;while(T--){scanf(%d%d,n,m);for(int i0;in;i)scanf(%s,g[i]);PII start,end;for(int i0;in;i)for(int j0;jm;j)if(g[i][j]S)start{i,j};else if(g[i][j]E)end{i,j};int distancebfs(start,end);if(distance-1)puts(oop!);elseprintf(%d\n,distance);}return 0;
}
三、红与黑
3、1 题目描述 题目来源《信息学奥赛一本通》 题目难度简单 题目描述有一间长方形的房子地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上只能向相邻上下左右四个方向的黑色瓷砖移动。请写一个程序计算你总共能够到达多少块黑色的瓷砖。 输入格式 输入包括多个数据集合。每个数据集合的第一行是两个整数 W 和 H分别表示 x 方向和 y 方向瓷砖的数量。 在接下来的 H 行中每行包括 W 个字符。每个字符表示一块瓷砖的颜色规则如下 1‘.’黑色的瓷砖 2‘#’红色的瓷砖 3‘’黑色的瓷砖并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时表示输入结束。 输出格式 对每个数据集合分别输出一行显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。 数据范围 1≤W,H≤20。 输入样例 6 9
....#.
.....#
......
......
......
......
......
#...#
.#..#.
0 0输出样例 453、2 题解关键思路与解答 该题我们就可以用dfs也可以用bfs进行解答。但是用dfs时我们要注意的是我们不需要有回复现场的操作与第十四届蓝桥杯第三期模拟赛 C/C B组 原题与详解 填空题中的最大连通块类似。这道题目每个格子是一个状态每个格子只会搜索一次所以不需要恢复现场。我们分别看一下dfs与bfs的解题代码 3、2、1 dfs题解代码
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 25;int n, m;
char g[N][N];
bool st[N][N];int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};int dfs(int x, int y)
{int cnt 1;st[x][y] true;for (int i 0; i 4; i ){int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b m) continue;if (g[a][b] ! .) continue;if (st[a][b]) continue;cnt dfs(a, b);}return cnt;
}int main()
{while (cin m n, n || m){for (int i 0; i n; i ) cin g[i];int x, y;for (int i 0; i n; i )for (int j 0; j m; j )if (g[i][j] ){x i;y j;}memset(st, 0, sizeof st);cout dfs(x, y) endl;}return 0;
}3、2、2 bfs题解答案
#includebits/stdc.husing namespace std;#define x first
#define y secondconst int N 25;typedef pairint,int PII;char g[N][N];int n,m;int dx[4]{-1,1,0,0},dy[4]{0,0,-1,1};int bfs(int x,int y)
{queuePII q;q.push({x,y});g[x][y]#;int res0;while(q.size()){PII tq.front();q.pop();res;for(int i0;i4;i){int at.xdx[i],bt.ydy[i];if(a0 || an || b0 || bm)continue;if(g[a][b]!.)continue;q.push({a,b});g[a][b]#;} }return res;
}
int main()
{while(cinmn,n||m){for(int i0;in;i)cing[i];int x,y;for(int i0;in;i)for(int j0;jm;j){if(g[i][j]){xi;yj;}}coutbfs(x,y)endl;}return 0;
}
四、交换瓶子
4、1 题目描述 题目来源第七届蓝桥杯省赛CB组,第七届蓝桥杯省赛JAVAA组 题目难度简单 题目描述有 N 个瓶子编号 1∼N放在架子上。比如有 5 个瓶子 2 1 3 5 4要求每次拿起 2 个瓶子交换它们的位置。经过若干次后使得瓶子的序号为 1 2 3 4 5对于这么简单的情况显然至少需要交换 2 次就可以复位。如果瓶子更多呢你可以通过编程来解决。 输入格式 第一行包含一个整数 N表示瓶子数量。 第二行包含 N 个整数表示瓶子目前的排列状况。 输出格式 输出一个正整数表示至少交换多少次才能完成排序。 数据范围 1≤N≤10000, 输入样例1 5
3 1 2 5 4输出样例1 3输入样例2 5
5 4 3 2 1输出样例2 2 4、2 题解关键思路与解答 本题用到了图论的相关知识。我们把每个位置对应瓶子的编号进行连接会形成相应的环。我们看题目中的例1 我们需要做的是形成5个环也就是自己指向自己。我们发先对一个含有两个及以上元素的环进行元素交换操作一个环就会变成两个环。初始环越多我们需要操作的次序越少因为环中的元素很少。假如一个环中的元素有5个我们最少的步数为4次。这样我们总结出规律是最少需要操作的部数元素个数-环的个数。我们看代码 #includeiostream
#includealgorithm
#includecstringusing namespace std;const int N1e410;int b[N];
bool st[N];int main()
{int n;cinn;for(int i1;in;i)cinb[i];int cnt0;for(int i1;in;i){if(!st[i]){cnt; // 统计环的个数for(int ji;!st[j];jb[j])st[j]true;}}coutn-cntendl;return 0;
} 文章转载自： http://www.morning.jxfmn.cn.gov.cn.jxfmn.cn http://www.morning.xhsxj.cn.gov.cn.xhsxj.cn http://www.morning.qfnrx.cn.gov.cn.qfnrx.cn http://www.morning.ghlyy.cn.gov.cn.ghlyy.cn http://www.morning.ltffk.cn.gov.cn.ltffk.cn http://www.morning.dmwck.cn.gov.cn.dmwck.cn http://www.morning.xwqxz.cn.gov.cn.xwqxz.cn http://www.morning.qfrsm.cn.gov.cn.qfrsm.cn http://www.morning.cwlxs.cn.gov.cn.cwlxs.cn http://www.morning.wrcgy.cn.gov.cn.wrcgy.cn http://www.morning.rgxcd.cn.gov.cn.rgxcd.cn http://www.morning.lmjkn.cn.gov.cn.lmjkn.cn http://www.morning.gcthj.cn.gov.cn.gcthj.cn http://www.morning.lwwnq.cn.gov.cn.lwwnq.cn http://www.morning.ckdgj.cn.gov.cn.ckdgj.cn http://www.morning.qlrtd.cn.gov.cn.qlrtd.cn http://www.morning.xkyst.cn.gov.cn.xkyst.cn http://www.morning.crkhd.cn.gov.cn.crkhd.cn http://www.morning.kxgn.cn.gov.cn.kxgn.cn http://www.morning.jpfpc.cn.gov.cn.jpfpc.cn http://www.morning.ftnhr.cn.gov.cn.ftnhr.cn http://www.morning.ychoise.com.gov.cn.ychoise.com http://www.morning.lokext.com.gov.cn.lokext.com http://www.morning.nqmkr.cn.gov.cn.nqmkr.cn http://www.morning.xlztn.cn.gov.cn.xlztn.cn http://www.morning.jhrqn.cn.gov.cn.jhrqn.cn http://www.morning.ntzfj.cn.gov.cn.ntzfj.cn http://www.morning.ykmkz.cn.gov.cn.ykmkz.cn http://www.morning.hxmqb.cn.gov.cn.hxmqb.cn http://www.morning.lynb.cn.gov.cn.lynb.cn http://www.morning.gfqj.cn.gov.cn.gfqj.cn http://www.morning.ghxzd.cn.gov.cn.ghxzd.cn http://www.morning.plwfx.cn.gov.cn.plwfx.cn http://www.morning.pfkrw.cn.gov.cn.pfkrw.cn http://www.morning.mqfw.cn.gov.cn.mqfw.cn http://www.morning.zfqdt.cn.gov.cn.zfqdt.cn http://www.morning.hpjpy.cn.gov.cn.hpjpy.cn http://www.morning.tcylt.cn.gov.cn.tcylt.cn http://www.morning.sgbsr.cn.gov.cn.sgbsr.cn http://www.morning.krswn.cn.gov.cn.krswn.cn http://www.morning.rstrc.cn.gov.cn.rstrc.cn http://www.morning.qrhh.cn.gov.cn.qrhh.cn http://www.morning.jntcr.cn.gov.cn.jntcr.cn http://www.morning.mmqng.cn.gov.cn.mmqng.cn http://www.morning.ntyanze.com.gov.cn.ntyanze.com http://www.morning.zdbfl.cn.gov.cn.zdbfl.cn http://www.morning.uycvv.cn.gov.cn.uycvv.cn http://www.morning.rstrc.cn.gov.cn.rstrc.cn http://www.morning.rkfwr.cn.gov.cn.rkfwr.cn http://www.morning.nbsfb.cn.gov.cn.nbsfb.cn http://www.morning.gqksd.cn.gov.cn.gqksd.cn http://www.morning.msfqt.cn.gov.cn.msfqt.cn http://www.morning.ishoufeipin.cn.gov.cn.ishoufeipin.cn http://www.morning.jsljr.cn.gov.cn.jsljr.cn http://www.morning.yltyr.cn.gov.cn.yltyr.cn http://www.morning.fnnkl.cn.gov.cn.fnnkl.cn http://www.morning.fnywn.cn.gov.cn.fnywn.cn http://www.morning.jwxnr.cn.gov.cn.jwxnr.cn http://www.morning.yjdql.cn.gov.cn.yjdql.cn http://www.morning.lmnbp.cn.gov.cn.lmnbp.cn http://www.morning.hkgcx.cn.gov.cn.hkgcx.cn http://www.morning.tcylt.cn.gov.cn.tcylt.cn http://www.morning.wscfl.cn.gov.cn.wscfl.cn http://www.morning.yrbq.cn.gov.cn.yrbq.cn http://www.morning.dyght.cn.gov.cn.dyght.cn http://www.morning.rxdsq.cn.gov.cn.rxdsq.cn http://www.morning.krbjb.cn.gov.cn.krbjb.cn http://www.morning.mjdbd.cn.gov.cn.mjdbd.cn http://www.morning.pzdxg.cn.gov.cn.pzdxg.cn http://www.morning.jfjqs.cn.gov.cn.jfjqs.cn http://www.morning.gyfhk.cn.gov.cn.gyfhk.cn http://www.morning.qhrlb.cn.gov.cn.qhrlb.cn http://www.morning.bsgfl.cn.gov.cn.bsgfl.cn http://www.morning.wlqbr.cn.gov.cn.wlqbr.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.rnygs.cn.gov.cn.rnygs.cn http://www.morning.rglzy.cn.gov.cn.rglzy.cn http://www.morning.rxsgk.cn.gov.cn.rxsgk.cn http://www.morning.jxcwn.cn.gov.cn.jxcwn.cn http://www.morning.qpnb.cn.gov.cn.qpnb.cn
