题解 GDFZOJ 2020普转提十连测day3

zhnzh · 2020-07-29 14:43:52 · 个人记录

零、写在前面

看原比赛戳这儿

本比赛难度：普及+/提高-

总体来说不算特别难，但是AK十分有难度。

一、T1 旋风回旋曲

看原题戳这儿

1、审题

题意简化后就是：在一条路径上，给定起点x和终点y与缆车的两端a和b，期间可以借助缆车减少路程，缆车走过的路程不计入徒步总路程，在缆车上a与b既可以作为起点，也可以作为终点，要求从x点徒步到y点路径最短。

数据范围：0 \le x,y,a,b \le 100

既然是T1，那就应该是一道签到题，我们来看一看怎么做。

2、做题

从x点走到y点，期间可以有三条路径可供选择x \Rightarrow y（直接走到y点）、x \Rightarrow a \Rightarrow b\Rightarrow y（在a处上缆车）和x \Rightarrow b \Rightarrow a \Rightarrow y(在b处上缆车)

这三条路径的长度很容易就可以求出来，分别是

|x-y|

|x-a|+|y-b|

|x-b|+|y-a|

然后我们将这三个比较一下就行啦！！！

3、代码

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,ans=1e9;
int main()
{
    scanf("%d%d%d%d",&a,&b,&c,&d);
    ans=min(ans,abs(a-c)+abs(b-d));
    ans=min(ans,abs(a-d)+abs(b-c));
    ans=min(ans,abs(a-b));
    printf("%d\n",ans);
    return 0;
}

4、易错点

没有求其中的最小值
重复运算
没有加绝对值

二、T2 假面饭店

看原题戳这儿

1、审题

题意简化后就是：给你一些数，你需要找出所有藏在数里面的平方关系。满足题意的平方关系 x^2 = y，x和y必须可以从原来的数中去掉一些数字并调换顺序后得到.。

数据范围：数的数量\le 20 , n < 10^{13}

直接全部枚举一遍的话肯定是会爆的，时间复杂度为O(Tn)，但是如果可以考虑优化一下，那应该是可以过的

2、做题

如何遍历

首先我们要开一个桶to，to_i记录的是i在n中出现了几次；然后再定义一个数c，表示大于n的最小的10的整数幂是多少

于是我们就可以从1遍历到c，但是我们不要遍历完，只需要在i^2 > c时就可以退出了，因为这个时候i的位数已经多于n了

如何判断

我们假设现在已经遍历到了i，那么我们就需要像n一样开一个桶，如果对于\forall k，都满足ton_k>toi_k，那么这个就是符合条件的，否则就不符合条件

处理好这两个问题之后，我们就可以完美的解决这个问题了，时间复杂度O(T \sqrt{n})，perfect!!!

3、代码

#include<bits/stdc++.h>
using namespace std;
long long int a,b,c,d,ans;
long long int aa[1001];
int main()
{
    scanf("%lld",&a);
    while(a!=0)
    {
        memset(aa,0,sizeof(aa));c=1;
        while(a!=0)
        {
            aa[a%10]++;
            a/=10;c*=10;
        }
        if(aa[1]==0&&aa[4]==0&&aa[5]==0&&aa[6]==0&&aa[9]==0&&aa[0]==0)
        {
            scanf("%lld",&a);
            continue;
        }
        for(long long int i=0;i*i<=c;++i)
        {
            long long int x=i*i,bb[10]={0,0,0,0,0,0,0,0,0,0};bool flag=false;
            if(x%10==2||x%10==3||x%10==7||x%10==8) continue;
            if(i==0)
            {
                if(aa[0]!=0) printf("0 * 0 = 0\n");
                continue;
            }
            while(x!=0)
            {
                bb[x%10]++;
                if(bb[x%10]>aa[x%10])
                {
                    flag=true;
                    break;
                }
                x/=10;
            }
            x=i;
            for(int j=0;j<=9;++j) bb[j]=0;
            if(flag==true) continue;
            while(x!=0)
            {
                bb[x%10]++;
                if(bb[x%10]>aa[x%10])
                {
                    flag=true;
                    break;
                }
                x/=10;
            }
            if(flag==true) continue;
            printf("%lld * %lld = %lld\n",i,i,i*i);
        }
        scanf("%lld",&a);
    }
    return 0;
}
/*
1369
27
10
0
*/

三、T3 疯狂外星人

看原题戳这儿

1、审题

题意简化后就是：有n件物品，每件物品的体积为D_i，现在要将这些物品装入一个容积为m的箱子里，使其不能再放入更多的物品，问总共有多少种方案满足条件

数据范围：1 \le T \le 1000,1\le n \le 30,1 \le m \le 1000

时间复杂度肯定不能高于O(Tnm)，所以暴力是肯定不行的，需要往dp这方面思考

2、做题

首先，我们观察出了一个规律：如果剩余的物品中体积最小的无法放进箱子里，那么剩余的其它的物品也必定无法放入箱子中，所以我们先需要从小到大将物品的体积排一个序，然后求出所有物品体积之和。

我们从体积最大的物品开始枚举，首先求出比当前物品小的最大物品的位置，然后就可以dp了

3、代码

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,ans;
int aa[101],sum[101],f[100001];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&a,&b);ans=c=0;
        for(int i=1;i<=a;++i) scanf("%d",aa+i);
        sort(aa+1,aa+a+1);
        for(int i=1;i<=a;++i) c+=aa[i];
        memset(f,0,sizeof(f));f[0]=1;
        for(int i=a;i>=1;--i)
        {
            int tot=i;
            while(aa[tot]==aa[i]&&tot!=0) tot--;
            for(int j=max(0,c-b-aa[i]);j<=c-b-1;++j) ans+=f[j];
            for(int j=c;j>=aa[i];--j) f[j]+=f[j-aa[i]];
        }
        if(c<=b) printf("1\n");
        else printf("%d\n",ans);
    }
    return 0;
}
/*
2
6 25
8 9 8 7 16 5
30 250
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
*/

四、T4 流浪地球

看原题戳这儿

\text{未完待续}