上了一年半的大学了，感觉水平还是很低，亟待提升。。。

假期里发现了一个北京大学的一个mooc《程序设计与算法》，正好满足的我的需要：编程能力低下，基础算法不熟。正好这个课才刚刚开始，我决定要跟下去，恩一定！ 下面两道题是第一章的练习：

##特殊密码锁

总Time Limit: 1000ms Memory Limit: 1024kB Description 有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹 凸两种状态，用手按按钮会改变其状态。="" 然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。

当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。

Input 两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。 Output 至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。 Sample Input

011

000

Sample Output

1

一开始，我想列出每一种情况然后挨个试，提交之后超时，导致错误的输入有27位。开始我还以为死循环了，自己试了一下那个输入，在十几秒的时候出现正确结果了。挨个试一共要试2^n次，而题目中n<30，我试了下for（int i = 0; i < n; i++){}（n=27）跑完都要四秒。去重也没想到有什么方法，所以只能转变思路。

首先，每个按钮至多会被按一次，假设按钮左右排列，如果左边的按钮状态确定，最后一个被确定状态的按钮只会受他右面的按钮影响（也就是说如果最后一个被确定状态的按钮凹凸情况与目标状态不符只能调整右边相邻按钮）。所以，这个问题被分为两种情况，第一个按钮有没有被改变。

 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

#include<string>
#include<iostream>

using namespace std;

inline void Flip(string &s, int i) //翻转
{
	s[i-1] = (s[i-1] == '1') ? '0' : '1';
	s[i] = (s[i] == '1') ? '0' : '1';
	s[i+1] = (s[i+1] == '1') ? '0' : '1';
}

int main()
{
	string a, b;
	cin >> a >> b;
	
	int len = a.size();
	int count1 = 0, count2 = 0;
	int flag = 0;
	
	string tmp = a;
	
	int i;
	for(i = 1; i < len - 1; i++)   //第一个按钮没有改变
	{
		if(tmp[i-1] != b[i-1])
		{
			Flip(tmp, i);
			count1++;
		}
	}
	if(tmp[i-1] != b[i-1])    //单独考虑最后一个按钮，减少判断
	{
		tmp[i-1] = (tmp[i-1] == '1') ? '0' : '1';
		tmp[i] = (tmp[i] == '1') ? '0' : '1';
		count1++;
	}
	if(tmp == b)
	{
		flag = 1;
	}
	
	tmp = a;
	
	tmp[0] = (tmp[0] == '1')? '0' : '1';   //第一个按钮状态改变
	tmp[1] = (tmp[1] == '1')? '0' : '1';
	count2++;
    for(i = 1; i < len-1; i++)
    {
    	if(tmp[i-1] != b[i-1])
    	{
    		Flip(tmp, i);
    		count2++;
		}
	}
	if(tmp[i-1] != b[i-1])
	{
		tmp[i-1] = (tmp[i-1] == '1') ? '0' : '1';
		tmp[i] = (tmp[i] == '1') ? '0' : '1';
		count2++;
	}
	if(tmp == b)
	{
		flag = 1;
	}
	
	if(flag)
	{
		cout << min(count1, count2) << endl; 
	}
	else
	{
		cout << "impossible" << endl; 
	}
	return 0;
}

拨钟问题

总Time Limit: 1000ms Memory Limit: 65536kB Description 有9个时钟，排成一个3*3的矩阵。

|——-| |——-| |——-| | | | | | | | |—O | |—O | | O | | | | | | | |——-| |——-| |——-| A B C

|——-| |——-| |——-| | | | | | | | O | | O | | O | | | | | | | | | | |——-| |——-| |——-| D E F

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

移动 影响的时钟

1
2
3
4
5
6
7
8
9

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

Input 9个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。其中，0=12点、1=3点、2=6点、3=9点。 Output 输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号从小到大输出结果。相邻两个整数之间用单个空格隔开。 Sample Input 3 3 0 2 2 2 2 1 2 Sample Output 4 5 8 9

这个可以穷举解决，每种移动的次数不会超过3次，每种移动一共有四种操作，共有4^9种情况不至于超时。

 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

#include<iostream> 

using namespace std;

int main()
{
	int origin[9];
	for(int i = 0; i < 9; i++)
	{
		cin >> origin[i];
	}
	
	int op[9] = {0};
	int min_op = 28;
	int sum = 0;
	for(int i1 = 0; i1 < 4; i1++)
		for(int i2 = 0; i2 < 4; i2++)
			for(int i3 = 0; i3 < 4; i3++)
				for(int i4 = 0; i4 < 4; i4++)
					for(int i5 = 0; i5 < 4; i5++)
						for(int i6 = 0; i6 < 4; i6++)
							for(int i7 = 0; i7 < 4; i7++)
								for(int i8 = 0; i8 < 4; i8++)
									for(int i9 = 0; i9 < 4; i9++)
									{
										if((i1 + i2 + i4 +origin[0]) % 4 == 0 && (i1 + i2 + i3 + i5 + origin[1]) % 4 == 0 && (i2 + i3 + i6 + origin[2]) % 4 == 0
										&& (i1 + i4 + i5 + i7 + origin[3]) % 4 == 0 && (i1 + i3 + i5 + i7 + i9 + origin[4]) % 4 == 0 && (i3 + i5 + i6 + i9 + origin[5]) % 4
										== 0 && (i4 + i7 + i8 + origin[6]) % 4 == 0 && (i5 + i7 + i8 + i9 + origin[7]) % 4 == 0 && (i6 + i8 + i9 + origin[8]) % 4 == 0)
										{
											sum = i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9;
											if(min_op > sum)
											{
												op[0] = i1;
												op[1] = i2;
												op[2] = i3;
												op[3] = i4;
												op[4] = i5;
												op[5] = i6;
												op[6] = i7;
												op[7] = i8;
												op[8] = i9;
											}
										}
									}
	
	for(int i = 0; i < 9; i++)
	{
		while(op[i]--)
		{
			cout << i+1 << " ";
		}
	}
	return 0;
}

第二种方法，找了一些移动的规律。只穷举A,B,C的，然后如果A不为0，通过第四种移动使其满足，B,C依次通过第五，六种满足。用第7，9种移动满足D，F为0。现在确定了A,B,C,D,F。然后检查E处是否为0和GHI处相不相等来确定是否继续。

  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
102
103
104
105
106
107
108
109
110
111
112
113
114

#include<iostream>
#include<memory> 

using namespace std;

const int m[10][9] = {
	{0},
    {1, 1, 0, 1, 1, 0, 0, 0, 0},  //op1: ABDE
    {1, 1, 1, 0, 0, 0, 0, 0, 0},  //op2: ABC
    {0, 1, 1, 0, 1, 1, 0, 0, 0},  //op3: BCEF
    {1, 0, 0, 1, 0, 0, 1, 0, 0},  //op4: ADG
    {0, 1, 0, 1, 1, 1, 0, 1, 0},  //op5: BDEFH
    {0, 0, 1, 0, 0, 1, 0, 0, 1},  //op6: CFI
    {0, 0, 0, 1, 1, 0, 1, 1, 0},  //op7: DEGH
    {0, 0, 0, 0, 0, 0, 1, 1, 1},  //op8: GHI
    {0, 0, 0, 0, 1, 1, 0, 1, 1}  //op9: EFHI
	};

void _plus(int t[9], int op_num, int mul) //op_num为第几种操作，mul提供此种移动的次数
{
	if(mul == 0)
	{
		return;
	}
	for(int i = 0; i < 9; i++)
	{
		t[i] += m[op_num][i] * mul;
		t[i] %= 4;
	}
}

int cal_mul(int t[9], int i)  //计算某处还需几次移动满足为0
{
	i -= 1;
	if(t[i] == 0)
	{
		return 0;
	}
	else
	{
		return 4 - t[i];
	}
}

int main()
{
	int origin[9];
	for(int i = 0; i < 9; i++)
		cin >> origin[i];
	
	int cur[9];        //移动中使用
	int result[9];    //记录结果
	for(int i = 0; i < 9; i++)
	{
		result[i] = 0;
	}
	int sum = 0;
	int min = 28;  //最多移动次数加一
	
	for(int i1 = 0; i1 < 4; i1++)
		for(int i2 = 0; i2 < 4; i2++)
			for(int i3 = 0; i3 < 4; i3++)
			{
				for(int i = 0; i < 9; i++)
				{
					cur[i] = origin[i];
				}
				_plus(cur, 1, i1);
				_plus(cur, 2, i2);
				_plus(cur, 3, i3);
				
				int i4,i5,i6,i7,i8,i9;
				
				i4 = cal_mul(cur, 1);
				_plus(cur, 4, i4);
				i5 = cal_mul(cur, 2);
				_plus(cur, 5, i5);
				i6 = cal_mul(cur, 3);
				_plus(cur, 6, i6);
				
				i7 = cal_mul(cur, 4);
				_plus(cur, 7, i7);
				i9 = cal_mul(cur, 6);
				_plus(cur, 9, i9);
				
				if(cur[4] == 0 && cur[6] == cur[7] && cur[7] == cur[8])
				{
					i8 = cal_mul(cur, 9);
					_plus(cur, 8, i8);
					sum = i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9;
					if(min > sum)
					{
						result[0] = i1;
						result[1] = i2;
						result[2] = i3;
						result[3] = i4;
						result[4] = i5;
						result[5] = i6;
						result[6] = i7;
						result[7] = i8;
						result[8] = i9;
						min = sum;
					}
				}
			}
	for(int i = 0; i < 9; i++)
	{
		while(result[i]--)
		{
			cout << i+1 << " ";
		}
	}
	return 0;
}