部分转载自：http://blog.csdn.net/idealism_xxm/article/details/50937688
还有：http://blog.csdn.net/summonlight/article/details/61427968
题目连接：http://www.doc88.com/p-7886959785035.html
3.填格子 （DFS）
有一个含有10个格子的图形，现用0~9填充，连续的数不能填充在相邻的格子中（包
括对角线相邻），问有多少种填充方法？
我认为每个数字只能填一次，算出来是：1580
用的方法是全排列，可以用库函数next_permutation解决。
代码如下：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int num[10] = {}, cnt = 0, maps[9][9] = {};
int nextr[4] = {0, -1, -1, -1};
int nextc[4] = {-1, -1, 0, 1};
bool check(int row, int column, int number)
{
for(int i = 0; i < 4; i++)
{
int rr = row + nextr[i];
int cc = column + nextc[i];
if(abs(maps[rr][cc] - number) <= 1) return false;
}
return true;
}
void dfs(int num[])
{
int cc = 1, rr = 1, i;
for(i = 0; i <= 9; i++)
{
cc++;
if(cc > 4)
{
rr++;
cc = 1;
}
maps[rr][cc] = num[i];
if(!check(rr, cc, num[i]))
{
break;
}
}
if(i > 9) cnt++;
}
int main(void)
{
long long counter = 0;
for(int i = 0; i < 7; i++)
{
for(int j = 0; j < 7; j++)
{
maps[i][j] = -6;
}
}
for(int i = 0; i <= 9; i++)
{
num[i] = i;
}
do{
dfs(num);
counter++;
}while(next_permutation(num, num + 10));
cout << cnt << endl;
return 0;
}
4.就是快排代码
5. x&(x + 1)
模拟一下就能出结果了
6.
答案：64
这里有个250秒出结果的代码：
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int num[15] = {}, cnt = 0;
void dfs(int num[])
{
if(num[1] + num[2] == num[3])
{
if(num[4] - num[5] == num[6])
{
if(num[7] * num[8] == num[9])
{
if(num[10] == num[11] * num[12])
{
cnt++;
}
}
}
}
}
int main()
{
for(int i = 1; i <= 13; i++)
{
num[i] = i;
}
do{
dfs(num);
}while(next_permutation(num + 1, num + 14));
printf("%d\n", cnt);
return 0;
}
改进后的代码：（总之就是要仔细），优化的方面：每个等式的结果是不用枚举的，
只要判断能否算出结果和是否有重复结果即可。该代码可一秒算出结果。
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int num[15] = {}, cnt = 0;
bool book[15] = {};
void dfs(int step)
{
if(step == 3)
{
if(num[1] % num[2] == 0 && num[1] > num[2] && !book[num[1] / num[2]])
{
book[num[1] / num[2]] = true;
dfs(4);
book[num[1] / num[2]] = false;
}
return;
}
if(step == 6)
{
if(num[4] * num[5] <= 13 && !book[num[4] * num[5]])
{
book[num[4] * num[5]] = true;
dfs(7);
book[num[4] * num[5]] = false;
}
return;
}
if(step == 9)
{
if(num[7] + num[8] <= 13 && !book[num[7] + num[8]])
{
book[num[7] + num[8]] = true;
dfs(10);
book[num[7] + num[8]] = false;
}
return;
}
if(step == 12)
{
if(num[10] + num[11] <= 13 && !book[num[10]+ num[11]])
{
cnt++;
}
return;
}
for(int i = 1; i <= 13; i++)
{
if(!book[i])
{
num[step] = i;
book[i] = true;
//if(step == 3 || step == 6 || step == 9 || step == 12) printf("%d\n", num[i]);
dfs(step + 1);
book[i] = false;
}
}
}
int main()
{
dfs(1);
cout << cnt << endl;
return 0;
}
7. 深度优先搜索（有点像走迷宫）
以邮票的每一个格子为起点列举不同的走法（每次走的都是相邻的格子），并记录所
走过的格子，走到第五个格子就终止本次“行走”，然后对那五个格子的坐标进行从
小到大排序，再跟之前记录的走法进行配对，若没有重复，则记录该走法，最终得出结果。
错误代码（我都不知道为啥会同一个格子走两次，醉了，咋改都不对）：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Node
{
pair<int, int>rc[5];
bool operator == (const Node &a) const
{
for(int i = 0; i < 5; i++)
{
if(rc[i].first != a.rc[i].first || rc[i].second != a.rc[i].second)
return false;
}
return true;
}
};
vector<Node>book;
int nextc[4] = {-1, 0, 1, 0}, ans = 0;
int nextr[4] = {0, -1, 0, 1};
bool vis[5][5] = {};
bool check1(int a, int b)
{
if(0 <= a && a < 3 && 0 <= b && b < 4) return true;
else return false;
}
bool check2(Node a)
{
for(int i = 0; i < book.size(); i++)
{
int j;
for(j = 0; j < 5; j++)
{
if(book[i].rc[j].first != a.rc[j].first || book[i].rc[j].second != a.rc[j].second)
{
break;
}
if(j > 0 && (a.rc[j].first == a.rc[j - 1].first) && (a.rc[j].second == a.rc[j - 1].second))
return false;
}
if(j >= 5) return false;
}
return true;
}
void dfs(Node st, int step)
{
if(step == 5)
{
Node rep;
for(int i = 0; i < 5; i++)
{
rep.rc[i].first = st.rc[i].first;
rep.rc[i].second = st.rc[i].second;
}
sort(rep.rc, rep.rc + 5);
if(check2(rep))
{
ans++;
cout << ans << endl;
for(int i = 0; i < 5; i++)
{
cout << st.rc[i].first << " " << st.rc[i].second << " ";
}
cout << endl;
book.push_back(rep);
}
}
for(int j = 0; j < 4; j++)
{
int rr = st.rc[step - 1].first + nextr[j];
int cc = st.rc[step - 1].second + nextc[j];
//cout << "one " << step << " " << rr << " "<< cc << endl;
if(check1(rr, cc) && !vis[rr][cc])
{
if(rr == st.rc[step - 1].first && cc == st.rc[step - 1].second)
cout << "**** " << rr << " " << cc << endl;
//cout << "two " << step << " " << rr << " " << cc << endl;
vis[rr][cc] = true;
st.rc[step].first = rr;
st.rc[step].second = cc;
dfs(st, step + 1);
vis[rr][cc] = false;
st.rc[step].first = -1;
st.rc[step].second = -1;
}
}
}
int main()
{
Node st;
for(int i = 0; i < 3; i++)
{
st.rc[0].first = i;
for(int j = 0; j < 4; j++)
{
//cout << i << " " << j << endl;
st.rc[0].second = j;
vis[i][j] = true;
dfs(st, 1);
vis[i][j] = false;
}
}
printf("#####\n");
cout << ans << endl;
int nn = 0;
for(int i = 0; i < book.size(); i++)
{
for(int j = 0; j < 5; j++)
{
if(j > 0 && book[i].rc[j].first == book[i].rc[j - 1].first && book[i].rc[j].second == book[i].rc[j - 1].second)
{
cout << "***" << endl;
nn--;
}
cout << book[i].rc[j].first << " " << book[i].rc[j].second << " ";
}
nn++;
cout << endl;
}
cout << nn << endl;
}
正确代码：
#include<cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
///num数组负责记录第1~5步的格子，rc数组负责记录12个格子的坐标，cnt负责记录步法种数
int num[10] = {}, rc[13][3] = {}, cnt = 0;
///book数组负责记录格子是否被走过
bool book[6][6] = {};
int cal(int xx, int yy)
{
if(!book[xx][yy]) return 0;
book[xx][yy] = 0;
return 1 + cal(xx - 1, yy) + cal(xx + 1, yy) + cal(xx, yy - 1) + cal(xx, yy + 1);
}
void dfs(int number, int step)
{
if(step == 5)
{
///memset要放最前面
memset(book, false, sizeof(book));
for(int i = 0; i < 5; i++)
{
book[rc[num[i]][0]][rc[num[i]][1]] = true;
}
if(cal(rc[number][0], rc[number][1]) == 5) cnt++;
return;///千万别忘了这个
}
for(int i = number + 1; i <= 12; i++)
{
num[step] = i;
dfs(i, step + 1);
num[step] = -1;
}
}
int main(void)
{
///i，j定义初始为 1 是为了cal函数的 xx-1 和 yy-1
for(int i = 1, n = 1; i <= 3; i++)
{
for(int j = 1; j <= 4; j++, n++)
{
rc[n][0] = i;
rc[n][1] = j;
}
}
dfs(0, 0);
cout << cnt << endl;
return 0;
}
8.emmm，就是优化的暴力枚举了，主要优化枚举时的下限和上限，不要怕超时。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int a[5];
void cal(int num)
{
int maxx[5];
maxx[1] = (int)(sqrt((double)(num) / 4)) + 1;
for(a[1] = 0; a[1] <= maxx[1]; a[1]++)
{
int max1 = num - a[1]*a[1];
if(max1 > 0)
{
maxx[2] = (int)(sqrt((double)(max1) / 3)) + 1;
for(a[2] = a[1]; a[2] <= maxx[2]; a[2]++)
{
int max2 = max1 - a[2]*a[2];
if(max2 > 0)
{
maxx[3] = (int)(sqrt((double)(max2) / 2)) + 1;
for(a[3] = a[2]; a[3] <= maxx[3]; a[3]++)
{
int k = max2 - a[3]*a[3];
a[4] = (int)sqrt((double)(k));
if(k > 0 && k == a[4] * a[4] && a[4] >= a[3])
{
return;
}
}
}
}
}
}
}
int main()
{
int num;
while(cin >> num)
{
cal(num);
cout << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << endl;
}
}