题目链接：JZOJ 3736/Maloyaroslavets Summer Camp 2008。
题目
题目描述
给定两个向量 $\vec{a}=(x _ 1,y _ 1),\vec{b}=(x _ 2,y _ 2)$。求出一对整数 $\lambda _ 1,\lambda _ 2$ 使得 $|\lambda _ 1\vec{a} +\lambda _ 2\vec{b}|$ 最小（ $|\vec{v} |$ 表示向量 $\vec{v}$ 的长度），要求 $\lambda _ 1,\lambda _ 2$ 不同时为 $0$。
输入格式
输入有多组输入有多组测例，每组测例有一行，为 $4$ 个整数 $x _ 1,y _ 1,x _ 2,y _ 2$，含义见题目描述。输入文件以 EOF 结束。
输出格式
对于每组测例，输出一行，为一个整数 $|\lambda _ 1\vec{a}+\lambda _ 2\vec{b}|^2$。
样例输入输出
#1
- Input:
3 0 1 2
6 0 4 0
- Output:
5
样例解释
- 第一组：$\lambda _ 1=0,\lambda _ 2=1$；
- 第二组：$\lambda _ 1=2,\lambda _ 2=3$（多种解法）。
数据范围
设单个测试点的测例组数为 $T$。
$20\%$ 的数据，满足 $T\leq 100$，存在一组最优的 $\lambda _ 1,\lambda _ 2$ 满足 $|\lambda _ 1|,|\lambda _ 2|\leq 30$。
$60\%$ 的数据，满足 $T\leq 10^4$，存在一组最优的 $\lambda _ 1,\lambda _ 2$ 满足 $\min\{|\lambda _ 1|,|\lambda _ 2|\}\leq 30$。
$100\%$ 的数据，满足 $T\leq 10^5,|x _ 1|,|x _ 2|,| y _ 1 |,| y_ 2 |\leq 10 ^ {4}$，存在一组最优的 $\lambda _ 1,\lambda _ 2$ 满足 $\min\{|\lambda _ 1|,|\lambda _ 2|\}\leq 10^4$。
时空限制
$$1000\text{ms}/256\text{MiB}$$
本题有多种解法（模拟两种（20分、60分），水法（100分），数论正解（100）），详情请看下一页。
题解
解法 A （直接模拟）
思路
思路十分简单，面对数据范围的编程思想十分明显。
代码
略
解法 B （优化模拟）
思路
略
代码
考场代码。
#include<cstdio>
#include<algorithm>
using std::min;
typedef long long ll;
#define INF 0X3F3F3F3F3F3F3F3Fll
const int MAXT=100000+5;
ll x1,y1,x2,y2;
int main(void){
//freopen("math.in","r",stdin);
//freopen("math.out","w",stdout);
register int i,j;
register ll now,last,ans;
while(scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2)!=EOF){
ans=INF;
for(i=-30;i<=30;++i){
last=INF;
for(j=1;j<=10000;++j){
now=(i*x1+j*x2)*(i*x1+j*x2)+(i*y1+j*y2)*(i*y1+j*y2);
if(now>last)
break;
//printf("%d %d %lld last=%lld\n",i,j,now,last);
last=now;
ans=min((ll)ans,(ll)now);
}
last=INF;
for(j=-1;j>=-10000;--j){
now=(i*x1+j*x2)*(i*x1+j*x2)+(i*y1+j*y2)*(i*y1+j*y2);
if(now>last)
break;
//printf("%d %d %lld last=%lld\n",i,j,now,last);
last=now;
ans=min((ll)ans,(ll)now);
}
}
for(j=-30;j<=30;++j){
last=INF;
for(i=1;i<=10000;++i){
now=(i*x1+j*x2)*(i*x1+j*x2)+(i*y1+j*y2)*(i*y1+j*y2);
if(now>last)
break;
//printf("%d %d %lld last=%lld\n",i,j,now,last);
last=now;
ans=min((ll)ans,(ll)now);
}
last=INF;
for(i=-1;i>=-10000;--i){
now=(i*x1+j*x2)*(i*x1+j*x2)+(i*y1+j*y2)*(i*y1+j*y2);
if(now>last)
break;
//printf("%d %d %lld last=%lld\n",i,j,now,last);
last=now;
ans=min((ll)ans,(ll)now);
}
}
printf("%lld\n",ans);
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
解法 C （水法：贪心）
很玄学，我也不会，估计是随机化（爬山）吧。
解法 D （数论正解）
思路
代码
代码实现起来比较短，时间复杂度难以分析，根据数据（itdep 的大小）得出算法的运行时间增长缓慢，大致为 $\log _ 2n$ 的级别，所以该算法的时间复杂度应该是 $\Theta(\log _ 2n)$。
#include<cstdio>
typedef long long ll;
int itdep=0;
ll x1,y1,x2,y2;
void Solve(ll,ll,ll,ll,int&,int&);
int main(void){
//freopen("math.in","r",stdin);
//freopen("math.out","w",stdout);
int lambda1,lambda2;
while(scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2)!=EOF){
Solve(x1,y1,x2,y2,lambda1,lambda2);
printf("%lld\n",(lambda1*x1+lambda2*x2)*(lambda1*x1+lambda2*x2)+(lambda1*y1+lambda2*y2)*(lambda1*y1+lambda2*y2));
//printf("itdep=%d\n",itdep);
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
void Solve(ll a,ll b,ll c,ll d,int &x,int &y){
++itdep;//统计步数，试图测量时间复杂度
ll dot=a*c+b*d;//向量点乘，也就是投影长度
if(dot<0){//不同方向
Solve(a,b,-c,-d,x,y);//反向
y=-y;
return;
}
ll L12=a*a+b*b,L22=c*c+d*d;
//两个向量模长的平方
if(L12>L22){//a更长
Solve(c,d,a,b,y,x);//交换
return;
}
if(dot*dot*4<=L12*L22){//如果夹角大于pi/3
x=1,y=0;
return;
}
ll k=dot/L12;//对应论文中的k
if(dot+dot<=L12*(k+k+1)){
Solve(a,b,c-k*a,d-k*b,x,y);
x-=k*y;
}
else{
Solve(a,b,c-(k+1)*a,d-(k+1)*b,x,y);
x-=(k+1)*y;
}
return;
}
近期评论