codeforces 385 E. Bear in the Field (先记录想法)

题目链接

题意:

有一只熊,初始在(sx,sy)处,如果当前的位置在(x,y),那么下一秒会在((x+dx-1)%n+1,(y+dy-1)%n+1)处, dx[i] = k[i-1] + dx[i-1],dy[i]=k[i-1] + dy[i-1],k表示的是某个点的花丛数目。

初始点(x,y)的花丛数为x+y,每经过一个时间,所有点的花丛数增加1.

所以,k[i] = x[i] + y[i] + i-1,现在问经过时间t后,熊的位置在哪里。也就是x[t],y[t]的值。

思路:

我们不妨先只考虑x方向的,因为y方向完全相同。

观察x[t]的式子, x[t] = (x[t-1] + dx[t-1] -1) % n +1。。这个%n之后+1简直蛋疼得一逼。。。

我们不妨构造g[t] = x[t]-1,这样原式子就变成了 g[t] = (g[t-1] + dx[t-1]) %n …看起来爽了很多。。。

观察式子g[t] = (g[t-1] + dx[t-1]) % n,我们发现这是一个前缀和的形式。

根据在hdu4686解题报告  中提到的经验,对于求和的式子,我们只需要考虑每一项的构造法。

因此问题转化成构造矩阵dx[t]

dx[t] = k[t-1] + dx[t-1]

其中k[t] = x[t] + y[t] + t-1,我们写成gx[t]和gy[t]的形式

k[t] = gx[t] + gy[t] + t + 1

k[t-1] = gx[t-1] + gy[t-1] + t

因此可以得到k[t-1]与k[t]之间的递推关系: k[t] = k[t-1] + dx[t-1] + dy[t-1] + 1

观察到k[t]的表达式中同时包含dx,dy项,因此之前考虑的单独处理x和y的想法应该是行不通的。我们考虑同事处理x,y。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz