目录
1.带分数
题目描述
思路
AC代码
2、走迷宫
题目描述
思路
AC代码
3、蓝桥幼儿园
题目描述
思路
并查集模板
AC代码
4、跳石头
题目描述
思路
AC代码
1.带分数
题目描述
题目链接
100100 可以表示为带分数的形式：100=3+69258714100=3+69258714
还可以表示为：100=82+3546197100=82+3546197
注意特征：带分数中，数字 1∼91∼9 分别出现且只出现一次（不包含 00）。
类似这样的带分数，100100 有 1111 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼91∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<1061≤N<106
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
思路
dfs搜出1~9的全排列，将全排列分成三个数进行判断，符合条件的ans+1
AC代码
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int p[11];int vis[11];int n;int a, b, c;long long ans = 0;int f(int l, int r) { //合并l，r区间内数组为数int sum = 0;for (int i = l; i <= r; i++) {sum = sum * 10 + p[i];}return sum;}void dfs(int u) {if (u > 9) {for (int i = 1; i <= 7; i++) {for (int j = i + 1; j <= 8; j++) { //分为三段区间int a = f(1, i);int b = f(i + 1, j);int c = f(j + 1, 9);if (a + (b / c) == n && (b % c == 0)) ans++;}}return ;}for (int i = 1; i <= 9; i++) { //1~9全排列放入p[1]~p[9]if (!vis[i]) {p[u] = i;vis[i] = 1;dfs(u + 1);p[u] = 0;vis[i] = 0;}}}int main() {cin >> n;dfs(1);cout << ans;return 0;}
2、走迷宫
题目链接
题目描述
给定一个 N×M的网格迷宫G。G的每个格子要么是道路，要么是障碍物（道路用1表示，障碍物用0表示）。
已知迷宫的入口位置为 (x1,y1)，出口位置为 (x2,y2)。问从入口走到出口，最少要走多少个格子。
输入描述
输入第11行包含两个正整数N,M，分别表示迷宫的大小。
接下来输入一个 N×M的矩阵。若Gi,j=1表示其为道路，否则表示其为障碍物。
最后一行输入四个整数 x1,y1,x2,y2，表示入口的位置和出口的位置。
1≤N,M≤10^2，0≤Gi,j≤1，1≤x1,x2≤N，1≤y1,y2≤M。
输出描述
输出仅一行，包含一个整数表示答案。
若无法从入口到出口，则输出-1
输入
5 5 1 0 1 1 01 1 0 1 1 0 1 0 1 11 1 1 1 11 0 0 0 11 1 5 5
输出
8
思路
bfs，每遍历到道路mp[ ][ ]=1便将其染色成障碍mp[ ][ ]=0，可以减少一个bool数组判断是否已遍历。注意步数的处理
AC代码
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include<queue>using namespace std;#define x first #define y second const int N=101 ;typedef pair<int,int>PII;int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};int mp[N][N];int d[N][N];int n;int m;int qx,zx,qy,zy;bool check(int x,int y){if(x<1||y<1||x>n||y>m) return false;//越界return true;}int bfs(int x ,int y){queue<PII>q;q.push({x,y});//vis[x][y]=1;d[x][y]=0;while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int fx=t.x+dx[i],fy=t.y+dy[i];if(!check(fx,fy)) continue;//越界//if(vis[fx][fy]) continue;if(mp[fx][fy]==0) continue;//障碍mp[fx][fy]=0;d[fx][fy]=d[t.x][t.y]+1;//步数加一q.push({fx,fy});}}return d[zx][zy];}int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>mp[i][j];}}memset(d,-1,sizeof(d));cin>>qx>>qy>>zx>>zy;cout<<bfs(qx,qy);return 0;}
3、蓝桥幼儿园
题目链接
题目描述
蓝桥幼儿园的学生是如此的天真无邪，以至于对他们来说，朋友的朋友就是自己的朋友。
小明是蓝桥幼儿园的老师，这天他决定为学生们举办一个交友活动，活动规则如下：
小明会用红绳连接两名学生，被连中的两个学生将成为朋友。
小明想让所有学生都互相成为朋友，但是蓝桥幼儿园的学生实在太多了，他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你，请你帮忙写程序判断某两个学生是否为朋友（默认自己和自己也是朋友）。
输入描述
第11行包含两个正整数N,M，其中N表示蓝桥幼儿园的学生数量，学生的编号分别为1 ∼N。
之后的第 2∼M+1行每行输入三个整数，op , x , y
如果op = 1，表示小明用红绳连接了学生x和学生y。如果op=2，请你回答小明学生x和 学生y是否为朋友。
1
输出描述
对于每个op=2 的输入，如果x和y是朋友，则输出一行YES，否则输出一行NO。
输入
5 5 2 1 21 1 32 1 31 2 3 2 1 2
输出
NOYESYES
思路
并查集模板题
并查集模板
void init(){//初始化并查集for (int i = 1; i <= n; i ++ ) p[i] = i;}int find(int x)//路径压缩并查集{if (p[x] != x) p[x] = find(p[x]);return p[x];}//p[find(a)] = find(b);合并集合
AC代码
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N=2e5+10 ;int n,m;int x,y,op;int p[N];void init(){//初始化并查集for (int i = 1; i <= n; i ++ ) p[i] = i;}int find(int x)//路径压缩并查集{if (p[x] != x) p[x] = find(p[x]);return p[x];}//p[find(a)] = find(b);合并集合int main(){cin>>n>>m;init();while(m--){cin>>op>>x>>y;if(op==1){p[find(x)]=find(y);}else if(op==2){int a=find(x);int b=find(y);if(a==b) puts("YES");else puts("NO");}}return 0;}
4、跳石头
题目链接
题目描述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。
组委会已经选择好了两块岩石作为比赛起点和终点。
在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。
在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。
由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入格式
输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来 N 行，每行一个整数，第 i 行的整数 Di（0 < Di < L） 表示第 i 块岩石与起点的距离
这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
输出文件只包含一个整数，即最短跳跃距离的最大值。
数据范围
0≤M≤N≤500000
1≤L≤10^9
输入样例
5 50 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0
输出样例
8
思路
二分查找最短跳跃距离的最大值
cnt代表移走石头的数量
last表示上一块石头的位置
如果当前石头和上一块石头之间的距离比mid值小,代表可以移走当前石头。如果石头移走，last仍然是上一块石头的位置。
AC代码
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 1e5 + 10;typedef long long ll;int m, n;int s;int l, r;int d[N];bool check(int mid) {//check函数判断查找到的最短跳跃距离mid是否合法int last = 0;int cnt = 0;//移走石头数量for (int i = 1; i <= n; i ++ )if (d[i] - last < mid) cnt ++;//当二分查找到的mid大于两石头之间的距离时//代表最短跳跃距离仍然可以变大，可以把当前石块移走，移走石头数量cnt++else last = d[i];//否之则不移走石头，对下一对石头进行判断return cnt <= m;//cnt如果超过m个的上限，就不合法。}int main() {cin >> s >> n >> m;for (int i = 1; i <= n; i++) {cin >> d[i];}d[n + 1] = s; //记得加入终点的位置l = 1, r = s;//二分范围while (l < r) {int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}cout << r;return 0;}
今天的题目做的真爽，大部分是模板题
