T1

实际上并非T1，因为根本不送分，一个小时才拿了50分不写正解if判断写死
事实上只需要判断a和b的大小
对于a>b时，如果同号我们都需要先把a变成负数再不断+1，所以答案为abs(a+1+b),如果不同号我们有两种选择，像上面一样或者先反过来再让两者绝对值相等再反过来，花费为abs(x-y)+2
同理，对于a<b时同号需要有b-a的花费，异号的时候需要abs(a+b)+1的花费

CPP

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int x,y;
	cin>>x>>y;
	if(x==y) {
		cout<<0;
	} else if(x<y) {
		cout<<min(abs(x+y)+1,abs(y-x));
	} else if(x>y) {
		cout<<min(abs(x+y)+1,abs(x-y)+2);
	}
	return 0;
}

T2

真正的T1来了
首先最简单的思路就是枚举三个数一直枚举
然后我们发现确定了两个数就可以确定第三个数的范围，并且a<=b<=c，也就是说明a×a×a<=a×b×b<=a×b×c<=n,这样枚举又省了时间
注意开longlong

T3

如果没有障碍，那么答案一定会是一个斐波那契数，于是就可以拿到部分分
如果障碍横向放置，那么竖着的就只有一种摆法，塞一个1*2

但如果竖向放置，方案数就变成了左边×右边，题目要求最多的方案数所以尽可能竖向放置

于是题意就变成了多个斐波那契数乘使等于m，由于longlong范围在第87个斐波那契数之间所以可以用最优性剪枝搜索

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 105;
int dp[maxn];
int m;
int minn=2e9;
void dfs(int pos,int sum,int pre) {
	if(sum>minn+1) {
		return;
	}
	if(pos==1) {
		minn=min(sum-1,minn) ;
		return;
	}
	for(int i=pre;i<=87&&dp[i]<=pos;i++) {
		if(pos%dp[i]==0) {
			dfs(pos/dp[i],sum+i+1,i);
		}
	}
	return;
}
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";
			continue;
		}
		dfs(m,0,2);
		if(minn==2e9) {
			cout<<0<<endl;
		} else {
			cout<<minn<<"\n";
		} 
		minn=2e9;
	}
	return 0;
}
//1 1 2 3 5 8

8.18test

文章操作

T1

T2

T3

相关推荐

评论

8.18test