首页 > 其他分享 >解题报告-跳跳棋

解题报告-跳跳棋

时间:2022-12-28 06:22:05浏览次数:36  
标签:node 报告 2a 跳棋 解题 swap 棋子 ans cnt2

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏:棋盘上有三颗棋子,分别在 \(a,b,c\)这三个位置。我们要通过最少的跳动把他们的位置移动成\(x,y,z\) (注意:棋子是没有区别的)。

跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。

写一个程序,首先判断是否可以完成任务。如果可以,输出最少需要的跳动次数。

分析

考虑一个三元组\((a,b,c)(a<b<c)\)可以怎么跳:

  1. \((2a-b,a,c)\)
  2. \((a,c,2c-b)\)
  3. \((b,2b-a,c)(|a-b|<|b-c|)\)
  4. \((a,2b-c,b)(|a-b|>|b-c|)\)

这四种操作里面,容易发现三四操作最多只能存在一种。

容易发现,操作具有可逆性。而操作1,2都导致\((a',b',c')\)边界向外扩张,而只有3,4向内收缩。

突然发现,如果\(|a-b|=|b-c|\),此时只能进行1,2操作,也即进行扩张。而操作1,2可以分为\(b\)向左/右跳的结果。由于是LCA的题,不难想到需要建模。

我们可以由一组\((a,b,2b-a)\)开始不断向外扩展,不妨扩展看看,记\(c=2b-a\)

1次:\((2a-b,a,c),(a,c,2c-b)\)
2次:\((3a-2b,2a-b,c),(2a-b,c,2c-a),(2a-c,2a-b,2c-a),(a,2c-b,3c-2b)\)

好像,它形成了一个树形结构?也即中间棋子向左跳为左儿子,向右跳为右儿子,向内跳的情况为父亲,这样就由\((a,b,c)\)能够到达的所有情况变成了一颗满二叉树。

此时,由于操作的可逆性,容易发现初始状态和终态有解当且仅当他们所在树的树根相同。然后最少操作次数就是二者在树上的距离。

但是容易发现这棵树好像无穷大,根本不可能建立出来好吧。我们先来考虑如何快速求三元组\((a,b,c)\)的根,亦或者说,我们考虑如何快速求解三元组\((a,b,c)\)的第\(k\)级祖先。

数据范围\(10^9\),显然可以卡掉所有复杂度不正确的算法。

考虑这样一个过程,我们优化掉连续向某个方向跳的操作,这个可以通过公式计算:

设\(x_1=b-a,x_2=c-b\),则若\(x_1<x_2\),则可以不断向右跳\(\left\lfloor\frac{x_2-1}{x_1}\right\rfloor\)步。

然后\(x_1'=x_2-x_1\left\lfloor\frac{x_2-1}{x_1}\right\rfloor,x_2'=x_1\)

这是一个类似于计算欧几里得算法的过程,到最终肯定会有一个终态。于是这部分复杂度被优化到了\(O(\log n)\)。

再接着,由于计算树上路径需要LCA,而这棵树的性质决定了我们不可能使用常用LCA算法优化这个过程。但倍增的思想告诉我们,我们可以自底向上地倍增!具体的,先将两个节点调整到同一高度。由于这个算法的存在,可以在\(O(\log n)\)的时间里求出某个节点的\(k\)级祖先,此时就可以食用倍增优化了。总体复杂度\(O(\log^2 n)\)。

事实上,这个复杂度应该远远跑不满才对。

#include<iostream>
#include<cstdio>
using namespace std;
struct node{
	int a,b,c;
	void init(){
		cin>>a>>b>>c;
		if(a>b)swap(a,b);if(a>c)swap(a,c);if(b>c)swap(b,c);
	}
	bool operator==(node x){
		return a==x.a&&b==x.b&&c==x.c;
	}
}a,b,fa,fb;
int cnt1,cnt2,ans,l1,l2;
void bezero(node &x){  
    if(x.a>x.b)swap(x.a,x.b);
    if(x.a>x.c)swap(x.a,x.c);
    if(x.b>x.c)swap(x.b,x.c);
}
node get(node a,int k,int &cnt){//得到a的k级父亲 
	node ans=a;
	cnt=0;
	while(k){
	   bezero(ans);
		int x1=ans.b-ans.a,x2=ans.c-ans.b,s;
		if(x1<x2){
			s=min(k,(x2-1)/x1);
			ans.a+=s*x1;
			ans.b+=s*x1;
			k-=s;
		}
		else if(x1>x2){
			s=min(k,(x1-1)/x2);
			ans.b-=s*x2;
			ans.c-=s*x2;
			k-=s;
		}
		else {
			return ans;
		}
		cnt+=s;
	}
	return ans;
}
int main(){
	a.init();b.init();
	fa=get(a,0x3f3f3f3f,cnt1);
	fb=get(b,0x3f3f3f3f,cnt2);
	if(!(fa==fb)){
		cout<<"NO\n";
		return 0;
	}
	cout<<"YES\n";
	if(cnt1>cnt2)swap(a,b),swap(cnt1,cnt2);
	ans+=cnt2-cnt1;
	b=get(b,cnt2-cnt1,cnt2);
	if(a==b){
	    cout<<ans;
	    return 0;
	}
	for(int i=29;i>=0;--i){
		node x=get(a,1<<i,l1),y=get(b,1<<i,l2);
		if(!(x==y)){
			a=x,b=y;
			ans+=1<<(i+1);
		}
	}
	cout<<ans+2;
}

清华集训的题都是神题

标签:node,报告,2a,跳棋,解题,swap,棋子,ans,cnt2
From: https://www.cnblogs.com/oierpyt/p/17009354.html

相关文章

  • 汪汪刷题设计报告
    汪汪刷题设计报告目录汪汪刷题设计报告...10.项目简介...11.规格书说明书...12.需求分析...13.项目概述...24.数据流图...35.用例图...36.类图...47.原......
  • CTT2022 解题报告
    因为摇奖想看博客,所以这篇文章发出来了!CTT2022解题报告场切题数在Day4突破了0,可喜可贺!D1T1区间计数一个简单的想法是计算【有多少个区间满足它和某个比它更左的区......
  • 网页大作业——丝绸之路网页报告
    一、实验目的和要求运用已经掌握的知识完成网站。通过此次设计可以达到全面理解、运用网页制作的知识,并使之得以融会贯通,在掌握运用Dreamweaver8flash8fireworks8制作网......
  • Ant发送接口测试报告到邮箱
    接口测试完成后生成测试报告的同时通过邮箱发送进行汇报接口测试结果,可以结合jenkins+ant+jmeter配置发送到指定邮箱来完成。一、jenkins+ant+jmeter的配置jenkins+ant+j......
  • 软件工程——软件测试(黑盒测试、白盒测试、测试分析报告)
    经过前面软件测编码阶段,是不是我们就可以把软件发布出去供用户使用了呢?不是的,为了确保软件不会出现不必要的差错,还需要经过重重测试的。目录​​软件测试的目的​​​​软件......
  • 软工视频——软件维护(软件维护申请报告)
    进行完软件测试阶段,这时程序还不可以完全的交给用户,需要进行软件维护阶段目录​​软件维护的类型有哪些?​​​​影响维护工作量的因素​​​​软件维护的策略​​​​那如何......
  • 实验八实验报告
                                             实验八介绍:YUM全程(YELLOWDOGUPDATE......
  • Selenium28-测试报告
    批量运行为什么要批量运行?测试用例数量庞大,需要一次运行,查看所有用例的运行结果。什么是测试套件和测试运行器?TestSuite(测试套件)是为了测试执行而分组的测试用例......
  • PPT 商务报告:如何建立专属PPT素材库
    PPT商务报告:如何建立专属PPT素材库为什么建立素材库?省事:直接套用应对紧急环境:无网络情况下,无法搜索提升设计思路:帮助提升思路通用型素材库企业型素材库模板......
  • 液体眼线笔BCOP测试报告
    什么产品需要这个认证呢?像接触眼睛外贸论坛外贸论坛的眼影,液体眼线笔,磁性睫毛,假睫毛,等都可能会对眼睛产生eBay论坛eBay论坛一定外贸论坛外贸论坛的刺激,所以亚马逊现在也在严......