《信息学奥赛深度优先搜索2.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛深度优先搜索2.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息学奥赛深度优先搜索信息学奥赛深度优先搜索2 2自然数的拆分问题自然数的拆分问题【问题描述】【问题描述】任何一个大于任何一个大于1的自然数的自然数n，总可以拆分成若干，总可以拆分成若干个小于个小于n的自然数之和。拆分成的数字相同但顺序不的自然数之和。拆分成的数字相同但顺序不同被看做是相同的方案，如同被看做是相同的方案，如1+3与与3+1被看做是同一被看做是同一种方案。种方案。【输入格式】【输入格式】一个正整数一个正整数n（1=n=20）表示待拆分的自）表示待拆分的自然数。然数。数字游戏（数字游戏（sudoku.in/out/pas/cpp）格的每一行和每一列都不存在重复的数字。格的每一行和每
2、一列都不存在重复的数字。当然，为了保证公平，所有人拿到的表格当然，为了保证公平，所有人拿到的表格都是随机的且标注了时间。这样都是随机的且标注了时间。这样KendyKendy就不可能就不可能把题目带回去慢慢研究了，因此他想请你帮忙把题目带回去慢慢研究了，因此他想请你帮忙以便在规定时间内能解决这个问题。以便在规定时间内能解决这个问题。保证都有解。保证都有解。数字游戏（数字游戏（sudoku.in/out/pas/cpp）【输入输出样例】【输入输出样例】数字游戏（数字游戏（sudoku.in/out/pas/cpp）【样例说明】【样例说明】本题共有两种填法，取其中第一行数值较本题共有两种填法，取其中
3、第一行数值较小的填法。小的填法。分书问题（分书问题（book.in/out/pas/cpp）【问题描述】【问题描述】已知有已知有n本书（从本书（从1n编号）和编号）和n个人（从个人（从1n编号），每个人都有一个自己喜爱的书的列表，现在编号），每个人都有一个自己喜爱的书的列表，现在请你编写一个程序，设计一种分书方案，使得每个人请你编写一个程序，设计一种分书方案，使得每个人都能获得一本书，且这本书一定要在他的喜爱列表中。都能获得一本书，且这本书一定要在他的喜爱列表中。【输入格式】【输入格式】输入共若干行，第一行为一个正整数输入共若干行，第一行为一个正整数n（n=20），从第），从第2行到第行到第n
4、+1行，每行有行，每行有n个个0或或1组成，第组成，第k行表示编号为行表示编号为k-1的人对这的人对这n本书的喜好列表，本书的喜好列表，0表示不表示不喜欢，喜欢，1表示喜欢。表示喜欢。分书问题分书问题（book.in/out/pas/cpp）【输出格式】【输出格式】输出数据仅一个整数，表示符合条件的分配输出数据仅一个整数，表示符合条件的分配方案的总数。方案的总数。分书问题（分书问题（book.in/out/pas/cpp）【输入样例】【输入样例】5 500110001101100111001011000110000010000100100101001【输出样例】【输出样例】1 1N皇后问题（皇
5、后问题（queen.in/out/pas/cpp）【问题描述】【问题描述】要求在要求在n*n格的国际象棋上摆放格的国际象棋上摆放n个皇后，个皇后，使其不能互相攻击，即任意两个皇后都不处于使其不能互相攻击，即任意两个皇后都不处于同一行、同一列或同一斜线上，输出一共有几同一行、同一列或同一斜线上，输出一共有几种摆法。种摆法。【输入格式】【输入格式】单独一行单独一行 一个整数一个整数(4=n=11)【输出格式】【输出格式】一个整数一个整数(一共有多少种摆法一共有多少种摆法)N皇后问题皇后问题（queen.in/out/pas/cpp）【输入样例】【输入样例】4【输出样例】【输出样例】2装箱问题装箱问
6、题【问题描述】【问题描述】有一个箱子容量为有一个箱子容量为V（正整数，（正整数，0V20000），同时有），同时有n个物品（个物品（0n30，每，每个物品有一个体积（正整数）且都不相同。个物品有一个体积（正整数）且都不相同。要求要求n个物品中，任取若干个装入箱内，使箱个物品中，任取若干个装入箱内，使箱子的剩余空间为子的剩余空间为0（装满）。（装满）。装箱问题装箱问题【输入】【输入】第一行一个整数第一行一个整数V，表示箱子容量。第二行一，表示箱子容量。第二行一个整数个整数N，表示有，表示有N个物品。第三行到第个物品。第三行到第n+2行行每行一个整数，表示这每行一个整数，表示这N个物品的体积。个物
7、品的体积。【输出】【输出】一个整数，能让箱子装满的方案数一个整数，能让箱子装满的方案数装箱问题装箱问题【输【输入样例入样例】543214【输【输出样例出样例】2砝码（砝码（scales.in/out/pas/cpp）【问题描述】【问题描述】已知一个天平已知一个天平 ，有，有N(1=N=1000)N(1=N=1000)个已知个已知质量的砝码（所有砝码质量的数值都在质量的砝码（所有砝码质量的数值都在3131位二位二进制内）。所称物体在天平的某一边，天平另进制内）。所称物体在天平的某一边，天平另一边加砝码，直到天平平衡，于是此时砝码的一边加砝码，直到天平平衡，于是此时砝码的总质量就是物体的质量（物体
8、和砝码不能放到总质量就是物体的质量（物体和砝码不能放到同一边）。天平能承受的物体的质量不是无限同一边）。天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于的，当天平某一边物体的质量大于C(1=C230)C(1=C230)时，天平就会被损坏。时，天平就会被损坏。砝码（砝码（scales.in/out/pas/cpp）砝码按照它们质量的大小被排成一行。并砝码按照它们质量的大小被排成一行。并且，这一行中从第且，这一行中从第3 3个砝码开始，每个砝码的质个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。
9、的砝码中质量最大的两个）的质量的和。用这些砝码以及这架天平，能称出的质量用这些砝码以及这架天平，能称出的质量最大是多少。由于天平的最大承重能力为最大是多少。由于天平的最大承重能力为C C，他，他不能把所有砝码都放到天平上。不能把所有砝码都放到天平上。砝码（砝码（scales.in/out/pas/cpp）现在告诉你每个砝码的质量，以及天平能现在告诉你每个砝码的质量，以及天平能承受的最大质量。你的任务是选出一些砝码，承受的最大质量。你的任务是选出一些砝码，使它们的质量和在不压坏天平的前提下是所有使它们的质量和在不压坏天平的前提下是所有组合中最大的。组合中最大的。【输入格式】【输入格式】第第1 1
10、行行:两个用空格隔开的正整数，两个用空格隔开的正整数，N N和和C C。第第2.N+12.N+1行行:每一行仅包含一个正整数，每一行仅包含一个正整数，即某个砝码的质量。保证这些砝码的质量是一即某个砝码的质量。保证这些砝码的质量是一个不下降序列。个不下降序列。砝码（砝码（scales.in/out/pas/cpp）【输出格式输出格式】1 1行行:一个正整数，表示用所给的砝码能称一个正整数，表示用所给的砝码能称出的不压坏天平的最大质量。出的不压坏天平的最大质量。【输入输出样例】【输入输出样例】砝码（砝码（scales.in/out/pas/cpp）【问题分析】【问题分析】1.1.数据规模？数据规模？2.2.预处理预处理 3.3.搜索方向搜索方向 4.4.剪枝剪枝 THANKS结束！结束！