USACO Section 1.4 Mother's Milk 搜索

2023-11-08 09:39

本文主要是介绍USACO Section 1.4 Mother's Milk 搜索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题是一个让人做完觉得很爽的搜索题,可以用深搜也可以用宽搜。 相对来说,深搜的代码量稍微小一点。 搜索策略就是模拟倒来倒去的过程,并且出现重复的没有意义。

BFS版本: 我是人工写了个队列,这样比STL中的快一点

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 2000000000
#define LOCA
#define M 1007
using namespace std;
int a, b, c;
bool can[M];
bool flag[M][M];
struct wwj
{int x, y, z;wwj(){}wwj(int xx, int yy, int zz){x = xx;y = yy;z = zz;}
}q[M * M];
void bfs(int x, int y, int z)
{int head = 0, tail = 0;wwj A(x, y, z);q[tail++] = A;flag[x][y] = true;if(A.x == 0) can[A.z] = true;while(head < tail){A = q[head++];if(A.x == 0) can[A.z] = true;if(A.x < a && A.z > 0){if(A.z > a - A.x && !flag[a][A.y]) {wwj B(a, A.y, A.z - a + A.x); flag[B.x][B.y] = true; q[tail++] = B;}if(A.z <= a - A.x && !flag[A.x + A.z][A.y]) {wwj B(A.x + A.z, A.y, 0); flag[B.x][B.y] = true; q[tail++] = B;}}if(A.y < b && A.x > 0){if(A.x > b - A.y && !flag[A.x + A.y - b][b]) {wwj B(A.x + A.y - b, b, A.z); flag[B.x][B.y] = true; q[tail++] = B;}if(A.x <= b - A.y && !flag[0][A.x + A.y]) {wwj B(0, A.x + A.y, A.z); flag[B.x][B.y] = true; q[tail++] = B;}}if(A.z < c && A.y > 0){if(A.y > c - A.z && !flag[A.x][A.y + A.z - c]) {wwj B(A.x, A.y + A.z - c, c); flag[B.x][B.y] = true; q[tail++] = B;}if(A.y <= c - A.z && !flag[A.x][0]) {wwj B(A.x, 0, A.z + A.y); flag[B.x][B.y] = true; q[tail++] = B;}}if(A.x > 0 && A.z < c){if(A.x > c - A.z && !flag[A.x + A.z - c][A.y]) {wwj B(A.x + A.z - c, A.y, c);flag[B.x][B.y] = true; q[tail++] = B;}if(A.x <= c - A.z && !flag[0][A.y]) {wwj B(0, A.y, A.z + A.x);flag[B.x][B.y] = true; q[tail++] = B;}}if(A.y > 0 && A.x < a){if(A.y > a - A.x && !flag[a][A.y + A.x - a]) {wwj B(a, A.y + A.x - a, A.z);flag[B.x][B.y] = true; q[tail++] = B;}if(A.y <= a - A.x && !flag[A.x + A.y][0]) {wwj B(A.x + A.y, 0, A.z);flag[B.x][B.y] = true; q[tail++] = B;}}if(A.z > 0 && A.y < b){if(A.z > b - A.y && !flag[A.x][b]) {wwj B(A.x, b, A.z + A.y - b);flag[B.x][B.y] = true; q[tail++] = B;}if(A.z <= b - A.y && !flag[A.x][A.y + A.z]) {wwj B(A.x, A.y + A.z, 0);flag[B.x][B.y] = true; q[tail++] = B;}}}
}
int main()
{
#ifdef LOCALfreopen("calfflac.in","r",stdin);freopen("calfflac.out","w",stdout);
#endifint i;scanf("%d%d%d", &a, &b, &c);bfs(0, 0, c);for(i = 0; i <= c; i++)if(can[i])printf("%d ", i);printf("\n");return 0;
}
DFS版本: 可以看到,步骤都很明确

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 2000000000
#define LOCA
#define M 1007
using namespace std;
int a, b, c;
bool can[M];
bool flag[M][M];
void dfs(int x, int y, int z)
{if(flag[x][y]) return;flag[x][y] = true;if(x == 0) can[z] = true;if(x < a && z > 0){if(z > a - x) dfs(a, y, z - a + x);if(z <= a - x) dfs(x + z, y, 0);}if(y < b && x > 0){if(x > b - y) dfs(x + y - b, b, z);if(x <= b - y) dfs(0, x + y, z);}if(z < c && y > 0){if(y > c - z) dfs(x, y + z - c, c);if(y <= c - z) dfs(x, 0, z + y);}if(x > 0 && z < c){if(x > c - z) dfs(x + z - c, y, c);if(x <= c - z) dfs(0, y, z + x);}if(y > 0 && x < a){if(y > a - x) dfs(a, y + x - a, z);if(y <= a - x) dfs(x + y, 0, z);}if(z > 0 && y < b){if(z > b - y) dfs(x, b, z + y - b);if(z <= b - y) dfs(x, y + z, 0);}
}
int main()
{
#ifdef LOCALfreopen("calfflac.in","r",stdin);freopen("calfflac.out","w",stdout);
#endifint i;scanf("%d%d%d", &a, &b, &c);dfs(0, 0, c);for(i = 0; i <= c; i++)if(can[i])printf("%d ", i);printf("\n");return 0;
}



这篇关于USACO Section 1.4 Mother's Milk 搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/369047

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.3 Calf Flac(暴搜)

思路是暴搜。 需要注意的地方是输入的方法,以及输出时的换行。 代码: /*ID: who jayLANG: C++TASK: calfflac*/#include<stdio.h>#include<string.h>#include<math.h>int main(){freopen("calfflac.in","r",stdin);freopen("calfflac.ou

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

usaco 1.2 Milking Cows(类hash表)

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时!! 第一种思路:我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<