本文共 1663 字，大约阅读时间需要 5 分钟。

Powered by:AB_IN 局外人

Problem A

$m$的数据范围比较小，全排列即可。利用$b$数组作为下标，用$b$数组进行全排列操作。

#include <bits/stdc++.h>#define  ll long longusing namespace std;const int N=1e6+10;struct sa{       ll x;    ll y;}a[N];ll b[N];ll t,n,m;int main(){       cin>>t;    while(t--){           cin>>n>>m;        for(int i=1;i<=m;i++) b[i]=i;        for(int i=1;i<=m;i++){               cin>>a[i].x>>a[i].y;        }        ll ans=0x3f3f3f3f;        do{               ll sum=0;            for(int i=1;i<m;i++){                   sum+=abs(a[b[i]].x-a[b[i+1]].x);                sum+=abs(a[b[i]].y-a[b[i+1]].y);            }            ans=min(sum,ans);        }while(next_permutation(b+1,b+1+m));        cout<<ans<<endl;    }    return 0;}

Problem B

首先，$fibs$到89项左右数据就到了接近$1e18$了。这个题就是找一个数能不能被拆成$fibs$的任意几项，每一项可以无限次使用。看到这，其实就是相当于一个完全背包的思想，但$fibs$数列中有数值$1$，我们可以好好把握这个条件，就不用写个背包了。

先利用二分把最接近$n$的数找出来，然后不停二分，直到$n=0$，共$cnt$个数。所以如果$k$在$[cnt,n]$之间，那么都是$yes$。为什么呢？因为既可以利用$fibs$的特性，把一个数拆成两个数，（例如：13=5+8），又可以充分利用$1$来补全。

#include <bits/stdc++.h>using namespace std;int t;long long n,k;long long a[100];int main(){       a[1]=1;a[2]=2;    for(int i=3;i<90;i++)        a[i]=a[i-1]+a[i-2];    scanf("%d",&t);    while(t--)    {           scanf("%lld%lld",&n,&k);        if(k>n){               printf("No\n");            continue;        }        long long emm,cnt=0,tmp=n;        while(n){               emm=upper_bound(a+1,a+89,n)-a-1;            n-=a[emm];            cnt++;        }        if(k>=cnt && k<=tmp) printf("Yes\n");        else printf("No\n");    }    return 0;}

完结。