素数环问题和滑雪
DongWeiYi564350 · · 个人记录
今天给大家讲一讲素数环问题和滑雪问题
其实这两个题我在考试时是唯二没有思路的题目，怪尴尬的。
咱先看素数环问题哈！
其实素数环问题在洛谷上的兄弟们还挺多的，（就是有很多类似的题目），但是他们都是同一个家族的。大致的问题基本上都是在
让你算出1到n个数摆成一个环后使相邻的两个数的和为素数。
偶尔会给你加加难度之类的，不过大致都是这样的。
什么是素数呢？
素数又叫质数（prime number），有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
好了！理解了题目的意思咱们来解题吧！
不过因为我手上没有洛谷上的具体的题目，所以我就以自己的想法来写了一个1-20的素数环，大家可以参考参考，不足的地方请指出来。谢谢！ 毕竟我对于素数环掌握的还不是很好，还要加油，回去后我还要听听课。大佬还是很多的.....
下面是代码加解析（是回溯算法哦！）：
#include<bits/stdc++.h>
using namespace std;
int a[21],k,sum,num=1;
bool b[21]={0};
bool p(int s){//判断素数
for(int i=2;i<=sqrt(s);i++)
if(s%i==0) return 0;
return 1;
}
void print()//输出，注意格式
{
for(int i=1;i<20;i++)
printf("%d",a[i]);
printf("%d\n",a[20]);
}
int search(int r){
for(int i=1;i<=20;i++)//美剧1-20 20个待填写的数
if(!b[i]&&p(i+a[r-1]))//如果没有被使用并且和上一个数之和为素数
{
a[r]=i;
b[i]=1;//记录并标记
if(r==20&&p(a[1]+a[20]))
print();//如果填完20个数且第一个数与最后一个数之和为素数（连成环） ，便输出
else search(r+1);
b[i]=0;//回溯，作相反操作（a[r]的值会覆盖，可不清0）
}
}
int main(){
search(1);
}以上就是素数环问题啦
接下来我们来看看滑雪问题。大家可以在洛谷主页搜索P1434就可以看到原题啦！
题目虽然说的是输出区域中最长滑坡的长度。
但我们还是要先去求最长的那个滑坡才能知道他的长度。
很明显，25-24-23-22......-2-1这条路是最长的那条路了。长度自然就是25啦，但是！但是！电脑没这么聪明，需要我们去帮他。
建议大家去用记忆化搜索的，不过有更好的办法就在好不过了。
代码如下，加了解析（记忆化搜索）：
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1};//可以向上，向下，向左，向右
int dy[4]={1,-1,0,0};//这个和上面的那个一样
int n,m,a[201][201],s[201][201],ans;
bool use[201][201];
int dfs(int x,int y){
if(s[x][y])return s[x][y];//记忆化搜索
s[x][y]=1;
for(int i=0;i<4;i++)
{ int xx=dx[i]+x;
int yy=dy[i]+y;//四个方向
if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]){
dfs(xx,yy);
s[x][y]=max(s[x][y],s[xx][yy]+1);//取最大的那个值
}
}
return s[x][y];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)//找从每个出发的最长距离
for(int j=1;j<=m;j++)
ans=max(ans,dfs(i,j));//取最大值
printf("%d",ans);
return 0;//终于结束了
}很高兴为大家讲解题目，咱们下次再见bye~