头像

Conan_2009




离线:5小时前



开始上课!

首先我们需要理解题目。

题目的意思就是:两栋楼之间有两个楼梯,长度为x和y。已知两个楼梯交点离地面的高度,求两栋楼之间的距离。

首先我们可以利用算法标签中的“二分”。

(这里 用一下 zpiceberg 的图))
8214_c54e733e71-QQ20200330-000954@2x.png

下面我就来依着这张图讲解这道题。

首先我们得找出二分的方法。

yxc的讲解视频中,有这么一个思路:

两栋楼之间,架着长度为x的梯子的那栋楼,
可以看成一个以长度为x的梯子为斜边、
以a高的墙为一条直角边的直角三角形.
那么在这个三角形之间,
又有一个一条直角边为c的直角三角形
。另一边也同理
(另一边也可以构出一个以长度为y的梯子为斜边
、以b高的墙为一条直角边的直角三角形,与一个一条直角边为c的相似直角三角形)。
这两个三角形很容易看出是一组相似三角形。
因为相似三角形每条边的比值都是一样的,
然后我们再将下面以c为一条直角边的底边设为n
(另一边的以c为一条直角边的直角三角形的底边为m)
,那么就有:

a/c=n/s
b/c=s/m

又通过两条以c为一条直角边的直角三角形的底边
相加就是s(m+n=s),可以得到:

n=s*c/a
m=s*c/b

上面两个方程联立m+n=s这个方程后,可以得出:

(s*c/a)+(s*c/b)=s

两边同时除以s:

a/c+b/c=1

转化:

1/a+1/b=1/c
最后得出:c=a*b/(a+b)
得出最后推导算式后
,我们可以选择二分计算s来计算如果当前两栋
楼之间长度为s时,c应该是多少?
然后判断此时的c是大于给定的c,
还是小于给定的c,通过判断结果来调整
二分的双指针。

既然有了图文并茂,应该都会做了吧……

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
double x,y,c;
double calc(double 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);
    while(r-l>1e-5){
        double mid=(l+r)/2;
        if(calc(mid)>c) l=mid;
        else r=mid;
    }
    printf("%.3lf",r);
    return 0;
}



开始讲课!

首先我们通过题目可以知道,有两个人在出数,每个人只能出5,10,15,20中的一个数。哪个人的数字大,那个人就获得两数之差这么多的分数。

当然,他也有反例:果一个人说的 20,但另一个说的是 5 或 10,则说 20 的这个人不得分,另一个人得 10 分。

所以我们只需要进行一个循环,然后枚举,这道题就搞定了!

代码时刻

#include <bits/stdc++.h>
using namespace std;
int k,aa,bb;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>k;
    while(k--){
        int a,b;
        cin>>a>>b;
        if((a==20&&(b==5||b==10))||(b==20&&(a==5||a==10))){
            if(a==20&&(b==5||b==10))
                bb+=10;
            if(b==20&&(a==5||a==10))
                aa+=10;
            continue;
        }
        if(a>=b)
            aa+=a-b;
        if(b>=a)
            bb+=b-a;
    }
    cout<<aa<<' '<<bb;
    return 0;
}


活动打卡代码 AcWing 1508. 划拳

#include <bits/stdc++.h>
using namespace std;
int k,aa,bb;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>k;
    while(k--){
        int a,b;
        cin>>a>>b;
        if((a==20&&(b==5||b==10))||(b==20&&(a==5||a==10))){
            if(a==20&&(b==5||b==10))
                bb+=10;
            if(b==20&&(a==5||a==10))
                aa+=10;
            continue;
        }
        if(a>=b)
            aa+=a-b;
        if(b>=a)
            bb+=b-a;
    }
    cout<<aa<<' '<<bb;
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
double n;
double lf(double x){return x*x*x;}
int main(){
    cin>>n;
    double l=-10000,r=10000;
    while(r-l>=1e-7){
        double mid=(l+r)/2;
        if(lf(mid)>=n) r=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(6)<<l;
    return 0;
}


活动打卡代码 AcWing 789. 数的范围

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,q,a[1000000];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    while(q--){
        int k;
        scanf("%d",&k);
        int l=0,r=n-1,mid=0;
        while(l<r){
            mid=(l+r)/2;
            if(a[mid]<k) l=mid+1;
            else r=mid;
        }
        if(a[l]!=k){
            printf("-1 -1\n");
            continue;
        }
        int l1=1,r1=n;
        while(l1+1<r1){
            mid=(l1+r1)/2;
            if(a[mid]<=k) l1=mid;
            else r1=mid;
        }
        cout<<l<<' '<<l1<<'\n';
    }
    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
long long n,a[1000000],tmp[1000000],res;
void merge_sort(long long q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else res+=mid-i+1,tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    merge_sort(a,1,n);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 787. 归并排序

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000],tmp[1000000];
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    merge_sort(a,1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000],k;
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[(l+r)/2];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    quick_sort(a,1,n);
    cout<<a[k];
    return 0;
}


活动打卡代码 AcWing 785. 快速排序

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000];
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    quick_sort(a,1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<' ';
    return 0;
}



#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> Pair; // 值与下标 
const int N=100010;
int n,m,query;
int h[N],e[N<<1],ne[N<<1],idx; // 邻接表 
int dist[N][2]; // 长度 
Pair q[N*2]; // 队列 
void add(int a,int b){ // 邻接表加边
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(){ // 预处理(BFS) 
    memset(dist,0x3f,sizeof(dist)); // 初距离始化为正无穷 
    int hh=0,tt=0;
    q[0]={1,0},dist[1][0]=0; // 初始化队列起点 
    while(hh<=tt){ // 遍历 
        Pair t=q[hh++];
        int ver=t.first,type=t.second; // ver与type为当前点编号
        for(int i=h[ver];~i;i=ne[i]){ // 遍历邻接表表邻边 
            int j=e[i]; // 取出邻边编号 
            if(dist[j][type^1]>dist[ver][type]+1){ // 如果走一步的长度大于dist[j][type]+1
                /*注:由于走一步就会变一下奇偶性,所以要用type^1*/ 
                dist[j][type^1]=dist[ver][type]+1;
                q[++tt]={j,type^1};
                /* 刷新并将点更新到队列中 */ 
            }
        }
    }
} 
int main(){
    cin.tie(0);
    memset(h,-1,sizeof(h)); // 邻接表初始化 
    cin>>n>>m>>query;
    for(int i=1;i<=m;i++){  
        int a,b;
        cin>>a>>b;
        add(a,b); // 加边 
        add(b,a); // 无向图加两次 
    }
    bfs(); // 预处理(BFS)
    while(query--){ // 循环处理工单 
        int a,l;
        cin>>a>>l; 
        if(a==1&&h[1]==-1) puts("No"); // 特判
        else if(dist[a][l&1]<=l) puts("Yes"); // 如果存在与L同奇偶性且比L小的路径,表示需要提供原材料 
        else puts("No"); // 如果不存在,表示不需要生产原材料
    }
    return 0;
}
/*
    注:本程序使用拆点法,将一个点拆成一个偶点和
    一个奇点,然后预处理偶点到偶点的最短距离与偶点
    到奇点的最短距离,最后再进行判断 
*/

/*
在新图中(拆点后的图),所有从1(偶)走到v(偶)的路径,对应的是原图中所有从1走到v的长度是偶数的路径。 
在新图中(拆点后的图),所有从1(偶)走到v(奇)的路径,对应的是原图中所有从1走到v的长度是奇数的路径。 

因此,在新图中,从1(偶)走到v(偶)的最短路,就是从1走到v的长度是偶数的所有路径中的最短路径, 
从1(偶)走到v(奇)的最短路,就是从1走到v的长度是奇数的所有路径中的最短路径

dist[v][0] : 1 ~ v 偶数路径最短路
dist[v][1] : 1 ~ v 奇数路径最短路
a,L
L是奇数,L>=dist[a][0]
L是偶数  L>=dist[a][1]
*/