首页 > 其他分享 >2024年2月6号题解

2024年2月6号题解

时间：2024-02-06 21:33:09浏览次数：35  
标签：high int 题解 ll ELEMENT 2024 low key

P2872 [USACO07DEC] Building Roads S

洛谷题目链接

解题思路

  1. 这个是一个最小生成树，把在平面直角坐标系中的点定义为顶点，把两个点的距离定义为边
  2. 但这个题目并没有给出图中的边，也就是两个点的距离，因此我们要把这个图的边给补上，这个平面直角坐标系的点的每条边都是图上的边。
  3. 但因为题目给了必须要包含的边，那么我们需要处理这些边，那么怎么让这些边一定在最小生成树中就成为了一个问题，解决方法就是把它的边的权重赋值为0。
  4. 但这个题有浮点数的问题，以此把答案乘以一个大的数来解决，在最后输出答案的时候在除以那个大的数，以此来解决浮点数的精度问题
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 1001

typedef struct {
	ll f;//从那个点
	ll t;//到那个点
	ll w;//边的权重
}p;

typedef p ELEMENT;

void quickSort(ELEMENT* a, int low, int high);
void swap(ELEMENT* a, int low, int high);//½»»»a[low]ºÍa[high]µÄÖµ 
int* partition(ELEMENT* a, int low, int high, ELEMENT key);//°ÑaÖÐlowµ½highµÄÊý°´ÕÕkey·ÖÀ࣬СÓÚkeyµÄÔÚ×ó±ß£¬µÈÓÚkeyµÄÔÚÖм䣬´óÓÚkeyµÄÔÚÓÒ±ß

int n;//n个点
int m;//m条边
int f[N];//并查集
ll a[N][2];//存放点
p b[N * N];
int size;//数组b的大小
ll c[2];//用来读边
ll ans;//最后的答案，通过乘法来避免浮点数

int find(int x) {
	if (x != f[x]) {
		f[x] = find(f[x]);
	}

	return f[x];
}

bool isSameSet(int a, int b) {
	return find(a) == find(b);
}

void unionSet(int a, int b) {
	f[find(a)] = find(b);
}

ll d(ll x1, ll y1, ll x2, ll y2) {//计算两个点的距离
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) * 100000;//通过乘以100000，来避免浮点数，如果精度还不够就换一个更大的数
}

int main(int argc, char* argv[])
{
	sc("%d%d", &n, &m);//读入点和边

	//初始化并查集
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}

	//读入每个点的坐标
	for (int i = 1; i <= n; i++) {
		sc("%lld%lld", a[i], a[i] + 1);
	}

	//给每个两个点都给一条边
	for (int i = 1; i < n; i++) {//因为是双向边，所以不用一直遍历同一个点，一共有Cn2条边
		for (int j = i + 1; j <= n; j++) {
			b[size].f = i;
			b[size].t = j;
			b[size].w = d(a[i][0], a[i][1], a[j][0], a[j][1]);
			size++;
		}
	}

	//把需要的边的权重赋值为0
	for (int i = 0; i < m; i++) {
		sc("%lld%lld", c, c + 1);
		b[size].f = c[0];
		b[size].t = c[1];
		b[size].w = 0;
		size++;
	}

	quickSort(b, 0, size - 1);//按照

	int cnt = 0;

	//最小生成树算法
	for (int i = 0; i < size && cnt < n - 1; i++) {
		if (!isSameSet(b[i].f, b[i].t)) {
			ans += b[i].w;
			unionSet(b[i].f, b[i].t);
			cnt++;
		}
	}

	//因为成了一个数，所以再除回去得到原本的答案
	pr("%.2lf", ans / 100000.0);

	return 0;
}

void quickSort(ELEMENT* a, int low, int high)
{
	int* p = NULL;//´æ´¢µÈÓÚ»ù×¼ÖµµÄ×óÓұ߽ç 

	if (low >= high) {//Èç¹ûÖ»ÓÐÒ»¸öÖµ²»ÓÃÅÅÐò¾ÍÖ±½Ó½áÊøÅÅÐò 
		return;
	}

	p = partition(a, low, high, a[low + rand() % (high - low + 1)]);//pÖ¸ÏòµÈÓÚ»ù×¼ÖµÇø¼ä×óÓұ߽ç 
	quickSort(a, low, p[0] - 1);//Ö»ÅÅСÓÚ»ù×¼ÖµµÄ²¿·Ö 
	quickSort(a, p[1] + 1, high);//Ö»ÅÅ´óÓÚ»ù×¼ÖµµÄ²¿·Ö
	free(p);//Êͷŵô¿ª±ÙµÄ¿Õ¼ä 
}
void swap(ELEMENT* a, int low, int high)
{
	ELEMENT t = { 0 };

	t = a[low];
	a[low] = a[high];
	a[high] = t;
}
int* partition(ELEMENT* a, int low, int high, ELEMENT key)
{
	int l = low;//´ú±íµÈÓÚkeyÇø¼äµÄ×ó±ß½ç,»òÕßÊÇСÓÚÇø¼äµÄÏÂÒ»¸öÊý  
	int r = high;//´ú±íµÈÓÚkeyÇø¼äµÄÓұ߽ç,»òÕßÊÇ´óÓÚÇø¼äµÄÏÂÒ»¸öÊý  
	int i = low;//´ÓÍ·¿ªÊ¼±éÀú 

	while (i <= r) {//ֻҪûÓе½´óÓÚÇø¼ä 
		if (a[i].w < key.w) {//ϱêiµÄÊýСÓÚ»ù×¼Öµ£¬·ÅÔÚ×ó±ß½çÀïÃæ 
			swap(a, l++, i++);//°Ñ×ó±ß½çµÄºóÒ»¸öÊýºÍϱêiµÄÖµ½»»»£¬È»ºó×óÇø¼äÀ©ÕÅ£¬È»ºóÈ¥¿´ÏÂÒ»¸öÊý 
		}
		else  if (a[i].w > key.w) {//ϱêiµÄÊý´óÓÚ»ù×¼Öµ£¬·ÅÔÚÓұ߽çÀïÃæ 
			swap(a, r--, i);//°ÑÓұ߽çµÄÇ°Ò»¸öÊýºÍϱêiµÄÖµ×ö½»»»£¬È»ºóÓÒÇø¼äÀ©ÕÅ£¬µ«i²»Äܶ¯£¬ÒòΪµ±Ç°iµÄÖµ»¹Ã»ÓзÃÎʹý 
		}
		else {//ϱêiµÄÊýµÈÓÚ»ù×¼Öµ£¬·ÅÔÚ×óÓұ߽çÖ®¼ä 
			i++;//Ö±½Ó¼Ó1
		}
	}
	int* p = (int*)malloc(sizeof(int) * 2);//´æ·ÅµÈÓÚÇø¼äµÄ×óÓұ߽ç 
	p[0] = l;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇl
	p[1] = r;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇr
	return p;//·µ»ØµÈÓÚkeyÇø¼äµÄ×óÓұ߽ç 
}

P1991 无线通讯网

洛谷题目链接

解题思路

  1. 这个题目需要我们把每个点到其他点的距离求出来，然后用最小生成树算法，和上面的题目边的构建是一样的
  2. 但这个题目的答案同样也要浮点数，因此我们用整数代替浮点数来进行转换，以此来避免精度问题
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 501

typedef struct {
	ll f;
	ll t;
	ll w;
}po;

typedef po ELEMENT;

void quickSort(ELEMENT* a, int low, int high);
void swap(ELEMENT* a, int low, int high);//½»»»a[low]ºÍa[high]µÄÖµ 
int* partition(ELEMENT* a, int low, int high, ELEMENT key);//°ÑaÖÐlowµ½highµÄÊý°´ÕÕkey·ÖÀ࣬СÓÚkeyµÄÔÚ×ó±ß£¬µÈÓÚkeyµÄÔÚÖм䣬´óÓÚkeyµÄÔÚÓÒ±ß

int s, p;//s是卫星电话的数量，p是边防哨所的数量 
ll a[N][2];//存放每个边防哨所的数量 
po b[N * N];//存放边 
int size;//数组b的大小   
int cnt;//选的边数 
ll ans;//答案 
int f[N];//并查集 

int find(int x) {
	if (x != f[x]) {
		f[x] = find(f[x]);
	}

	return f[x];
}

bool isSameSet(int a, int b) {
	return find(a) == find(b);
}

void unionSet(int a, int b) {
	f[find(a)] = find(b);
}

//计算两点之间的距离 
ll d(ll x1, ll x2, ll y1, ll y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) * 100000;//通过乘以一个数来避免浮点数问题
}

int main(int argc, char* argv[])
{
	sc("%d%d", &s, &p);

	//读入每个点的坐标 
	for (int i = 1; i <= p; i++) {
		sc("%d%d", a[i], a[i] + 1);
	}

	for (int i = 1; i <= p; i++) {
		f[i] = i;
	}

	//把每条边计算出来，因为是双向边，所以j = i + 1开始算，不然就会重复计算
	for (int i = 1; i < p; i++) {
		for (int j = i + 1; j <= p; j++) {
			b[size].f = i;
			b[size].t = j;
			b[size].w = d(a[i][0], a[j][0], a[i][1], a[j][1]);
			size++;
		}
	}

	//按边的权重升序排序 
	quickSort(b, 0, size - 1);

	//最小生成树算法，但要减去s + 1条边，因为s个卫星电话可以少一条边
	for (int i = 0; i < size && cnt < p - 1 - s + 1; i++) {
		if (!isSameSet(b[i].f, b[i].t)) {
			if (b[i].w > ans) {
				ans = b[i].w;
			}
			unionSet(b[i].t, b[i].f);
			cnt++;
		}
	}

	pr("%.2lf", ans / 100000.0);//因为之前乘了一个数所以再除以这个数得到原本的答案

	return 0;
}

void quickSort(ELEMENT* a, int low, int high)
{
	int* p = NULL;//´æ´¢µÈÓÚ»ù×¼ÖµµÄ×óÓұ߽ç 

	if (low >= high) {//Èç¹ûÖ»ÓÐÒ»¸öÖµ²»ÓÃÅÅÐò¾ÍÖ±½Ó½áÊøÅÅÐò 
		return;
	}

	p = partition(a, low, high, a[low + rand() % (high - low + 1)]);//pÖ¸ÏòµÈÓÚ»ù×¼ÖµÇø¼ä×óÓұ߽ç 
	quickSort(a, low, p[0] - 1);//Ö»ÅÅСÓÚ»ù×¼ÖµµÄ²¿·Ö 
	quickSort(a, p[1] + 1, high);//Ö»ÅÅ´óÓÚ»ù×¼ÖµµÄ²¿·Ö
	free(p);//Êͷŵô¿ª±ÙµÄ¿Õ¼ä 
}
void swap(ELEMENT* a, int low, int high)
{
	ELEMENT t = { 0 };

	t = a[low];
	a[low] = a[high];
	a[high] = t;
}
int* partition(ELEMENT* a, int low, int high, ELEMENT key)
{
	int l = low;//´ú±íµÈÓÚkeyÇø¼äµÄ×ó±ß½ç,»òÕßÊÇСÓÚÇø¼äµÄÏÂÒ»¸öÊý  
	int r = high;//´ú±íµÈÓÚkeyÇø¼äµÄÓұ߽ç,»òÕßÊÇ´óÓÚÇø¼äµÄÏÂÒ»¸öÊý  
	int i = low;//´ÓÍ·¿ªÊ¼±éÀú 

	while (i <= r) {//ֻҪûÓе½´óÓÚÇø¼ä 
		if (a[i].w < key.w) {//ϱêiµÄÊýСÓÚ»ù×¼Öµ£¬·ÅÔÚ×ó±ß½çÀïÃæ 
			swap(a, l++, i++);//°Ñ×ó±ß½çµÄºóÒ»¸öÊýºÍϱêiµÄÖµ½»»»£¬È»ºó×óÇø¼äÀ©ÕÅ£¬È»ºóÈ¥¿´ÏÂÒ»¸öÊý 
		}
		else  if (a[i].w > key.w) {//ϱêiµÄÊý´óÓÚ»ù×¼Öµ£¬·ÅÔÚÓұ߽çÀïÃæ 
			swap(a, r--, i);//°ÑÓұ߽çµÄÇ°Ò»¸öÊýºÍϱêiµÄÖµ×ö½»»»£¬È»ºóÓÒÇø¼äÀ©ÕÅ£¬µ«i²»Äܶ¯£¬ÒòΪµ±Ç°iµÄÖµ»¹Ã»ÓзÃÎʹý 
		}
		else {//ϱêiµÄÊýµÈÓÚ»ù×¼Öµ£¬·ÅÔÚ×óÓұ߽çÖ®¼ä 
			i++;//Ö±½Ó¼Ó1
		}
	}
	int* p = (int*)malloc(sizeof(int) * 2);//´æ·ÅµÈÓÚÇø¼äµÄ×óÓұ߽ç 
	p[0] = l;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇl
	p[1] = r;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇr
	return p;//·µ»ØµÈÓÚkeyÇø¼äµÄ×óÓұ߽ç 
}

 

标签：high,int,题解,ll,ELEMENT,2024,low,key
From： https://www.cnblogs.com/lwj1239/p/18009241

相关文章

  • 题解 AT_exawizards2019_e【Black or White】
    设\(P_b(k),P_w(k)\)表示已经吃了\(k\)块巧克力，把所有黑/白巧克力都吃光了的概率。枚举最后一块黑/白巧克力被吃的时间，容易得到：\[\begin{aligned}P_b(k)&=\sum_{i=1}^k\frac{\binom{i-1}{b-1}}{2^i}\\P_w(k)&=\sum_{i=1}^k\frac{\binom{i-1}{w-1}}{2^i}\\\end{aligned}\]......
  • (C语言)代码学习||2024.2.6||题目是codewars上的【 IP Validation】
    C语言#sscanf#代码学习#codewars题目链接：IPValidation|Codewars代码如下：#include<stdio.h>intis_valid_ip(constchar*addr){unsignedn[4],i,nc;//Mustbe4integersseparatedbydots:if(sscanf(addr,"%d.%d.%d.%d%n",&n[0],&n......
  • 2024.2.6每日一题
    LeetCode魔塔游戏LCP30.魔塔游戏-力扣（LeetCode）题目描述小扣当前位于魔塔游戏第一层，共有N个房间，编号为0~N-1。每个房间的补血道具/怪物对于血量影响记于数组nums，其中正数表示道具补血数值，即血量增加对应数值；负数表示怪物造成伤害值，即血量减少对应数值；0表示房间对血量......
  • BeginCTF 2024（自由赛道）
    哈哈哈最后的排名Miscrealcheckin得到题目给了一段密文MJSWO2LOPNLUKTCDJ5GWKX3UN5PUEM2HNFXEGVCGL4ZDAMRUL5EDAUDFL5MU6VK7O5UUYMK7GEYWWZK7NE3X2===base32解码得到flag所以flag为：begin{WELCOMe_to_B3GinCTF_2024_H0Pe_YOU_wiL1_11ke_i7}whereiscrazymanv1.0拿......
  • 2024.2.6
    1.Java不支持多继承但支持多重继承2.继承的特性·子类拥有父类非private的属性、方法·子类可以拥有自己的属性和方法，即子类可以对父类进行扩展·Java的继承是单继承，但是可以多重继承，单继承就是一个子类只能继承一个父类，多重继承就是，例如B类继承A类，C类继承B类，所以按照关系就......
  • 【愚公系列】2024年02月 WPF控件专题 Frame控件详解
    ......
  • Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contes
    JapanRegistryServices(JPRS)ProgrammingContest2024(AtCoderBeginnerContest339)A-TLD代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__......
  • L3HCTF 2024 -Cry部分
    babySPNK=[0,1,1,0,1,0,1,0,1,1,0,1,1,0,0,1,0,1,0,1,0,0,0,0,1,0,1,0,0,0,1,0]给了k，按照代码逻辑直接跑，非预期。K=[0,1,1,0,1,0,1,0,1,1,0,1,1,0,0,1,0,1,0,1,0,0,0,0,1,0,1,0,0,0,1,0]hash_value=sh......
  • 博主项目经验-至2024
    讯飞内部vue2+vue3后管开发项目集合。一．讯飞医疗，AI能力演示平台，vue2项目。项目技术栈：Vue2+elementui+vuex+vue-router优化项目代码，包括axios二次封装，使用axios拦截器，统一报错处理，登录校验等等。使用Nginx转发翻译服务，声纹识别，自然语言理解服务。语音识别使用websocket完成......
  • 【题解】P5907 数列求和加强版 / P4948 数列求和
    本题解是对warzone的题解的补充。题意：求\[\sum_{i=1}^ni^ka^i\]普通版：\(k\leq2\times10^3\)。加强版：\(k\leq10^7\)。首先先考虑普通版。\[\begin{aligned}\sum_{i=1}^ni^ka^i&=\sum_{i=1}^na^i\sum_{j=0}^k{k\bracej}i^{\underline{j}}\\&=\sum_{j=0......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99