150 lines
2.8 KiB
Markdown
150 lines
2.8 KiB
Markdown
1（必做） 子集和问题(回溯) *
|
||
Score 100
|
||
已知 n+1 个正数：w
|
||
i
|
||
|
||
(1≤i≤n) 和 M ，要求找出{w
|
||
i
|
||
|
||
} 的所有子集使得子集中元素之和等于 M 。解采用大小固定的n-元组(x
|
||
1
|
||
|
||
,...,x
|
||
n
|
||
|
||
) 表达，其中：x
|
||
i
|
||
|
||
∈{0，1}，1≤i≤n 。若x
|
||
i
|
||
|
||
=0 ，表示解集合不包含 w
|
||
i
|
||
|
||
；若 x
|
||
i
|
||
|
||
=1，表示解集合包含 w
|
||
i
|
||
|
||
。隐式约束条件是∑
|
||
i=1
|
||
n
|
||
|
||
w
|
||
i
|
||
|
||
x
|
||
i
|
||
|
||
=M。
|
||
要求利用回溯方法解决子集和数问题。
|
||
|
||
输入格式:
|
||
第一行为一个正整数 n ，表示总集规模；
|
||
第二行是正整数 M ，表示子集的和数；
|
||
第三行是总集中 n 个正整数，中间用空格隔开。
|
||
|
||
输出格式:
|
||
如果有答案，则输出所有满足条件的子集（用固定长度n-元组表示符合条件的一个子集，即每行是一个长度为n的0/1序列），按字典序排列。
|
||
如果没有答案，则输出 -1
|
||
|
||
输入样例1:
|
||
4
|
||
31
|
||
11 13 24 7
|
||
输出样例1:
|
||
0011
|
||
1101
|
||
输入样例2:
|
||
6
|
||
30
|
||
5 10 12 13 15 18
|
||
输出样例2:
|
||
001001
|
||
101100
|
||
110010
|
||
数据范围
|
||
n≤20,∑w
|
||
i
|
||
|
||
,M≤10
|
||
9
|
||
|
||
|
||
Bonus
|
||
想一想，若只要求判断是否有解，当 n=40 时，有没有在最坏情况下仍能得到答案的算法？
|
||
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
1000 ms
|
||
Memory Limit
|
||
512 MB
|
||
Stack size limit
|
||
8192 KB
|
||
|
||
---
|
||
|
||
2 宝石排列
|
||
Score 100
|
||
有 n 种形状不同的宝石，每种形状有 n 颗，一共有 n
|
||
2
|
||
颗宝石。所有宝石一共有 n 种颜色，每种形状的 n 颗宝石颜色均不相同。现在要将这 n
|
||
2
|
||
颗宝石排成 n 行 n 列的方阵，使得方阵中每一行和每一列中的宝石，都具有 n 种不同的形状和颜色。请设计一个算法，计算对于给定的 n ，有多少种不同的宝石排列方案。
|
||
|
||
输入格式:
|
||
输入 n 值。
|
||
|
||
输出格式:
|
||
输出宝石排列方案的个数。
|
||
|
||
输入样例:
|
||
2
|
||
输出样例:
|
||
0
|
||
数据范围
|
||
1≤n≤4
|
||
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
1000 ms
|
||
Memory Limit
|
||
512 MB
|
||
Stack size limit
|
||
8192 KB
|
||
|
||
---
|
||
|
||
3 营救问题(分支限界)
|
||
Score 100
|
||
轮船A在海上遇险，它发出了求救信号。距离最近的轮船B收到了讯息，必须尽快赶到那里。 通过通讯，B获取了一张海洋图。这张图将海洋部分分化成n*n个单位，其中用1 标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。 为了尽快赶到出事地点A，B最少需要走多远的距离。
|
||
|
||
输入格式:
|
||
第一行为N， 2<N<=1000
|
||
第二行到第N+1行是一个N*N的01矩阵，表示海洋地图
|
||
最后一行是4个小于N的整数，分别表示哥伦比亚号的行列坐标和铁塔尼号的行列坐标。
|
||
|
||
输出格式:
|
||
哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。
|
||
|
||
输入样例:
|
||
3
|
||
001
|
||
101
|
||
100
|
||
1 1 3 3
|
||
输出样例:
|
||
4
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
400 ms
|
||
Memory Limit
|
||
64 MB
|
||
Stack size limit
|
||
8192 KB
|
||
C (gcc)
|