头像

闫睿


访客:175

离线:29天前



闫睿
2个月前

题目描述

请见原题

样例

input:30 40 10
output:26.033


图解

ACWING000.png

解题思路

假设已知s求c,通过相似模型可得c=ab/a+b ,然后移动两栋楼,知道找出合适的c为止(详见注释)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
double x,y,c;
double calc(double s)//求s函数 
{
    double a=sqrt(x*x-s*s);//勾股定理 
    double b=sqrt(y*y-s*s);

    return a*b/(a+b);
}
int main()
{

    cin>>x>>y>>c;

    double l=0,r=min(x,y);//l为两栋楼之间的最小值,r为最大值 

    while(r-l>1e-5)
    {
        double mid=(l+r)/2;
        if(calc(mid)>c) l=mid;//太近了 ,放的远一些 
        else r=mid; //太远了,放的近一些 
    }   
    printf("%.3lf\n",r);//保留三位小数输出 
    return 0;       
}//yr




闫睿
3个月前

题目描述

https://leetcode.com/problems/n-queens/description/

样例



方法

枚举N皇后的所有情况,在DFS过程中用剪枝函数排除(详见代码注释)

备注

本代码不能直接拿去粘贴

C++ 代码

//左上角原点(0,0);已经放好的皇后(i,j);下一个皇后(r,c) 
#include<bits/stdc++.h>
using namespace std;
int n,cnt=0;
int col[12]={0};
/* 
皇后剪枝规则
1.不同行
2.不同列
3.斜对角 abs(col[i]-c)==abs(i-r) 
*/ 
bool check(int c,int r)//剪枝函数   
{  
    for(int i=0;i<r;i++) 
        if(col[i]==c||(abs(col[i]-c)==abs(i-r)))//剪枝判断 
            return false;
    return true;
}
void DFS(int r)//轮到第r行 
{
    if(r==n)//递归返回 
    {
        cnt++;//统计个数 
        return;
    }
    for(int i=0;i<n;i++)
        if(check(i,r))//剪枝 
        {
            col[r]=i;//在第i行第c列放皇后 
            DFS(r+1);//接着来 
        }
}
int main(){
    int ans[12]={0};//答案数组 
    for(n=1;n<=10;n++)
    {
        memset(col,0,sizeof(col));//干完了初始化 
        cnt=0;
        DFS(0);
        ans[n]=cnt;//然后接着干...... 
    }
    while(cin>>n)
    {
        if(n==0)
            return 0;//干到0为止 
        cout<<ans[n]<<endl;
    }
    return 0;
}//yr