实训题目整理

熄灯问题

枚举/二进制优化

有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。

在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。

请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道1）第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次；2）各个按钮被按下的顺序对最终的结果没有影响；3）对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。

  • 输入
    5行组成，每一行包括6个数字（0或1）。

相邻两个数字之间用单个空格隔开。

0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。

  • 输出
    5行组成，每一行包括6个数字（0或1）。

相邻两个数字之间用单个空格隔开。

其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。

  • 输入样例

2
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
0 0 1 0 1 0
1 0 1 0 1 1
0 0 1 0 1 1
1 0 1 1 0 0
0 1 0 1 0 0

  • 输出样例

PUZZLE #1
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
PUZZLE #2
1 0 0 1 1 1
1 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 0 1 1 0 1
注意：PUZZLE行结尾没有空格，数字行最后有一个空格。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/* 每次碰一个开关就会使他上下左右（还有自己！）的灯都改变状态，灯只有开关两种状态，那么要使灯全部关掉，
其实每个灯最多只需要按一次。
  如何枚举？从第二排开始，只关注当前行和上一行的状态，用当前行把上一行的灯都关掉，而不考虑其他变
化，这样到最后一行，如果恰好全部熄灭，就是结果。能够影响结果的，就是第一行的状态，枚举第一行。
  第一行的状态怎么表示？由于只有开关（1/0）两种状态，可以用二进制数来表示，之后再按顺序输入到矩阵中
*/

#include <iostream>
#include <vector>
using namespace std;


bool ButtomStatu(const int m, int ori[5][6], int res[5][6])
{
	//枚举第一行的所有按键情况 利用二进制数来枚举 由于有6列 情况为2^6种 得到第一行的按键情况
	int temp = m;
	
	for (int i = 0; i < 6; i++)
	{
		res[0][i] = temp % 2;
		temp /= 2;
	}
 
	//把上面的情况按一遍 记得按自己所在的位置
	for (int i = 0; i < 6; i++)
	{
		if (res[0][i])
		{
			ori[0][i]= (ori[0][i] + 1) % 2;
			ori[1][i] = (ori[1][i] + 1) % 2;
			if (i + 1 < 6)ori[0][i + 1] = (ori[0][i + 1] + 1) % 2;
			if (i - 1 >= 0)ori[0][i - 1] = (ori[0][i - 1] + 1) % 2;
		}
	}

	//从第一行下面的每一行枚举 （核心是 第一行决定了下面每一行的情况 所以只需要枚举第一行
	for (int i = 1; i < 5; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			if (ori[i - 1][j] != 0)
			{
				if (i - 1 >= 0)ori[i - 1][j] = 0;
				if (i + 1 < 5)ori[i + 1][j] = (ori[i + 1][j] + 1) % 2;
				if (j + 1 < 6)ori[i][j + 1] = (ori[i][j + 1] + 1) % 2;
				if (j - 1 >= 0)ori[i][j - 1] = (ori[i][j - 1] + 1) % 2;
				ori[i][j]= (ori[i][j] + 1) % 2;
				res[i][j] = 1;
			}
		}
	}

	//如果灯全部关完 则为true
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 6; j++)
			if (ori[i][j] != 0)return false;

	return true;
}


int main()
{
	int n;
	cin >> n;
	int orilight[5][6];
	int resultlight[5][6];
	int constorilight[5][6];
	for(int k=1;k<=n;k++)
	{
		for (int row = 0; row < 5; row++)
		{
			for (int col = 0; col < 6; col++)
			{
				cin >> constorilight[row][col];
			}
		}
		//枚举64种情况
		for (int i = 0; i < 64; i++)
		{
			for (int i = 0; i < 5; i++)
				for (int j = 0; j < 6; j++)
				{
					orilight[i][j] = constorilight[i][j];
					resultlight[i][j] = 0;
				}
			//如果得到结果就输出
			if (ButtomStatu(i, orilight, resultlight))
			{
				cout << "PUZZLE #" << k << endl;
				for (int i = 0; i < 5; i++)
				{
					for (int j = 0; j < 6; j++)
						cout << resultlight[i][j] << " ";
					cout << endl;
				}
			}
		}
	}
	return 0;
}

假币问题

枚举

林克有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但林克不知道假币比真币轻还是重。

于是他向他朋友约珥借了一架天平，用这架天平称了这些币三次。

如果用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。

经过精心的设计，聪明的林克根据这三次称量结果找出假币，并且能够确定假币是轻是重。

如果给你林克的称量数据，你也可以找出假币并且确定假币是轻是重吗？（林克提供的称量数据保证一定能找出假币）。

  • 输入

第一行有一个数字n，表示有n组测试用例。

对于每组测试用例：

输入有三行，每行表示一次称量的结果。林克事先将银币标号为A-L。

每次称量的结果用三个以空格隔开的字符串表示：

天平左边放置的硬币 天平右边放置的硬币 平衡状态。

其中平衡状态用’’up’’, ‘’down’’, 或 ‘’even’’表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。

  • 输出

输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)

  • 输入样例 1

1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

  • 输出样例 1

K is the counterfeit coin and it is light. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/* 枚举十二枚硬币和轻重共24种状态，先设假币为轻，那么一定在上升的一边，依次枚举十二枚硬币是否在
上升的一边，如果不是，说明为真币或者假币不为轻，那么返回false。否则遍历三次称重，最后返回true，说明
这个就是假币并且为轻。
优化：不需要分别写轻，重的函数，只需要传一个参数表示状态，当判断重时把左右交换，就与判断轻的代码一样
*/
#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;
#include <string>
#include <vector>
vector<string>lef(3);
vector<string>rig(3);
vector<string>zt(3);
bool check(char iCoin,bool is_light)
{
	

	for (int i = 0; i < 3; i++)
	{
		string l = lef[i];
		string r = rig[i];
		string z = zt[i];
		if (!is_light)
			swap(l, r);
		switch (zt[i][0])
		{
		case 'e':
			if (l.find(iCoin)!=string::npos||r.find(iCoin)!=string::npos)
				return false;//说明在平衡的地方找到了  肯定是真币
			break;
		//现在枚举的是轻的 那么假币一定在上升的一方 
			//右边没找到那就肯定是真币
		case 'u':
			if (r.find(iCoin)==string::npos)return false;
			break;
			//左边没找到那就肯定是真币
		case 'd':
			if (l.find(iCoin)==string::npos)return false;
			break;
		default:
			break;
		}
	}
	return true;
}

int main()
{
	int n;
	cin >> n;
	
	while (n--)
	{
		int cmp[12] = { 0 };

		for (int i = 0; i < 3; i++)
		{
			cin >> lef[i]>>rig[i]>> zt[i];
		}
		
		//枚举十二枚硬币
		for (char iCoin = 'A'; iCoin <= 'L'; iCoin++) 
		{
			//枚举假币为轻的情况
			if (check(iCoin,true))
			{
				cout << iCoin << " is the counterfeit coin and it is light. " << endl;
				break;
			}
			if (check(iCoin,false))
			{
				cout << iCoin << " is the counterfeit coin and it is heavy. " << endl;
				break;
			}
		}
		lef.clear(), rig.clear(), zt.clear();
	}
	return 0;
}

拨钟问题

子集型回溯

有9个时钟，排成一个3*3的矩阵。

(图 1)明显显示不出来嘛！

现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如下表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。

移动 影响的时钟

1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

  • 输入

9个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。其中，0=12点、1=3点、2=6点、3=9点。

  • 输出

输出一个最短的时钟指针移动序列，使得9个时钟的指针都指向12点。按照移动的序号从小到大输出结果。 相邻两个整数之间用单个空格隔开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*子集型回溯：进入dfs之后首先判断退出条件。之后是选或不选，对于1~9每个拨钟的方法，都可以选择拨或者
不拨！！然后是每个数字循环三次（最多只需要拨三次）。
判断，k>9的时候判断是否符合，符合判断最短，之前应记录每一步。
*/
#include <bits/stdc++.h>
using namespace std;
vector<string>inf = { " ","ABDE" ,"ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};
vector<int>ori(100);
vector<int>movevec(100);
vector<int>showvec(100);
int u = 0;
int si = 0;
int mi = 50;

bool check(vector<int>ori)//检查是否符合条件（全为0
{
	for (int i = 0; i < 9; i++)
	{
		if (ori[i] != 0)return false;
	}
	return true;
}

void move(int k)//移动的距离
{
	for (int i = 0; i < inf[k].size(); i++)
	{
		ori[inf[k][i] - 'A'] = (ori[inf[k][i] - 'A'] + 1) % 4;
	}
}

void dfs(int k)
{
	if (k > 9)//相当于循环9次  即枚举9种拨钟方法
	{
		if (check(ori) && si < mi)//由于需要最少的次数所以用mi记录（当全为0时）最少次数
		{
			mi = si;
			showvec = movevec;//记录最少次数的走法 由于是按顺序枚举 所以一定是从小到大的
		}
		return;
	}
 
 //子集型回溯  可以一个都不选
	dfs(k + 1);//先进去9次  这样才可以回溯 只拨第9个不行 从这里退出 拨第8个和第9个 由于move（K） 则可以枚举到1次8 1次9 2次9 3次9 ） 2次8 1次9 2次9 3次9 ）3次8 1次9 2次9 3次9。。。依次类推可以枚举到全部的情况

	for (int i = 1; i <= 3; i++)//每一种方法拨三次
	{
		movevec[si++] = k;//记录拨钟方法和次数
		move(k);//拨钟
		dfs(k + 1);
	}
	si -= 3;
	move(k);
}

int main()
{
	for (int i = 0; i < 9; i++)
	{
		cin >> ori[i];
	}

	dfs(1);

	for (int i = 0; i <mi ; i++)
	{
		cout << showvec[i] << " ";
	}

}

2的幂次方表示

递归 呜呜 递归真的好抽象 难过 tllwtg和wegret怎么都说自然就会了

题目居然是图片 那就点链接了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/* 当n=1的时候怎么办？n=2的时候怎么办？n=其他数的时候怎么办？再把次方也递归一下（1次方要特判！！）
然后减去这个数，剩下的数再拆分
*/
#include <iostream>
using namespace std;

void mf(int n)
{
	if (n == 1)
	{
		// 1不可划分 直接输出
		cout << "2(0)";
		return;
	}
	else if (n == 2)
	{
		// 2不可划分
		cout << "2";
		return;
	}
	// 其他数 可划分 

	int k = 0;
	int a = 1;
	while (a * 2 <= n)
	{
		a *= 2;
		k++;
	}
	// 分解次方
	// 这个地方要特判  因为只剩一个2的时候就直接输出了 而不是把k=1再拿去递归
	if (a == 2)
	{
		cout << "2";
	}
	else
	{
		cout << "2(";
		mf(k);
		cout << ")";
	}

	int x = n - a;
	if (x == 0)return;
	cout << "+";
	mf(x);
}

int main()
{
	int n;
	cin >> n;
	mf(n);
}

直接用python写算了

算24

回溯
熟悉了递归和深度优先搜索，小华知道现在是让小鲁综合运用所学知识的时候了，他让小鲁调整一道经典题：算24.

给出4个小于10个正整数，你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于24。

这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。

比如，对于5，5，5，1，我们知道5 * (5 – 1 / 5) = 24，因此可以得到24。又比如，对于1，1，4，2，我们怎么都不能得到24。

注意：输入数字的次序可以改变。

  • 输入
    输入数据包括多行，每行给出一组测试数据，包括4个小于10个正整数。最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。

  • 输出
    对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""回溯，首先寻找结束条件，当等于24时退出递归，记得用绝对值和浮点数判断。
然后基本思路时把每种组合的加减乘除都算一遍，如何储存状态？使用一个列表，每次选出两个数，进行四则
运算，然后把剩余的没算的数也加进shengyu数组里面，递归运算。记得要回溯pop，还要排除b == 0的情况（被除数）。
"""
import math
def cal(lis):
    if len(lis) == 1 and math.fabs(lis[0] - 24) < 1e-6:
        return True
    for i in range(len(lis)):
        for j in range(len(lis)):

            if i == j:
                continue

            a = lis[i]
            b = lis[j]
            shengyu = []
            for k in range(len(lis)):
                if k != i and k != j:
                    shengyu.append(lis[k])
            if b == 0:
                continue
            sum1 = a + b
            sub = a - b
            mul = a * b
            div = a / b
            left = [sum1, sub, mul, div]
            for x in left:
                shengyu.append(x)
                if cal(shengyu):
                    return True
                shengyu.pop()

    return False



while True:
    lis = list(map(float, input().split()))
    if lis.count(0) == 4:
        break

    if cal(lis):
        print("YES")
    else:
        print("NO")

求排列的逆序数

分治 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
"""
首先分治的思路分别来求逆序数，只在左半边的，只在右半边的和跨两边的。利用归并排序的模板，当左边
的数大于右边的时候，就是逆序数，由于归并排序已经排好了数，所以逆序数的个数为 mid - i + 1，
（mid右边的比i小）
"""
n = int(input())
temp = [0 for _ in range(n)]
lis = list(map(int, input().split()))
ret = 0

def merge(l, r):
    global ret
    if l >= r:
        return
    mid = (l + r) >> 1
    merge(l, mid)
    merge(mid + 1, r)
    i, j, k = l, mid + 1, 0
    while i <= mid and j <= r:
        if lis[i] <= lis[j]:
            temp[k] = lis[i]
            i += 1
            k += 1
        else:
            temp[k] = lis[j]
            j += 1
            k += 1
            ret += mid - i + 1
    while i <= mid:
        temp[k] = lis[i]
        i += 1
        k += 1
    while j <= r:
        temp[k] = lis[j]
        j += 1
        k += 1

    j = 0
    for i in range(l, r + 1):
        lis[i] = temp[j]
        j += 1

merge(0, n - 1)
print(ret)

海拉鲁城堡问题

深搜 位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
"""因为需要找到所有房间中最大的，而一次搜索只能找一个房间的面积，可以遍历寻找未搜索过的房间。
深搜和广搜选哪个，一看是找面积最大的本来想用广搜但是判断条件写出来可能会比深搜麻烦很多，所以还是用深搜。
每次搜索之前，位运算判断该位是否可以走
"""
import sys
sys.setrecursionlimit(5000)
N = 100
row = int(input())
col = int(input())
lis = [[0] * N for _ in range(N)]
color = [[0] * N for _ in range(N)]
maxArea = 0
maxRoom = 0


def mask1(x):
    return (x & 1) == 0


def mask2(x):
    return (x & 2) == 0


def mask3(x):
    return (x & 4) == 0


def mask4(x):
    return (x & 8) == 0


def dfs(a, b):
    global maxArea, maxRoom
    if color[a][b] != 0:
        return
    maxArea += 1
    color[a][b] = maxRoom
    if mask1(lis[a][b]):
        dfs(a, b - 1)
    if mask2(lis[a][b]):
        dfs(a - 1, b)
    if mask3(lis[a][b]):
        dfs(a, b + 1)
    if mask4(lis[a][b]):
        dfs(a + 1, b)


for i in range(row):
    a = list(map(int, input().split()))
    for j in range(col):
        lis[i][j+1] = a[j]

retArea = 0

for i in range(1,row+1):
    for j in range(1,col+1):
        if color[i][j] == 0:
            maxArea = 0
            maxRoom += 1
            dfs(i, j)
            retArea = max(retArea, maxArea)

print(maxRoom)
print(retArea)

英杰们的蛋糕塔

深搜 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
//宏定义简化
#define ButtonArea(r) (r*r)
#define surArea(r,h) (2*r*h)
#define Volume(r,h) ((r)*(r)*(h))
#define V2surArea(r,v) (2*v/(r))
#define INF 0x7fffffff 
int N, V, minsurArea = INF;
int sumMinS[27], sumMinV[27];

// 搜索的主体是 枚举每一层的R H 寻找体积符合时 最小的表面积
void dfs(int u,int nr,int nh,int lv,int cs)
{
	if (u == 0)
	{
		if (lv == 0 && cs < minsurArea)minsurArea = cs;
		return;
	}
	// 剪枝操作 1.当前剩余的体积小于上面累加起来最小的体积 说明已经不符合 
	// 2.当前表面积加上上面的最小表面积 大于minsurArea 不符合
	// 3.启发式剪枝 提前看到下一步的结果 当nr没到最后一层 并且 上一层的表面积加上当前累加的面积已经大于minsurArea 不符合
	if (lv < sumMinV[u])return;
	if (cs + sumMinS[u] >= minsurArea)return;
	if (nr > 1 && V2surArea(nr - 1, lv) + cs >= minsurArea)return;

	//从最大层 （r最大） 到最小
	for (int r = nr - 1; r >= u; r--)
	{
		// 当到达最高层的时候 让这一层的面积等于 底面积（后面是加上表面积 是每个都有的操作 
		if (u == N)cs = ButtonArea(r);
		// 预处理出最大高度的最小值 （如果把当前剩余的体积 全部做成一层 除以当前的表面积 就是最大高度
		int H_max = (1.0 * lv / ButtonArea(r)) + 1;
		if (H_max > nh - 1)H_max = nh - 1;
		// 枚举h
		for (int h = H_max; h >= u; h--)
		{
			int s = surArea(r, h);
			int v = Volume(r, h);
			dfs(u - 1, r, h, lv - v, cs + s);
		}
	}
}

int main()
{
	cin >> V >> N;

	//预处理出 累加到每一层的最小的面积和体积 用于后面的剪枝
	sumMinS[0] = sumMinV[0] = 0;
	for (int i = 1; i <= N; i++)
	{
		sumMinS[i] = sumMinS[i - 1] + surArea(i, i);
		sumMinV[i] = sumMinV[i - 1] + Volume(i, i);
	}
	//预处理出 最下面一层的 R H的上界 减少计算
	int maxH = (V - sumMinV[N - 1]) / ButtonArea(N) + 1;
	int maxR = sqrt(double((V - sumMinV[N - 1]) + 1));

	dfs(N, maxR, maxH, V, 0);//从最大的蛋糕往上搜索
	if (minsurArea == INF)
		cout << 0 << endl;
	else cout << minsurArea << endl;
}

击杀黄金蛋糕人马

记忆化搜索 动态规划

在海拉鲁大陆冒险，没有绝佳的剑法+想象力是不可能存活下来的。
这不，林克遇到了一个特别巨大的敌人——黄金蛋糕人马（莱尼尔的变种）
这黄金蛋糕人马长相非常特别，没有脚没有手没有嘴巴没有头，整个身材就是一个大矩形（喂喂，这不就是黄金莱尼尔吗？）
它的长和宽分别是整数w、h。
林克举起大师之剑，挥向黄金蛋糕人马，要将其切成m块矩形小块打包走，分给自己的朋友（每块都必须是矩形、且长和宽均为整数）。
大师之剑无比锐利，每一斩带出的剑气能将黄金蛋糕人马劈成两半（形成两个小矩形蛋糕）
经过m-1斩，黄金蛋糕人马居然被劈成m块小蛋糕（喂喂，你的想象力也太丰富了，明明切不开好吗？）
请计算：最后得到的m块小蛋糕中，最大的那块蛋糕的面积下限。
假设w= 4,h= 4,m= 4，则下面的斩击可使得其中最大蛋糕块的面积最小。(十字斩)
假设w= 4,h= 4,m= 3，则下面的斩击可使得其中最大蛋糕块的面积最小:.(二连斩)

  • 输入

共有多行，每行表示一个测试案例。
每行是三个用空格分开的整数w, h, m ，其中1 ≤ w, h, m ≤ 20 ， m ≤ wh.
当 w = h = m = 0 时不需要处理，表示输入结束。

  • 输出

每个测试案例的结果占一行，输出一个整数，表示最大蛋糕块的面积下限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
* 记忆化搜索 储存已经搜过的值 下次需要时直接返回 储存的一般为搜索的值 dfs返回值一般定义为int（不为void）
* 
* 原来的方法主要是分成左右两边的时候不好表示 
* 该方法dfs传入的是当前的方块的长和宽 分为左右两边（分治）枚举左右边切的位置 和左右边分别切的刀数
*/

#include <bits/stdc++.h>
using namespace std;
int w, h, m;
int maxCake[30][30][500];
const int inf = 0x3fffffff;
int dfs(int w, int h, int m)
{
	// 当m为0的时候返回当前的面积
	if (m == 0)return w * h;
	// 记忆化搜索
	if (maxCake[w][h][m])return maxCake[w][h][m];

	int a, b, ans = inf;
	
	for (int i = 0; i < m; i++)
	{
		for (int j = 1; j < w; j++) 
		{
			a = dfs(j, h, i);// 切m 刀的蛋糕是由切i刀和m - i - 1刀组成的   w - i 最后会反转 可以变量所有情况
			b = dfs(w - j, h, m - 1 - i);
			if (ans > max(a, b))ans = max(a, b);// 得到最大的蛋糕 取最小
		}
		for (int j = 1; j < h; j++)
		{
			a = dfs(w, j, i);
			b = dfs(w, h - j, m - 1 - i);
			if (ans > max(a, b))ans = max(a, b);
		}
	}
	maxCake[w][h][m] = ans;
	return ans;
}

int main()
{
	while (cin >> w >> h >> m)
	{
		if (w == h && h == m && m == 0)return 0;
		
		cout << dfs(w, h, m - 1) << endl;
		memset(maxCake, 0, sizeof maxCake);
	}
}

滚石柱

广搜 结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
广搜加上结构体表示物体的状态，主要难点就在于状态的表示。用结构体表示物体的状态，更新状
态时，用三维数组，增加的一维用来表示0立着横着竖着

#include <bits/stdc++.h>
using namespace std;
struct State
{
	int x, y, lie;
};
const int N = 510;
char g[N][N];
int d[N][N][3];
int row, col;

int dir[3][4][3] =
{
	{{1,0,2},{-2,0,2},{0,1,1},{0,-2,1}},//0 立着
	{{-1,0,1},{0,2,0},{1,0,1},{0,-1,0}},//1 横着
	{{-1,0,0},{2,0,0},{0,1,2},{0,-1,2}}//2 竖着
};


bool check(int x, int y)
{
	if (x >= row || y >= col || x < 0 || y < 0)return false;
	return g[x][y] != '#';
}

int bfs(State start, State end)
{
	memset(d, -1, sizeof d);
	d[start.x][start.y][start.lie] = 0;
	queue<State>q;
	q.push(start);

	while (!q.empty())
	{
		State t = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			State next = { t.x + dir[t.lie][i][0],t.y + dir[t.lie][i][1],dir[t.lie][i][2] };
			int x = next.x, y = next.y;
			if (!check(x, y))continue;
			if (next.lie == 0 && g[x][y] == 'E')continue;
			if (next.lie == 1 && !check(x, y + 1))continue;
			if (next.lie == 2 && !check(x + 1, y))continue;
			if (d[x][y][next.lie] == -1)
			{
				d[x][y][next.lie] = d[t.x][t.y][t.lie] + 1;
				q.push(next);
			}
		}
	}
	return d[end.x][end.y][end.lie];
}

int main()
{
	while (cin >> row >> col, row || col)
	{
		for (int i = 0; i < row; i++)
			cin >> g[i];

		State start = { -1 }, end;
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				if (g[i][j] == 'X' && start.x == -1)
				{
					if (g[i + 1][j] == 'X')start = { i,j,2 };
					else if (g[i][j + 1] == 'X')start = { i,j,1 };
					else start = { i,j,0 };
				}
				else if (g[i][j] == 'O')
				{
					end = { i,j,0 };
				}
			}
		}

		int res = bfs(start, end);
		if (res == -1)puts("Impossible");
		else cout << res << endl;
	}
}
algorithm
#Ans
实训题目整理
https://brtulien.github.io/2023/07/23/实训题目整理/
作者
Brtulien
发布于
2023年7月23日
更新于
2024年7月1日
许可协议