[ACM] POJ1067解题报告, Beatty贝蒂数列

136 Replies

无意看到的题目.. 因为是中文的就猫了一眼, 觉得挺水就做做, 结果一做就是一下午.. NOI还有点名堂

开始觉得就是博弈+简单DP, 右图每一个格子 (a, b) , 玩家一次取石子以后能变成的状态是 (a-i, b) , (a, b-i) , 或者 (a-i, b-i) , 只要路线上存在lose, 赋值为win, 否则赋值lose. 整个表格是对称的. 自底向上DP就可以解决.

然后看了discuss, 存在O(1) 的算法..

Beatty sequence Wiki 讲解 , 看一下就了了..

The positive irrational number r\, generates the Beatty sequence

\mathcal{B}_r = \lfloor r \rfloor, \lfloor 2r \rfloor, \lfloor 3r \rfloor,... = ( \lfloor nr \rfloor)_{n\geq 1}

If r > 1 \,, then s = r/(r-1)\, is also a positive irrational number. They naturally satisfy

\frac1r + \frac1s = 1 \,

and the sequences

\mathcal{B}_r = ( \lfloor nr \rfloor)_{n\geq 1} and
\mathcal{B}_s = ( \lfloor ns \rfloor)_{n\geq 1}

form a pair of complementary Beatty sequences.

For r = the golden mean, we have s = r + 1. In this case, the sequence ( \lfloor nr \rfloor), known as the lower Wythoff sequence, is

  • 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, … (sequence A000201 in OEIS).

and the complementary sequence ( \lfloor ns \rfloor), the upper Wythoff sequence, is

  • 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, … (sequence A001950 in OEIS).

上下两个数列整好组成 lose 状态的坐标 (1,2) (3,5) (4,7) … 至于为什么等我有空会思考update一下 =D 好神奇阿

其中r是黄金分割律, 即 (1+sqrt(5))/2

则如果m在第一个数列里,则

m=[nr]=nr-x
m/r=n-x/r

其中x属于[0,1) , 先求出n再判断m/r是否在等式右边的区间里即可. 再返回n判断输入的b是否在二队列中相应的位置

Code:
[cpp]
#include <stdio.h>
#include <math.h>
#include <algorithm>

//return num in Beatty sequence(r=golden mean), -1 if not belong to
int Br(int m) {
static const double P=(1+sqrt(5.0))/2;
double foo=m/P;
int n=(int)foo;
if(foo-n>0.999999)
n++;
n++;
if(foo>(n-1/P))
return n;
else
return -1;
}

int main() {
int a,b;
while(scanf("%d%d",&a,&b)!=EOF) {
if(a>b)
std::swap(a,b);
int foo=Br(a);
bool win=true;
if(foo!=-1)
if(a+foo==b)
win=false;
if(win)
printf("1\n");
else
printf("0\n");
}
return 0;
}
[/cpp]

136 thoughts on “[ACM] POJ1067解题报告, Beatty贝蒂数列”

Leave a Reply

Your email address will not be published. Required fields are marked *