P2730 [USACO3.2] 魔板 Magic Squares 题解

这篇具有很好参考价值的文章主要介绍了P2730 [USACO3.2] 魔板 Magic Squares 题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一些废话

夜深人静的夜晚,我开了这道题。看起来,完成它是一件轻而易举的事。我想了想,打开Dev-C++,开始写代码。
然而,那时的我还不知道,我踏入了深渊......

咳咳,中二病犯了,前面的文字请忽略。

思路

题目要求最少操作次数,显然,我们要使用BFS来求解。
对于每个节点,接下来有最多三个子节点,用函数模拟即可。
因为要求输出操作序列,所以需要存储每个节点的父节点。

细节

我们还需要对魔板进行去重操作来剪枝。
这是因为:
由于BFS的特性,当一个魔板第一次出现时,得到它所需要的操作次数是最少的;如果它出现了多次,那么与首次出现相比,它所需的操作次数更多。从该魔板出发还原成目标魔板时,如果从第一个魔板出发,所用的总次数最少;而多次出现的必然比首次出现的所用的总次数多。
因此通过去重操作进行剪枝是必要的,这会使原本MLE的程序AC(作者亲身经历)。
别忘了输出60个字符就要换行。
另外,当目标模板与初始模板一致时,需要直接输出0,结束程序。

实现

变量等命名不规范,望见谅。文章来源地址https://www.toymoban.com/news/detail-637387.html

#include <cstdio>
#define N 10000005
#define fot(x,y,z) for(int x=y;x<=z;x++)
#define tof(x,y,z) for(int x=y;x>=z;x--)
int bd[9],bb[9];
int b2[9];
int q[N][9];
int dep[N];
int list[N];
char stk[N];
int fa[N];
bool exis[16777216];
void swap(int &x,int &y)
{
	int temp=x;
	x=y;
	y=temp;
}
void A()
{
	fot(i,1,4)
		swap(bd[i],bd[9-i]);
}
void B()
{
	int f[2];
	f[0]=bd[4];
	f[1]=bd[5];
	tof(i,3,1)
		bd[i+1]=bd[i];
	fot(i,6,8)
		bd[i-1]=bd[i];
	bd[1]=f[0];
	bd[8]=f[1];
}
void C()
{
	int temp=bd[2];
	bd[2]=bd[7];
	bd[7]=bd[6];
	bd[6]=bd[3];
	bd[3]=temp;
}
void setts(int i)
{
	fot(j,1,8)
		q[i][j]=bd[j];
}
void getts(int i)
{
	fot(j,1,8)
		bd[j]=q[i][j];
}
bool judge()
{
	fot(i,1,8)
	{
		if(bd[i]!=b2[i])
			return 0;
	}
	return 1;
}
void print(int x)
{
	printf("%d\n",dep[x]);
	int i;
	for(i=1;x;i++)
	{
		stk[i]=list[x]-1+'A';
		x=fa[x];
	}
	int cnt=0;
	tof(j,i-1,1)
	{
		cnt++;
		printf("%c",stk[j]);
		if(cnt%60==0)
			printf("\n");
	}
}
bool exist()
{
	int number=0;
	fot(i,1,8)
		number=number*8+bd[i]-1;
	if(exis[number])
		return 1;
	else
	{
		exis[number]=1;
		return 0;
	}
}
int main()
{
	fot(i,1,8)
		scanf("%d",&b2[i]);
	fot(i,1,8)
		bd[i]=i;
	if(judge())
	{
		printf("0");
		return 0;
	}
	int head=0,tail=0;
	setts(0);
	fa[0]=-1;
	while(head<=tail)
	{
		getts(head);
		fot(i,1,3)
		{
			if(i==1) A();
			if(i==2) B();
			if(i==3) C();
			if(exist())
			{
				getts(head);
				continue;
			}
			tail++;
			list[tail]=i;
			fa[tail]=head;
			setts(tail);
			dep[tail]=dep[head]+1;
			if(judge())
			{
				print(tail);
				return 0;
			}
			getts(head);
		}
		head++;
	}
}

到了这里,关于P2730 [USACO3.2] 魔板 Magic Squares 题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [USACO11MAR] Brownie Slicing G题解(二分+二维前缀和+矩阵分割)

    题目地址 P3017 [USACO11MAR] Brownie Slicing G 二分最大化最小值 切割思路: 一行一行进行切割,如果这一行可以切割出b块大于等于mid的块,就开始切割下一行 如果无法切割出b块,就把正在切割的行与下一行拼起来一起切割 最后通过能切割出b块的水平块块够不够a条来判断m是否合

    2024年02月07日
    浏览(39)
  • CF1781 D. Many Perfect Squares [数学题]

    传送门:CF [前题提要]:一道有意思的数学题 直接想这道题是不好想的(博主当时就完全没有思路).那么 考虑将一个大问题分解成一个小问题想一下(感觉这种思考方式在CF题中还是挺常见的) ,考虑如果同时存在多个完全平方数,那么必然满足存在 两个完全平方数 .而当我们确定了

    2024年02月20日
    浏览(36)
  • 偏最小二乘(Partial Least Squares,PLS)原理及模型建立

    随着对数据驱动的工业检测与诊断方法的逐步深入,过程监测的多元统计需要总结的东西越来越多,那么今天来整理一下。 内容较多,理论较复杂,建议细品,你品!最好推一遍~ It’s time to conclude PLS!!! PCA和偏最小二乘(PLS)是从 数据中描述正常情况 的首选方法。 天气

    2024年02月16日
    浏览(47)
  • python scipy.optimize.least_squares用法,各个参数详细介绍

    最优化作业,要用一个老师给出的一个线性加非线性的模型 来拟合 太菜了,手搓不了,只能直接用scipy.optimize.least_squares,充分利用到least_squares各个参数,之后拟合效果还是挺好的。         fun, x0, jac=\\\'2-point\\\', bounds=(-np.inf, np.inf), method=\\\'trf\\\',         ftol=1e-8, xtol=1e-8, gtol=1e-8,

    2024年03月17日
    浏览(44)
  • Leetcode 2897. Apply Operations on Array to Maximize Sum of Squares

    Leetcode 2897. Apply Operations on Array to Maximize Sum of Squares 1. 解题思路 2. 代码实现 题目链接:2897. Apply Operations on Array to Maximize Sum of Squares 这一题事实上非常的简单,我们只需要想明白一些关键点就行了。 题中最终的目标是获得 k k k 个数,使得其平方和最大。因此,我们就只需要

    2024年02月07日
    浏览(49)
  • 模型评估(误差平方和(SSE The sum of squares due to error))

    举例:(下图中数据-0.2, 0.4, -0.8, 1.3, -0.7, 均为真实值和预测值的差) 在k-means中的应用: 公式各部分内容: 上图中: k=2 SSE图最终的结果,对图松散度的衡量. (eg:  SSE(左图)SSE(右图) ) SSE随着聚类迭代,其值会越来越小,直到最后趋于稳定: 如果质心的初始值选择不好,SSE只会达到一个不怎

    2024年02月04日
    浏览(52)
  • windows10上运行magic keyboard和magic mouse

    所有需要的软件和插件都可以在这里寻找到 链接:https://pan.baidu.com/s/1Y8vjRnznqKP7f8dFFrHoGw?pwd=vpsy 提取码:vpsy 你的windows电脑可能自带了蓝牙,那你直接连接键盘鼠标便可。 若你的windows电脑主板上没有蓝牙,你也可以上网买一个蓝牙接收器,他的价格往往在10RMB左右,效果都差

    2024年02月05日
    浏览(28)
  • 荣耀Magic5至臻版摄像头参数怎么样 荣耀Magic5至臻版电池容量

    荣耀Magic5 至臻版将会采用索尼IMX989 大底传感器,该传感器拥有1/1. 12 英寸大底,支持OIS防抖。索尼IMX989 是1. 02 英寸大底,单像素面积为1.6μm,支持四像素合一技术,融合像素面积可以达到3.2um, 5000 万像素镜头,采用四拜耳色彩阵列,是目前拥有最大底的手机CMOS传感器。 荣

    2024年02月17日
    浏览(45)
  • Springboot集成magic-api

    目录 1、前言 2、springboot集成magic-api 2.1、添加maven依赖 2.2、application.yml配置 2.3、编写测试接口 2.4、启动程序,访问接口 2.5、magic-api脚本 3、magic-api其他语法 4、注意事项 今天项目中遇到一个问题,springboot后端项目经常使用log4j输出日志,同时会配置相应日志级别。但是由于

    2024年02月08日
    浏览(40)
  • [USACO14DEC] Marathon G

    洛谷[USACO14DEC] Marathon G 题目大意 Bessie text{Bessie} Bessie 设计了一条马拉松路线,有 N N N 个点。 Bessie text{Bessie} Bessie 有 q q q 次操作,每次操作是修改或询问。每次修改会修改一个点的坐标,每次询问是选手跑过一条子路径的时间,一条子路线是整条路线中包含若干连续点的一

    2024年02月15日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包