第五题，谢谢

来源：蜘蛛抓取(WebSpider) 时间：2017-10-03 16:08 标签： 谢谢你半命题作文
欢迎加入我们，一同切磋技术。 &
用户名： &&&
密　码： &
共有 1892 人关注过本帖
标题：蓝桥杯B组决赛第五题,现求好算法或帮我改进，谢谢
等　级：业余侠客
帖　子：106
专家分：202
结帖率：100%
&&已结贴√
&&问题点数：20&&回复次数：9&&&
蓝桥杯B组决赛第五题,现求好算法或帮我改进，谢谢
标题：格子刷油漆
X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如图所示），现需要把这些格子刷上保护漆。
你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）
&&& 比如：a d b c e f 就是合格的刷漆顺序。
&&& c e f d a b 是另一种合适的方案。
&&& 当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对
(十亿零七) 取模。
&&& 输入数据为一个正整数（不大于1000）
&&& 输出数据为一个正整数。
用户输入：
程序应该输出：
用户输入：
程序应该输出：
用户输入：
程序应该输出：
资源约定：
峰值内存消耗 & 64M
CPU消耗&&& 1000ms
附件: 您没有浏览附件的权限，请
搜索更多相关主题的帖子:
等　级：业余侠客
帖　子：106
专家分：202
我的程序是：
#include &stdio.h&
#include &math.h&
#include &time.h&
int sum=0,a[2][1000];
int panduan()
&&& int i,j;
&&& for(i=0;i&2;i++)
&&& for(j=0;j&N;j++)
&&& if(a[i][j]!=1)
&&& return 0;
&&& return 1;
void fun(int x,int y,int result,int dq)
&&& a[x][y]=1;
&&& if(dq==result)
&&& if(panduan())
&&&&&&&&sum++;
&&& if(x+1&2&&a[x+1][y]==0)
&&&&&&&&fun(x+1,y,result,dq+1);
&&&&&&&&a[x+1][y]=0;
&&& if(x-1&=0&&a[x-1][y]==0)
&&&&&&&&fun(x-1,y,result,dq+1);
&&&&&&&&a[x-1][y]=0;
&&& if(y+1&N&&a[x][y+1]==0)
&&&&&&&&fun(x,y+1,result,dq+1);
&&&&&&&&a[x][y+1]=0;
&&& if(y-1&=0&&a[x][y-1]==0)
&&&&&&&&fun(x,y-1,result,dq+1);
&&&&&&&&a[x][y-1]=0;
&&& if(x+1&2&&y-1&=0&&a[x+1][y-1]==0)
&&&&&&&&fun(x+1,y-1,result,dq+1);
&&&&&&&&a[x+1][y-1]=0;
&&& if(x+1&2&&y+1&N&&a[x+1][y+1]==0)
&&&&&&&&fun(x+1,y+1,result,dq+1);
&&&&&&&&a[x+1][y+1]=0;
&&& if(x-1&=0&&y-1&=0&&a[x-1][y-1]==0)
&&&&&&&&fun(x-1,y-1,result,dq+1);
&&&&&&&&a[x-1][y-1]=0;
&&& if(x-1&=0&&y+1&N&&a[x-1][y+1]==0)
&&&&&&&&fun(x-1,y+1,result,dq+1);
&&&&&&&&a[x-1][y+1]=0;
int main()
&&& int i,j,k;
&&& double start,
&&& scanf(&%d&,&N);
&&& start=time(NULL);
&&& k=2*N;
&&& for(i=0;i&2;i++)
&&& for(j=0;j&N;j++)
&&&&&&&&fun(i,j,k,1);
&&&&&&&&a[i][j]=0;
&&& printf(&%d&,sum);
&&& end=time(NULL);
&&& printf(&\n%lf&,end-start);
加油加油！
等　级：业余侠客
帖　子：106
专家分：202
我这个程序当N&13基本就算不出。
高手来看看有什么好的程序或建议给我。
加油加油！
等　级：小飞侠
帖　子：660
专家分：2400
明显的递推，不过递推公式可能比较复杂，我推导一下
等　级：业余侠客
帖　子：106
专家分：202
回复 4楼 czz5242199
我用的是递归，去遍历每种可能，不过这样的效果不尽人意啊！
加油加油！
等　级：小飞侠
帖　子：660
专家分：2400
&&得分:20&
递推公式比较复杂，不当面说还真有点难说清，我简略说下
一共有两个递推数组：
首先设Dn表示从左边或者右边的某个角出发，然后走遍所有格子回到同一列有多少种方法。
明显D1=2,Dn=2*Dn-1
所以Dn=2^n
然后设An表示从某个角出发，走遍所有格子（不一定回到同一列）有多少种方法。
An=Dn-1+2*An-1+4*An-2
这个递推公式就用统计原理分析出来，分别对应三种不同的走法
Dn-1对应从这个角走到下一列，然后走遍所有格子回到下一列，再回到这列的走法
2*An-1表示直接走到这列的另一个角，然后再走其他的地方
4*An-1表示走对角线方法走遍前两列，然后走其他的地方
这样答案如果从四个角出发，总数就是4*An
然后分析从某一列开始，假设第i列(1&i&n)
则总数为2*(2*Di-1*An-i+2*Dn-i*Ai-1)
对i从2到n-1全部加和，得到这部分答案
两部分答案加起来，就是总数，经测试无误
[ 本帖最后由 czz5242199 于
22:56 编辑 ]
等　级：小飞侠
帖　子：660
专家分：2400
程序代码：#include &stdio.h&
long long a[<font color=#0],d[<font color=#0],
int i,j,k,n;
int main()
&&& d[<font color=#]=<font color=#;
&&& for (i=<font color=#; i&<font color=#0; i++) d[i]=((long long)d[i-<font color=#]+d[i-<font color=#])%M;
&&& a[<font color=#]=<font color=#; a[<font color=#]=<font color=#;
&&& for (i=<font color=#; i&<font color=#0; i++) a[i]=((long long)d[i-<font color=#]+<font color=#*a[i-<font color=#]+<font color=#*a[i-<font color=#])%M;
&&& while (scanf(&%d&,&n))
&&&&&&&&& long long ans=a[n]*<font color=#;
&&&&&&&&& for (i=<font color=#; i&n; i++)
&&&&&&&&&&&&&&ans=(ans+<font color=#*d[i-<font color=#]*a[n-i]+<font color=#*d[n-i]*a[i-<font color=#])%M;
&&&&&&&&& printf(&%lld\n&,ans);
来　自：南方
等　级：论坛游民
帖　子：21
专家分：20
等　级：业余侠客
帖　子：106
专家分：202
回复 6楼 czz5242199
你的分析，我还要慢慢消化。你的分析能力不错。
加油加油！
等　级：业余侠客
帖　子：106
专家分：202
怎么没有其他人在发表一下看法啊！
加油加油！
版权所有，并保留所有权利。
Powered by , Processed in 0.057103 second(s), 7 queries.
Copyright&, BCCN.NET, All Rights Reserved

我要回帖

更多关于 谢谢你半命题作文 的文章

 

随机推荐