第四课
A 点到线段的距离
题意
在三维中有一个点和一条线段，问你点到线段的最近距离。
思路
首先，线段上有一个唯一的点是与另一个点的距离是最小的。
而从这个点往两侧，距离会越大。
那么这条线从左往右的点到另外一个点的距离在坐标轴上就是条抛物线。
二分不能算出这种规律，我们要用三分。
三分就是使用两个类似 $mid$ 的东西，分别在区间的 $\frac {1}{3}$ 和 $\frac {2}{3}$ 处如果发现第一个指针的距离大于第二个指针的，我们就把第一个舍去，也就是抛弃 $\frac {1}{3}$ 的区间，如果第二个大于第一个同理。
这样就可以慢慢接近最近的那个点了。
三维距离可以用勾股定理算出来。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
using namespace std;
struct node{
double x,y,z;
};
node a,b,p;
const double eps=1e-6;
double get(double mid)
{
node k;
k.x=a.x+(b.x-a.x)*mid;
k.y=a.y+(b.y-a.y)*mid;
k.z=a.z+(b.z-a.z)*mid;
return sqrt((p.x-k.x)*(p.x-k.x)+(p.y-k.y)*(p.y-k.y)+(p.z-k.z)*(p.z-k.z));
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&a.z,&b.x,&b.y,&b.z,&p.x,&p.y,&p.z);
double l=0,r=1,mid1=0,mid2,best=-1;
while(r-l>eps)
{
mid1=l+(r-l)/3.0;
mid2=r-(r-l)/3.0;
if(get(mid1)<get(mid2))r=mid2,best=mid2;
else l=mid1,best=mid1;
}
printf("%.2f\n",get(best));
}
return 0;
}
|
B 三角形与四边形
题意
已知三角形 $ABC$，$DE$ 平行于 $BC$，给定三角形 $ADE$ 与四边形 $BCED$ 的面积之比，求 $AD$ 的长度。
思路
首先根据这两个相似三角形，我们需要知道以下定理；
- $\frac {AD}{AB} = \frac {AE}{AC} = \frac {DE}{BC} = k$
- 三角形 $ADE$ ：三角形 $ABC$ $=$ $k^2$
所以我们可以直接二分 $AD$ 的长度，根据题目给出的数据算出每条边的长度，通过海伦公式算出三角形 $ADE$ 的面积和 $ABC$ 的面积，得出比例，然后就能判断出是否接近答案了。
注意多组数据
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
using namespace std;
int tt;
const double eps = 1e-6;
double ab,ac,bc,k;
double calc(double a,double b,double c)
{
double p=(a+b+c)/2.0;
return sqrt(p*fabs(p-a)*fabs(p-b)*fabs(p-c));
}
bool check(double mid)
{
double ad=mid;
double de=(ad*bc)/ab;
double ae=(ac*ad)/ab;
double ret=calc(ad,de,ae)/(calc(ab,bc,ac)-calc(ad,de,ae));
return ret>=k;
}
int main()
{
scanf("%d",&tt);
int ca=0;
while(tt--)
{
scanf("%lf%lf%lf%lf",&ab,&ac,&bc,&k);
double l=0,r=ab,best=-1;
int step=100;
while(step--)
{
double mid=(l+r)/2.0;
if(check(mid))
{
best=mid;
r=mid;
}
else l=mid;
}
printf("Case %d: %.2f\n",++ca,best);
}
}
|
C 最大比例
题意
有 $n$ 对元素 $(𝑣1,𝑤1),(𝑣2,𝑤2), (𝑣3,𝑤3), …,(𝑣𝑛,𝑤𝑛)$。要求从中挑选出 $k$ 对，使得 $v$ 的和除以 $w$ 的和最大。
思路
题目让我们求
$\frac {v_1+v_2+…+v_k}{w_1+w_2+…+v_k} = ans$
等式两遍同时乘：
$v_1+v_2+…+v_k = ans·(w_1+w_2+…w_k)$
拆括号：
$v_1+v_2+…v_k = ans·w_1+…ans·w_k$
移项：
$(v_1 - ans·w_1) + (v_2 - ans·w_2)…+ (v_k - ans·w_k) = 0$
而我们发现，当 $ans$ 越大，每一项都会变小。
所以我们就二分找到一个最大的 $ans$ ，把 $v$ 数组减去 $ans·w$，然后选出最大的几个数相加，看是否大于或等于 $0$，如果满足，记录指针并保存答案。
否则让 $ans$ 变小。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const double eps = 1e-6;
int n,m;
double v[N],w[N];
struct node
{
int id;
double num;
bool operator < (const node&cmp) const
{
if(fabs(num-cmp.num)>eps) return num>cmp.num;
return id<cmp.id;
}
};
node b[N];
double a[N];
bool cmp(double a,double b)
{
return a-b>eps;
}
bool check(double bi)
{
for(int i=1;i<=n;i++) a[i]=1.0*v[i]-1.0*w[i]*bi;
sort(a+1,a+n+1,cmp);
double sum=0;
for(int i=1;i<=m;i++) sum+=a[i];
return sum>eps;
}
vector<int> vv;
signed main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf%lf",&v[i],&w[i]);
double l=0,r=1e9,best=-1;
int step=55;
while(step--)
{
double mid=(l+r)/2.0;
if(check(mid)) l=mid,best=mid;
else r=mid,best=r;
}
for(int i=1;i<=n;i++) b[i].num=v[i]-w[i]*best,b[i].id=i;
sort(b+1,b+n+1);
for(int i=1;i<=m;i++) vv.push_back(b[i].id);
sort(vv.begin(),vv.end());
int t=vv.size();
for(int i=0;i<t;i++) printf("%d ",vv[i]);
}
|
D 后缀零
题意
找出最小的自然数 $n$，使得 $n!$ 刚好有 $q$ 个后缀零。
思路
我们可以发现，如果想让一个数的乘积末尾有 $0$，两个数的因数中必须有 $2$ 和 $5$。
而一个数的阶乘中，因数 $2$ 的数量总是要大于 $5$ 的，所以我们只需要考虑 $5$ 的个数。
我们可以直接使用数学方法求得：
1
2
3
4
5
6
| int check(int mid)
{
int ans=0;
while(mid>0) ans+=mid/5,mid/=5;
return ans;
}
|
所以我们直接二分答案，看时候满足条件即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <bits/stdc++.h>
using namespace std;
int q;
int t;
int check(int mid)
{
int ans=0;
while(mid>0) ans+=mid/5,mid/=5;
return ans;
}
int main()
{
scanf("%d",&t);
int ca=0;
while(t--)
{
scanf("%d",&q);
int l=0,r=1e9;
int best=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)==q)
{
best=mid;
r=mid-1;
}
else if(check(mid)>q) r=mid-1;
else l=mid+1;
}
printf("Case %d: ",++ca);
if(best==-1) puts("impossible");
else printf("%d\n",best);
}
}
|
E 最小距离最大化
题意
在坐标轴上有 $n$ 个点，从中选取 $m$ 个点，使得这 $m$ 个点两两之间的最小距离最大。
思路
首先，几个点的最小距离一定是在排序后相邻两个点之间的。
所以我们直接二分答案，看能否选出 $m$ 个点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
int n,m;
int x[100010];
bool check(int xx)
{
int last=x[1],cnt=1;
for(int i=2;i<=n;i++)
{
if(x[i]-last>=xx) cnt++,last=x[i];
}
return cnt>=m;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
sort(x+1,x+n+1);
int l=0,r=(int)1e9;
int best=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
best=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%d",best);
}
|
F 矩阵
题意
有一个 $n\times n$ 的矩阵，第 $i$ 行 $j$ 列的数值为 $i^2 + 100000\times i+ j^2 - 100000 \times j + i\times j$ ，求矩阵中第 $m$ 小的数。
思路
我们可以直接二分答案，然后看矩阵中有多少个数大于这个数。
而我们可以通过二分求出每一列中有多少个数大于我们二分的数，所以枚举每一行可以求出整个矩阵多少个数大于这个数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m;
int check(int x)
{
int sum=0;
for(int i=1;i<=n;i++)
{
int l=1,r=n,k=0;
while(l<=r)
{
int mid=(l+r)/2;
int zhi=mid*mid+100000*mid+i*i-100000*i+mid*i;
if(zhi<=x) k=mid,l=mid+1;
else r=mid-1;
}
sum+=k;
}
return sum;
}
signed main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
int l=(int)-8e9,r=(int)8e9;
int best=-1;
while(l<=r)
{
int mid=(l+r)/2;
int kk=check(mid);
if(kk>=m) best=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",best);
}
}
|
