day21

好难，得分40/400；

加个0不就满分了吗

t1写了个最小生成树，但没有考虑完全；

题意：从n个点中取m个点生成一棵最小生成树，使他的边权与点权的比值最小；

由于n及其小，可以枚举取哪些点来做一棵最小生成树；

为了避免精度问题，可以考虑去分母变成乘法

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#define oyy main
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
int w[20],m,n;
int mp[20][20];
int ans[20],v[20],temp[20],ans1=1,ans2=1,bq,dq;
void prime()
{
    int d[20]={},vv[20]={};
    memset(d,0x3f,sizeof(d));
    d[temp[1]]=0;
    for(int i=1;i<=m;i++)
    {
        int k=0,minn=0x7ffff;
        for(int j=1;j<=m;j++)
        if(!vv[temp[j]]&&minn>d[temp[j]])
        {
            minn=d[temp[j]];k=temp[j];
        }
        vv[k]=1;
        for(int j=1;j<=m;j++)
        if(!vv[temp[j]]&&d[temp[j]]>mp[k][temp[j]])d[temp[j]]=mp[k][temp[j]];
    }
    for(int i=1;i<=m;i++)
    {
        bq+=d[temp[i]];
        dq+=w[temp[i]];
    }
    if(bq*ans2<dq*ans1)
    {
        for(int i=1;i<=m;i++)
        ans[i]=temp[i];
        ans1=bq;
        ans2=dq;
    }
    return;
}
void dfs(int x,int i)
{
    if(x==m)
    {
        bq=0;dq=0;
        prime();
        return;
    }
    i++;
    for(;i<=n;i++)
        if(!v[i])
        {
            x++;
            temp[x]=i;
            v[i]=1;
            dfs(x,i);
            temp[x]=0;
            v[i]=0;
            x--;
        }
}
inline int cmp(int x,int y){return x<y;}
int oyy()
{
    freopen("ratio.in","r",stdin);freopen("ratio.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++)
    w[i]=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
    mp[i][j]=read();if(i==j)mp[i][j]=0x7ffff;}
    dfs(0,0);
    sort(ans+1,ans+m+1,cmp);
    for(int i=1;i<=m;i++)
    cout<<ans[i]<<" ";
    return 0;
}

 t2二分答案！；

时间只在1~10000；

设 $f[i][j]$ 表示前 $i$ 个人做了 $j$ 个1任务后能做的最多2任务的个数；

转移显然 $f[i][j]=max{f[i][j],f[i-1][j-k]+(ans-k*a[i])/b[i]}$ 

复杂度$o（n*m^2*log(10000))$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#define oyy main
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
int a[110],b[110],n,m;
inline bool check(int ans)
{
    int f[120][200]={};
    for(int i=0;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        f[i][j]=-0x3f3f3f;
        f[i][0]=0;
    }
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<=j;k++)
    {
        if(k*a[i]<=ans)
        f[i][j]=max(f[i][j],f[i-1][j-k]+(ans-k*a[i])/b[i]);
    }
    return f[n][m]>=m;
}
int oyy()
{
    freopen("company.in","r",stdin);freopen("company.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++)
    a[i]=read(),b[i]=read();
    int l=1,r=10000,mid=l+r>>1;
    while(l<r)
    {
        if(!check(mid))l=mid+1;
        else r=mid;
        mid=l+r>>1;
    }
    cout<<mid<<endl;
    return 0;
}

 t3转化一下模型，把每两个星系之间连一条边，弗洛伊德乱搞一下就过了，

要不是三维立体太难想，我考场就做了。

三维算距离是$\sqrt{(\delta x)^2+(\delta y)^2+(\delta z)^2}$

再减去两个星系半径就是距离，如果小于$0$就用$0$代替(毕竟距离没有负的)

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cmath>
#define oyy main
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
double mp[103][103];
int n;
struct node{
    int x,y,z,r;
}a[103];
inline double jl(double x1,double x2,double y1,double y2,double z1,double z2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);
}
int oyy()
{
    freopen("warp.in","r",stdin);freopen("warp.out","w",stdout);
    n=read();
    while(n!=-1)
    {
        for(int i=1;i<=n;i++)
        {
            a[i].x=read();a[i].y=read();a[i].z=read();a[i].r=read();
        }
        a[0].x=read();a[0].y=read();a[0].z=read();
        a[n+1].x=read();a[n+1].y=read();a[n+1].z=read();
        a[0].r=a[n+1].r=0;
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=n+1;j++)
                if(i!=j)
                {
                    double temp=sqrt(jl(a[i].x,a[j].x,a[i].y,a[j].y,a[i].z,a[j].z))-a[i].r-a[j].r;
                    mp[i][j]=temp>0?temp:0;
                }
        for(int k=0;k<=n+1;k++)
            for(int i=0;i<=n+1;i++)
                for(int j=0;j<=n+1;j++)
                    if(k!=i&&k!=j&&i!=j)
                        mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
        double temp=mp[0][n+1]*10;
        int ans=floor(temp+0.5);
        cout<<ans<<endl;
        n=read();
    }
    return 0;
}

 t4鸽了，等我学会最短路+记录路径再做