UVALive 7505 Hungry Game of Ants

1. 笔记

比较容易的动态规划题。往左很好考虑，往右用dpi表示前i只都被k吃掉后，k继续往右仍然不死的情况数。状态转移方程为dp[I]=dp[I+1]+...+dp[j]，分别对应第I+1位向左，...，第j位向左（I和j之间的都向右）。其中j为满足条件的最大的蚂蚁（如果I+1到j都向右，j向左，那么k死）。貌似这个dp和网上一些题解不太一样，不过没细看。这些都不要紧，关键的是写完代码各自玄学TLE，花了足足五个小时才改到A，最后发现罪魁祸首是sqrt。。。吐血。以前从来没注意过这个，今天才发现凡是小数运算都奇慢无比，真是血的教训啊。

2. 代码

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define ms(arr,a) memset(arr,a,sizeof arr)

#define debug(x) cout<<"< "#x" = "<<x<<" >"<<endl

typedef long long ll;

const int maxn=1e6+5;

const ll mod=1e9+7;

int pos[maxn];

int dp[maxn];

int n,k;

int quick_pow(int a,int n)

{

    register int ret=1;

    while(n)

    {

        if(n&1)ret=1LL*ret*a%mod;

        a=1LL*a*a%mod;

        n>>=1;

    }

    return ret;

}

inline ll sum(int x)

{

    return 1LL*x*(x+1);

}

int bs(int l,int r,int i)

{

    int m;bool ll=(sum(l)<=2*sum(i)),rr=(sum(r)<=2*sum(i));

    if(ll&&rr)return r;

    if(!ll&&!rr)return -1;

    if(!ll){r=r^l;l=r^l;r=r^l;}

    while(r-l>1||l-r>1)

    {

        m=(l+r)/2;

        if(sum(m)<=2*sum(i))l=m;

        else r=m;

    }

    return l;

}

int main()

{

	//freopen("Input.txt","r",stdin);

	//freopen("1.txt","w",stdout);

	for(int i=1;i<maxn;++i)pos[i]=bs(i+1,maxn,i);

    int T;scanf("%d",&T);

    rep(Case,1,T)

    {

        scanf("%d%d",&n,&k);

        if(k==1){printf("Case #%d: 0\n",Case);continue;}

        dp[n]=1;dp[n+1]=0;

        for(int i=n-1;i>=k;--i)

        {

            int j=pos[i];

            j=min(n,j);

            dp[i]=((2*dp[i+1]-dp[j+1])%mod+mod)%mod;

        }

        int l=1,m,r=k-1;

        while(l<r)

        {

            m=(l+r+1)/2;

            if(2*sum(m)<sum(k))l=m;

            else r=m-1;

        }

        //l=ceil(sqrt(k*(k+1)/2+0.25)-0.5)-1;

        printf("Case #%d: %lld\n",Case,1LL*quick_pow(2,l+1)*(dp[k]-dp[k+1]+mod)%mod);//

    }

	//freopen("CON","w",stdout);

	//system("start Output.txt");

}

巴特西

UVALive 7505 Hungry Game of Ants

最新文章

热门文章