欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

day21

程序员文章站 2024-03-30 19:56:03
好难,得分40/400; 加个0不就满分了吗 T1写了个最小生成树,但没有考虑完全; 题意:从N个点中取M个点生成一棵最小生成树,使他的边权与点权的比值最小; 由于N及其小,可以枚举取哪些点来做一棵最小生成树; 为了避免精度问题,可以考虑去分母变成乘法 代码 #include # ......

好难,得分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鸽了,等我学会最短路+记录路径再做