AtCoder Beginner Contest 374(D-E)

A-C：

惯例是宝宝题，会打暴力就能过哈

D：

其实也是暴力dfs，有一个double打错成int（我是猪鼻），卡了我很久

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 10,eps=1e-7;
int n,s,t;
bool vis[10];
double sum=1e8;
struct Node{
	double x,y,x1,y1;
}a[maxn];
double dis(double x,double y,double x1,double y1){
	return sqrt(1.0*(x-x1)*(x-x1)+1.0*(y-y1)*(y-y1));
}
void dfs(double sm,int x,int y){
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			double tmp=dis(a[i].x,a[i].y,x,y);
			dfs(sm+tmp,a[i].x1,a[i].y1);
			tmp=dis(a[i].x1,a[i].y1,x,y);
			dfs(sm+tmp,a[i].x,a[i].y);
			vis[i]=0;
		}
		else cnt++;
	}
	if(cnt==n){
		if(sm-sum<eps)sum=sm;
		return;
	}
}
signed main(){
    cin>>n>>s>>t;
	double ans=0;
	for(int i=1;i<=n;i++){
		double x,y,x1,y1;cin>>x>>y>>x1>>y1;
		ans+=dis(x,y,x1,y1);
		a[i].x=x,a[i].y=y,a[i].x1=x1,a[i].y1=y1;
	}
	for(int i=1;i<=n;i++){
		vis[i]=1;
		double tmp=dis(0,0,a[i].x,a[i].y);
		dfs(tmp,a[i].x1,a[i].y1);
		tmp=dis(0,0,a[i].x1,a[i].y1);
		dfs(tmp,a[i].x,a[i].y);
		vis[i]=0;
	}
	ans=ans*1.0/t+sum*1.0/s;
	printf("%.7lf",ans);
}

E：

一开始以为是dp想了很久想不通。后来才发现是经典二分+DP。不过check部分还是要思考一下，要求生产数量大于mid在最优情况下能否实现。一种机器严格优于另一种机器是在\(A_i*B_i\)的条件下才会具备的，在这个结论下我们也会思考去先求出最大可取值k再暴力枚举剩下的部分。
这个做法是过不了hack数据的，因为我们并不能直接枚举剩余部分，剩余部分其实是不确定的（可能只取k-1然后再枚举取AB更优），所以做法最终为枚举剩余部分（最多只有ai或者bi个，因为超过一定换成更优的）用某个机器生产，剩下的用另一个机器生产的最小值。
代码很丑，建议看官解代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define int long long
using namespace std;
const int maxn=200;
int a[maxn],p[maxn],b[maxn],q[maxn],n,x;
bool jud(int mid){
    int sum=0;
    for(int i=1;i<=n;i++){
        int k=mid/(a[i]*b[i]);
        int res=mid-k*a[i]*b[i];
        int ans=1e18,ans2=1e18;
        int tte=0;
        for(int j=0;j<=b[i];j++){
            for(int m=0;m<=a[i];m++){
                if(a[i]*j+b[i]*m>=res)ans=min(ans,p[i]*j+m*q[i]);
            }
        }
        tte=ans+k*p[i]*b[i];
        if(k>0){
            res=mid-(k-1)*a[i]*b[i];
            for(int j=0;j<=b[i];j++){
                for(int m=0;m<=a[i];m++){
                    if(a[i]*j+b[i]*m>=res)ans2=min(ans2,p[i]*j+m*q[i]);
                }
            }
            tte=min(ans2+(k-1)*p[i]*b[i],tte);
        }
        sum+=tte;
        
        //if(mid==4)cout<<p[i]<<' '<<sum<<endl;
    }
    if(sum<=x)return 1;
    else return 0;
}
signed main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>p[i]>>b[i]>>q[i];
        int v1=b[i]*p[i],v2=a[i]*q[i];
        if(v1>v2)swap(a[i],b[i]),swap(p[i],q[i]);
    }
    int l=0,r=1e9+7,mid=(l+r+1)/2;
    while(l<r){
        if(jud(mid))l=mid;
        else r=mid-1;
        mid=(l+r+1)/2;
    }
    cout<<mid<<endl;
}

F：

DP吧。不会