Class 06 搜索

文章目录

• 枚举
• • NOIP 2001 一元三次方程
  • NOIP 2011 铺地毯
• DFS
• • 输出全排列
  • 经典寻路问题
  • 加分二叉树
• BFS
• • 二叉树的遍历
  • 马的遍历
• 双向BFS
• • 走迷宫
  • 八数码难题
• 状压搜索
• • 砝码称重
  • 虫食算

枚举

枚举范围：

• 枚举的边界要设定好

数据规模：

• 枚举要保证数据规模在时间限制内能够枚举完

枚举方式：

• 枚举顺序有时会影响时间

NOIP 2001 一元三次方程

问题描述
有形如： a x 3 + b x 2 + c x + d = 0 ax^3+bx^2+cx+d=0 ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根 (根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1

样例
输入：1 -5 -4 20
输出：-2.00 2.00 5.00

枚举，用区间[-100, 100]枚举

#include
using namespace std;const double eps=0.01;
double a,b,c,d;int main() {scanf("%lf%lf%lf%lf",&a,&b,&c,&d);for(double x=-100.00;x<=100.00;x+=eps) {double f=a*x*x*x+b*x*x+c*x+d;if(f>=(-0.001) && f<=(0.001)) printf("%.2lf ",x);}return 0;
}

NOIP 2011 铺地毯

题目描述
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯，一共有n张地毯，编号从 1 到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入
输入共 n+2行。
第一行有一个整数n，表示总共有 n张地毯。
接下来的 n行中，第 i+1行表示编号 i的地毯的信息，包含四个正整数 a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在 x轴和 y轴方向的长度。
第 n+2 行包含两个正整数 x 和 y，表示所求的地面的点的坐标（x，y）。

输出
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。

输入
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
输出
3

输入
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
输

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！