洛谷 B3925 题解

sunyizhe · 2024-02-01 22:48:26 · 题解

零、前言

注意：本题解非正常思路，若要正解请移步到其他题解。

有 OIer 云：暴力出奇迹，打表出省一。这题感觉打表好题。

一、思路

1.1 写出暴力程序

这就很简单了，只要从 1 开始无限枚举，若成功则 break。代码中 n 为题目中 N，m 为题目中 i。

//云剪贴板维护，只能把代码贴在文中了qwq
#include <bits/stdc++.h>
using namespace std;

int n,m;

bool check(int x)
{
    for(int rnd=1;rnd<=n;rnd++)
    {
        if(x==0)return false;//判断是否有鱼吃
        int r=x%n;//计算本轮扔掉的鱼i
        if(r!=m)return false;
        //cout<<(x-r)/n<<' ';
        x-=m;//坑点：要减去余数
        x=x-x/n;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i=1;;i++)
    {
        if(check(i))
        {
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

轻松 90 pts。

1.2 打表

我们一看数据范围：0<N<10，i<N。这么小？我们自然想到用 for 枚举所有的 N 和 i，搞出所有的数据答案。打表程序可以通过魔改上面的代码自行写出。可以得到二维的 ans。最后输入 N 和 i，输出对应答案即可。

二、代码

注意：代码中因为我没有用 0 把 ans_{0,1 \sim n} 占位，所以输出时其实输出的是 ans_{n-1,m}。

//程序算法：枚举
#include <bits/stdc++.h>
using namespace std;

int n,m,ans[20][20]={
{1,0,0,0,0,0,0,0,0},
{4,7,0,0,0,0,0,0,0},
{27,25,23,0,0,0,0,0,0},
{256,253,250,247,0,0,0,0,0},
{3125,3121,3117,3113,3109,0,0,0,0},
{46656,46651,46646,46641,46636,46631,0,0,0},
{823543,823537,823531,823525,823519,823513,823507,0,0},
{16777216,16777209,16777202,16777195,16777188,16777181,16777174,16777167,0},
{387420489,387420481,387420473,387420465,387420457,387420449,387420441,387420433,387420425},
};

void fast_read()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);

    fast_read();

    cin>>n>>m;
    cout<<ans[n-1][m]<<endl;

    return 0;
}

打表抢到最优解，与第二名相差 50ms。暴力出奇迹，打表出省一。