牛客算法周周练7A和E

https://ac.nowcoder.com/acm/contest/5713/A
题意：给定物品坐标与初始坐标，求收集完所有物品再回来的最短路径

分析：看一下题目数据，最多只有10张卡片，数据很小直接枚举就行了，用dfs全排列搜索，记录每个方式的路径，取最小值即可。复杂度O(10!)

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int i,j,ans,n,k,t,x,y,sx,sy;
int a[15],b[15],vis[15];
void dfs(int now,int cnt,int sum){
    if(cnt==n){
        sum=sum+abs(a[now]-sx)+abs(b[now]-sy);
        if(sum<ans){
            ans=sum;
        }
        return;
    }
    else{
        for(int i=1;i<=n;i++){
            if(vis[i]==0){
                vis[i]=1;
                sum+=(abs(a[i]-a[now])+abs(b[i]-b[now]));
                dfs(i,cnt+1,sum);
                sum-=(abs(a[i]-a[now])+abs(b[i]-b[now]));
                vis[i]=0;
            }
        }
    }
}
int main()
{
    scanf("%d",&t);
    while(t--){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(vis,0,sizeof(vis));
        ans=inf;
        scanf("%d%d%d%d",&x,&y,&sx,&sy);
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d%d",&a[i],&b[i]);
        }
        a[0]=sx;
        b[0]=sy;
        dfs(0,0,0);
        printf("The shortest path has length %d\n",ans);
    }
}

https://ac.nowcoder.com/acm/contest/5713/E

题意：比较x^y与y^x的大小关系。

分析：数据大小为1e9，显然直接算数据溢出，无法准确比较，那么我们不妨转化一下问题，比较大小，我们可以比较x^y/y^x是否大于1，如果x^y>y^x,则x^y/y^x>1，两边同时取log（10）得lg(x^y/y^x)>0,变换一下得到:ylgx-xlgy>0，所以问题转化为判断ylgx-xlgy与0之间的关系，大于0就>,小于0就<,等于0就=。

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int i,j,ans,n,k,x,y;
int main()
{
    scanf("%d%d",&x,&y);
    if(x==y){
        printf("=");
    }
    else if(y*log10(x)-x*log10(y)>0){
        printf(">");
    }else if(y*log10(x)-x*log10(y)<0){
        printf("<");
    }else{
        printf("=");
    }
}

签到题混抽奖，可惜没中......看来卑微的我只能靠牛币了硬肝了