题解 P2203 【Blink】

Mr_Li · 2016-10-07 10:08:56 · 题解

由于N<=16，所以我们可以把灯的状态压成一个数。

由于B会超过32位数的范围，所以我们可以用倍增的方法解此题。

设用2^i的时间，会把可以压成j的灯的状态变成可以压成f[i][j]的灯的状态。

例如我们可以把“1 0 0 0 0”压成“16”，“1 0 1 0 0”压成“20”，“1 1 1 0 1”压成“29”，（这里利用了二进制的思想）于是f[1][16]=20，f[2][20]=29。

对于边界条件f[0][i]可以模拟。

倍增算法通用的状态转移方程是f[i][j]=f[i-1][f[i-1][j]]。

时间复杂度是O(2^Nlog B)。

附代码：

···cpp

#include<iostream>
using namespace std;
long long n,b,i,j,f[51][65536]={},light,compress=0;
int main ()
{
    cin>>n>>b;
    for (i=0;i<1<<n;i++)
    for (j=0;j<n;j++)
    f[0][i]+=((i&1<<(j+1)%n)>0^(i&1<<j)>0)*(1<<j);
    for (i=1;i<=50;i++)
    for (j=0;j<1<<n;j++)
    f[i][j]=f[i-1][f[i-1][j]];
    for (i=1;i<=n;i++)
    {
        cin>>light;
        compress=compress<<1|light;
    }
    for (i=50;i>=0;i--)
    if (1LL<<i<=b)
    {
        b-=1LL<<i;
        compress=f[i][compress];
    }
    for (i=n-1;i>=0;i--)
    cout<<((compress&1<<i)>0)<<endl;
    return 0;
}
···