第一次双周赛

7-2 a*b

• 知识点：十六进制数的高精度乘法

• 核心代码：用两个for循环处理

  for(int i=0;i<len1;i++)
  	{
  		len3=i;
  		for(int j=0;j<len2;j++)
  		{
  			z[len3]+=x[i]*y[j];
  			if(z[len3]>=16)
  			{
  				z[len3+1]+=z[len3]/16;
  				z[len3]%=16;
  			}
  			len3++;
  		}
  	}
  

• 注意：要记得去掉先导0！！

  int index=len1+len2;
  	while(index>0&&z[index]==0)
  	index--;
  	for(int i=index;i>=0;i--)
  	{
  		if(z[i]>=0&&z[i]<=9)
  		cout<<z[i];
  		else 
  		cout<<q[z[i]-10];
  	}
  

7-3 山头狙击战

• 知识点：二分答案（装子弹时间：最大的最小

• 主要思路：mi[]数组记录敌人一开始的位置，sort排序，从离小明最近的敌人开始考虑

  ​ 用s记录下一个敌人往前走了多少

  ​ mi[i]-s表示敌人距离小明的相对位置

  ​ 二分法检查当前答案是否能让能击倒敌人数大于实际敌人数

  #include<bits/stdc++.h>
  using namespace std;
  int m,n,mi[10000005],ans=-1,sum=0,s=0;
  bool check(int k)
  {
  	if(mi[0]>m)
  	s=mi[0]-m; //s表示下一个敌人往前走了多少 
  	sum++;
  	for(int i=1;i<n;i++)
  	{
  		s+=k;
  		if(mi[i]<s) break; //敌人已经到小明处
  		else if(mi[i]-s>m) //敌人在小明射程以外
  		{
  			s+=mi[i]-s-m;
  			sum++; 
  		 } 
  		 else
  		 sum++;
  	}
  	
  	if(sum>=n) return true;
  	return false;
  }
  int main()
  {
  	cin>>n>>m;
  	for(int i=0;i<n;i++)
  	cin>>mi[i];
  	sort(mi,mi+n);
  	
  	int l=1,r=mi[n-1];
  	while(l<=r)
  	{
  		int mid=l+(r-l)/2;
  		if(check(mid))
  		{
  			ans=mid;
  			l=mid+1;
  		}
  		else
  		{
  			r=mid-1;
  		}
  		sum=0;
  		s=0;
  	}
  	cout<<ans<<endl;
  	return 0;
  }
  

7-5 一元三次方程

• 二分大法好QWQ

#include <bits/stdc++.h>
using namespace std;
double a,b,c,d,n,p,q;
double f(double x){
    return (a*x*x*x+b*x*x+c*x+d);
}
void js(){
    for(double i=p;i<q;i++){
        double l=i,r=i+1,mid;
        if(f(l)==0) printf("%.6lf ",l);
        else if(f(l)*f(r)<0){
            while((r-l)>1e-7){
                mid=(l+r)/2;
                if(f(mid)*f(r)<=0) l=mid;
                else r=mid;
            }
            printf("%.6lf ",l);
        }
    }
}
int main(){
	int t;
	cin>>t;
	while(t--)
	{
		cin>>a>>b>>c>>d>>p>>q;
		js();
		cout<<endl;
	}
    return 0;
}