BZOJ2165 大楼

2014.12.27 10:46 Sat| 4 visits oi_2015| 2015_刷题日常| Text

Solution

这道题和USACO 2007 Nov Gold 2.Cow Relays好像有异曲同工之妙,不同的是那道题问的是N步最多可以走多远,这道题问走多少步可以走到M。同样构造矩阵,进行二进制拆分+矩阵乘法即可解决。另外,这道题矩阵的初值好像很奇特的样子。

Code

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f3f3f3f3fLL

inline long long read()
{
    long long x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int t,n,cnt;
long long m;

struct matrix
{
    static const int N = 105;
    long long v[N][N];
    matrix(){ memset(v,0xc0,sizeof v); }
    matrix(bool flag)
    {
        long long x;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                v[i][j]=(x=read())?x:-inf;
    }
    friend matrix operator *(const matrix &a,const matrix &b)
    {
        matrix re;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++)
                    re.v[i][j]=max(re.v[i][j],a.v[i][k]+b.v[k][j]);
                re.v[i][j]=min(re.v[i][j],m);
            }
        return re;
    }
    matrix &operator *=(const matrix &x){ return *this=*this*x; }
    bool check()
    {
        for(int i=1;i<=n;i++)
            if(v[1][i]>=m) return true;
        return false;
    }
    void print()
    {
        for(int i=1;i<=n;i++,puts(""))
            for(int j=1;j<=n;j++)
                cout<<max(0LL,v[i][j])<<' ';
    }
}s[100];

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        s[0]=matrix(true);
        for(cnt=0;!s[cnt].check();cnt++)
            s[cnt+1]=s[cnt]*s[cnt];
        cnt--;
        long long ans=1LL<<cnt;
        for(int i=cnt-1;i>=0;i--)
            if(!(s[cnt]*s[i]).check())
                s[cnt]*=s[i], ans+=1LL<<i;
        cout<<ans+1<<endl;
    }
}