ABC300 做题笔记

MoSalah · 2023-05-03 12:01:53 · 个人记录

A

简单题，不讲。

B

数据范围很小，随便暴力。O(hw) 枚举二元组，然后再 O(hw) 判断。

感觉这种题放在这种位置上就没啥意思。码量不小，又不小清新，也不知道想考啥。

C

这题也没意思。直接枚举 #，然后往四角扩展直到不能扩展为止。如果扩展成功则计入答案。时间复杂度 O(hw)。

D

这题时限 3s。

然后我赛时擦着时限过了，2.837 s。

现在还是最劣解第一页。

1. 我赛时的做法

这玩意其实很直觉，也特别暴力，什么优化都不带的那种。随便放缩一下就有 a^{5}\lt n，因此先这么枚举 a，再看是不是质数。这里最多要枚举 54 个。

然后再放缩，于是 b^{3}\lt \lfloor \dfrac{n}{a^{2}} \rfloor，再枚举一下。这里即使 n 取满也只有 6064 对 (a,b) 满足条件。

接下来就是最耗时的地方了。记 p=\lfloor \dfrac{n}{a^{2}\times b} \rfloor，则直接在 [b+1,\sqrt p] 里枚举 c 然后一个个判断，如果是质数则计入答案。复杂度 O(可过)。天知道它是怎么过的。

2. 优化

其实这个东西特别好优化，但是赛时我看它卡过去了就没管。

上面这个东西最耗时的地方有两点：

判断一个东西是不是质数。
数出 [l,r] 内有几个质数。

我们发现我们枚举的范围最多也只有 \sqrt n，即 10^{6}。因此我们筛一遍再做个前缀和即可。

有了这两个简单优化，它跑得飞起，27ms 就过了。

for(int i=2;i*i*i*i*i<=n;i++)
{
    if(isp[i]-isp[i-1])
    {
        int lft=n/(i*i);
        for(int j=i+1;j*j*j<=lft;j++)
        {
            if(isp[j]-isp[j-1])
            {
                int rgt=lft/j;
                int x=__builtin_sqrt(rgt);
                cnt+=isp[x]-isp[j];
            }
        }
    }
}

E

定义 dp(x) 表示从 x 开始最终获得 1 的概率。则答案为 dp(n)。显然最终都变成 1，所以 dp(1)=1。

于是 dp(x)=\dfrac{dp(x)}{6}+\sum_{i=2}^{6} [x\bmod i = 0]\times dp(\lfloor \dfrac{x}{i} \rfloor)。两边消掉，则 dp(x)=\dfrac{\sum_{i=2}^{6} [x\bmod i=0]\times dp(\lfloor \dfrac{x}{i} \rfloor)\times 6}{5}。

记忆化+递归求解即可。时间复杂度 O(能过)。

int dp(int x)
{
    if(vis.count(x)){return vis[x];}
    if(x==1){return vis[x]=1;}
    int ans=0;
    for(int i=2;i<=6;i++)
    {
        if(x%i==0)
        {
            ans+=inv(6)*dp(x/i)%mod;
            ans%=mod;
        }
    }
    return vis[x]=((ans*6)%mod*inv(5)%mod);
}

F

这玩意很简单，就是注意细节。

我们考虑肯定存在一种答案满足左端点在 1 到 n 之间。然后就随便做了。下面是赛时做法：

二分答案。然后枚举左端点，用前缀和和循环的性质判断结果是否满足条件。完结撒花。

好的，那么我为什么吃了 3 发罚时呢？

边界错误 1 次，拍出来的。

边界错误 2 次，拍出来的。

边界错误 3 次，拍出来的。

心态爆炸，终于过了。

bool check(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(n*m-(i-1)<x){continue;}//边界 1：如果剩下不足 x 个
        if(i+x-1<=n)//边界二：如果根本没有循环
        {
            if(pre[x+i-1]-pre[i-1]<=k){return 1;}
            continue;
        }
        int cur=x-(n-i+1);
        int tmp=pre[n]-pre[i-1];
        tmp+=pre[n]*(cur/n);
        cur%=n;
        tmp+=pre[cur];
        if(tmp<=k){return 1;}
    }
    return 0;
}

G

我们发现 100 以内的质数也就 25 个，因此考虑暴力搜索。

但是显然，这样搜就突出一个奇慢无比，最大数据 10 s 都跑不出来。交上去总共 T 了 25 个点。

这时我们就可以考虑 Meet in the middle 了。先对一半的质数搜一遍，搜出所有可以得到的结果；再对另一半的质数搜一遍，搜完之后假设结果是 x，则只要在第一次搜出的结果中二分出 \le \lfloor \dfrac{n}{x} \rfloor 的数个数即可。

但是如果就这么搜，还是会 TLE（在 Custom Test 中需要 7871 ms 才能跑的出来极限数据）。究其原因，还是因为后面那些大的质数其实根本跑不出来几个结果（只有 152097 个），而那些小的质数则有很多结果，不均衡。

如何解决？其实也很简单，把质数 random_shuffle 一下就可以做到相对的均衡了。这样极限数据也只需要跑 613ms。

lqy 神还有一种跑的很快的做法，供欣赏。

void init()
{
    random_shuffle(pr,pr+cnt+1);
}
void dfs(int x,int cur)
{
    if(x==cnt/2+1)
    {
        vis.pb(cur);return;
    }
    dfs(x+1,cur);
    while(cur<=n/pr[x])
    {
        dfs(x+1,(cur*=pr[x]));
    }
}
void dfs2(int x,int cur)
{
    if(x==cnt+1)
    {
        ans+=upper_bound(vis.begin(),vis.end(),n/cur)-vis.begin();
        return;
    }
    dfs2(x+1,cur);
    while(cur<=n/pr[x])
    {
        dfs2(x+1,(cur*=pr[x]));
    }
}

Ex

不会，咕。