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("="); } }
签到题混抽奖,可惜没中......看来卑微的我只能靠牛币了硬肝了