C/C++编程五级 题库
漫漫回国路
2020年5月,国际航班机票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(不考虑转机次数和机票价格)。
时间限制:1000
内存限制:65536
输入
第一行为case个数n(n < 10)。 每一个case,第一行为机场个数N,N ≤ 10。 之后的N行,每一行包含N个整数。第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个机场出发到第j个机场的能买到的航班的最低票价t(0 < t < 10000)。如果不幸没有航班,那么用-1表示。第i行第i个整数为0。 起点华盛顿杜勒斯国际机场的编号为1,终点北京首都国际机场的编号为N。
输出
每一个case一行。 能够回国,输出字符串:YES。如果无法回国,输出字符串:NO
样例输入
2 3 0 100 -1 -1 0 200 -1 -1 0 4 0 1 5 -1 3 0 1 -1 2 4 0 -1 4 1 1 0
样例输出
YES NO
// 广搜
#include <bits/stdc++.h>
using namespace std;
int a[12][12], n;
bool v[12][12];
bool bfs(int p) {
queue<int> q;
q.push(p);
v[p][p] = true;
while (!q.empty()) {
int h = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (!v[h][i] && a[h][i] > 0) {
if (i == n)
return true;
else {
q.push(i);
v[h][i] = true;
}
}
}
}
return false;
}
int main() {
int k;
cin >> k;
while (k--) {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
if (bfs(1))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}// 参考代码2
// 深度优先搜索
#include <stdbool.h>
#include <stdio.h>
#define MAX_N 10
#define INF 10000
int airports[MAX_N][MAX_N]; // 存储机场之间的航班票价
bool visited[MAX_N]; // 记录机场是否被访问过
int n; // 机场个数
bool found; // 是否找到回国路径
void dfs(int start, int end) {
if (start == end) {
found = true; // 找到回国路径
return;
}
visited[start] = true;
for (int i = 1; i <= n; i++) {
if (!visited[i] && airports[start][i] != -1) {
dfs(i, end);
}
}
}
bool canReturn() {
found = false;
for (int i = 1; i <= n; i++) {
visited[i] = false;
}
dfs(1, n);
return found;
}
int main() {
int cases;
scanf("%d", &cases);
while (cases--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &airports[i][j]);
}
}
if (canReturn()) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}通配符匹配
给定一个字符串s和一个字符模式p,请实现一个支持'?'和'*'的通配符匹配功能。
其中‘?’可以匹配任何单个字符,如‘a?c’可以成功匹配‘aac’,‘abc’等字符串,但不可匹配‘ac’,‘aaac’等字符串 。
‘*’ 可以匹配任意长度字符串(包括空字符串),如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串,但不可匹配‘acb’,‘cac’等字符串。
两个字符串完全匹配才算匹配成功。
时间限制:2000
内存限制:262144
输入
输入为一个数字n表示测试字符串与字符模式对数,换行。(n ≤ 30) 后续2n行为每组匹配的s与p,每行字符串后换行。 s 非空,只包含从 a-z 的小写字母。 p 非空,只包含从 a-z 的小写字母,以及字符 ? 和 *。 字符串s和p的长度均小于50
输出
每一组匹配串匹配成功输出‘yes’,否则输出‘no’。
样例输入
3 abc abc abc a*c abc a??c
样例输出
yes yes no
#include <iostream>
#include <cstring>
using namespace std;
bool isMatch(char* s, char* p) {
int m = strlen(s);
int n = strlen(p);
int i = 0; // s的指针
int j = 0; // p的指针
int star = -1; // 上一个星号的位置
int match = 0; // 上一个星号匹配到的位置
while (i < m) {
if (j < n && (p[j] == '?' || s[i] == p[j])) { // '?'或者相等的情况
i++;
j++;
}
else if (j < n && p[j] == '*') { // '*'的情况
star = j; // 保存上一个星号的位置
match = i; // 保存当前匹配到的位置
j++; // p的指针向后移动一位
}
else if (star != -1) { // p中有星号,并且当前字符和p的字符不同,则回溯
j = star + 1; // p的指针回到上一个星号的下一位
match++; // 匹配位置向后移动一位
i = match; // s的指针回到上一个星号匹配到的位置的下一位
}
else { // 最后一种情况,匹配失败
return false;
}
}
while (j < n && p[j] == '*') { // 如果p中还有星号,则可以匹配空字符串
j++;
}
return j == n; // s和p都遍历完了才算匹配成功
}
int main() {
int n; // 测试样例数
cin >> n;
char s[51]; // s的最大长度为50,再加上一个结束符'\0'
char p[51]; // p的最大长度为50,再加上一个结束符'\0'
for (int i = 0; i < n; i++) {
cin >> s >> p;
if (isMatch(s, p)) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
}
return 0;
}求逆序对数
对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序
请求出整数序列A的所有逆序对个数
时间限制:500
内存限制:65536
输入
输入包含多组测试数据,每组测试数据有两行 第一行为整数N(1 <= N <= 20000),当输入0时结束 第二行为N个整数,表示长为N的整数序列
输出
每组数据对应一行,输出逆序对的个数
样例输入
5 1 2 3 4 5 5 5 4 3 2 1 1 1 0
样例输出
0 10 0
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int merge(int a[], int s, int m, int e) {
vector<int> a1;
int m1 = s, m2 = m + 1, c = 0;
while (m1 <= m && m2 <= e) {
if (a[m1] > a[m2]) {
c += m - m1 + 1;
a1.push_back(a[m2]);
m2++;
} else {
a1.push_back(a[m1]);
m1++;
}
}
while (m1 <= m) {
a1.push_back(a[m1]);
m1++;
}
while (m2 <= e) {
a1.push_back(a[m2]);
m2++;
}
int k = 0;
for (int i = s; i <= e; i++)
a[i] = a1[k++];
return c;
}
int solve(int a[], int s, int e) {
if (s >= e)
return 0;
int m = (s + e) / 2;
int l = solve(a, s, m);
int r = solve(a, m + 1, e);
int l_r = merge(a, s, m, e);
return l + r + l_r;
}
int main() {
int n;
int a[N];
while (scanf("%d", &n) && n != 0) {
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int sum = solve(a, 0, n - 1);
cout << sum << endl;
}
return 0;
}分成互质组
给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?
时间限制:1000
内存限制:65536
输入
第一行是一个正整数n。1 <= n <= 10。 第二行是n个不大于10000的正整数。
输出
一个正整数,即最少需要的组数。
样例输入
6 14 20 33 117 143 175
样例输出
3
// 参考答案1:
#include <iostream>
#include <vector>
using namespace std;
const int N = 15;
int n, cnt, ans = N, p[N];
vector<int> s[N];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int k, int x) {
for (int i = 0; i < s[k].size(); i++)
if (gcd(s[k][i], x) > 1)
return false;
return true;
}
void dfs(int u) {
if (u == n) {
ans = min(ans, cnt);
return;
}
for (int i = 0; i < cnt; i++)
if (check(i, p[u])) {
s[i].push_back(p[u]);
dfs(u + 1);
s[i].pop_back();
}
s[cnt++].push_back(p[u]);
dfs(u + 1);
s[--cnt].pop_back();
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i];
dfs(0);
cout << ans << endl;
return 0;
}
// 参考答案2:
#include <iostream>
using namespace std;
const int N = 15;
int n;
int p[N];
int group[N][N];
bool used[N];
int ans = N;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int group[], int k, int x) {
for (int i = 0; i < k; i++)
if (gcd(p[group[i]], x) > 1)
return false;
return true;
}
void dfs(int g, int gc, int cnt, int start) {
if (g >= ans)
return;
if (cnt == n)
ans = g;
bool flag = false;
for (int i = start; i < n; i++)
if (!used[i] && check(group[g], gc, p[i])) {
used[i] = true;
group[g][gc] = i;
dfs(g, gc + 1, cnt + 1, i + 1);
used[i] = false;
flag = true;
}
if (!flag)
dfs(g + 1, 0, cnt, 0);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i];
dfs(1, 0, 0, 0);
cout << ans << endl;
return 0;
}拼点游戏
C和S两位同学一起玩拼点游戏。有一堆白色卡牌和一堆蓝色卡牌,每张卡牌上写了一个整数点数。C随机抽取n张白色卡牌,S随机抽取n张蓝色卡牌,他们进行n回合拼点,每次两人各出一张卡牌,点数大者获得三颗巧克力,小者获得一颗巧克力,如果点数相同,每人各得二颗巧克力,使用过的卡牌不得重复使用。已知C和S取到的卡牌点数,请编程计算S最多和最少能得到多少颗巧克力。
时间限制:1000
内存限制:65536
输入
输入包含多组测试数据。 每组测试数据的第一行是一个整数n(1<=n<=1000),接下来一行是n个整数,表示C抽到的白色卡牌的点数,下一行也是n个整数,表示S抽到的蓝色卡牌的点数。 输入的最后以一个0表示结束。
输出
对每组数据,输出一行,内容是两个整数用空格格开,分别表示S最多和最少可获得的巧克力数。
样例输入
3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0
样例输出
9 5 4 4 4 4
#include <bits/stdc++.h>
using namespace std;
int n, o = 0;
int c[1000] = {0}, s[1000] = {0};
int c1[1000], s1[1000];
int main() {
while (cin >> n, n) {
o++;
for (int i = 0; i < n; i++) {
cin >> c[i];
}
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int cs = 0, ss = 0;
int ch = 0, sh = 0, ct = n - 1, st = n - 1;
sort(c, c + n);
sort(s, s + n);
while (ch <= ct) {
if (s[st] > c[ct]) {
ss += 3;
cs += 1;
st--;
ct--;
} else if (s[st] < c[ct]) {
ss += 1;
cs += 3;
sh++;
ct--;
} else if (s[st] == c[ct]) {
if (s[sh] <= c[ch]) {
if (s[sh] < c[ct]) {
ss += 1;
cs += 3;
sh++;
ct--;
} else if (s[sh] == c[ct]) {
ss += 2;
cs += 2;
sh++;
ct--;
}
} else {
ss += 3;
cs += 1;
sh++;
ch++;
}
}
}
s1[o] = ss;
for (int i = 0; i < n; i++) {
swap(c[i], s[i]);
}
cs = 0, ss = 0;
ch = 0, sh = 0, ct = n - 1, st = n - 1;
sort(c, c + n);
sort(s, s + n);
while (ch <= ct) {
if (s[st] > c[ct]) {
ss += 3;
cs += 1;
st--;
ct--;
} else if (s[st] < c[ct]) {
ss += 1;
cs += 3;
sh++;
ct--;
} else if (s[st] == c[ct]) {
if (s[sh] <= c[ch]) {
if (s[sh] < c[ct]) {
ss += 1;
cs += 3;
sh++;
ct--;
} else if (s[sh] == c[ct]) {
ss += 2;
cs += 2;
sh++;
ct--;
}
} else {
ss += 3;
cs += 1;
sh++;
ch++;
}
}
}
c1[o] = cs;
}
for (int i = 1; i <= o; i++) {
cout << s1[i] << " " << c1[i] << endl;
}
return 0;
}数字变换
给定一个包含5个数字(0-9)的字符串,例如 “02943”,请将“12345”变换到它。 你可以采取3种操作进行变换
1. 交换相邻的两个数字
2. 将一个数字加1。如果加1后大于9,则变为0
3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。
最多只能用第2种操作3次,第3种操作2次 求最少经过多少次操作可以完成变换。
时间限制:1000
内存限制:65536
输入
有最多 100,000 组数据 每组数据就是包含5个数字的字符串
输出
对每组数据,输出将"12345"变换到给定字符串所需要的最少操作步数。如果无法变换成功,输出-1
样例输入
12435 99999 12374
样例输出
1 -1 3
提示
由于测试数据太多,如果对每组数据都从头进行搜索,就会超时。 建议先做预处理,即以“12345”作为初始状态做一遍彻底的广搜,找出“12345”经合法变换能够到达的所有字符串,并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据,在上述预处理记录的结果中进行查询即可。
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
char a[6] = "12345";
bool vis[100000][4][3];
int ans[100000];
struct node {
string a;
int op2, op3, step;
node(string aa, int o2, int o3, int ss = 0)
: a(aa), op2(o2), op3(o3), step(ss){};
};
queue<node> q;
int main() {
memset(vis, false, sizeof(vis));
memset(ans, -1, sizeof(ans));
q.push(node("12345", 0, 0));
vis[12345][0][0] = true;
ans[12345] = 0;
while (!q.empty()) {
node no = q.front();
q.pop();
string temp = no.a;
if (ans[int(atof(temp.c_str()))] == -1)
ans[int(atof(temp.c_str()))] = no.step;
// cout<<no.a<<endl;
// 第一种操作
for (int i = 0; i < 4; i++) {
swap(temp[i], temp[i + 1]);
if (!vis[int(atof(temp.c_str()))][no.op2][no.op3]) {
vis[int(atof(temp.c_str()))][no.op2][no.op3] = true;
q.push(node(temp, no.op2, no.op3, no.step + 1));
}
swap(temp[i], temp[i + 1]);
}
// 第二种操作
if (no.op2 < 3) {
for (int i = 0; i < 5; i++) {
temp = no.a;
int num = temp[i] - '0';
num++;
if (num == 10)
num = 0;
temp[i] = '0' + num;
if (!vis[int(atof(temp.c_str()))][no.op2 + 1][no.op3]) {
vis[int(atof(temp.c_str()))][no.op2 + 1][no.op3] = true;
q.push(node(temp, no.op2 + 1, no.op3, no.step + 1));
}
}
}
// 第三种操作
if (no.op3 < 2) {
for (int i = 0; i < 5; i++) {
temp = no.a;
int num = temp[i] - '0';
num *= 2;
if (num > 9)
num %= 10;
temp[i] = '0' + num;
if (!vis[int(atof(temp.c_str()))][no.op2][no.op3 + 1]) {
vis[int(atof(temp.c_str()))][no.op2][no.op3 + 1] = true;
q.push(node(temp, no.op2, no.op3 + 1, no.step + 1));
}
}
}
}
while (cin >> a) {
cout << ans[int(atof(a))] << endl;
}
return 0;
}打怪救公主
公主被魔王抓起来关在了迷宫的某处,骑士想要拯救公主,也进入了迷宫。
但是魔王不会轻易让骑士拯救公主,魔王在迷宫中安排了许多怪兽。
每个怪兽都有血量,骑士也有初始血量,骑士打败怪兽后血量的减少量为怪物的血量值,血量减到0,骑士会死去。
迷宫由m*n个方块组成,每个方块有墙或者路或者怪物,骑士在其中一个方块上,他每个时间单位可以四个方向(上、下、左、右)走到相邻方格,若遇到怪物,必须打败怪物才能继续前进。
请帮忙判断骑士能否成功拯救公主,如果能,给出骑士还剩的最大血量。
时间限制:1000
内存限制:65536
输入
第一行为三个整数m、n和t,t表示骑士的初始血量。(m,n <= 20, t <= 30) 第2至m+1行描述了迷宫,迷宫以m行n列的方格组成,若方格为"."则表示骑士可以通过,若方格为"#"则表示墙,骑士不能通过,若方格为数字则表示怪物,数字为怪物的血量,保证怪物的血量小于10(一位数)。"*"表示了骑士当前所在的位置,"+"表示公主被囚禁的位置。
输出
若骑士能成功拯救公主,则输出骑士走到公主所囚禁方格所剩最大血量,否则输出0。
样例输入
5 6 10 ..*... .#2### 5#..4# .##9.# .#+..#
样例输出
4
整理中……
Freda的越野跑
Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这N个人同时沿着道路向相同的方向跑去。换句话说,这N个人可以看作x轴上的N个点,在比赛开始后,它们同时向x轴正方向移动。
假设越野跑的距离足够远,这N个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生“赶超”的事件呢?
时间限制:1000
内存限制:262144
输入
第一行1个整数N。 第二行为N 个非负整数,按从前到后的顺序给出每个人的跑步速度。 对于50%的数据,2<=N<=1000。 对于100%的数据,2<=N<=100000。
输出
一个整数,表示有多少对参赛者之间发生赶超事件。
样例输入
5 1 3 10 8 5
样例输出
7
提示
我们把这5个人依次编号为A,B,C,D,E,速度分别为1,3,10,8,5。 在跑步过程中: B,C,D,E均会超过A,因为他们的速度都比A快; C,D,E都会超过B,因为他们的速度都比B快; C,D,E之间不会发生赶超,因为速度快的起跑时就在前边。
#include <iostream>
using namespace std;
int a[100001];
int ta[100001];
long long int ans = 0;
void merge(int left, int right, int middle) {
int i, j, index1, index2;
for (j = left; j <= right; ++j)
ta[j] = a[j];
index1 = left;
index2 = middle + 1;
i = left;
while (index1 <= middle && index2 <= right) {
if (ta[index1] >= ta[index2]) {
a[i] = ta[index1];
++i;
++index1;
} else {
a[i] = ta[index2];
ans += middle - index1 + 1; // 这个右子列元素超过了左子列中剩余的元素
++i;
++index2;
}
}
while (index1 <= middle) {
a[i] = ta[index1];
++i;
++index1;
}
while (index2 <= right) {
a[i] = ta[index2];
++i;
++index2;
}
}
void mergesort(int left, int right) {
int middle;
if (left < right) {
middle = (left + right) / 2;
mergesort(left, middle);
mergesort(middle + 1, right);
merge(left, right, middle);
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
mergesort(0, n - 1);
cout << ans;
// system("pause");
return 0;
}问题求解
给定一个正整数N,求最小的M满足比N大且M与N的二进制表示中有相同数目的1。
举个例子,假如给定N为78,二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。
时间限制:1000
内存限制:65536
输入
输入若干行,每行一个数N(1 ≤ N ≤ 1000000),如果这行为0表示输入结束。
输出
对于每个N,输出对应的M。
样例输入
1 2 3 4 78 0
样例输出
2 4 5 8 83
//解法1
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 1001
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n)
{
int cnt=0;
int temp=n;
while(temp>0)
{
if(temp%2)
cnt++;
temp/=2;
}
int sum=0;
while(1)
{
temp=++n;
while(temp>0)
{
if(temp%2)
sum++;
temp/=2;
}
if(cnt==sum)
{
cout<<n<<endl;
break;
}
sum=0;
}
}
return 0;
}//解法2 样例代码 枚举
using namespace std;
int n; // 定义变量 n
int tj(int x) {
int ans = 0; // 定义变量 ans
while (x) { // 当 x 不为0循环执行
if (x &)
ans++; // 如果 x 的最低位为1,则将 ans 加1
x >>= 1; // 将 x 右移1位,即将 x 的二进制表示向右移动一位
}
return ans; // 返回 ans
}
int main() {
while (1) { // 无限循环
cin >> n; // 从标准输入读取一个整数 n
if (!n)break; 如果 n 为0,则结束循环
int t = tj(n); // 调用函数 tj 计算 n 的二进制中的1的个数,并将结果赋值给 t
for (int i = n + 1;; i++) { // 从 n+1 开始递增遍历整数 i
if (t == tj(i)) {
cout << i << endl; // 输出第一个满足条件的整数 i,即其二进制表示中的1的个数与 t 相等
break; // 结束循环
}
}
}
return 0; // 返回 0,表示程序正常结束
}算24
给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于24。 这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致(这里的除法定义是实数除法)。 比如,对于5,5,5,1,我们知道5 * (5 – 1 / 5) = 24,因此可以得到24。又比如,对于1,1,4,2,我们怎么都不能得到24。
时间限制:6000
内存限制:65536
输入
输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。
输出
对于每一组测试数据,输出一行,如果可以得到24,输出“YES”;否则,输出“NO”。
样例输入
5 5 5 1 1 1 4 2 0 0 0 0
样例输出
YES NO
//解法1
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include <iostream>
#include<cmath>
#include<bits/stdc++.h>
#define EPS 1e-6
using namespace std;
bool iszero(double c){
if(fabs(c) <= EPS) return 1;
else return 0;
}
bool suan24(double* a,int k){
if(k==1 && iszero(a[0]-24)) return 1;
double b[5];
for(int i=0;i<k-1;i++)
for(int j=i+1;j<k;j++) {
int z = 0;
for (int xx = 0; xx < k; xx++)
if (xx != i && xx != j) b[z++] = a[xx];
b[z] = a[i] + a[j];
if (suan24(b, k - 1)) return 1;
b[z] = a[i] - a[j];
if (suan24(b, k - 1)) return 1;
b[z] = a[j] - a[i];
if (suan24(b, k - 1)) return 1;
b[z] = a[i] * a[j];
if (suan24(b, k - 1)) return 1;
if (a[j] != 0) {
b[z] = a[i] / a[j];
if (suan24(b, k - 1)) return 1;
}
if (!iszero(a[i])) {
b[z] = a[j] / a[i];
if (suan24(b, k - 1)) return 1;
}
}
return 0;
}
int main()
{
while(1)
{
double a[6];
int sum=0;
for(int i=0;i<4;++i)
{
cin>>a[i];
sum+=a[i];
}
if(sum==0)break;
bool flag=suan24(a,4);
if(flag==1)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
// cout<<flag<<endl;
}
return 0;
}//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
double a[5];
bool fig(double a[],int n){
double b[5];
int i,j,k,m;
if(fabs(a[0]-24)<1e-6 && n==1) return 1;
if(n==1) return 0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++){
m=0;
for(k=0;k<n;k++)
if(k!=i&&k!=j) b[++m]=a[k];
b[0]=a[i]+a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]-a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]-a[i];if(fig(b,n-1)) return 1;
b[0]=a[i]*a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]/a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]/a[i];if(fig(b,n-1)) return 1;
}
return 0;
}
int main() {
while(1){
for(int i=0;i<4;i++) cin>>a[i];
if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0) break;
if(fig(a,4)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}忍者道具
忍者道具有很多种,苦无,飞镖,震爆弹。L君热衷于收集忍者道具,现在他有N个道具,每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里,请问他最少需要多少个工具包?
时间限制:1000
内存限制:65536
输入
第一行包含两个用空格隔开的整数,N和W。 接下来N行每行一个整数,其中第i+1行的整数表示第i个道具的重量Ci。
输出
输出一个整数,最少需要多少个工具包。
样例输入
5 1996 1 2 1994 12 29
样例输出
2
提示
对于100%的数据,1<=N<=18,1<=Ci<=W<=10^8。
//解法1
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include <iostream>
using namespace std;
const int MAXN = 18;
int used[MAXN];
int W;
int m, n, ans = (1 << 30);
int item[MAXN];
int bag[MAXN];
void dfs(int x, int sum) {
if (sum >= ans) return;
if (x == n) {
ans = min(ans, sum);
return;
}
for (int i = 0; i < sum; ++i) {
if (bag[i] >= item[x]) {
bag[i] -= item[x];
dfs(x + 1, sum);
bag[i] += item[x];
}
}
bag[sum] -= item[x];
dfs(x + 1, sum + 1);
bag[sum] += item[x];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> item[i];
bag[i] = m;
}
dfs (0, 1);
cout << ans << endl;
return 0;
}//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
int n,w,ans=20;
int a[20],bag[20];
void dfs(int x,int sum){//放第x个物品,已使用sum个包
if(sum>=ans) return;//背包数量不够
if(x>n) {ans=min(ans,sum);return;}//所有物品已放完
for(int i=1;i<=sum;i++){//放入现有背包
if(bag[i]>=a[x]){
bag[i]-=a[x];
dfs(x+1,sum);
bag[i]+=a[x];//回溯
}
}
bag[sum+1]-=a[x];//放入新背包
dfs(x+1,sum+1);
bag[sum+1]+=a[x];//回溯
}
int main() {
cin>>n>>w;
for(int i=1;i<=n;i++) {
cin>>a[i];
bag[i]=w;//初始化n个背包的开始可用容量
}
dfs(1,1);
cout<<ans<<endl;
return 0;
}泳池
小C在一个排水系统不太好的学校上学。又是一个下雨天,学校里高低不平积了很多水。小C突发奇想:如果大雨一直下,多久以后我可以在学校里游泳呢?
学校是 N x N 的坐标方格 grid 中,每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时,此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格,但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。
现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)?
时间限制:1000
内存限制:65536
输入
第一行有一个整数N,以下是一个N*N的方阵,代表各处的高度。 输入范围: 2 ≤ N ≤ 300 0 ≤ Height ≤ 10000000
输出
输出一个整数,代表最少等待时间T
样例输入
样例输入1:
2 0 2 1 3
样例输入2:
5 0 1 2 3 4 24 23 22 21 5 12 13 14 15 16 11 17 18 19 20 10 9 8 7 6
样例输出
样例输出1:
3
样例输出2:
16
提示
样例1:时间为3时,才可以游向平台(1,1),此时水位为3。 样例2:时间为16时,水位为16,此时才能保证(0,0)和(4,4)是联通的(请自行找出一条通路)。
//动规+广搜+二分
//从(0,0)到(N-1,N-1)的各条路径最大值中的最小值。
//直接深搜和广搜会超时
#include <bits/stdc++.h>
using namespace std;
int n,m[305][305];// n 是矩阵的大小,m 存储矩阵元素
bool v[305][305];// v 记录矩阵中点是否被访问过
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
struct Point{
int x,y;
Point(int a,int b):x(a),y(b){}
};
bool is_reach(int t){// 判断是否在时间t内到达右下角坐标
if(m[0][0]>t) return false;// 左上角大于t无法到达
memset(v,0,sizeof(v));
v[0][0]=1;
queue<Point> myq;// 创建一个队列存储待访问的点
myq.push(Point(0,0));
while(!myq.empty()){
Point top=myq.front();
myq.pop();
// 到达右下角坐标,返回true
if((top.x==n-1)&&(top.y==n-1)) return true;
for(int i=0;i<4;i++){
int xx=top.x+dx[i];
int yy=top.y+dy[i];
// 如果已访问过或元素大于t,则无法继续前进
if(xx<0||xx>=n||yy<0||yy>=n||v[xx][yy]||(m[xx][yy]>t)) continue;
v[xx][yy]=1;// 标记坐标访问状态
myq.push(Point(xx,yy));// 将可继续访问的坐标加入队
}
}
return false;// 无法到达右下角坐标,返回false
}
int main()
{
memset(m,0,sizeof(m));
cin>>n;
int L=1e7,R=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin>>m[i][j];
L=min(L,m[i][j]);
R=max(R,m[i][j]);
}
int result=1e7;
while(L<R){// 二分查找
int mid=(L+R+1)/2;
if(is_reach(mid)){// mid值能到达右下角坐标
R=mid-1;
result=min(result,mid);// 更新结果
}
else L=mid;
}
cout<<result;
return 0;
}红与黑
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
时间限制:1000
内存限制:65536
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。
输出
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
样例输出
45
//解法1:深搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
char mp[N][N];//地图
int w, h, ct;//h:行数,w:ct:结果计数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
void dfs(int sx, int sy)
{
for(int i = 0; i < 4; ++i)
{
int x = sx + dir[i][0], y = sy + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
ct++;
vis[x][y] = true;
dfs(x, y);
}
}
}
int main()
{
int stx, sty;//起始位置
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));//多组数据,注意状态还原
ct = 1;
vis[stx][sty] = true;
dfs(stx, sty);
cout << ct << endl;
}
return 0;
}//解法2:广搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
struct Node
{
int x, y;
Node(){}
Node(int a, int b):x(a),y(b){}
};
char mp[N][N];//地图
int w, h;//w:列数 h:行数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
int bfs(int sx, int sy)//传入起始位置
{
queue<Node> que;
vis[sx][sy] = true;
que.push(Node(sx, sy));
int ct = 1;//计数,看可以到达几个黑色格子
while(que.empty() == false)
{
Node u = que.front();
que.pop();
for(int i = 0; i < 4; ++i)
{
int x = u.x + dir[i][0], y = u.y + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
vis[x][y] = true;
que.push(Node(x, y));
ct++;
}
}
}
return ct;
}
int main()
{
int stx, sty;
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));
cout << bfs(stx, sty) << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1001
using namespace std;
int m,n;
char ch;
int maps[N][N];
int vis[N][N];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&vis[nx][ny]==0&&maps[nx][ny]==1)
{
vis[nx][ny]=1;
cnt++;
dfs(nx,ny);
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF&&m&&n)
{
int x,y;
cnt=1;
memset(vis,0,sizeof(vis));
memset(maps,0,sizeof(maps));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ch;
if(ch=='@')
{
x=i;
y=j;
maps[i][j]=1;
}
if(ch=='.')
maps[i][j]=1;
if(ch=='#')
maps[i][j]=0;
}
vis[x][y]=1;
dfs(x,y);
cout<<cnt<<endl;
}
return 0;
}装箱问题
一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。
时间限制:1000
内存限制:65536
输入
输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。
输出
除了输入的最后一行6个0以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。
样例输入
0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0
样例输出
2 1
//解法1:贪心
#include <bits/stdc++.h>
using namespace std;
int status[8][4];//status[i][j]:包裹中已有1个大小为i*i的产品,此时可以最多放入多少个j*j的产品
void initStatus()
{//status[0]:包裹中没有产品时,各种产品最多可以放多少个
status[2][2] = 8;
status[3][2] = 5, status[3][3] = 3;
status[4][2] = 5;
for(int i = 1; i <= 6; ++i)
status[i][1] = 36 - i*i;
}
int pro[8];//pro[i]:i*i产品的数量
int main()
{
initStatus();
while(true)
{
int sum = 0, bag = 0, rem[8];//sum:总产品数量 bag:包裹数 rem[i]:当前剩余空间能放几个i*i
for(int i = 1; i <= 6; ++i)
{
cin >> pro[i];
sum += pro[i];
}
if(sum == 0)//如果6个数都是0,那么加和为0,要跳出循环
break;
for(int i = 6; i >= 1; --i)
{
while(pro[i] > 0)
{
bag++;//用一个新包裹放i*i
pro[i]--;
for(int j = 1; j <= 3; ++j)//获取当前剩余空间情况
rem[j] = status[i][j];
int j = 3;
while(j >= 1)
{
if(rem[j] > 0 && pro[j] > 0)//如果可以放j*j的产品
{
pro[j]--;//放一个产品
if(j == 3)
{
rem[3]--;
rem[2] -= 2;
rem[1] -= 9;
}
else if(j == 2)
{
rem[2]--;
rem[1] -= 4;
}
else//j == 1
rem[1]--;
}
else
--j;
}
}
}
cout << bag << endl;
}
return 0;
}//解法2:手动完成贪心过程
#include<bits/stdc++.h>
using namespace std;
int bag;//总包裹数
int k[4] = {0, 5, 3, 1};//k[i]表示3*3的产品有i个时(k[0]表示有4个时)剩余空间可以放2*2产品的个数
int pro[8], p2, p1;//p2:2*2空位数 p1:1*1空位数
int main()
{
while(true)
{
for(int i = 1; i <= 6; ++i)
cin >> pro[i];
if(pro[1] == 0 && pro[2] == 0 && pro[3] == 0 && pro[4] == 0 && pro[5] == 0 && pro[6] == 0)
break;
bag = pro[6] + pro[5] + pro[4] + ceil(pro[3]/4.0);//6*6和5*5和4*4一定是一个占一个箱子,而3*3 4个占一个箱子
p2 = 5*pro[4]+k[pro[3]%4];//k[pro[3]%4]:有pro[3]%4个3*3在一个包裹中时,剩下的位置可以放2*2的数目
if(pro[2] > p2)//2*2的个数比我们留出来为2*2的空间个数多,就需要为2*2另开箱子
bag += ceil((pro[2]-p2)/9.0);//多出来的2*2箱子应该占用的新箱子数
p1 = 36*bag-36*pro[6]-25*pro[5]-16*pro[4]-9*pro[3]-4*pro[2];//求出当前包裹中所有剩下的可以放1*1的位置数
if(pro[1] > p1)//如果1*1的个数,比我们留出的空间多就需要另开空间
bag += ceil((pro[1]-p1)/36.0);//将多出来的另开箱子
cout << bag << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 101
using namespace std;
int main()
{
int a,b,c,d,e,f;
int g[4]={0,5,3,1};
int x,y;
while(cin>>a>>b>>c>>d>>e>>f)
{
if(a+b+c+d+e+f==0)
break;
int n=f+e+d+(c+3)/4;
x=5*d+g[c%4];
if(b>x)
n+=(b-x+8)/9;
y=36*n-36*f-25*e-16*d-9*c-4*b;
if(a>y)
n+=(a-y+35)/36;
cout<<n<<endl;
}
return 0;
}课程表
现在你总共有n门课需要选,记为0到n-1。在选修某些课程之前需要一些先修课程。例如,想要学习课程0,你需要先完成课程1,我们用一个匹配来表示他们:[0, 1]。给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?
时间限制:1000
内存限制:65536
输入
多组数据。每组数据第一行是n和m,n表示有n门课程,m表示有m组依赖关系,接下来的m行是依赖关系的具体信息a b,表示第a门课程依赖第b门课程。 0<=n <=1000,0 <= m <= 4000 两组数据之间可能有空行
输出
对每组数据,能完成输出 True,不能完成输出 False
样例输入
2 1 1 0 2 2 1 0 0 1
样例输出
True False 提示
示例2解释: 总共有2门课程。学习课程1之前,你需要先完成课程0;并且学习课程0之前,你还应先完成课程1。这是不可能的。
//拓扑排序:Kahn算法+邻接表+栈
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[1005][1005];//邻接点
int rd[1005],cd[1005];//入度 出度
int main()
{
int r,c,num,i,j,k;
stack<int> st;
while(cin>>n>>m){
memset(a,0,sizeof(a));
memset(rd,0,sizeof(rd));
memset(cd,0,sizeof(cd));
while(!st.empty()) st.pop();
for(i=1;i<=m;i++){
cin>>r>>c;
rd[c]++;
cd[r]++;
a[r][cd[r]]=c;
}
for(i=0;i<=n-1;i++)
if(rd[i]==0){
st.push(i);
}
num=0;
while(!st.empty()){
i=st.top();
st.pop();
num++;
for(j=1;j<=cd[i];j++){
k=a[i][j];
rd[k]--;
if(rd[k]==0)st.push(k);
}
}
if(num==n) cout<<"True"<<endl;
else cout<<"False"<<endl;
}
return 0;
}最小新整数
给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。 现在从m位中删除k位(0<k < m),求生成的新整数最小为多少? 例如: n = 9128456, k = 2, 则生成的新整数最小为12456
时间限制:1000
内存限制:65536
输入
第一行t, 表示有t组数据; 接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n, k。
输出
t行,每行一个数字,表示从n中删除k位后得到的最小整数。
样例输入
2 9128456 2 1444 3
样例输出
12456 1
//解法1:每次找k+1个数中的最小值
#include<bits/stdc++.h>
using namespace std;
#define N 15
int main()
{
int k, t;
char s[N], a[N];
cin >> t;
while(t--)
{
cin >> s >> k;
int an = 0, len = strlen(s), i = 0;
while(i < len)
{
if(k == len-i)//如果剩下的元素个数只有k个,那么都删掉
break;
int mi = i;//求i~i+k的最小值下标
for(int j = i; j <= i+k; ++j)
{
if(s[j] < s[mi])
mi = j;
}
a[++an] = s[mi];
k -= mi - i;//s[i]~s[mi-1]都删掉,删掉了mi-i个元素
i = mi + 1;
}
for(i = 1; i <= an; ++i)
cout << a[i];
cout << endl;
}
return 0;
}//解法2:删掉比后面数字大的数字
#include<bits/stdc++.h>
using namespace std;
#define N 15
int main()
{
int k, t;
char s[N], a[N];
cin >> t;
while(t--)
{
cin >> s >> k;
int an = 0, len = strlen(s), ct = 0;
for(int i = 0; i < len; ++i)
{
while(an > 0 && a[an] > s[i] && ct < k)//a[an]为前一个数 s[i]为后一个数,当a[an]>s[i]时,删除a[an]
{
an--;
ct++;//删除数字个数加1
}
a[++an] = s[i];//无论如何s[i]都会填充进数组a
}
while(ct < k)//删除末尾的k-ct个元素
{
an--;
ct++;
}
for(int i = 1; i <= an; ++i)
cout << a[i];
cout << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 101
using namespace std;
char str[N];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>str>>n;
int len=strlen(str);
while(n--)
{
for(int i=0;i<len-1;i++)
if(str[i]>str[i+1])
{
for(int j=i;j<len-1;j++)
str[j]=str[j+1];
break;
}
len--;
}
str[len]='\0';
cout<<str<<endl;
}
return 0;
}书架(2023.12)
John最近买了一个书架用来存放奶牛养殖书籍,但书架很快被存满了,只剩最顶层有空余。
John共有N头奶牛(1 ≤ N ≤ 20,000),每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000),N头奶牛的总高度为S。书架高度为B(1 ≤ B ≤ S < 2,000,000,007).
为了到达书架顶层,奶牛可以踩着其他奶牛的背,像叠罗汉一样,直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层,找出使用奶牛数目最少的解决方案吧。
时间限制:10000
内存限制:65536
输入
第1行:空格隔开的整数N和B 第2~N+1行:第i+1行为整数Hi
输出
能达到书架高度所使用奶牛的最少数目
样例输入
6 40 6 18 11 13 19 11
样例输出
3
// 参考代码1
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define INF 999999999
#define N 20001
using namespace std;
int a[N];
void qsort(int x, int y) {
int i = x, j = y, mid = a[(x + y) / 2];
while (i <= j) {
while (a[i] > mid)
i++;
while (a[j] < mid)
j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
if (x < j)
qsort(x, j);
if (i < y)
qsort(i, y);
}
int main() {
int n, b;
int sum = 0;
int i;
cin >> n >> b;
for (i = 1; i <= n; i++)
cin >> a[i];
qsort(1, n);
for (i = 1; i <= n; i++) {
sum += a[i];
if (sum >= b)
break;
}
cout << i << endl;
;
return 0;
}// 参考代码2
#include <bits/stdc++.h>
using namespace std;
int n, b, a[20002];
int main() {
cin >> n >> b;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
long long s = 0;
for (int i = n - 1; i >= 0; i--) {
s += a[i];
if (s >= b) {
cout << n - i << endl;
return 0;
}
}
return 0;
}抓牛(2023.12)
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
时间限制:2000
内存限制:65536
输入
两个整数,N和K
输出
一个整数,农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
// 参考代码1
#include <bits/stdc++.h>
using namespace std;
int b[200100];
int a[10];
queue<int> q;
int n, k;
void bfs(int x) {
q.push(x);
b[x] = 1;
while (!q.empty()) {
int s = q.front();
a[1] = s - 1;
a[2] = s + 1;
a[3] = 2 * s;
for (int i = 1; i < 4; i++) {
if (b[a[i]] == 0 && a[i] >= 0 && a[i] < 100100) {
b[a[i]] = b[s] + 1;
q.push(a[i]);
if (a[i] == k) {
cout << b[k] - 1 << endl;
}
}
}
q.pop();
}
}
int main() {
cin >> n >> k;
bfs(n);
return 0;
}// 参考代码2
#include <bits/stdc++.h>
using namespace std;
int n, k;
bool v[100005];
struct nod {
int x, dis;
};
int main() {
cin >> n >> k;
queue<nod> q;
if (n == k) {
cout << 0;
return 0;
}
v[n] = true;
q.push({n, 0});
while (!q.empty()) {
int l = q.size();
for (int i = 1; i <= l; i++) {
if (q.front().x + 1 == k || q.front().x - 1 == k ||
q.front().x * 2 == k) {
cout << q.front().dis + 1;
return 0;
}
if (q.front().x + 1 >= 0 && q.front().x + 1 <= 100000 &&
!v[q.front().x + 1]) {
v[q.front().x + 1] = true;
q.push({q.front().x + 1, q.front().dis + 1});
}
if (q.front().x - 1 >= 0 && q.front().x - 1 <= 100000 &&
!v[q.front().x - 1]) {
v[q.front().x - 1] = true;
q.push({q.front().x - 1, q.front().dis + 1});
}
if (q.front().x * 2 >= 0 && q.front().x * 2 <= 100000 &&
!v[q.front().x * 2]) {
v[q.front().x * 2] = true;
q.push({q.front().x * 2, q.front().dis + 1});
}
q.pop();
}
}
return 0;
}鸣人和佐助(2023.12)
描述
佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?
已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费1个单位时间,打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了,则只可以走到没有大蛇丸手下的位置,不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动,大蛇丸的手下也不移动。请问,鸣人要追上佐助最少需要花费多少时间?
输入
输入的第一行包含三个整数:M,N,T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200,0 ≤ T < 10
后面是M行N列的地图,其中@代表鸣人,+代表佐助。*代表通路,#代表大蛇丸的手下。
输出
输出包含一个整数R,代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助,则输出-1。
样例输入1
4 4 1 #@## **## ###+ ****
样例输入2
4 4 2 #@## **## ###+ ****
样例输出1
6
样例输出2
4
#include <bits/stdc++.h>
using namespace std;
int n, m, t, s2[10][256][256], fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char s1[256][256];
struct AAA {
int i;
int j;
int bs;
int st;
};
int bfs() {
int i, j, k, ti, tj, ret = -1;
queue<AAA> dl;
AAA tmp, tmp1;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++)
if (s1[i][j] == '@') {
tmp.i = i;
tmp.j = j;
tmp.bs = 0;
tmp.st = t;
break;
}
if (j < n)
break;
}
dl.push(tmp);
for (i = 0; i < 10; i++)
for (j = 0; j < m; j++)
for (k = 0; k < n; k++)
s2[i][j][k] = 0;
s2[0][tmp.i][tmp.j] = 1;
while (!dl.empty()) {
tmp = dl.front();
dl.pop();
if (s1[tmp.i][tmp.j] == '+') {
ret = tmp.bs;
break;
}
for (i = 0; i < 4; i++) {
ti = tmp.i + fx[i][0];
tj = tmp.j + fx[i][1];
if ((ti < 0) || (ti >= m) || (tj < 0) || (tj >= n))
continue;
if (s2[t - tmp.st][ti][tj] == 1)
continue;
if ((s1[ti][tj] == '#') && (tmp.st == 0))
continue;
s2[t - tmp.st][ti][tj] = 1;
tmp1.i = ti;
tmp1.j = tj;
tmp1.bs = tmp.bs + 1;
tmp1.st = tmp.st;
if (s1[ti][tj] == '#')
tmp1.st--;
dl.push(tmp1);
}
}
return ret;
}
int main() {
int i, j, k;
char tmp[16];
gets(tmp);
sscanf(tmp, "%d%d%d", &m, &n, &t);
for (i = 0; i < m; i++)
gets(s1[i]);
printf("%d", bfs());
return 0;
}//参考代码2
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,sx,sy,st,minstep=inf;
int step[201][201][11],dx[]={0,1,-1,0},dy[]={1,0,0,-1};
char mp[201][201];
bool vis[201][201];
void dfs(int x,int y,int t,int stp)
{
if(x<1 || x>n || y<1 || y>m || vis[x][y]) return ;
if(t<0) return ;
if(stp>=minstep) return ;
if(stp>=step[x][y][t]) return ;
step[x][y][t]=stp;
if(mp[x][y]=='#') t--;
else if(mp[x][y]=='+') {
if(stp<minstep) minstep=stp;
return ;
}
vis[x][y]=1;
for(int i=0;i<4;++i){
int nx=x+dx[i];
int ny=y+dy[i];
dfs(nx,ny,t,stp+1);
}
vis[x][y]=0;
}
int main()
{
scanf("%d%d%d",&n,&m,&st);
getchar();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%c",&mp[i][j]);
if(mp[i][j]=='@') {
sx=i;
sy=j;
}
}
getchar();
}
memset(step,0x3f,sizeof(step));
dfs(sx,sy,st,0);
if(minstep==inf) printf("-1");
else printf("%d",minstep);
return 0;
}//参考代码3
#include<cstdio>
#include<queue>
using namespace std;
struct POINT
{
int x,y,tot,T;
} point;
queue<POINT> que;
int main()
{
bool walked[205][205][15]={};
int r,c,T,F[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
scanf("%d%d%d",&r,&c,&T);
char maze[205][205]={};
for(int i=0;i<r;i++)
{
scanf("%s",maze[i]);
for(int j=0;j<c;j++)
if(maze[i][j]=='@')
{
point.x=i;point.y=j;
point.tot=0;point.T=T;
}
}
que.push(point);
while(!que.empty())
{
for(int i=0;i<4;i++)
{
point.x=que.front().x+F[i][0];
point.y=que.front().y+F[i][1];
point.tot=que.front().tot+1;
point.T=que.front().T;
if(point.x<0 || point.x>=r || point.y<0 || point.y>=c || walked[point.x][point.y][point.T]) continue;
if(maze[point.x][point.y]=='#')
if(point.T) point.T--;
else continue;
if(maze[point.x][point.y]=='+') {printf("%d\n",point.tot);return 0;}
walked[point.x][point.y][point.T]=true;
que.push(point);
}
que.pop();
}
printf("-1\n");
return 0;
}// 参考代码4
#include <bits/stdc++.h>
using namespace std;
char a[202][202];
int v_ckl[202][202]; // 走到该坐标点时的最小消耗的查克拉
struct nod {
int x, y, ckl, step;
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int main() {
int n, m, k, mi, mj;
cin >> m >> n >> k;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == '@') {
mi = i;
mj = j;
}
}
queue<nod> q;
q.push({mi, mj, k, 0});
v_ckl[mi][mj] = k;
memset(v_ckl, -1,
sizeof(v_ckl)); // 注意:初始值 查克拉为零时条件允许也可以走的
while (!q.empty()) {
nod t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
if (t.x + dx[i] < 1 || t.x + dx[i] > m || t.y + dy[i] < 1 ||
t.y + dy[i] > n)
continue;
else if (a[t.x + dx[i]][t.y + dy[i]] == '+') {
cout << t.step + 1;
return 0;
} // 注意:比较查克拉值 好判断该点是否需要更新
else if (a[t.x + dx[i]][t.y + dy[i]] == '*' &&
t.ckl > v_ckl[t.x + dx[i]][t.y + dy[i]]) {
q.push({t.x + dx[i], t.y + dy[i], t.ckl, t.step + 1});
v_ckl[t.x + dx[i]][t.y + dy[i]] = t.ckl;
} else if (a[t.x + dx[i]][t.y + dy[i]] == '#' && t.ckl > 0 &&
t.ckl > v_ckl[t.x + dx[i]][t.y + dy[i]]) {
q.push({t.x + dx[i], t.y + dy[i], t.ckl - 1, t.step + 1});
v_ckl[t.x + dx[i]][t.y + dy[i]] = t.ckl - 1;
}
}
}
cout << "-1";
return 0;
}献给阿尔吉侬的花束
阿尔吉侬是一只聪明又慵懒的小白鼠,它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫,研究员们为了鼓励阿尔吉侬尽快到达终点,就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道,如果阿尔吉侬足够聪明,它最少需要多少时间就能吃到奶酪。
迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置,字符E表示奶酪所在的位置,字符#表示墙壁,字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置,但不能走出地图边界。
时间限制:100
内存限制:65536
输入
第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。 每一组数据的第一行包含了两个用空格分开的正整数R和C(2 <= R, C <= 200),表示地图是一个R×C的矩阵。 接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。
输出
对于每一组数据,输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。
样例输入
3 3 4 .S.. ###. ..E. 3 4 .S.. .E.. .... 3 4 .S.. #### ..E.
样例输出
5 1 oop!
#include <bits/stdc++.h>
using namespace std;
char a[202][202];
struct nod {
int x, y, step;
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int main() {
int t, r, c, mi, mj;
cin >> t;
while (t--) {
cin >> r >> c;
memset(a, 0, sizeof(a));
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) {
cin >> a[i][j];
if (a[i][j] == 'S') {
mi = i;
mj = j;
}
}
queue<nod> q;
q.push({mi, mj, 0});
bool is_t = false;
while (!q.empty()) {
nod t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
if (t.x + dx[i] < 1 || t.x + dx[i] > r || t.y + dy[i] < 1 ||
t.y + dy[i] > c)
continue;
else if (a[t.x + dx[i]][t.y + dy[i]] == '#')
continue;
else if (a[t.x + dx[i]][t.y + dy[i]] == 'E') {
cout << t.step + 1 << endl;
is_t = true;
break;
} else if (a[t.x + dx[i]][t.y + dy[i]] == '.') {
q.push({t.x + dx[i], t.y + dy[i], t.step + 1});
a[t.x + dx[i]][t.y + dy[i]] = '#';
}
}
if (is_t)
break;
}
if (!is_t)
cout << "oop!" << endl;
}
return 0;
}