信息学奥赛深度优先搜索2.ppt

《信息学奥赛深度优先搜索2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、深度优先搜索2自然数的拆分问题【问题描述】任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。拆分成的数字相同但顺序不同被看做是相同的方案，如1+3与3+1被看做是同一种方案。【输入格式】一个正整数n（1<=n<=20）表示待拆分的自然数。自然数的拆分问题【输出格式】输出若干个拆分方案(具体见样例)。自然数的拆分问题【输入样例】4【输出样例】1+1+1+11+1+21+32+2数字游戏（sudoku.in/out/pas/cpp）【问题描述】这天Kendy路过KFC，看到KFC的橱窗上贴着大幅的宣传海报，海报上说，如果能在规定的时间内解决他们提出

2、的问题，就可以获得价值100元的KFC最新款套餐。Kendy当然不想放过这样的机会。他发现题目是这样的：给你一个N×N的表格（3

3、doku.in/out/pas/cpp）【输入输出样例】sudoku.insudoku.out430020204200000213142123424134321数字游戏（sudoku.in/out/pas/cpp）【样例说明】本题共有两种填法，取其中第一行数值较小的填法。31421234241343213412123421434321分书问题（book.in/out/pas/cpp）【问题描述】已知有n本书（从1～n编号）和n个人（从1～n编号），每个人都有一个自己喜爱的书的列表，现在请你编写一个程序，设计一种分书方案，使得每个人都能获得一本书，且这本书一定

4、要在他的喜爱列表中。【输入格式】输入共若干行，第一行为一个正整数n（n<=20），从第2行到第n+1行，每行有n个0或1组成，第k行表示编号为k-1的人对这n本书的喜好列表，0表示不喜欢，1表示喜欢。分书问题（book.in/out/pas/cpp）【输出格式】输出数据仅一个整数，表示符合条件的分配方案的总数。分书问题（book.in/out/pas/cpp）【输入样例】50011011001011000001001001【输出样例】1N皇后问题（queen.in/out/pas/cpp）【问题描述】要求在n*n格的国际象棋上摆放n个皇后，使其不能互相攻击，

5、即任意两个皇后都不处于同一行、同一列或同一斜线上，输出一共有几种摆法。【输入格式】单独一行一个整数(4<=n<=11)【输出格式】一个整数(一共有多少种摆法)N皇后问题（queen.in/out/pas/cpp）【输入样例】4【输出样例】2装箱问题【问题描述】有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个物品有一个体积（正整数）且都不相同。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为0（装满）。装箱问题【输入】第一行一个整数V，表示箱子容量。第二行一个整数N，表示有N个物品。第三行到第n+2行每行一个整数

6、，表示这N个物品的体积。【输出】一个整数，能让箱子装满的方案数装箱问题【输入样例】543214【输出样例】2砝码（scales.in/out/pas/cpp）【问题描述】已知一个天平，有N(1<=N<=1000)个已知质量的砝码（所有砝码质量的数值都在31位二进制内）。所称物体在天平的某一边，天平另一边加砝码，直到天平平衡，于是此时砝码的总质量就是物体的质量（物体和砝码不能放到同一边）。天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于C(1<=C<2^30)时，天平就会被损坏。砝码（scales.in/out/pas/cpp）砝码按照它们质量的大

7、小被排成一行。并且，这一行中从第3个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。用这些砝码以及这架天平，能称出的质量最大是多少。由于天平的最大承重能力为C，他不能把所有砝码都放到天平上。砝码（scales.in/out/pas/cpp）现在告诉你每个砝码的质量，以及天平能承受的最大质量。你的任务是选出一些砝码，使它们的质量和在不压坏天平的前提下是所有组合中最大的。【输入格式】第1行:两个用空格隔开的正整数，N和C。第2..N+1行:每一行仅包含一个正整数，即某个砝码的质量。保证这些砝码的质量是一个不下降序

8、列。砝码（scales.in/out/pas/cpp