题解 GDFZOJ 2020普转提十连测day3 零、写在前面 一、T1 旋风回旋曲 二、T2 假面饭店 三、T3 疯狂外星人 四、T4 流浪地球
看原比赛戳这儿
本比赛难度：普及+/提高-
总体来说不算特别难，但是(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 bRightarrow y)（在(a)处上缆车）和(x Rightarrow b Rightarrow a Rightarrow y)(在(b)处上缆车)
这三条路径的长度很容易就可以求出来，分别是
然后我们将这三个比较一下就行啦！！！
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
",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
");
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
",i,i,i*i);
}
scanf("%lld",&a);
}
return 0;
}
/*
1369
27
10
0
*/
三、T3 疯狂外星人
看原题戳这儿
1、审题
题意简化后就是：有n件物品，每件物品的体积为D_i，现在要将这些物品装入一个容积为m的箱子里，使其不能再放入更多的物品，问总共有多少种方案满足条件
数据范围：(1 le T le 1000,1le 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
");
else printf("%d
",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 流浪地球
看原题戳这儿