当前位置：首页 > news >正文

洛谷刷题Day1——P1706+P1157+P2089+P3654

news 来源：原创 2025/9/16 7:48:05

1. P1706 全排列问题
- 题目描述
- 输入格式
- 输出格式
- 输入输出样例 #1
- - 输入 #1
  - 输出 #1
- 说明/提示
- 代码
2. P1157 组合的输出
- 题目描述
- 输入格式
- 输出格式
- 输入输出样例 #1
- - 输入 #1
  - 输出 #1
- 代码
3. P2089 烤鸡
- 题目背景
- 题目描述
- 输入格式
- 输出格式
- 输入输出样例 #1
- - 输入 #1
  - 输出 #1
- 说明/提示
- 代码
4. P3654 First Step (ファーストステップ)
- 题目背景
- 题目描述
- 输入格式
- 输出格式
- 输入输出样例 #1
- - 输入 #1
  - 输出 #1
- 说明/提示
- 代码1-写两个dfs函数，容易理解版
- 代码2-写一个dfs函数

1. P1706 全排列问题

题目描述

按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 $n$ 。

输出格式

由 $\sim n$ 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 $5$ 个场宽。

输入输出样例 #1

输入 #1

输出 #1

    1    2    31    3    22    1    32    3    13    1    23    2    1

说明/提示

$\leq n \leq 9$ 。

代码

#include <iostream>
#include <vector>
using namespace std;
const int N = 15;
bool st[N];
vector<int> path;
int n;
void dfs(int depth)
{if (depth == n){for (auto p : path) printf("%5d", p);puts("");return;}for (int i = 1; i <= n; i ++){if (!st[i]){st[i] = true;path.push_back(i);dfs(depth + 1);path.pop_back();st[i] = false;}}
}
int main()
{cin >> n;dfs(0);return 0;
}

2. P1157 组合的输出

题目描述

排列与组合是常用的数学方法，其中组合就是从 $n$ 个元素中抽出 $r$ 个元素（不分顺序且 $\le n$ ），我们可以简单地将 $n$ 个元素理解为自然数 $1,2,\dots,n$ ，从中任取 $r$ 个数。
现要求你输出所有组合。
例如 $n = 5, r = 3$ ，所有组合为：
$123, 124, 125, 134, 135, 145, 234, 235, 245, 345$ 。

输入格式

一行两个自然数 $\le r \le n)$ 。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
注意哦！输出时，每个数字需要 $3$ 个场宽。以 C++ 为例，你可以使用下列代码：

cout << setw(3) << x;

输出占 $3$ 个场宽的数 $x$ 。注意你需要头文件 iomanip。

输入输出样例 #1

输入 #1

5 3

输出 #1

1  2  31  2  41  2  51  3  41  3  51  4  52  3  42  3  52  4  53  4  5

代码

#include <iostream>
#include <vector>
using namespace std;
const int N = 25;
vector<int> path;
bool st[N];
int n, r;
void dfs(int depth, int father)
{if (depth == r){for (auto p : path) printf("%3d", p);puts("");return;}for (int i = 1; i <= n; i ++){if (!st[i] && father < i) // 组合是递增序列，所以必须保证先选进去的点要更小{st[i] = true;path.push_back(i);dfs(depth + 1, i);path.pop_back();st[i] = false;}}
}
int main()
{cin >> n >> r;dfs(0, -1);return 0;
}

3. P2089 烤鸡

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 $10$ 种配料（芥末、孜然等），每种配料可以放 $1$ 到 $3$ 克，任意烤鸡的美味程度为所有配料质量之和。
现在， Hanke 想要知道，如果给你一个美味程度 $n$ ，请输出这 $10$ 种配料的所有搭配方案。

输入格式

一个正整数 $n$ ，表示美味程度。

输出格式

第一行，方案总数。
第二行至结束， $10$ 个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个 $0$ 。

输入输出样例 #1

输入 #1

输出 #1

10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1

说明/提示

对于 $100\%$ 的数据， $\leq 5000$ 。

代码

#include <iostream>
#include <vector>
using namespace std;
vector<int> path;
vector<vector<int>> paths;
int n;
void dfs(int depth)
{if (depth == 10){int tmp = 0;for (auto p : path) tmp += p;if (tmp == n) paths.push_back(path);return;}for (int i = 0; i < 3; i ++){path.push_back(i + 1);dfs(depth + 1);path.pop_back();}
}
int main()
{cin >> n;dfs(0);cout << paths.size() << endl;if (paths.size()){for (auto pa : paths){for (auto p : pa)cout << p << ' ';puts("");}}return 0;
}

4. P3654 First Step (ファーストステップ)

题目背景

知らないことばかりなにもかもが（どうしたらいいの？）
一切的一切尽是充满了未知数（该如何是好）
それでも期待で足が軽いよ（ジャンプだ！）
但我仍因满怀期待而步伐轻盈（起跳吧！）
温度差なんていつか消しちゃえってね
冷若冰霜的态度有朝一日将会消失得无影无踪
元気だよ元気をだしていくよ
拿出活力打起精神向前迈进吧

我们 Aqours，要第一次举办演唱会啦！

虽然学生会长看上去不怎么支持我们的样子，可是有了理事长的支持，我们还是被允许在校内的篮球场里歌唱！

歌曲也好好地准备过了，名字叫“最喜欢的话就没问题！ (ダイスキだったらダイジョウブ！)“，大家一定会喜欢的吧！

演唱会一定会顺利进行的！

希望不要发生停电什么的事故哦……！

题目描述

可是……这个篮球场，好像很久没有使用过的样子啊……

里面堆满了学校的各种杂物呢……

我们 Aqours 的成员要怎么在里面列队站下呢？

我们浦之星女子学院的篮球场是一个 $R$ 行 $C$ 列的矩阵，其中堆满了各种学校的杂物 (用 # 表示)，空地 (用 . 表示) 好像并不多的样子呢……

我们 Aqours 现在已经一共有 $K$ 个队员了，要歌唱舞蹈起来的话，我们得排成一条 $1\times K$ 的直线，一个接一个地站在篮球场的空地上呢 (横竖均可)。

我们想知道一共有多少种可行的站位方式呢。

Aqours 的真正的粉丝的你，能帮我们算算吗？

输入格式

第一行三个整数 $R, C, K$ 。

接下来的 $R$ 行 $C$ 列，表示浦之星女子学院篮球场。

输出格式

总共的站位方式数量。

输入输出样例 #1

输入 #1

5 5 2
.###.
##.#.
..#..
#..#.
#.###

输出 #1

说明/提示

	$R$	$C$	$K$	备注
$1\sim2$	$\leq 10$	$\leq 10$	$\leq \min(R,C)$	无
$3\sim4$	$\leq 100$	$\leq 100$	$\leq 1$	无
$5\sim6$	$\leq 100$	$\leq 100$	$\leq \min(R,C)$	没有障碍
$7\sim10$	$\leq 100$	$\leq 100$	$\leq \min(R,C)$	无

对于所有数据， $\leq R,C \leq 100$ ， $\leq k \leq \min(R,C)$ 。

代码1-写两个dfs函数，容易理解版

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
vector<PII> points;
const int N = 110;
char g[N][N];
bool is_visited[N][N];
int res;
int r, c, k;
void right_dfs(int x, int y, int depth)
{if (depth == k){res ++;return;}if (x < 0 || x >= r || y < 0 || y >= c || g[x][y] == '#') return;right_dfs(x, y + 1, depth + 1);
}
void down_dfs(int x, int y, int depth)
{if (depth == k){res ++;return;}if (x < 0 || x >= r || y < 0 || y >= c || g[x][y] == '#') return;down_dfs(x + 1, y, depth + 1);
}
int main()
{cin >> r >> c >> k;for (int i = 0; i < r; i ++)for (int j = 0; j < c; j ++){cin >> g[i][j];if (g[i][j] == '.') points.push_back({i, j});}if (k == 1) {cout << points.size() << endl;return 0;}for (auto p : points){auto x = p.first, y = p.second;right_dfs(x, y, 0); // 向右深搜down_dfs(x, y, 0);// 向下深搜g[x][y] = '#';}cout << res << endl;return 0;
}

代码2-写一个dfs函数

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
vector<PII> points;
const int N = 110;
char g[N][N];
bool is_visited[N][N];
int res;
int r, c, k;
int dx[2] = {0, 1}, dy[2] = {1, 0};
void dfs(int x, int y, int dire, int depth)
{if (depth == k){res ++;return;}if (x < 0 || x >= r || y < 0 || y >= c || g[x][y] == '#') return;auto nx = x + dx[dire], ny = y +  dy[dire];dfs(nx, ny, dire, depth + 1);
}
int main()
{cin >> r >> c >> k;for (int i = 0; i < r; i ++)for (int j = 0; j < c; j ++){cin >> g[i][j];if (g[i][j] == '.') points.push_back({i, j});}if (k == 1) {cout << points.size() << endl;return 0;}for (auto p : points){auto x = p.first, y = p.second;dfs(x, y, 0, 0); // 向右深搜dfs(x, y, 1, 0);// 向下深搜g[x][y] = '#';}cout << res << endl;return 0;
}

目录

1. P1706 全排列问题

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

代码

2. P1157 组合的输出

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

代码

3. P2089 烤鸡

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

代码

4. P3654 First Step (ファーストステップ)

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

代码1-写两个dfs函数，容易理解版

代码2-写一个dfs函数

相关文章：