8.18 S组-程皓楠-第五场补题

Crash_Man_CHN · 2025-08-19 11:38:43 · 个人记录

T1

错误

1. 考场思路混乱，有些情况判断错误，

解决方案：应当打好草稿再去写题

正确思路

其实只有三种情况，x<y,x>y,x==y,详情如下

x<y：
    说明x只有可能是比y小的正数/负数，如果是正数那么就是abs(y-x),反之就是先加到-y,在转，也就是abs(y+x)+1，最后把这两种情况取min

x>y：
    两种情况：abs(y+x)+1,abs(x-y)+2，取min即可

x==y：
    输出0，不需要变

很简单了吧，直接变红题

100pts code

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int x,y;
    cin>>x>>y;
    if(x<y)cout<<min(abs(y-x),abs(y+x)+1);
    else if(x>y)cout<<min(abs(y+x)+1,abs(x-y)+2);
    else cout<<0;
    return 0;
}

T2

AC

T3

通过画图找规律其实可以发现，很像斐波那契数列，那么40%的分数就拿到了，我们可以用记忆化搜索，这样的话，时间会更优，所以每次可以加上剪枝，若当前的值已经大于了最小值，可以直接return,反之若当前x与dp[i]相等直接dfs,然后取min即可

100pts code

 #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int dp[N],n=1e18,m;
void dfs(int x,int sum,int pre)
{
    if(sum+1>n)return ;
    if(x==1)
    {
        n=min(n,sum-1);
        return ;
    }
    for(int i=pre;i<=87&&dp[i]<=x;i++)
    {
        if(x%dp[i]==0)
        {
            dfs(x/dp[i],sum+(i+1),i);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    dp[1]=1,dp[2]=2;
    for(int i=3;i<=87;i++)dp[i]=dp[i-1]+dp[i-2];
    while(t--)
    {
        cin>>m;
        if(m==1)
        {
            cout<<"1\n";
            n=1e18;
            continue;
        }
        dfs(m,0,2);
        if(n==1e18)cout<<"0\n";
        else cout<<n<<"\n";
        n=1e18;
    }
    return 0;
}