| 题目名称 | 1838. [国家集训队 2011] 跳跳棋 |
|---|---|
| 输入输出 | nt2011_hop.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-12-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：55， 提交：124， 通过率：44.35% | ||||
 Youngsc |
100 | 0.000 s | 0.00 MiB | C++ |
 归魂者 |
100 | 0.003 s | 0.31 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.005 s | 0.31 MiB | C++ |
 Qw. |
100 | 0.005 s | 0.31 MiB | C++ |
 _Horizon |
100 | 0.005 s | 0.32 MiB | C++ |
 cstdio |
100 | 0.006 s | 0.31 MiB | C++ |
 梦那边的美好ET |
100 | 0.006 s | 3.16 MiB | C++ |
 Vergil |
100 | 0.007 s | 0.29 MiB | C++ |
 zhanggengchen |
100 | 0.007 s | 0.30 MiB | Pascal |
 mikumikumi |
100 | 0.007 s | 0.31 MiB | C++ |
| 关于 跳跳棋 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
首先广搜有20分
对于一个状态 例如2 3 7 中间可以往两侧跳，即2 3 7->1 2 7 / 2 3 7->2 7 11 两侧仅有一个能往中间跳，即2 3 7->3 4 7 那么所有的状态就能表示为一棵二叉树，第一种情况为其两个儿子，第二种为其父亲 问题转换为给定树上的两个结点，求其距离 直接暴力可以得40分 可以构造这样的数据 1 2 1000000000 99999998 99999999 1000000000 这样左边要一直往中间跳上上亿次 我们发现若记前两个数差t1，后两个数差t2，不妨设t1<t2 则左边最多往中间跳(t2-1)/t1次 然后只能右边往中间跳，是一个辗转相除的过程，即在logK的时间内我们可以用这种方法得到某个结点它向上K次后的结点，或者根节点，同时还可以顺便算下深度 那么只要求始终两个状态的深度d1,d2,将较深的调整到同一深度 然后二分/倍增求与lca的深度差x ans=2*x+abs(d1-d2)  Emine
2017-04-29 10:55
2楼
| ||||
|
这思路太机智了……
| ||||
【题目描述】
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。
我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）
跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。
写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。
【输入格式】
第一行包含三个整数，表示当前棋子的位置a b c。（互不相同）
第二行包含三个整数，表示目标位置x y z。（互不相同）
【输出格式】
如果无解，输出一行NO。
如果可以到达，第一行输出YES，第二行输出最少步数。
【样例输入】
1 2 3 0 3 5
【样例输出】
YES 2
【提示】
20% 输入整数的绝对值均不超过10
40% 输入整数的绝对值均不超过10000
100% 绝对值不超过10^9
【来源】
国家集训队2011 何朴藩