一、带分数（全排列）
题目链接：带分数 - 蓝桥云课 (lanqiao.cn)
题目要求：
100 可以表示为带分数的形式：100 = 3 + 69258 / 714
还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0 ）。
类似这样的带分数，100 有 11 种表示法。
解题思路：
全排列出1-9，排列出来所有的情况，在所有的排列中，枚举所有假分数的情况就行。
#include<bits/stdc++.h> using namespace std; int a[210]; bool st[210]; int ans,n; void init() { int aa=0,bb=0,cc=0; for(int i=1;i<=7;i++) { aa=0; for(int k=1;k<=i;k++) { aa*=10; aa+=a[k]; } for(int j=i+1;j<=8;j++) { bb=0,cc=0; for(int k=i+1;k<=j;k++) { bb*=10; bb+=a[k]; } for(int k=j+1;k<=9;k++) { cc*=10; cc+=a[k]; } if(bb%cc) { continue; } if(aa+bb/cc==n) { ans++; } } } } void dfs(int u) { if(u==9) { init(); } for(int i=1;i<=9;i++) { if(!st[i]) { st[i]=true; a[u+1]=i; dfs(u+1); st[i]=false; } } } int main() { cin>>n; dfs(0); cout<<ans<<endl; }
二、走迷宫（bfs）
题目链接：走迷宫 - 蓝桥云课 (lanqiao.cn)
题目要求：
给定一个 N×M 的网格迷宫 GG 的每个格子要么是道路，要么是障碍物（道路用 1 表示，障碍物用 0 表示）。
已知迷宫的入口位置为 (x1,y1)，出口位置为 (x2,y2)。问从入口走到出口，最少要走多少个格子。
解题思路：
BFS套就完了。
#include<bits/stdc++.h> using namespace std; const int N = 110; typedef pairPII; queueq; int a,b,c,t; int g[N][N],d[N][N]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int n,m; int bfs(int x,int y) { q.push({x,y}); d[x][y] = 0; while(q.size()) { PII t = q.front(); q.pop(); for(int i=0;i<4;i++) { int xx = t.first + dx[i]; int yy = t.second + dy[i]; if(d[xx][yy]==-1&&g[xx][yy]==1) { d[xx][yy]=d[t.first][t.second]+1; q.push({xx, yy}); } } } return d[c][t]; } int main() { cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> g[i][j]; } } memset(d, -1, sizeof d); cin >> a >> b >> c >> t; cout << bfs(a, b); return 0; }
三、蓝桥幼儿园（并查集）
题目链接：蓝桥幼儿园 - 蓝桥云课 (lanqiao.cn)
题目要求：
蓝桥幼儿园的学生是如此的天真无邪，以至于对他们来说，朋友的朋友就是自己的朋友。
小明是蓝桥幼儿园的老师，这天他决定为学生们举办一个交友活动，活动规则如下：
小明会用红绳连接两名学生，被连中的两个学生将成为朋友。
小明想让所有学生都互相成为朋友，但是蓝桥幼儿园的学生实在太多了，他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你，请你帮忙写程序判断某两个学生是否为朋友（默认自己和自己也是朋友）。
解题思路：
并查集模板 加一个路径压缩，在查询程序 find_set() 中，查询元素 i 所属的集，需要搜索路径找到根结点，返回的结果是根结点。这条搜索路径可能很长，导致超时。
#include<bits/stdc++.h> using namespace std; const int maxn = 8e5+5; int s[maxn]; void init_set(){ for(int i = 1; i <= maxn; i++) s[i] = i; } int find_set(int x){ if(x != s[x]) s[x] = find_set(s[x]); return s[x]; } void merge_set(int x, int y){ x = find_set(x); y = find_set(y); if(x != y) s[x] = s[y]; } int main (){ int op, n, m, x, y; init_set(); cin >> n >> m; while(m--){ cin >> op >> x >> y; if(op == 1) merge_set(x, y); if(op == 2){ if(find_set(x)==find_set(y)) cout << "YES"<<endl; else cout << "NO"<<endl; } } return 0; }
四、跳石头（贪心二分）
题目链接：跳石头 - 蓝桥云课 (lanqiao.cn)
题目要求：
一年一度的"跳石头"比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走M 块岩石（不能移走起点和终点的岩石）。
解题思路：
直接二分加贪心。
#include<bits/stdc++.h> using namespace std; int L,N,M,a[100010]; bool ok(int x) { int ret = 0, sx = 0; for(int i=1;i<=N;i++) { if(a[i]-a[sx] { ret++; } else { sx = i; } } return ret<=M; } int main() { cin>>L>>N>>M; for(int i=1;i<=N;i++) { cin>>a[i]; } int j=L,i=1; while(i<=j) { int mid = (i+j)/2; if(ok(mid)) { i = mid+1; } else { j = mid-1; } } cout<<i-1 return 0; }
