1、六角填数
运用stl 中的函数next_permutation(a,a+n)
题意：
7：六角填数
如图【1.png】所示六角形中，填入1~12的数字。
使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
请通过浏览器提交答案，不要填写多余的内容。
答案 10
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[12]={1,2,3,4,5,6,7,8,9,10,11,12};
bool fun()
{
if(a[0]+a[2]+a[5]+a[6]==26)
{
if(a[6]+a[7]+a[8]+a[10]==26)
{
if(a[0]+a[3]+a[9]+a[10]==26)
{
if(a[1]+a[2]+a[3]+a[4]==26)
{
if(a[1]+a[5]+a[7]+a[11]==26)
{
if(a[4]+a[9]+a[8]+a[11]==26)
{
return true;
}
}
}
}
}
}
return false;
}
int main()
{
// a[12]={1,2,3,4,5,6,7,8,9,10,11,12};
do{
if(a[0]==1&&a[1]==8&&a[11]==3)
{
if(fun())
{
cout<<a[5]<<endl;
break;
}
}
}while(next_permutation(a,a+12));
return 0;
}
2、方格填数
运用全排列，不过要注意条件不要写错了。
答案 1580
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[10]={0,1,2,3,4,5,6,7,8,9};
bool fun()
{
if(abs(a[0]-a[1])==1||abs(a[0]-a[4])==1||abs(a[0]-a[5])==1||abs(a[0]-a[3])==1)
return false;
if(abs(a[4]-a[1])==1||abs(a[1]-a[5])==1||abs(a[1]-a[2])==1||abs(a[1]-a[6])==1)
return false;
if(abs(a[2]-a[6])==1||abs(a[2]-a[5])==1)
return false;
if(abs(a[3]-a[7])==1||abs(a[3]-a[4])==1||abs(a[3]-a[8])==1)
return false;
if(abs(a[4]-a[7])==1||abs(a[4]-a[8])==1||abs(a[4]-a[9])==1||abs(a[4]-a[5])==1)
return false;
if(abs(a[5]-a[8])==1||abs(a[5]-a[9])==1||abs(a[6]-a[5])==1)
return false;
if(abs(a[6]-a[9])==1)
return false;
if(abs(a[7]-a[8])==1||abs(a[8]-a[9])==1)
return false;
return true;
}
int main()
{
int ans=0;
// a[12]={1,2,3,4,5,6,7,8,9,10};
do{
if(fun())
{
ans++;
}
}while(next_permutation(a,a+10));
cout<<ans;
return 0;
}
3、减邮票
正确答案是116
给一个错误的解法吧
错误答案为：222
错误原因，排列出C 12 5 的组合后，判断相连出了问题，错误的判断是，只要每一个有一个相连即可，其实并不是，全部都有相连 可能存在两个连通块。啦啦啦，纸上觉来终觉浅觉，绝知此事要躬行。老师讲的就是这种方法，我不敲一下，真的以为是对的。放个错解，以示教训吧。解是错的，但是运用组合数来找解的思路还是棒棒哒，一下把解的范围缩小了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct node{
int x;
int y;
};
int i,j,k,m,l;
node num[13];
bool fun()
{
if((abs(num[i].x-num[j].x)+abs(num[i].y-num[j].y))==1||(abs(num[i].x-num[k].x)+abs(num[i].y-num[k].y))==1||(abs(num[i].x-num[m].x)+abs(num[i].y-num[m].y))==1||(abs(num[i].x-num[l].x)+abs(num[i].y-num[l].y))==1)
{
if((abs(num[i].x-num[j].x)+abs(num[i].y-num[j].y))==1||(abs(num[j].x-num[k].x)+abs(num[j].y-num[k].y))==1||(abs(num[j].x-num[m].x)+abs(num[j].y-num[m].y))==1||(abs(num[j].x-num[l].x)+abs(num[j].y-num[l].y))==1)
{
if((abs(num[m].x-num[j].x)+abs(num[m].y-num[j].y))==1||(abs(num[m].x-num[k].x)+abs(num[m].y-num[k].y))==1||(abs(num[i].x-num[m].x)+abs(num[i].y-num[m].y))==1||(abs(num[m].x-num[l].x)+abs(num[m].y-num[l].y))==1)
{
if((abs(num[k].x-num[j].x)+abs(num[k].y-num[j].y))==1||(abs(num[i].x-num[k].x)+abs(num[i].y-num[k].y))==1||(abs(num[k].x-num[m].x)+abs(num[k].y-num[m].y))==1||(abs(num[k].x-num[l].x)+abs(num[k].y-num[l].y))==1)
{
if((abs(num[l].x-num[j].x)+abs(num[l].y-num[j].y))==1||(abs(num[i].x-num[l].x)+abs(num[i].y-num[l].y))==1||(abs(num[l].x-num[m].x)+abs(num[l].y-num[m].y))==1||(abs(num[k].x-num[l].x)+abs(num[k].y-num[l].y))==1)
{
cout<<i<<" "<<j<<" "<<m<<" "<<k<<" "<<l<<endl;
return true;
}
}
}
}
}
return false;
}
int main()
{
num[1].x=1;
num[1].y=1;
num[2].x=1;
num[2].y=2;
num[3].y=3;
num[3].x=1;
num[4].y=4;
num[4].x=1;
num[5].y=1;
num[5].x=2;
num[6].y=2;
num[6].x=2;
num[7].y=3;
num[7].x=2;
num[8].y=4;
num[8].x=2;
num[9].y=1;
num[9].x=3;
num[10].y=2;
num[10].x=3;
num[11].y=3;
num[11].x=3;
num[12].y=4;
num[12].x=3;
int ans=0;
for(i=1;i<9;i++)
{
for(j=i+1;j<10;j++)
{
for(m=j+1;m<11;m++)
{
for(k=m+1;k<12;k++)
{
for(l=k+1;l<13;l++)
{
if(fun())
{
ans++;
}
}
}
}
}
}
cout<<ans;
return 0;
}
再分享一个错解吧：哈哈，又搞错了
3x4的矩阵中一笔画完的 5个连续的图案一共有多少种
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int i,j;
int mapp[3][4];
int ans=0;
void dfs(int a,int b,int n)// x,y,几步
{
if(n==5)
{
ans++;
}
if(a+1<3)
{
dfs(a+1,b,n+1);
}
if(b+1<4)
{
dfs(a,b+1,n+1);
}
}
int main()
{
for(i=0;i<3;i++)
{
for(j=0;j<4;j++)
{
dfs(i,j,1);
}
}
cout<<ans;
return 0;
}
正解：运用深搜，判断连通块
终于正确了，参考了别人的方法，为了避免 一行的最后一个和下一行的第一个在搜索的时候判断连续，把图做了一下处理
【1，2，3，4 ，5，6，7，8， 9， 10，11，12】
【1，2，3，4， 6，7，8，9， 11，12，13，14】
用 -5 +5 表示上下 -1 +1 表示左右，比用0 1 矩阵存储彼此的相邻关系简单许多
博客地址
http://blog.csdn.net/u014552756/article/details/50946197
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int ans=0;
int a[5];
int visited[5];
int num[12]={1,2,3,4,6,7,8,9,11,12,13,14};
int d[4]={-1,1,5,-5};
int i,j,k,l,m;
void dfs(int n)//判断这五个数是不是一个连通块
{
for(int i=0;i<4;i++)//
{
int t=a[n]+d[i];
if(t>14||t<1||t==5||t==10)
continue;
for(int j=0;j<5;j++)
{
if(visited[j]!=1&&a[j]==t)
{
visited[j]=1;
dfs(j);
}
}
}
}
int main()
{
for(i=0;i<8;i++)
{
for(j=i+1;j<9;j++)
{
for(k=j+1;k<10;k++)
{
for(l=k+1;l<11;l++)
{
for(m=l+1;m<12;m++)
{
a[0]=num[i];
a[1]=num[j];
a[2]=num[k];
a[3]=num[l];
a[4]=num[m];
memset(visited,0,sizeof(visited));
visited[0]=1;
dfs(0);
int f=1;
for(int i=0;i<5;i++)
{
if(visited[i]==0)
{
f=0;
}
}
if(f)
ans++;
}
}
}
}
}
cout<<ans;
return 0;
}
网友评论