您所在位置：主题：急求
zzj12345
[专家分：160] 发布于 2010-08-14 20:06:00
贪心算法
题目名称 集合删数 d-规则问题 射击竞赛
提交程序
( PAS / CPP) number.pas
number.cpp drule.pas
drule.cpp sho.pas
sho.cpp
输入文件 number.in Drule.in Sho .in
输出文件 number.out Drule.out sho.out
内存限制 32MB 32MB 32MB
问题A: 集合删数
问题描述：
一个集合有如下元素：1是集合元素；若P是集合的元素，则2 * P +1，4*P+5也是集合的元素，取出此集合中最小的K个元素，按从小到大的顺序组合成一个多位数，现要求从中删除M个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。
注：不存在所有数被删除的情况`
输入格式：
输入的仅一行，K，M的值，K，M均小于等于30000。
输出格式：
输出为两行，第一行为删除前的数字，第二行为删除后的数字。
样例输入：
5 4
样例输出：
137915
95
问题B: d-规则问题
问题描述：
对任意给定的m (m∈N+)和n(n∈N+)，满足m<n，构造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)。现定义一种d规则如下：若存在a∈P，且存在K∈N+ ,K>1，使得K´a∈P，则修改P为：P=P-{y|y=s´a,s∈N+ } ，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。
输入格式：
输入仅一行，M,N的值。
输出格式：
输出每次使用d规则时的分值和集合p的变化过程(即变化后的集合内所有的数,每个数用空格隔开),注意D后面有个空格，冒号后面有个空格。如果没有一次可以变化就输出0。
样例输入：
(1)
1 10
(2)
56 57
样例输出：
(1)
5 : 1 2 3 4 6 7 8 9
4 : 1 2 3 6 7 9
2 : 1 3 7 9
3 : 1 7
1 :
(2)
0
问题C PROBLEM: SHO（射击竞赛）
欢迎来参加年度的BYTELAND射击竞赛。每个参赛者的射击目标是一个矩形网格。目标由R×C个小方格组成，分别为R行，C列。小方格被涂成白色或黑色。每一列恰有2个白色的小方格和R－2个黑色的小方格。行从顶至底编号依次为1，…，R，列从左至右编号依次为1，…，C。射击者可射击C次。
在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。
请帮助射击者找到一种正确的射击法，若这样的射击法存在。
例子：
考虑以下目标：
一连串的射击分别击中第1列的第2列，第2列的第3列，第3列的第1行，第4列的
第4行，这种射击方法是正确的。
任务：
写一个程序：
 从文件SHO.IN中读出数据的组数；每组包括针对这一问题的一套数据。
 对每组数
 读取目标的大小和白色方格的设置；
 证明是否存在正确的射击方法，若存在，请找出一种；
 将结果写至文件SHO.OUT上。
【输入格式】
输入文件SHO.IN:的第一行包括数据的组数X，1≦X≦5，接下来的行由X组组成。第一组从该文件第二行开始，其它各组依次直接接在前一组之后。
每组的首行包括两个整数R和C，被一空格隔开，2≦R≦C≦1000，这分别是矩形网格的行数和列数。该组中接下来的C行，每行包括两个整数，被一空格隔开。每组中的第I+1行的整数（1≦ I≦C），是第I列中白色方格所在的行的标号。
【输出格式】
输出文件SHO.OUT对第I组，1≦I≦X，你的程序应将以下内容写至文件SHO.OUT中；或者是由对白色方格的正确的一连串射击，形成的一个由C个行号组成的序列（中间均由1个空格隔开），即在列1，2，…，C上依次被击中的白色方格的行号，或者若不存在这样一种正确的射击法，写上单词NO。
示例：
【输入样例】
2
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3
【输出样例】
2 3 1 4
NO
题目名称 集合删数 d-规则问题 射击竞赛
提交程序
( PAS / CPP) number.pas
number.cpp drule.pas
drule.cpp sho.pas
sho.cpp
输入文件 number.in Drule.in Sho .in
输出文件 number.out Drule.out sho.out
内存限制 32MB 32MB 32MB
问题A: 集合删数
问题描述：
一个集合有如下元素：1是集合元素；若P是集合的元素，则2 * P +1，4*P+5也是集合的元素，取出此集合中最小的K个元素，按从小到大的顺序组合成一个多位数，现要求从中删除M个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。
注：不存在所有数被删除的情况`
输入格式：
输入的仅一行，K，M的值，K，M均小于等于30000。
输出格式：
输出为两行，第一行为删除前的数字，第二行为删除后的数字。
样例输入：
5 4
样例输出：
137915
95
问题B: d-规则问题
问题描述：
对任意给定的m (m∈N+)和n(n∈N+)，满足m<n，构造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)。现定义一种d规则如下：若存在a∈P，且存在K∈N+ ,K>1，使得K´a∈P，则修改P为：P=P-{y|y=s´a,s∈N+ } ，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。
输入格式：
输入仅一行，M,N的值。
输出格式：
输出每次使用d规则时的分值和集合p的变化过程(即变化后的集合内所有的数,每个数用空格隔开),注意D后面有个空格，冒号后面有个空格。如果没有一次可以变化就输出0。
样例输入：
(1)
1 10
(2)
56 57
样例输出：
(1)
5 : 1 2 3 4 6 7 8 9
4 : 1 2 3 6 7 9
2 : 1 3 7 9
3 : 1 7
1 :
(2)
0
问题C PROBLEM: SHO（射击竞赛）
欢迎来参加年度的BYTELAND射击竞赛。每个参赛者的射击目标是一个矩形网格。目标由R×C个小方格组成，分别为R行，C列。小方格被涂成白色或黑色。每一列恰有2个白色的小方格和R－2个黑色的小方格。行从顶至底编号依次为1，…，R，列从左至右编号依次为1，…，C。射击者可射击C次。
在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。
请帮助射击者找到一种正确的射击法，若这样的射击法存在。
例子：
考虑以下目标：
一连串的射击分别击中第1列的第2列，第2列的第3列，第3列的第1行，第4列的
第4行，这种射击方法是正确的。
任务：
写一个程序：
 从文件SHO.IN中读出数据的组数；每组包括针对这一问题的一套数据。
 对每组数
 读取目标的大小和白色方格的设置；
 证明是否存在正确的射击方法，若存在，请找出一种；
 将结果写至文件SHO.OUT上。
【输入格式】
输入文件SHO.IN:的第一行包括数据的组数X，1≦X≦5，接下来的行由X组组成。第一组从该文件第二行开始，其它各组依次直接接在前一组之后。
每组的首行包括两个整数R和C，被一空格隔开，2≦R≦C≦1000，这分别是矩形网格的行数和列数。该组中接下来的C行，每行包括两个整数，被一空格隔开。每组中的第I+1行的整数（1≦ I≦C），是第I列中白色方格所在的行的标号。
【输出格式】
输出文件SHO.OUT对第I组，1≦I≦X，你的程序应将以下内容写至文件SHO.OUT中；或者是由对白色方格的正确的一连串射击，形成的一个由C个行号组成的序列（中间均由1个空格隔开），即在列1，2，…，C上依次被击中的白色方格的行号，或者若不存在这样一种正确的射击法，写上单词NO。
示例：
【输入样例】
2
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3
【输出样例】
2 3 1 4
NO