今日题目难度较大，三道题均来自洛谷，最后一题有些问题还没找出来，大概晚上更新

1.马的遍历

 思路：DFS做法

#includeusing namespace std;int n,m,x,y;int dx[8]={2,-2,2,-2,-1,1,-1,1};int dy[8]={1,1,-1,-1,2,2,-2,-2};// 标记马的行走方向 int ans[401][401];//每个点的步数 int check(int a,int b)//检查是否越界 {    if(an||bm) return 0;    return 1;}void dfs(int a,int b,int sum)//a和b是当前搜到的坐标，sum为步数 {    int nx,ny;    ans[a][b]=sum;//将答案标记     for(int i=0;i<8;i++)    //搜索八个方向 { nx=a+dx[i]; ny=b+dy[i]; //扩展新点  if(check(nx,ny)&&(sum+1>n>>m;    cin>>x>>y;    memset(ans,-1,sizeof(ans));//初始化     dfs(x,y,0);//搜索     for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)     printf("%-5d",ans[i][j]); cout<<endl;    }//输出     return 0;}

 2.切绳子

思路： 二分中比较坑的一题，可以先把小数*100化为整数比较简单，二分时mid=(f+r+1)/2;千万记住+1，否则会炸，二分移动端点条件 ans和k的关系

if(ans<k)r=mid-1; else l=mid;#include#include#include#include#include#include#includeusing namespace std;long long n,k,s[10005],ans,l,r,sum,mid;double s1[10005],t;int main(){    cin>>n>>k;    for(int i=1;i>s1[i],s[i]=s1[i]*100,ans=ans+s[i];    l=0,r=ans/k+1;    while(l<r)    { mid=(l+r+1)/2; ans=0; for(int i=1;i<=n;i++)ans=ans+s[i]/mid; if(ans<k)r=mid-1; else l=mid;    }    t=r*1.00/100;    printf("%.2lf\n",t);    return 0;}

 3.导弹拦截（待更新）

 思路：这道题就是要求一个最长单调不升子序列和一个最长单调上升子序列。

//问题主要是求解最长上升子序列#include#includeusing namespace std;int main(){int m;cin>>m;int *p = new int[m];    int *dp = new int[m];for(int i = 0; i >p[i]; dp[i] = 1;}for(int i = 0; i < m; i ++)    { for(int j = 0; j  p[j])     {  dp[i] = max(dp[j] + 1, dp[i]);     } }    }    int max = dp[0];    for(int i = 0; i < m; i ++)    { if(max < dp[i]) {     max = dp[i]; }    }    cout<<max;}