紫书第七章 暴力求解法 例题
开年攻略第七章，这章比较省脑子，暴力法刚就是了 2.10
原来简单的时代早已过去了 2.27
2019/2/10
UVA725 配平等式！穷举！刚！
做完这个就做不进去了，娱乐之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
using namespace std;
int n;
bool f(long long x){
x = x + x * n * 100000;
int a[10] = {0};
for (int i = 0; i <= 9;i++){
a[x % 10]++;
x /= 10;
}
for (int i = 0; i <= 9;i++)
if(!a[i]) return false;
return true;
}
int main(){
int kase = 0;
while(scanf("%d",&n)&&n){
if(kase++) putchar('\n');
bool mark = false;
for(int i = 1234; i * n <= 98765;i++){
if(f(i)){
printf("%.5d / %.5d = %d\n", i * n, i,n);
mark = true;
}
}
if(!mark) printf("There are no solutions for %d.\n", n);
}
return 0;
}
2019/2/12
UVA11059 找最大乘积!穷举！刚！
做完这个又做不进去了，娱乐之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
using namespace std;
long long a[1000];
int main(){
int n;
int kase = 0;
while(cin>>n){
long long x;
long long max = -100000;
for (int i = 0; i < 1000;i++)
a[i] = 1;
for (int i = 0; i < n; i++)
{
cin >> x;
for (int j = 0; j <= i; j++)
{
a[j] *= x;
if (a[j] > max)
max = a[j];
}
}
if(max<0)
max = 0;
cout << "Case #" << ++kase << ": The maximum product is "<<max<<".\n\n";
}
return 0;
}
2019/2/14
UVA10976 又配平等式，穷举！1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int x[1000],y[1000];
int main(){
int k;
while(cin>>k){
int count=0;
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
for (int i=k+1;i<=2*k;i++){
if(((k*i)%(i-k)==0)&&((k*i)/(i-k)>=i)){
y[count]=i;
x[count]=(k*i)/(i-k);
count++;
}
}
cout<<count<<'\n';
for(int i=0;i<count;i++)
cout<<"1/"<<k<<" = 1/"<<x[i]<<" + 1/"<<y[i]<<"\n";
}
return 0;
}
UVA524 找特定排列，穷举！
坑点：最后一行没有换行符
EXP：学了点快速素数筛算法(另起一篇有写)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
using namespace std;
const int maxn=16*2+5;
bool number[maxn];
int prime[maxn],a[maxn],vis[maxn];
int n;
void isprime(){
int i,j,c=0;
memset(number,true,sizeof(number));
memset(prime,0,sizeof(prime));
for(int i=2;i<=maxn;i++){
if(number[i]) prime[c++]=i;
for(j=0;j<c&&prime[j]*i<=maxn;j++){
number[prime[j]*i]=false;
if(i%prime[j]==0) break;
//保证每个合数只会被它的最小质因数筛去
//因此每个数只会被标记一次
}
}
}
void dfs(int cur){
if(cur==n&&number[a[0]+a[n-1]]){
for(int i=0;i<n-1;i++)
cout<<a[i]<<' ';
cout<<a[n-1]<<'\n';
}
else for(int i=2;i<=n;i++){
if(!vis[i]&&number[i+a[cur-1]]){
a[cur]=i;
vis[i]=i;
dfs(cur+1);
vis[i]=0;
}
}
}
int main(){
int kase=0;
isprime();
while(cin>>n){
if(kase) cout<<'\n';
cout<<"Case "<<++kase<<":\n";
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
a[0]=1;
dfs(1);
}
return 0;
}
UVA129 简单的回溯法
debug到吐，不想评价了，看课本源码吧
UVA140 回溯法 排列
总情况数8!，还不算太大。
回溯法求解，注意当前已计算节点的最小带宽大于等于最小带宽时剪枝即可。
用到了next_permutation()来快速求下一排列。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
using namespace std;
int a[100][30];
int sizea[100];
char m[30],ans[30];
int main(){
char x,y;
int cnt,minans,now,part;
while(scanf("%c",&x)&&x!='#'){
minans=999999;
now=cnt=0;
memset(sizea,0,sizeof(sizea));
memset(m,0,sizeof(m));
do{
getchar();
while(y=getchar(),isalpha(y)){
a[x][sizea[x]]=y;
if(++sizea[x]==1) m[cnt++]=x;
a[y][sizea[y]]=x;
if(++sizea[y]==1) m[cnt++]=y;
}
if(y==';') x=getchar();
else break;
}while(1);
sort(m,m+cnt);
do{
now=0;
for(int i=0;i<cnt;i++){
part=0;
for(int j=0;j<sizea[m[i]];j++){
int k;
for(k=0;m[k]!=a[m[i]][j];k++);
if(abs(i-k)>part) part=abs(i-k);
}
if(part>now) now=part;
if(now>minans) break;
}
if(now<minans){
minans=now;
for(int i=0;i<cnt;i++) ans[i]=m[i];
}
}while(next_permutation(m,m+cnt));
for(int i=0;i<cnt;i++) printf("%c ",ans[i]);
printf("-> %d\n",minans);
}
return 0;
}
2019/2/22
UVA1354 集合的二进制运算
做不出来，上题解UVa1354 ——天平难题
这种思路很新颖，但我实现不来，先放着吧
2019/2/25
P1359 状态空间搜索 hash表
这几天忙于补寒假作业(最后没补完)和补考(最后也没过)，这几天开学突然闲下来了，可以继续展开工作了。这题一开始被紫书上巨量的篇幅吓退了，包括上面那道和接下来的几道都是比较复杂的题目。学习进度也在这里卡住了。但现在有空了，年轻嘛，有了时间一个劲儿的钻研就是了
最后看了看洛谷上的题解，基本上就是一点就通，不多说了，看代码。
核心就是BFS，特殊的是这一题使用了map来记录访问状态(我第一次见)
卡点:一开始矩阵转数字串的算法前后颠倒，出来的数字串与目标相反，卡了20min
EXP:年轻人还是得撑得住气儿，慢慢钻研，慢慢思考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
using namespace std;
const ll dx[4]={-1,1,0,0};
const ll dy[4]={0,0,-1,1};
map<ll,ll> m;
queue<ll> q;
ll a[3][3];
void swap(ll &a,ll &b){
a=a^b;
b=b^a;
a=a^b;
}
ll getseq(){
ll seq=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++){
seq*=10;
seq+=a[i][j];
}
return seq;
}
int main(){
int i;
ll temp,x2,y2,x1,y1,newseq,seq;
cin>>seq;
m[seq]=0;
q.push(seq);
while(!q.empty()){
seq=q.front();
if(seq==123804765) break;
q.pop();
temp=seq;
for(i=8;i>=0;i--){
a[i/3][i%3]=temp%10;
temp/=10;
}
int j;
for(j=0;a[j/3][j%3]!=0;j++);
x1=j%3;
y1=j/3;
for(i=0;i<4;i++){
x2=x1+dx[i];
y2=y1+dy[i];
if(x2<0||y2<0||x2>=3||y2>=3) continue;
swap(a[y1][x1],a[y2][x2]);
newseq=getseq();
swap(a[y1][x1],a[y2][x2]);
if(m.count(newseq)==1) continue;
//若key存在count()返回1，否则返回0
m[newseq]=m[seq]+1;
q.push(newseq);
}
}
cout<<m[123804765];
return 0;
}
2019/2/26
UVA10603 状态空间搜索 set去重原理
与上一题题型相同，只不过这题的队列根据dist排序，并且用了set来记录访问状态。行文至此我发现用map也可以,试验之后确实也可以，代码量和速度上二者差不多。
卡点:不知道set判重的原理导致中途查了一会儿资料
EXP1:set和map判重会用到小于运算符，如果(哈希值相等||小于运算符返回0)即为重复
EXP2:priority_queue默认从大到小排列，可通过覆写小于预算付更改顺序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
using namespace std;
struct node{
int v[3];
int dist;
node(const node& n){
for(int i=0;i<3;i++) v[i]=n.v[i];
dist=n.dist;
}
node(int a,int b,int c,int d)
:v{a,b,c},dist(d){}
};
struct mnode{//set判重用的node衍生节点
int v[3];
mnode(const node& n)
:v{n.v[0],n.v[1],n.v[2]}{}
mnode(int a,int b,int c)
:v{a,b,c}{}
};
bool operator < (const mnode& m,const mnode& n){
if(m.v[0]!=n.v[0]) return m.v[0]<n.v[0];
else if(m.v[1]!=n.v[1]) return m.v[1]<n.v[1];
else return m.v[2]<n.v[2];
//set判重原理:(哈希值相等||小于运算符返回0)即为重复
}
bool operator < (const node& a,const node& b){
return a.dist>b.dist;
//priority_queue中默认最大元素位于队首
}
int maxv[3],aim,maxd,mindist;
void solve(){
int i,j;
cin>>maxv[0]>>maxv[1]>>maxv[2]>>aim;
priority_queue<node> q;
set<mnode> s;
q.push(node(0,0,maxv[2],0));
s.insert(mnode(0,0,maxv[2]));
maxd=-1;
mindist=0;
while(!q.empty()){
node n=q.top();
q.pop();
for(i=0;i<3;i++){
if(n.v[i]==aim){
maxd=aim;
mindist=n.dist;
return;
}
else if(aim-n.v[i]>0){
if(n.v[i]>maxd||(n.v[i]==maxd&&n.dist<mindist)){
maxd=n.v[i];
mindist=n.dist;
}
}
}
for(i=0;i<3;i++)
for(j=0;j<3;j++){
if(i==j) continue;
node newn(n);
if(n.v[i]+n.v[j]<=maxv[j]){//倒完
newn.v[j]+=newn.v[i];
newn.v[i]=0;
newn.dist+=n.v[i];
}
else{//倒不完且有剩余
newn.v[i]-=maxv[j]-newn.v[j];
newn.v[j]=maxv[j];
newn.dist+=maxv[j]-n.v[j];
}
if(newn.dist&&!s.count(mnode(newn))){
q.push(newn);
s.insert(mnode(newn));
}
}
}
return;
}
int main(){
int kase;
cin>>kase;
while(kase--){
solve();
cout<<mindist<<' '<<maxd<<'\n';
}
return 0;
}
2019/2/27
UVA1601 状态空间搜索
这题要点在于从所给图里抠出一张简化的图来降低运算量。我写得看起来很麻烦，还WA了，但能通过udebug证明算法还是基本正确的。
最后抄了一遍洛谷的题解，感觉学到了几条奇淫巧技。
EXP1:fgets比scanf快，也已用来处理地图问题
EXP2:可以使用<<与&来灵活的在一个变量里塞入多个变量
EXP3:scanf的参数可以用来过滤换行符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//WA代码，看看就好不要模仿
using namespace std;
struct node{
int v[3];
node(int a,int b,int c)
:v{a,b,c}{}
};
const int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
int map[20][20];
int g[200][5];
int vis[200][200][200];
int aim[3],now[3];
int xmax,ymax,ghostnum;
bool conflict(int a, int b, int a2, int b2) {
return ((a2 == b2) || (a == b2 && b == a2));
}
int main(){
int i,j,k;
while(cin>>xmax>>ymax>>ghostnum){
if(!(xmax||ymax||ghostnum)) return 0;
memset(map,0,sizeof(map));
memset(g,-1,sizeof(g));
memset(vis,0,sizeof(vis));
memset(now,0,sizeof(now));
memset(aim,0,sizeof(aim));
int count=0;
getchar();
for(i=0;i<ymax;i++){
for(j=0;j<xmax;j++){
map[i][j]=getchar();
if(map[i][j]=='#') map[i][j]=-1;
else{
if(map[i][j]==' ') count;
else if(isupper(map[i][j])) aim[map[i][j]-'A']=count+1;
else if(islower(map[i][j])) now[map[i][j]-'a']=count+1;
map[i][j]=count+1;
count++;
}
}
getchar();
}
for(i=0;i<ymax;i++)
for(j=0;j<xmax;j++)
if(map[i][j]>-1){
int l=0;
for(k=0;k<5;k++){
if(i+dy[k]>=ymax||j+dx[k]>=xmax||i+dy[k]<0||j+dx[k]<0||
map[i+dy[k]][j+dx[k]]==-1) continue;
g[map[i][j]][l++]=map[i+dy[k]][j+dx[k]];
}
}
queue<node> q;
q.push(node(now[0],now[1],now[2]));
vis[now[0]][now[1]][now[2]]=1;
while(!q.empty()){
node n=q.front();
q.pop();
if(n.v[0]==aim[0]&&n.v[1]==aim[1]&&n.v[2]==aim[2]) break;
for(i=0;g[n.v[0]][i]>-1&&i<5;i++){
if(n.v[1]==0){
if(vis[g[n.v[0]][i]][0][0]==0){
vis[g[n.v[0]][i]][0][0]=vis[n.v[0]][0][0]+1;
q.push(node(g[n.v[0]][i],0,0));
}
}
else{
for(j=0;g[n.v[1]][j]>-1&&j<5;j++){
if(n.v[2]==0){
if(vis[g[n.v[0]][i]][g[n.v[1]][j]][0]==0&&
!conflict(n.v[0],n.v[1],g[n.v[0]][i],g[n.v[1]][j])){
vis[g[n.v[0]][i]][g[n.v[1]][j]][0]=vis[n.v[0]][n.v[1]][0]+1;
q.push(node(g[n.v[0]][i],g[n.v[1]][j],0));
}
}
else{
for(k=0;g[n.v[2]][k]>-1&&k<5;k++){
if(vis[g[n.v[0]][i]][g[n.v[1]][j]][g[n.v[2]][k]]==0&&
!conflict(n.v[0],n.v[1],g[n.v[0]][i],g[n.v[1]][j])&&
!conflict(n.v[0],n.v[2],g[n.v[0]][i],g[n.v[2]][k])&&
!conflict(n.v[2],n.v[1],g[n.v[2]][k],g[n.v[1]][j])){
vis[g[n.v[0]][i]][g[n.v[1]][j]][g[n.v[2]][k]]=vis[n.v[0]][n.v[1]][n.v[2]]+1;
q.push(node(g[n.v[0]][i],g[n.v[1]][j],g[n.v[2]][k]));
}
}
}
}
}
}
}
cout<<vis[aim[0]][aim[1]][aim[2]]-1<<'\n';
}
return 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
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
using namespace std;
int w, h, n, s[3], t[3];//s起始t终止
char dataset[20][20];
int G[200][5], dist[200][200][200];//dist记录访问状态和所用步数
int deg[200]; //记录每个编号为i的空格周围可以走的步数
int dx[] = {0, -1, 1, 0, 0};
int dy[] = {0, 0, 0, -1, 1};
inline int ID(int a, int b, int c) {
return (a << 16) | (b << 8) | c;
}
inline bool conflict(int a, int b, int a2, int b2) {
return ((a2 == b2) || (a == b2 && b == a2));
}
int bfs() {
queue<int> q;
q.push(ID(s[0], s[1], s[2]));
dist[s[0]][s[1]][s[2]] = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
int a = (u >> 16) & 0xff, b = (u >> 8) & 0xff, c = u & 0xff; //解码出出列状态三个小鬼的位置
if(a == t[0] && b == t[1] && c == t[2]) return dist[a][b][c];
for(int i = 0; i < deg[a]; i++) {
int a2 = G[a][i];
for(int j = 0; j < deg[b]; j++) {
int b2 = G[b][j];
if(conflict(a, b, a2, b2)) continue;
for(int k = 0; k < deg[c]; k++) {
int c2 = G[c][k];
if(conflict(a, c, a2, c2) || conflict(b, c, b2, c2)) continue;
if(dist[a2][b2][c2] == -1) { //等于-1说明没有访问过该状态，就要压入队列
dist[a2][b2][c2] = dist[a][b][c] + 1;
q.push(ID(a2, b2, c2));
}
}
}
}
}
return -1;
}
int main() {
while(~scanf("%d%d%d\n", &w, &h, &n) && n) {
for(int i = 0; i < h; i++) fgets(dataset[i], 20, stdin); //此处不能用scanf来处理输入，会TLE
int cnt = 0, x[200], y[200], id[20][20]; //从图中抽取出空间并求出初始状态和目标状态
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++) {
if(dataset[i][j] != '#') {
x[cnt] = i; y[cnt] = j; id[i][j] = cnt;
if(islower(dataset[i][j])) s[dataset[i][j] - 'a'] = cnt;
else if(isupper(dataset[i][j])) t[dataset[i][j] - 'A'] = cnt;
cnt++; //注意这里的cnt++不能偷懒在上面一行末尾，因为这样有时候cnt++会没有执行
}
}
for(int i = 0; i < cnt; i++) { //利用空格建立图
deg[i] = 0;
for(int j = 0; j < 5; j++) {
int nx = x[i] + dx[j]; int ny = y[i] + dy[j];
if(dataset[nx][ny] != '#') G[i][deg[i]++] = id[nx][ny];
}
}
//当小鬼2号不存在时，让2的地址指向无法移动的格子
if(n <= 2) { deg[cnt] = 1; G[cnt][0] = cnt; s[2] = t[2] = cnt++; }
//注意不要加else
if(n <= 1) { deg[cnt] = 1; G[cnt][0] = cnt; s[1] = t[1] = cnt++; }
memset(dist, -1, sizeof(dist));
printf("%d\n", bfs());
}
return 0;
}
UVA1343 迭代加深搜索 IDA*
这迭代加深搜索看的我一头雾水，总理不清迭代加深搜索与IDA*，A*的概念。在阅读了一下几篇博文后才有了一定的认识：
A* 算法详解 从红警讲开来
搜索进阶-迭代加深搜索
IDDFS（迭代加深搜索）基础题两则
以下是自己的一点理解:
A*: 用于求最短路径，在BFS的基础上优先遍历(离起点路程+预估的离终点的距离)最小的点。预估值可以用曼哈顿距离来，这个名字听起来好高端，说白了，就是横向距离格子数+纵向距离格子数。
迭代加深搜索(ID-DFS): 用BFS的思想来写DFS。首先深度优先搜索k层，若没有找到可行解，再深度优先搜索k+1层，直到找到可行解为止。因为深度有效到大递增，所以所以当搜索到结果时可以保证搜索深度是最小的。也因此IDDFS有时候比单纯的BFS要快。
IDA*: IDA*算法就是基于迭代加深的A*算法，倒过来讲也可以。就是IDDFS+乐观估计函数。
乐观估计函数: 从当前深度到找到最终的解“至少”还需要多少步，或者距离找到最终的解还需要至少扩展多少层。如果超出了当前限制的深度maxd，说明当前限制的最大深度下是不可能找到解的，直接退出。
代码是直接临摹的前人的，用来梳理思路。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
using namespace std;
const int MAXN = 24, LEN = 8;
int board[LEN][LEN - 1] = { {0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10} };
int check_order[] = {6, 7, 8, 11, 12, 15, 16, 17}, a[MAXN], maxd;
char order[30];
int unordered() {//计算达到目标所需变更的最少中心块儿数
int n1 = 0, n2 = 0, n3 = 0;
for (int i = 0; i < LEN; i++)
if (a[check_order[i]] == 1) n1++;
else if (a[check_order[i]] == 2) n2++;
else n3++;
return LEN - max(max(n1, n2), n3);
}
void rotate(int di) {
int t = a[board[di][0]];
for (int i = 1; i < LEN - 1; i++) a[board[di][i - 1]] = a[board[di][i]];
a[board[di][LEN - 2]] = t;
}
bool dfs(int d) {
int cnt = unordered();
if (!cnt) return true;
if (cnt + d > maxd) return false;
int temp[MAXN]; //保存a的状态
memcpy(temp, a, sizeof(a));
for (int i = 0; i < LEN; i++) {
rotate(i);
order[d] = i + 'A';
if (dfs(d + 1)) return true;
memcpy(a, temp, sizeof(a));//恢复a的状态
}
return false;
}
int main() {
while (scanf("%d", &a[0]) && a[0]!=0) {
for (int i = 1; i < MAXN; i++) scanf("%d", &a[i]);
if (!unordered()) { printf("No moves needed\n%d\n", a[6]); continue;}
for (maxd = 1;!dfs(0); maxd++);
for (int i = 0; i < maxd; i++) printf("%c", order[i]);
printf("\n%d\n", a[6]);
}
return 0;
}
2019/2/28
UVA12325 穷举
刷成就感用的小题，虽然在洛谷上是蓝色标签，但与前几个相比不值一提。
忘用long long卡了一次，忘用lld又卡一次，丢人进行时。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int main(){
long long t,n,s1,s2,v1,v2,temp,m,ans,now;
scanf("%lld",&t);
for(long long i=0;i<t;i++){
scanf("%lld%lld%lld%lld%lld",&n,&s1,&v1,&s2,&v2);
if(s2*v1<s1*v2){//int*int可能大于int，故用long long
swap(s1,s2);
swap(v1,v2);
}
ans=0;
for(long long i=0;i<s1;i++){
m=n-s2*i;
if(m<0) continue;
now=(m/s1)*v1+i*v2;
if(now>ans) ans=now;
}
printf("Case #%lld: %lld\n",i+1,ans);
}
return 0;
}
UVA11212 IDA*
这是我记录在案的第一道紫题。因为初学IDA*，不会使唤，所以先看了一遍前人的大体思路(UVA-11212)，然后自己实现了一下。在计算数组下标变更上卡了一会儿，主要是我算的太慢了，还怕算错，反反覆覆想了好几遍，这过程中隔壁的朋友还顺便向我问了个题，写到最后死活过不了测试。推倒DFS部分重来，再推倒重来，前前后后一晚上就搞完了这一个题，丢人++。
主要思路： IDA*的核心就是g() + h() < maxd，搞完这题后发现以前记得太死，只学了个形式没学到变通的思想。对于这个题来讲，如紫书所言，每次剪切最多产生三处连续，所以剪枝条件就是(还能遍历的层数 = 允许的最深层数 - 当前层数 ， 还能遍历的层数 * 3 > 未排序的数字个数)，具体实现看代码。
EXP1： 要冷静分析bug，戒骄戒躁。
EXP2： memcpy(目标，源头，长度)这个函数好使的很。既快又省事
EXP3： 指针的加减以它单位长度进行变更，太久没用差点忘了
感觉自己一番鏖战后又变强了，可以制服得了IDA*进而为我所用了，爽！！！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
using namespace std;
const int sot=sizeof(int);
int a[10];
int n;
bool isOrdered(){
for(int i=0;i<n-1;i++)
if(a[i]!=i+1) return false;
return true;
}
int unordered(){
int cnt=0;
for(int i=1;i<n;i++)
if(a[i]!=a[i-1]+1) cnt++;
return cnt;
}
bool dfs(int di,int maxd){
if((maxd-di)*3<unordered()) return false;
if(isOrdered()) return true;
int old[10],cut[10],least[10];
int p,cnt;
memcpy(old,a,sizeof(a));
for(int i=0;i<n;i++)
for(int j=i+1;j<=n;j++){
cnt=j-i;
memcpy(cut,a+i,sot*cnt);
memcpy(least,a,sot*i);
memcpy(least+i,a+j,sot*(n-j));
for(int k=0;k<=n-cnt;k++){
//紫书所讲的策略二，测试后果然是错误的
//if((k>0&&least[k-1]!=cut[0])&&(k<n-cnt&&least[k]!=cut[cnt-1])) continue;
memcpy(a,least,sot*k);
memcpy(a+k,cut,sot*cnt);
//memcpy(a+k+cnt,least,(n-cnt-k));//万恶之源，卡了我老长时间
memcpy(a+k+cnt,least+k,sot*(n-cnt-k));
if(dfs(di+1,maxd)) return true;
memcpy(a,old,sizeof(a));
}
}
return false;
}
int main(){
int kase=0;
while(scanf("%d",&n)&&n){
for(int i=0;i<n;i++) scanf("%d",&a[i]);
int maxd;
for(maxd=0;maxd<n;maxd++) if(dfs(0,maxd)) break;
printf("Case %d: %d\n",++kase,maxd);
}
return 0;
}
2019/3/1
UVA1374 IDA*
因为这题名为快速幂，我又不会，所以先去充了个电。一搜发现这东西原来就是一个函数，三分钟学会了。然后发现懂不懂快速幂并不影响做这个题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
38int pow(int a,int b){
int ans=1;
while(b){
if(b&1) ans*=a;
a*=a;
b>>=1;
}
return ans;
}
```
紫书已经把核心思路和算法指明了，想明白了后实现起来也很简单，一遍过。(好吧我其实下意识地看了眼洛谷的题解)
```cpp
using namespace std;
const int MAXN=1024;
int a[MAXN],n;
bool dfs(int di,int maxd,int maxnum){
if((maxnum<<(maxd-di))<n||di>maxd) return false;
if(a[di]==n) return true;
for(int i=di;i>=0;i--){
a[di+1]=a[di]+a[i];
if(dfs(di+1,maxd,max(a[i],a[di+1]))) return true;
a[di+1]=a[di]-a[i];
if(dfs(di+1,maxd,max(a[i],a[di+1]))) return true;
}
return false;
}
int main(){
while(~scanf("%d",&n)&&n){
int maxd;
a[0]=1;
for(maxd=0;maxd<20;maxd++) if(dfs(0,maxd,1)) break;
printf("%d\n",maxd);
}
return 0;
}