第3章 枚举！很暴力
第1节 坑爹的奥数
问题描述
小哼遇到了一道奥数题：
？？？+？？？=？？？，将数字1~9分别填入9个？中使得等式成立的组合共几种？
注：一个式子中每个数字只能使用一次。并且规定左右如173+286=459 和 286+173=459的形式是同一个组合。
package com.qianwei.chapter3;
public class MathematicalOlympiadTest1 {
public static void main(String[] args) {
int[] a = new int[10];
int[] book = new int[10];
int count = 0;
for (a[1] = 1; a[1] <= 9; a[1]++)
for (a[2] = 1; a[2] <= 9; a[2]++)
for (a[3] = 1; a[3] <= 9; a[3]++)
for (a[4] = 1; a[4] <= 9; a[4]++)
for (a[5] = 1; a[5] <= 9; a[5]++)
for (a[6] = 1; a[6] <= 9; a[6]++)
for (a[7] = 1; a[7] <= 9; a[7]++)
for (a[8] = 1; a[8] <= 9; a[8]++)
for (a[9] = 1; a[9] <= 9; a[9]++)
{
//此步不能省
for (int i = 1; i <= 9; i++)
book[i] = 0;
for (int i = 1; i <= 9; i++)
book[a[i]] = 1;
int sum = 0;
for (int i = 1; i <= 9; i++)
sum += book[i];
if (sum == 9 && a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6] == a[7]*100+a[8]*10+a[9])
{
count++;
System.out.println(""+a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8] + a[9]);
}
}
System.out.println(count/2);
}
}
若使用全排列的方法做十分简单，如下所示
package com.qianwei.chapter3;
public class MathematicalOlympiadTest2 {
static int cnt = 0;
public static void main(String[] args) {
int[] x = {1,2,3,4,5,6,7,8,9};
f(x,0);
System.out.println(cnt/2);
}
private static void f(int[] x, int k) {
if(k>=x.length){
test(x);
return;
}
for(int i=k; i<x.length; i++){
{int t=x[k]; x[k]=x[i]; x[i]=t;}
f(x,k+1);
{int t=x[k]; x[k]=x[i]; x[i]=t;}
}
}
private static void test(int[] x) {
int a = x[0]*100 + x[1]*10 + x[2];
int b = x[3]*100 + x[4]*10 + x[5];
int c = x[6]*100 + x[7]*10 + x[8];
if (a+b==c) {
System.out.println(a+" + "+b+" = "+c);
cnt++;
}
}
}
第2节 炸弹人
问题描述
小哼最近爱上了“炸弹人”游戏。你还记得在小霸王游戏机上的炸弹人吗？用放置炸弹的方法来消灭敌人。需将画面上的敌人全部消灭后，并找到隐藏在墙里的暗门才能过关。
现在有一个特殊的关卡如下。你只有一枚炸弹，但是这枚炸弹威力超强（杀伤距离超长，可以消灭杀伤范围内所有的敌人）。请问在哪里放置炸弹才可以消灭最多的敌人呢。
我们先将这个地图模型化。墙用 # 表示。这里有两种墙，一种是可以被炸掉的，另外一种是不能被炸掉的。但是由于现在只有一枚炸弹，所以都用 # 表示，炸弹是不能穿墙的。敌人用 G 表示，空地用 . 表示，当然炸弹只能放在空地上。
输入格式:
第一行2个整数为n m 表示迷宫的行和列，接下来的n行m列为地图。 1<=n,m<=50
输出格式:
输出做最多可以消灭的敌人数
样例 1 :
输入: 13 13 ############# #GG.GGG#GGG.# ###.#G#G#G#G# #.......#..G# #G#.###.#G#G# #GG.GGG.#.GG# #G#.#G#.#.### ##G...G.....# #G#.#G###.#G# #...G#GGG.GG# #G#.#G#G#.#G# #GG.GGG#G.GG# #############
输出: 8
package com.qianwei.chapter3;
import java.util.Scanner;
public class Bomberman {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sum, x, y;
int p=0, q=0, map=0;
int n = sc.nextInt();
int m = sc.nextInt();
char[][] a = new char[n][m];
for (int i=0;i<n;i++)
a[i] = sc.next().toCharArray();
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
if (a[i][j] == '.') {
sum = 0;
//由于所给地图最外围是一圈围墙，所以下面试探各个方向都不会出现数组越界
//向上统计可以消灭的敌人数
x = i;
y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
x--;
}
//向下统计可以消灭的敌人数
x = i;
y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
x++;
}
//向左统计可以消灭的敌人数
x = i;
y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
y--;
}
//向右统计可以消灭的敌人数
x = i;
y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
y++;
}
//更新map的值
if (sum > map) {
map = sum;
p = i;
q = j;
}
}
}
}
System.out.println("将炸弹放置在"+"("+p+","+q+"),"+"最多可以消灭"+map+"个敌人");
sc.close();
}
}
第3节 火柴棍等式
问题描述
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：
注意：
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
3. n根火柴棍必须全部用上
输入格式:
只有一行，有一个整数n（n<=24）。
输出格式:
只有一行，表示能拼成的不同等式的数目。
提示:
NOIP提高组2008
限制:
每个测试点1秒
样例 1 :
输入: 14
输出: 2
说明: 2个等式为0+1=1和1+0=1。
样例 2 :
输入: 18
输出: 9
说明: 9个等式为： 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11
package com.qianwei.chapter3;
import java.util.Scanner;
public class Matchstick {
static int[] f= {6,2,5,5,4,5,6,3,7,6};
public static int fun(int x)
{
int num = 0;
while (x / 10 != 0)
{
num += f[x%10];
x = x/10;
}
num += f[x];
return num;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sum = 0;
int m = sc.nextInt();
for (int a = 0; a <= 1111; a++)
for (int b = 0; b <= 1111; b++)
{
int c = a + b;
if (fun(a) + fun(b) + fun(c) == m-4)
{
System.out.println(a + " + " + b + " = " + c);
sum++;
}
}
System.out.println("一共可以拼出"+sum+"个不同的等式");
sc.close();
}
}
第4节 数的全排列
问题描述
输入一个自然数N（1<=N<=9），从小到大输出用1~N组成的所有排列，也就说全排列。例如输入3则输出
123
132
213
231
312
321
输入格式:
输入一个自然数N（1<=N<=9）
输出格式:
N的全排列，每行一个
限制:
每个测试点1秒
样例 1 :
输入: 2
输出: 12 21
样例 2 :
输入: 3
输出: 123 132 213 231 312 321
package com.qianwei.chapter3;
import java.util.Scanner;
public class FullPermutation {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i=1;i<=n;i++)
a[i-1] = i;
f(a,0);
sc.close();
}
private static void f(int[] x, int k) {
if(k>=x.length){
for (int i=0;i<x.length;i++)
System.out.print(x[i]+" ");
System.out.println();
return;
}
for(int i=k; i<x.length; i++){
{int t=x[k]; x[k]=x[i]; x[i]=t;}
f(x,k+1);
{int t=x[k]; x[k]=x[i]; x[i]=t;}
}
}
}