8.18test

kamikuQAQ · 2025-08-19 22:08:02 · 个人记录

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的花费

#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个斐波那契数之间所以可以用最优性剪枝搜索

#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