T1

错误

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

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

正确思路

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

CPP

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

CPP

#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

T3

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

100pts code

CPP

 #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;
}

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

文章操作

T1

错误

正确思路

100pts code

T2

T3

100pts code

相关推荐

评论

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