这次的比赛没有现场打,而是等到了今天才来补。
主要是因为那时候和HHHOJ上的比赛冲突了,所以就没写。
这次前三题的难度都比较低,但是就是一个T4要莫比乌斯反演。又是不可食用的。
好了我们开始看题。
A. 贝壳找房搬家
这道题刚开始看的时候没看懂题意,觉得T1就是这种立体几何的题目,有种想死的感觉。
因为我认为这个方块可以不规则地想怎么放就怎么放的,其实题目中有一句话:
我们可以把这堆箱子看成一个\(x \times y \times z\) 的长方体。
什么?刚开始只能是长方体吗?好吧好像还是不可做的样子。
然后一看时限:5000ms,那不就……暴力一下?
我们枚举最短边\(a(1<=a<=\sqrt[3]n)\),然后是次短边\(b(1<=b<=\sqrt n)\)。
然后我们只需要算出第三边\(h(h为整数)\),然后讨论一下谁是长,谁是宽,谁是高。
然后直接更新最大最小值即可。注意这里长宽都是原来+2的结果,但高是+1。
CODE
#include<cstdio>
using namespace std;
int t,n,h,v,MAX,MIN;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int a,b; read(t);
while (t--)
{
read(n); MAX=-1; MIN=1e9;
for (a=1;a*a*a<=n;++a)
for (b=1;b*b<=n;++b)
{
if (n%(a*b)) continue; h=n/a/b;
MIN=min(MIN,(a+2)*(b+2)*(h+1)-n); MAX=max(MAX,(a+2)*(b+2)*(h+1)-n);
MIN=min(MIN,(a+2)*(b+1)*(h+2)-n); MAX=max(MAX,(a+2)*(b+1)*(h+2)-n);
MIN=min(MIN,(a+1)*(b+2)*(h+2)-n); MAX=max(MAX,(a+1)*(b+2)*(h+2)-n);
}
write(MIN); putchar(' '); write(MAX); putchar('\n');
}
return 0;
}
B. 贝壳找房算数(简单)
这还是比较水的,直接\(O(n^2logn)\)判断即可。
因为分解以及gcd都是log的,所以不会超时。
CODE
#include<cstdio>
using namespace std;
int n,a,b,ans;
long long k;
inline int f(int x)
{
int tot=1;
while (x) tot*=x%10,x/=10;
return tot;
}
inline int gcd(int m,int n)
{
return n?gcd(n,m%n):m;
}
int main()
{
register int i,j; scanf("%d%lld",&n,&k);
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
{
int a=f(i),b=f(j);
if (!a||!b) continue;
if (gcd(a,b)<=k) ++ans;
}
printf("%d",ans);
return 0;
}
C. 贝壳找房算数(中等)
这个也是很Easy的,因为我们注意到像124,142和241等等这些数它们的贡献是一样的。
因此我们发现有用的\(f(i)\)很少,所以我们统计一下所有\(f(i)=x\)的数分别有多少。
这里由于数的分布不均匀,因此我们上map大法
这里主意一下对于map的遍历,需要用指针和一个奇奇怪怪的STL来完成
这遍历非人哉,我才不会告诉你我是从网上找的方法
CODE
#include<cstdio>
#include<map>
using namespace std;
const int mod=998244353;
map <int,int> t;
map <int,int>::iterator a,b;
int n,w;
long long k,ans;
inline int f(int x)
{
int tot=1;
while (x) tot*=x%10,x/=10;
return tot;
}
inline int gcd(int m,int n)
{
return n?gcd(n,m%n):m;
}
int main()
{
register int i; scanf("%d%lld",&n,&k);
for (i=1;i<=n;++i)
++t[f(i)];
for (a=t.begin();a!=t.end();++a)
for (b=a;b!=t.end();++b)
{
int x1=a->first,y1=a->second,x2=b->first,y2=b->second;
if (!x1||!x2) continue;
if (gcd(x1,x2)>k) continue;
if (x1^x2) ans=(ans+(long long)y1*y2*2)%mod; else ans=(ans+y1*y2)%mod;
}
printf("%lld",ans);
return 0;
}