首页 > 代码库 > BZOJ2144 跳跳棋
BZOJ2144 跳跳棋
蒟蒻只会广搜。。。20分。。。
后来发现对于一个状态，中间的一个棋子可以往两边跳，而两边的棋子最多只有一个可以往中间跳（怎么发现的？废话嘛、、、！）
故每个状态看做一个点，有关连的状态连起来，就形成了一棵二叉树
对于一个某个有解的状态而言，中间往两边跳的两个状态是它的儿子，两边往中间跳的状态是它的父亲
于是就变成了树上两点求距离问题。
暴力还是不行，只有40分。。。
hzwer："我们发现若记前两个数差t1，后两个数差t2，不妨设t1<t2
则左边最多往中间跳(t2-1)/t1次
然后只能右边往中间跳，是一个辗转相除的过程，即在logK的时间内我们可以用这种方法得到某个结点它向上K次后的结点，或者根节点，同时还可以顺便算下深度"
好像挺对？Orz。。。
于是就变成了先把两个节点调到树上同一深度再二分LCA的深度即可，做完了。。。
1 /************************************************************** 2 Problem: 2144 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:0 ms 7 Memory:804 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 const int INF = (int) 1e9;15 struct data{16 int a[4];17 };18 inline bool operator != (const data a, const data b){19 return a.a[1] != b.a[1] || a.a[2] != b.a[2] || a.a[3] != b.a[3];20 }21 int t1, t2, tmp, ans;22 int a[4], b[4];23 24 data calc(int *a, int k){25 data res;26 int t1 = a[2] - a[1], t2 = a[3] - a[2], i, t;27 for (i = 1; i < 4; ++i)28 res.a[i] = a[i];29 if (t1 == t2) return res;30 if (t1 < t2){31 t = min(k, (t2 - 1) / t1);32 k -= t, tmp += t;33 res.a[2] += t * t1, res.a[1] += t * t1;34 }else{35 t = min(k, (t1 - 1) / t2);36 k -= t, tmp += t;37 res.a[2] -= t * t2, res.a[3] -= t * t2;38 }39 return k ? calc(res.a, k) : res;40 }41 42 int main(){43 int d1, d2, i;44 data t1, t2;45 for (i = 1; i < 4; ++i)46 scanf("%d", a + i);47 for (i = 1; i < 4; ++i)48 scanf("%d", b + i);49 sort(a + 1, a + 4);50 sort(b + 1, b + 4);51 t1 = calc(a, INF), d1 = tmp, tmp = 0;52 t2 = calc(b, INF), d2 = tmp, tmp = 0;53 if (t1 != t2){54 puts("NO");55 return 0;56 }57 if (d1 > d2){58 swap(d1, d2);59 for (i = 1; i < 4; ++i)60 swap(a[i], b[i]);61 }62 ans = d2 - d1;63 t1 = calc(b, ans);64 for (i = 1; i < 4; ++i)65 b[i] = t1.a[i];66 int l = 0, r = d1, mid;67 while (l <= r){68 mid = l + r >> 1;69 if (calc(a, mid) != calc(b, mid)) l = mid + 1;70 else r = mid - 1;71 }72 puts("YES");73 printf("%d\n", ans + 2 * l);74 return 0;75 }
BZOJ2144 跳跳棋
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。