1 小埋的排列序列
给出集合
[1,2,3,......,𝑛]
[1,2,3,......,n] ,其所有元素共有 𝑛! 种排列。
按招大小顺序列出所有排列情况，并一一标记，当 𝑛=所有排列如下：
1.“123”
2.“132”
3.“213”
4.“231“
5.“312”
6.“321”
给定 𝑛和 𝑘返回第 𝑘个排列。
输入格式
第一行输入两个整数
𝑛 和 𝑘
输出格式
输出第 k 个序列。
样例
Input 1
3 3
Output 1
213
Input 2
4 9
Output 2
2314
数据范围
1<=𝑛<=9
1<=k<=n!
这道题是一个全排列，肥肠的简单
我相信在座的各位应该都会了吧
那么我们就把伪代码给各位
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005],book[10001];
int sum;
//搜索
void dfs(int x){
if(x>n){
//结束条件以及输出
}
for(int i=1;i<=n;i++){
//判断是否走过
}
}
int main(){
//输入
//调用函数
return 0;
}
- 没有被选中的区间
### **题目描述：**
数轴上有 𝑛n 个点，编号为 11 到 𝑛n。
小信有 m 个区间，区间可能有重叠。小信要选出 m−1 个区间覆盖尽可能多的点。在这之后，小信想知道没被覆盖的点的数量，以及没有选中的区间的编号，如果有多个满足条件的区间，输出最大的那个。
### **输入格式：**
第一行包含两个整数 n, m。
接下来 𝑚 行，每行包含两个整数 𝐿i, Ri 。
### **输出格式：**
输出两个整数，第一个整数表示没有被选中的区间编号，如果有多个满足条件的区间，输出最大的那个，编号从 11 开始；第二个数表示没有被覆盖的点的数量。
### **样例1输入：**
10 4 1 6 4 9 3 4 5 8
### **样例1输出：**
4 1
这道题呢需要用到前缀和和插分去把m-1个的区间中没有被遍历到的去找到在输出，废话不多说
伪代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[100001],b[100001],x[100001],y[100001];
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i];
...
}
int cnt=0;
for(int i=1;i<=n;i++){
...
}
int ans=1e9;
int sum=0;
for(int i=1;i<=m;i++){
int s=...];
if(...){
ans=s;
sum=i;
}
}
cout<<sum<<" "<<ans<<endl;
return 0;
}
- 锻炼身体的路径
题目描述
时间：1s 空间：256M
题目描述：
有一个 𝑛×𝑚n×m 的地图，空地为’.‘，高楼为’#'，小信的家在 ‘S’。
小信想找一条锻炼身体的路径，路径需要从家出发，不经过相同的空地，最后回到家。出于锻炼身体的目的，这条路径的长度必须至少为4，也就是说除了终点和起点都是家以外，经过的不同的空地个数至少为 3。
小信想知道这样的路径存不存在。当然，小信无法通过有高楼的地方，所以可能不存在这样的路径。
输入格式：
第一行包含两个整数 n,m。
接下来包含一个 n×m 的地图，地图只包含 ‘.’,‘#’,‘S’ 三种字符。
输出格式：
如果存在锻炼身体的路径，输出"Yes"，否则输出"No"。
样例1输入：
4 4
....
#.#.
#S#.
....
样例1输出：
Yes
样例2输入：
4 4
.#..
#.#.
#S#.
....
样例2输出：
No
这道题是一个典型的搜索题
但是我们只需要遍历他有没有路的同时再看一看他的路线大不大于3就行了
#include<bits/stdc++.h>
using namespace std;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int n, m, x, y;
map<int, map<int, bool> > mp;
map<int, map<int, int> > flag;
void dfs(int x, int y, int xd, int yd, int res) {
if(...)
if(...){ cout << "Yes"<<endl;... }
else return;
if(...) return;
else flag[x][y] = res;
for(int i = 0; i < 4; i ++) {
...
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
char s;
cin >> s;
if(...) ...
else if(...) ...;
else...
}
}
dfs(...);
cout<<"No“<<endl;
return 0;
}
- 大哈的变换迷宫
【题目描述】
大哈已经是个成年人了，网页游戏在他当年还是风靡一时。他记忆中有这么一款游戏。
角色一开始在迷宫的(1,1)处，最终要到达(n,n)的位置，迷宫中有一些障碍物，障碍不能走。同时迷宫中有些点是彩色点，彩色点的颜色按照这个点的颜色序列每秒变换一次，变完了又会循环，比如这个颜色点会这么变，“1 2 4”,所以它第一秒是1，第二秒是2，第三秒是4，第四秒又是1，依次往复。当你到达彩色点的时候，你可以选择把他当普通点直接走上去，也可以选择在彩色点传送，传送到任意一个此时和它颜色相同的彩色点上，传送不需要时间。大哈可以往上下左右走，走一格花费1秒，他也可以选择不动，等一秒，因为说不定等一秒，下一步就可以直接传送了。大哈现在已经学过一些算法了，他想知道到达(n,n)的最短时间是多少？
【输入格式】
第一行，一个整数n
接下来n行，每行n个整数，用空格隔开。每个整数是0或者1，0表示空地，1表示障碍物。保证起点和终点都是0
接下来1行，一个整数t，表示彩色格子的数量
接下来t行，每行第一个和第二个整数xi和yi表示这个彩色格子的坐标；第三个整数mi，表示第i个彩色格子的颜色序列长度，后面跟着mi个整数，表示当前这个彩色点的颜色变换顺序
【输出格式】
一个整数，表示到达终点的最短时间，如果不能到达终点，输出-1.
【样例输入】
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 1 1
0 0 1 0 0
3
2 2 3 1 2 3
3 4 5 1 2 1 2 4
5 4 4 5 5 5 4
## 【样例输出】
21
## 【数据范围】
n<=1000, t<=10, 颜色种类不超过10，mi不超过10
//未完待续