2018 計蒜之道初賽第五場

這次的比賽沒有現場打，而是等到了今天才來補。

主要是因為那時候和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;
}

轉載于:https://www.cnblogs.com/cjjsb/p/9130281.html

2018 計蒜之道 初賽 第五場

A. 貝殼找房搬家

B. 貝殼找房算數（簡單）

C. 貝殼找房算數（中等）

2018 計蒜之道初賽第五場