首页 > 其他分享 >2024年3月18号题解

2024年3月18号题解

时间：2024-03-19 22:57:48浏览次数：24  
标签：index int 题解 2024 ++ 18 MinHeap include define

Dungeon Master

解题思路

  1. 给格子编号，从1开始，这样我们就可以构建一个图
  2. 对这个图跑迪杰斯特拉算法就可以得到我们需要的答案

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.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 1000000

typedef struct {
	int from;
	int distance;
}ELEMENT;

typedef struct heap {
	ELEMENT* data;//´æ·ÅÔªËصÄÊý×é 
	int size;//×îС¶ÑÖеÄÔªËظöÊý 
	int maxSize;//¶ÑÖÐ×î¶àÄܹ»ÈÝÄɵÄÔªËظöÊý 
}minHeap, * MinHeap;

MinHeap createMinHeap(int n);//´´½¨Ò»¸ö×î¶àÄܹ»ÈÝÄÉn¸öÔªËصÄ×îС¶Ñ 
int MinHeapSize(MinHeap h);//·µ»Ø×îС¶ÑµÄÔªËظöÊý 
bool isMinHeapFull(MinHeap h);//ÅжÏ×îС¶ÑÊDz»ÊÇÂúÁË 
bool addMinHeap(MinHeap h, ELEMENT item);//Íù×îС¶ÑÀïÃæÌí¼ÓÔªËØitem
ELEMENT deleteMinHeap(MinHeap h);//µ¯³ö×îС¶ÑµÄ¶Ñ¶¥ÔªËØ 
void MinHeapInsert(MinHeap h, int index);//ÔÚ×îС¶ÑindexλÖÃнøÀ´Ò»¸öÔªËØ£¬ËùÒÔÒªÏòÉϵ÷Õû£¬À´ÈöÑÈÔÈ»ÊÇÒ»¸ö×îС¶Ñ 
void MinHeapify(MinHeap h, int index);//ÔÚ×îС¶ÑindexλÖõÄÔªËرäСÁË£¬ËùÒÔÏòϵ÷Õû¶Ñ£¬À´ÈöÑÈÔÈ»ÊÇÒ»¸ö×îС¶Ñ 
bool isMinHeapEmpty(MinHeap h);//ÅжÏ×îС¶Ñ¿ÕÁËûÓÐ 
void swap(MinHeap h, int i, int j);//½»»»×îС¶ÑÖÐiºÍjλÖõÄÔªËØ 
int MinHeapCompare(ELEMENT a, ELEMENT b);//»ùÓÚijÖйæÔòÀ´±È½Ï,ÀàËÆÓë±È½ÏÆ÷ 
void freeMinHeap(MinHeap h);//ÊÍ·Å×îС¶ÑµÄ¿Õ¼ä 
ELEMENT peekMinHeap(MinHeap h);//µÃµ½×îС¶ÑÖеĶѶ¥ÔªËØ 

int head[N];
int w[2 * N];
int next[2 * N];
int to[2 * N];
int cnt = 1;
char s[31][31][31];
int dist[N];
bool v[N];
int l, r, c;
int start = 1;
int end = 1;
int num;
int to1;

void build();
void add(int s, int e, int v);

int main(int argc, char* argv[])
{
	while (sc("%d%d%d", &l, &r, &c), l != 0 || r != 0 || c != 0) {
		build();
		for (int i = 0; i < l; i++) {
			for (int j = 0; j < r; j++) {
				sc("%s", s[i][j]);
				for (int k = 0; k < c; k++) {
					if (s[i][j][k] == 'S') {
						start = i * r * c + j * c + k + 1;
					}
					else if (s[i][j][k] == 'E') {
						end = i * r * c + j * c + k + 1;
					}
				}
			}
		}

		for (int i = 0; i < l; i++) {
			for (int j = 0; j < r; j++) {
				for (int k = 0; k < c; k++) {
					if (s[i][j][k] != '#') {
						num = i * r * c + j * c + k + 1;

						if (j - 1 >= 0 && s[i][j - 1][k] != '#') {//bei
							to1 = num - c;
							add(num, to1, 1);
						}
						if (j + 1 < r && s[i][j + 1][k] != '#') {//nan
							to1 = num + c;
							add(num, to1, 1);
						}
						if (k + 1 < c && s[i][j][k + 1] != '#') {//dong
							to1 = num + 1;
							add(num, to1, 1);
						}
						if (k - 1 >= 0 && s[i][j][k - 1] != '#') {//xi
							to1 = num - 1;
							add(num, to1, 1);
						}
						if (i - 1 >= 0 && s[i - 1][j][k] != '#') {//shang
							to1 = num - (r * c);
							add(num, to1, 1);
						}
						if (i + 1 < l && s[i + 1][j][k] != '#') {
							to1 = num + (r * c);
							add(num, to1, 1);
						}
					}
				}
			}
		}

		/*for (int i = 1; i <= l * r * c; i++) {
			pr("%d:\n", i);
			for (int j = head[i]; j; j = next[j]) {
				pr("%d\t", to[j]);
			}
			pr("\n");
		}*/

		MinHeap h = createMinHeap(cnt);

		dist[start] = 0;

		ELEMENT t = { start, 0 };

		addMinHeap(h, t);

		while (!isMinHeapEmpty(h)) {
			t = deleteMinHeap(h);

			if (!v[t.from]) {
				for (int i = head[t.from]; i; i = next[i]) {
					to1 = to[i];

					if (!v[to1] && t.distance + w[i] < dist[to1]) {
						dist[to1] = t.distance + w[i];
						ELEMENT temp = { to1, dist[to1] };
						addMinHeap(h, temp);
					}
				}
			}
			v[t.from] = 1;
		}

		if (dist[end] != INT_MAX) {
			pr("Escaped in %d minute(s).\n", dist[end]);
		}
		else {
			pr("Trapped!\n");
		}

		freeMinHeap(h);
	}

	return 0;
}

void add(int s, int e, int v)
{
	next[cnt] = head[s];
	w[cnt] = v;
	to[cnt] = e;
	head[s] = cnt++;
}

void build()
{
	cnt = 1;
	for (int i = 0; i <= l * r * c; i++) {
		head[i] = 0;
		dist[i] = INT_MAX;
		v[i] = 0;
	}
}

MinHeap createMinHeap(int n)
{
	MinHeap h = (MinHeap)malloc(sizeof(minHeap));//¿ª±ÙÒ»¸ö×îС¶Ñ 

	h->data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//¿ª±ÙÒ»¸ön¸ö¿Õ¼äµÄELEMENTÊý×é 
	h->size = 0;//³õʼ»¯×îС¶ÑÔªËØÊÇ0 
	h->maxSize = n;//×îС¶ÑÄÜ´æ·Å×î´óÔªËصĸöÊýÊÇn 

	return h;//·µ»Ø×îС¶Ñ 
}
int MinHeapSize(MinHeap h)
{
	return h->size;//·µ»Ø×îС¶ÑÖеÄÔªËظöÊý 
}
bool isMinHeapFull(MinHeap h)
{
	return h->size == h->maxSize;//Èç¹û×îС¶ÑÖеÄÔªËظöÊýµÈÓÚÄܹ»ÈÝÄɵÄ×î´óÔªËظöÊý£¬ÄÇôÂúÁË 
}
bool addMinHeap(MinHeap h, ELEMENT item)
{
	if (isMinHeapFull(h)) {//Èç¹û×îС¶ÑÒѾ­ÂúÁË£¬ÄÇô¾Í²»ÄÜÌí¼ÓÔªËØÁË£¬·µ»Øfalse 
		return false;
	}

	h->data[h->size] = item;//°Ñitem·ÅÔÚ×î϶ÑÖÐÔªËظöÊýµÄϱêÖÐ,ÒòΪԪËظöÊýµÄϱê¾ÍÊÇÒª·ÅµÄλÖà 
	MinHeapInsert(h, h->size);//ÒòΪ¸Õ¸ÕнøÀ´Ò»¸öÔªËØ£¬ËùÒÔÏëÈöѼÌÐø±£³Ö×îС¶Ñ£¬ÄÇô¾ÍÐèÒªÏòÉϵ÷Õû¶Ñ 
	h->size++;//ÈÃ×îС¶ÑÖеÄÔªËظöÊý¼ÓÒ» 

	return true;//Ìí¼Ó³É¹¦·µ»Øtrue 
}
ELEMENT deleteMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//Èç¹û×îС¶ÑÖÐûÓÐÔªËØ£¬ÄÇô²»ÄܽøÐÐɾ³ý£¬Î¥·¨·µ»ØÒ»¸öÌض¨µÄÖµ£¬¼´ERROR 
		ELEMENT t = { 0 };

		return t;
	}

	ELEMENT ans = h->data[0];//·µ»Ø×îС¶ÑÖеĶѶ¥ÔªËØ 
	swap(h, 0, --h->size);//°Ñ×îС¶ÑÖеÄ×îºóÒ»¸öÔªËØÓë¶Ñ¶¥ÔªËؽøÐн»»»£¬²¢ÇÒÈöÑÖÐÔªËؼõÒ»£¬ÄÇô¾Í·ÃÎʲ»µ½¸Õ¸Õ±»É¾³ýµÄÔªËØÁË¡£ 
	MinHeapify(h, 0);//ϱê0λÖõÄÔªËرä´óÁË£¬ÄÇôΪÁ˼ÌÐø±£³ÖÒ»¸ö×îС¶Ñ£¬¾ÍÒªÏòϵ÷Õû 

	return ans;//·µ»Ø×îС¶ÑÖеĶѶ¥ÔªËØ 
}
void MinHeapInsert(MinHeap h, int index)//indexλÖõÄÊýÏòÉϵ÷ÕûС¸ù¶Ñ 
{
	while (MinHeapCompare(h->data[index], h->data[(index - 1) / 2]))//Èç¹ûϱêindexµÄֵСÓÚËüµÄ¸¸½Úµã 
	{
		swap(h, index, (index - 1) / 2);//ϱêindexµÄÖµºÍËüµÄ¸¸½ÚµãµÄÖµ½»»» 
		index = (index - 1) / 2;//¸üÐÂindexµÄλÖà 
	}
}
bool isMinHeapEmpty(MinHeap h)
{
	return !h->size;//Èç¹û×îС¶ÑÖеÄÔªËØÊÇ0¸ö£¬ÄÇô¾ÍÊÇ¿Õ£¬ÓÐÔªËؾͲ»ÊÇ¿Õ 
}
void swap(MinHeap h, int i, int j)
{
	ELEMENT t = h->data[i];
	h->data[i] = h->data[j];
	h->data[j] = t;
}
void MinHeapify(MinHeap h, int index)
{
	int left = 2 * index + 1;//¼ÆËãϱêindexµÄ×óº¢×Ó 

	while (left < h->size) {//Èç¹ûÓк¢×Ó 
		int lessest = left + 1 < h->size && MinHeapCompare(h->data[left + 1], h->data[left]) ? left + 1 : left;//Èç¹ûÓÐÓÒº¢×Ó²¢ÇÒÓÒº¢×ÓСÓÚ×óº¢×Ó£¬ÄÇôº¢×ÓÖÐ×îСµÄ¾ÍÊÇÓÒº¢×Ó£¬·ñÔò¾ÍÊÇ×óº¢×Ó 

		lessest = MinHeapCompare(h->data[index], h->data[lessest]) ? index : lessest;//Èç¹û¸¸Ç×½Úµã±Èº¢×ÓÖÐ×îСµÄ»¹ÒªÐ¡£¬ÄÇô×îСµÄ½Úµã¾ÍÊǸ¸½Úµã£¬²»È»×îСµÄ½Úµã¾ÍÊǺ¢×ÓÖÐ×îСµÄ½Úµã 

		if (lessest == index) {//Èç¹û×îСµÄ½ÚµãÊǸ¸½Úµã£¬ÄÇô²»ÓüÌÐøÁË£¬ÒѾ­ÊÇ×îС¶ÑÁË 
			break;
		}

		swap(h, index, lessest);//Óë×îСµÄº¢×Ó½øÐн»»» 
		index = lessest;//¸üÐÂindexϱ꣬ÒòΪ¸Õ¸Õ½»»»ÁË 
		left = 2 * index + 1;//ÖØмÆËãϱêindexµÄ×óº¢×Ó 
	}
}
int MinHeapCompare(ELEMENT a, ELEMENT b)
{
	return a.distance < b.distance;//Ö±½Ó½øÐÐÖµµÄ±È½Ï 
}
void freeMinHeap(MinHeap h)
{
	free(h->data);//ÏÈÊÍ·Å×îС¶Ñ´æ·ÅÔªËصĿռä 
	free(h);//ÔÙÊÍ·Å×îС¶ÑµÄ¿Õ¼ä 
}
ELEMENT peekMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//×îС¶ÑÀïÃæûÓÐÔªËØÄÇô£¬²Ù×÷Î¥·¨£¬·µ»ØÌض¨Öµ 
		ELEMENT t = { 0 };

		return t;
	}

	ELEMENT ans = deleteMinHeap(h);//µ¯³ö×îС¶ÑµÄ¶Ñ¶¥ 

	addMinHeap(h, ans);//ÔÙ·ÅÈë×îС¶Ñ£¬ÒÔ´ËÀ´ÊµÏÖ´úÂ븴Óà 

	return ans;
}

Find The Multiple

解题思路

  1. 暴力所有倍数的话会很慢
  2. 因为答案是只包含0101的数字，所以我们可以直接生成一个只有0101的数字，再判断是不是n的倍数

代码实现

#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 101

int n;
bool isans = 0;

void dfs(ll m, int bit);

int main(int argc, char* argv[])
{
	while (sc("%d", &n), n) {
		dfs(1, 1);
		isans = 0;
	}

	return 0;
}

void dfs(ll m, int bit)
{
	if (bit == 20) {
		return;
	}

	if (isans) {
		return;
	}

	if (m % n == 0) {
		pr("%lld\n", m);
		isans = 1;
		return;
	}

	dfs(10 * m, bit + 1);
	dfs(10 * m + 1, bit + 1);
}

Oil Deposits

解题思路

  1. 扫描整个矩阵利用洪水填充，进行感染在一个油田的油

代码实现

#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 101

char s[N][N];
int n;
int m;
int cnt;
int d[8][2] = {
	{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}
};

void dfs(int i, int j)
{
	if (s[i][j] == '#') {
		return;
	}

	s[i][j] = '#';

	for (int k = 0; k < 8; k++) {
		int nx = i + d[k][0];
		int ny = j + d[k][1];

		if (nx >= 0 && nx < n && ny >= 0 && ny < m && s[nx][ny] == '@') {
			dfs(nx, ny);
		}
	}
}

int main(int argc, char* argv[])
{
	while (sc("%d%d", &n, &m), n + m) {
		cnt = 0;
		for (int i = 0; i < n; i++) {
			sc("%s", s[i]);
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (s[i][j] == '@') {
					dfs(i, j);
					cnt++;
				}
			}
		}
		pr("%d\n", cnt);
	}



	return 0;
}

Find a way

解题思路

  1. 求两遍最短路径数组，一个从M出发，另一个从Y出发
  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 201

typedef struct {
	int x;
	int y;
	int step;
}p;

int d[4][2] = {
	{-1, 0}, {1, 0} , {0, -1}, {0, 1}
};
int n;
int m;
char s[N][N];
int sSize;
int eSize;
int ans;
int y[N][N];
int ms[N][N];
p start[2];
p end[N * N];
p q[N * N];
int l = 0;
int r = 0;

void bfs(p start, int a[][N]);
int min1(int a, int b);

int main(int argc, char* argv[])
{
	while (~sc("%d%d", &n, &m)) {
		ans = INT_MAX;
		l = 0;
		r = 0;
		sSize = 0;
		eSize = 0;
		for (int i = 0; i < n; i++) {
			sc("%s", s[i]);

			for (int j = 0; j < m; j++) {
				if (s[i][j] == 'Y' || s[i][j] == 'M') {
					start[sSize].step = 0;
					start[sSize].x = i;
					start[sSize++].y = j;
				}
				else if (s[i][j] == '@') {
					end[eSize].x = i;
					end[eSize].y = j;
					end[eSize++].step = 0;
				}
			}
		}

		bfs(start[0], y);
		l = 0;
		r = 0;
		bfs(start[1], ms);

		for (int i = 0; i < eSize; i++) {
			if (y[end[i].x][end[i].y] != 0 && ms[end[i].x][end[i].y] != 0) {
				ans = min1(ans, y[end[i].x][end[i].y] + ms[end[i].x][end[i].y]);
			}
		}

		pr("%d\n", ans * 11);
	}

	return 0;
}

int min1(int a, int b) {
	return a <= b ? a : b;
}

void bfs(p start, int a[][N]) {
	p t = { 0 };
	p temp = { 0 };
	bool v[N][N] = { 0 };

	v[start.x][start.y] = 1;

	q[r++] = start;

	while (l < r) {
		t = q[l++];

		for (int i = 0; i < 4; i++) {
			int nx = t.x + d[i][0];
			int ny = t.y + d[i][1];

			if (nx >= 0 && nx < n && ny >= 0 && ny < m && s[nx][ny] != '#' && !v[nx][ny]) {
				a[nx][ny] = t.step + 1;

				temp.x = nx;
				temp.y = ny;
				temp.step = t.step + 1;
				q[r++] = temp;
				v[nx][ny] = 1;
			}
		}
	}
}

 

标签：index,int,题解,2024,++,18,MinHeap,include,define
From： https://www.cnblogs.com/lwj1239/p/18081418

相关文章

  • USACO24OPEN Bessie's Interview S 题解
    题意简述：有\(n\)个奶牛，\(k\)个农夫，\(k\len\)，每一个奶牛有一个面试时长\(t_i\)，表示面试这个奶牛要多长时间。\(0\)时刻时对于所有的\(1\lei\lek\)，第\(i\)个农夫会面试第\(i\)个奶牛，之后的面试顺序满足以下条件：若在某时刻\(t\)，存在某个农夫已经面试完当前的奶牛，那......
  • 计数组合【2024蓝桥杯0基础】-学习笔记
    文章目录计数原理排列数组合数组合数性质例题分析代码复现例题2状态分析代码复现常见的排列组合问题圆排列代码复现第二类斯特林数感悟计数原理排列数组合数组合数性质例题分析代码复现defksm(a,b,c):ans=1%cwhileb!=0:......
  • 史上最全Java核心面试题（带全部答案）2024年最新版
    今天要谈的主题是关于求职，求职是在每个技术人员的生涯中都要经历多次。对于我们大部分人而言，在进入自己心仪的公司之前少不了准备工作，有一份全面细致面试题将帮助我们减少许多麻烦。在跳槽季来临之前,特地做这个系列的文章，一方面帮助自己巩固下基础，另一方面也希望帮助想要换工......
  • abc176F题解
    abs176F题意:给定长度为\(3\timesn\)，值域是\([1,n]\)的序列，不断下列操作直至序列剩余\(3\)个数：1.对序列最左侧\(5\)个数进行任意排列。2.取出序列最左侧\(3\)个数，如果\(3\)个数一样，则得分加一，然后删除这三个数。问最大得分为多少。思路：神仙dp题。首先有一个显然的\(\Thet......
  • codeforce Round 935 div3 个人题解（A-E）
    A.SettingupCamp时间限制：每个测试1秒内存限制：每个测试256兆字节输入：标准输入输出：标准输出组委会计划在游览结束后带领奥林匹克运动会的参赛选手进行徒步旅行。目前，正在计算需要搭帐篷的数量。已知每顶帐篷最多可容纳3人。在参赛选手中，有a个内向型，b个外向型和c个综合型：......
  • 20240319每日一题题解
    20240319每日一题题解Problem判断一个数的结构是否为某个数重复两遍得到。例如，\(123123\)是重复两遍的数，而\(333\)，\(809680\)​则不是保证输入的数字不超过longlong型范围。若是，则输出yes；否则输出no。Solution从数字的角度要想解决这个问题也不是不可以，但是不如将给定的数......
  • 【蓝桥杯选拔赛真题70】python最短路径和 第十五届青少年组蓝桥杯python选拔赛真题 算
    目录python最短路径和一、题目要求1、编程实现2、输入输出二、算法分析三、程序编写四、程序说明五、运行结果六、考点分析七、 推荐资料1、蓝桥杯比赛2、考级资料3、其它资料python最短路径和第十五届蓝桥杯青少年组python比赛选拔赛真题一、题目要求（注：i......
  • 更新用户密码(2024-3-19)
    //userController@PatchMapping("/updatePwd")publicResultupdatePwd(@RequestBodyMap<String,String>params){//1.校验参数StringoldPwd=params.get("old_pwd");StringnewPwd=params.get("new_pwd&qu......
  • 【办公类-22-15】周计划系列（5-6）“周计划-06 周计划打印pdf（docx删除内容转PDF）“ （2024年
    作品展示背景需求：前期用docx（删除第一页反思部分内容）转PDF转png（第一页）的方式获得上传网页用的图片。【办公类-22-14】周计划系列（5-5）“周计划-05上传周计划png（docx转PDF转png）“（2024年调整版本）-CSDN博客文章浏览阅读600次，点赞11次，收藏9次。【办公类-22-14】周计划系列（5-5）“......
  • [ABC345F] Many Lamps 题解
    题意：给定一个\(n\)个点\(m\)条边的无向图，每个点的初始颜色为\(0\)。一次操作是将一条边的两个端点的颜色翻转。求是否能通过若干次操作使得最终有\(k\)个颜色为\(1\)的点。首先考虑什么情况下无解。会发现每一次操作，颜色为\(1\)的点的数量变化一定是\([0,+2,-2]\)......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99