蓝桥杯官网试题 PREV-251 历届真题补给【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法

72 阅读 0 评论 48 点赞

我是靠谱客的博主无聊月饼，最近开发中收集的这篇文章主要介绍蓝桥杯官网试题 PREV-251 历届真题补给【第十一届】【决赛】【研究生组】【C++】【C】【Java】【Python】四种解法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

为帮助大家能在6月18日的比赛中有一个更好的成绩，我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。

今年的最大目标就是能为【一亿技术人】创造更高的价值。

资源限制：

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

C++

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define sz(a) (int)a.size()
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
#define endl "n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
const int maxn=22;
int dis[maxn][maxn];
int px[maxn],py[maxn];
ll n,d;
int calc(int a,int b)
{
	ll dis=(px[a]-px[b])*(px[a]-px[b])+(py[a]-py[b])*(py[a]-py[b]);
	// dd(dis);de(d*d);
	if(d*d<dis)return 1e9;
	else return sqrt(dis)*10000;
}
const int maxm=(1<<20);
int dp[maxm][maxn];
int main()
{
	cin>>n>>d;
	for(int i=0;i<n;i++)
	{
		cin>>px[i]>>py[i];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			dis[i][j]=calc(i,j);
			// dd(i);dd(j);de(dis[i][j]);
		}
	}
	for(int k=0;k<n;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	int tmp=(1<<n)-1;
	for(int i=0;i<=tmp;i++)
	{
		for(int j=0;j<n;j++)//j is last visit
		{
			if(((i>>j)&1)==0)continue;
			for(int k=0;k<n;k++)
			{
				if(((i>>k)&1)==0)continue;
				// dd(i);dd(j);de(k);
				// dd(dp[i][j]);dd(dp[i-(1<<k)][k]);de(dis[k][j]);
				dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+dis[k][j]);
				// de(dp[i][j]);
			}
		}
	}
	int ans=1e9;
	
	for(int i=0;i<n;i++)
	{
		ans=min(ans,dp[tmp][i]+dis[i][0]);
	}
	printf("%.2lf",1.0*ans/10000.0);
	return 0;
}

Java

import java.util.*;

public class Main{

    public static double getDistance(int[] point1, int[] point2) {
        int x_diff = point1[0] - point2[0];
        int y_diff = point1[1] - point2[1];

        return Math.sqrt(x_diff * x_diff + y_diff * y_diff);
    }

    public static void main(String[] args) {
        final double INF = 1e9;
        Scanner sc = new Scanner(System.in);
        String[] firstLine = sc.nextLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int D = Integer.parseInt(firstLine[1]);

        int[][] points = new int[n][2];

        for (int i = 0; i < n; i++) {
            String[] line = sc.nextLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            points[i][0] = x;
            points[i][1] = y;
        }

        double[][] distances = new double[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                double distance = getDistance(points[i], points[j]);
                if (distance > D) {
                    distances[i][j] = INF;
                    distances[j][i] = INF;
                } else {
                    distances[i][j] = distance;
                    distances[j][i] = distance;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
                }
            }
        }

        double[][] f = new double[1 << n][n];
        for (int i = 0; i < 1 << n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j] = INF;
            }
        }
        f[1][0] = 0;

        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) != 0) {        // i的比特位 里面包含 j
                    for (int k = 0; k < n; k++) {
                        if ((((i - (1 << j)) >> k) & 1) != 0) {     //  i 的比特位去掉 j 后包含k
                            f[i][j] = Math.min(f[i][j], f[i - (1 << j)][k] + distances[k][j]);
                        }
                    }
                }
            }
        }

        double ans = INF;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, f[(1 << n) - 1][i] + distances[i][0]);
        }

        System.out.println(String.format("%.2f", ans));

    }
}