2019JZ集训Day21

倒计时最后一天。

有点不舍???


T1:【最小比例】(传送门

  • 由于n,m都不大,所以直接暴力枚举m个点,每次对于m个点跑最小生成树。
  • 哭了。为什么这么暴力。这是非常裸并且非常容易想到的算法,但是因为太暴力了没想打。并且因为我是在11点又看了一遍题目才发现之前理解错了,想到这个算法时觉得要打好久所以也没去实现。害,后悔。

T2:【软件公司】(传送门

  • dp+二分。如果确定了数组表示什么,那么状态转移方程还是挺好推的。
  • f[i][j]代表到前i个人,在1项目做了j个的情况下,2项目能做的最多的个数。转移为:f[i][j]=max{f[i][j],f[i-1][j-k]+(ans-k*A[i])/B[i]};二分答案ans为当前的mid,如果f[n][m]>=m说明这个mid是可行的的,那么可以继续缩小范围往左边找,否则往右边找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,inf=1e9+9;
int f[120][120],a[120],b[120];
int xxl_dalao(int l,int r)
{
    if(l>r) return l;
    int mid=(l+r)>>1;
    for(int i=0;i<=n;++i)
    {
        f[i][0]=0;
        for(int j=1;j<=m;++j)
            f[i][j]=-inf;
    }
    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]<=mid)
                    f[i][j]=max(f[i][j],f[i-1][j-k]+(mid-k*a[i])/b[i]);
            }
    if(f[n][m]>=m)
        return xxl_dalao(l,mid-1);
    else
        return xxl_dalao(mid+1,r);
}
int main()
{
    freopen("company.in","r",stdin);
    freopen("company.out","w",stdout);
   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&a[i],&b[i]);
    printf("%d",xxl_dalao(1,10000));
    return 0;
}

T3:【空间航行】(传送门

  • 需要把题目理解后转换一下模型。
  • 把起点和终点看成半径为0的星域。那么可以把这题转换成最短路。显然,两个星域之间的距离就是两个球心的距离减去半径。跑floyd或者dijkstra都行。可能有两个星域重叠在一起的,所以要注意不能有负边。
  • 感谢xxl大佬的细心指导。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
double a[110][110];
struct note
{
    int x,y,z,r;
}q[110];
double mmp(int x1,int x2,int y1,int y2,int z1,int z2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
double Min(double a,double b)
{
    if(a<=b) return a;
    return b;
}
int main()
{
    freopen("warp.in","r",stdin);
    freopen("warp.out","w",stdout);
   
    scanf("%d",&n);
    while(n!=-1)
    {
        for(int i=1;i<=n;++i)
            scanf("%d%d%d%d",&q[i].x,&q[i].y,&q[i].z,&q[i].r);
        scanf("%d%d%d%d%d%d",&q[n+1].x,&q[n+1].y,&q[n+1].z,&q[n+2].x,&q[n+2].y,&q[n+2].z);
        q[n+1].r=0;q[n+2].r=0;
        for(int i=1;i<=n+2;++i)
            for(int j=1;j<=n+2;++j)
            {
                double xxl_dl=(mmp(q[i].x,q[j].x,q[i].y,q[j].y,q[i].z,q[j].z)-q[i].r*1.0-q[j].r*1.0)*10;
                a[i][j]=(xxl_dl<0?0:xxl_dl);
            }
        for(int k=1;k<=n+2;++k)
            for(int i=1;i<=n+2;++i)
                for(int j=1;j<=n+2;++j)
                    if(i!=k&&i!=j&&j!=k)
                        a[i][j]=Min(a[i][j],a[i][k]+a[k][j]);
        if((int)(a[n+1][n+2]*2)>(int)(a[n+1][n+2])*2)
            printf("%d\n",(int)(a[n+1][n+2])+1);
        else printf("%d\n",(int)(a[n+1][n+2]));
        scanf("%d",&n);
    }
    return 0;
}

T4:【摧毁巴士站】(传送门

  • 好像很很多种解法。并且搜索+花样剪枝或者迭代深搜是能过的。
  • 暂时还没改。丢个题解(摧毁巴士站)。

啊最后一天了不知道要说些什么。

那就总结blog见吧。

——end。

发表评论

电子邮件地址不会被公开。 必填项已用*标注