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

深度优先搜索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的橱窗上贴着大幅的宣传海报，海报上说，如果能在规定的时间内解决他们提出的问题，就可以获得价值100元的KFC最新款套餐。Kendy当然不想放过这样的机会。他发现题目是这样的：给你一个NN的表格（3N10），在表格中事先已经填入了一部分的数字，现在请你的表格中空余的格子里填入1N范围内的数字，使得整个表格的每一行和每一列都不存在重复的数字。,数字游戏（sudoku.in/out/pas/cpp）,格的每一行和每一列都不存在重复的数字。当然，为了保证公平，所有人拿到的表格都是随机的且标注了时间。这样Kendy就不可能把题目带回去慢慢研究了，因此他想请你帮忙以便在规定时间内能解决这个问题。保证都有解。,数字游戏（sudoku.in/out/pas/cpp）,【输入输出样例】,数字游戏（sudoku.in/out/pas/cpp）,【样例说明】本题共有两种填法，取其中第一行数值较小的填法。,分书问题（book.in/out/pas/cpp）,【问题描述】已知有n本书（从1n编号）和n个人（从1n编号），每个人都有一个自己喜爱的书的列表，现在请你编写一个程序，设计一种分书方案，使得每个人都能获得一本书，且这本书一定要在他的喜爱列表中。【输入格式】输入共若干行，第一行为一个正整数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【输出样例】1,N皇后问题（queen.in/out/pas/cpp）,【问题描述】要求在n*n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不处于同一行、同一列或同一斜线上，输出一共有几种摆法。【输入格式】单独一行一个整数(4=n=11)【输出格式】一个整数(一共有多少种摆法),N皇后问题（queen.in/out/pas/cpp）,【输入样例】4【输出样例】2,装箱问题,【问题描述】有一个箱子容量为V（正整数，0V20000），同时有n个物品（0n30，每个物品有一个体积（正整数）且都不相同。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为0（装满）。,装箱问题,【输入】第一行一个整数V，表示箱子容量。第二行一个整数N，表示有N个物品。第三行到第n+2行每行一个整数，表示这N个物品的体积。【输出】一个整数，能让箱子装满的方案数,装箱问题,【输入样例】543214,【输出样例】2,砝码（scales.in/out/pas/cpp）,【问题描述】已知一个天平，有N(1=N=1000)个已知质量的砝码（所有砝码质量的数值都在31位二进制内）。所称物体在天平的某一边，天平另一边加砝码，直到天平平衡，于是此时砝码的总质量就是物体的质量（物体和砝码不能放到同一边）。天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于C(1=C230)时，天平就会被损坏。,砝码（scales.in/out/pas/cpp）,砝码按照它们质量的大小被排成一行。并且，这一行中从第3个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。用这些砝码以及这架天平，能称出的质量最大是多少。由于天平的最大承重能力为C，他不能把所有砝码都放到天平上。,砝码（scales.in/out/pas/cpp）,现在告诉你每个砝码的质量，以及天平能承受的最大质量。你的任务是选出一些砝码，使它们的质量和在不压坏天平的前提下是所有组合中最大的。【输入格式】第1行:两个用空格隔开的正整数，N和C。第2.N+1行:每一行仅包含一个正整数，即某个砝码的质量。保证这些砝码的质量是一个不下降序列。,砝码（scales.in/out/pas/cpp）,【输出格式】1行