NOIP模拟测试6「那一天我们许下约定（背包dp）·那一天她离我而去」

那一天我们许下约定

内部题，题干不粘了。

$30分算法$

首先看数据范围，可以写出来一个普通dp

#include<bits/stdc++.h>

#define ll int

#define A 2100

#define mod 998244353

using namespace std;

ll f[1501][A+A+A],n,d,m;

int main()

{

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

    while(n!=0&&d!=0&&m!=0){

        memset(f,0,sizeof(f));

        f[0][0]=1;

        for(ll i=1;i<=d;i++)

        f[0][i]=1;

        for(ll i=1;i<=n;i++)

            for(ll k=1;k<=d;k++)

            {

                for(ll j=min(m-1,i);j>=0;j--)

                if(i-j>=0)    f[i][k]=(f[i][k]+f[i-j][k-1])%mod;

            }

        printf("%d\n",f[n][d]);

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

    }

}

d最大为$1e^12$所以你这个dp会完美T掉或者M掉

$100分算法$

观察，发现n的范围非常小，m的范围也特别小。

所以我们利用这条性质，先片面的忽视掉这一天不给她饼干的情况，我们设定$f$定义为每天都给她饼干的情况。

设$f[i][j]$中i表示为前$i$天目前给了$j$个饼干的情况

然后可以推出来方程式

可以给她1～m-1个饼干

$f[i][j]=\sum_\limits {k=(j-M-1)}^{k<=j-1} f[i-1][k]$

然后直接转移，复杂度仍然难以接受，观察dp式子发现它是由一个字段转移过来的，我们要用前缀和维护优化一下。

仍然AC不了？

可能你会乘爆long long

注意多取模

#include<bits/stdc++.h>

#define ll long long

#define  A 2010

#define mod 998244353

using namespace std;

ll f[A][A],n,m,q,d;

ll sum[A];

ll meng(ll x,ll k)

{

    ll ans=1;

    for(;k;k>>=1,x=x*x%mod)

        if(k&1)

            ans=x*ans%mod;

    return ans%mod;

}

int main(){

    while(1){

        scanf("%lld%lld%lld",&n,&d,&m);

        ll ans=0;

        if(n==0&&d==0&&m==0){

            return 0;

        }

        memset(f[1],0,sizeof(f[1]));

        f[0][0]=1;

        for(ll i=1;i<=min(n,m-1);i++)

            f[1][i]=1;

        for(ll i=2;i<=n;i++){

            for(ll j=0;j<=n;j++)

                sum[j]=(sum[j-1]%mod+f[i-1][j]%mod)%mod;

            for(ll j=1;j<=n;j++)

                f[i][j]=(sum[j-1]%mod-sum[max(j-m,0ll)]%mod+mod)%mod;

        }

        ll sd=d%mod;

        for(ll i=1;i<=min(n,d);i++)

        {

                if(i==1)

                    ans=(ans+sd*f[i][n]%mod)%mod,ans%=mod;

                else{

                    sd=(sd%mod*meng(i,mod-2)%mod*((d-i+1)%mod))%mod;

                    ans%=mod;

                    ans=(ans+f[i][n]%mod*sd%mod)%mod;

                }

//                if(sd!=0)printf("sd=%lld ans=%lld f*s=%lld\n",sd,ans,f[i][n]*sd%mod);

        }

        cout<<(ans+mod)%mod<<endl;

    }

}

那一天她离我而去

听说暴力可以AC所以我打的A*？？？

看不懂题解，如果给一个菊花图题解不就爆炸了吗？$2^{10000}$我觉得会炸

所以这个题瞎搞就行了？？？

然后我就瞎搞了个A*

跑的还特别快。大约600毫。

思路大约就是把每个直接与1相连的点拿出来，然后对于每个点跑A*，因为已经提前处理出来各种dis所以比较快。

然后没了

#include<bits/stdc++.h>

using namespace std;

#define ll int

#define A 100010

#define in inline

ll n,m;

bool flag[A],ok=0;

ll head[A],nxt[A],ver[A],tot1=0,t;

ll head2[A],nxt2[A],ver2[A],cnt=0,tot2=0;

ll value[A],value2[A],e,d[A],len=0;

struct qnode{

    ll v,w,sz,id;

    friend bool operator < (qnode x,qnode y)

    {

        return x.w+d[x.v]>y.w+d[y.v];

    }

};

void re()

{

    tot1=1,tot2=1;

    memset(flag,0,sizeof(flag));

    memset(head,0,sizeof(head));memset(head2,0,sizeof(head2));

    memset(ver,0,sizeof(ver));memset(ver2,0,sizeof(ver2));

    memset(nxt,0,sizeof(nxt));memset(nxt2,0,sizeof(nxt2));

    memset(value,0,sizeof(value));memset(value2,0,sizeof(value2));

}

in void add1(ll u,ll v,ll w)

{

    ver[++tot1]=v;

    nxt[tot1]=head[u];

    value[tot1]=w;

    head[u]=tot1;

}

in void add2(ll x,ll y,ll w)

{

    ver2[++tot2]=y;

    nxt2[tot2]=head2[x];

    value2[tot2]=w;

    head2[x]=tot2;

}

in void spfa(ll root)

{

    memset(flag,0,sizeof(flag));

    memset(d,0x3f,sizeof(d));

    queue <ll>q;

    q.push(root);

    flag[root]=1;

    d[root]=0;

    while(!q.empty())

    {

        ll x=q.front();

        q.pop();

        flag[x]=0;

        for(ll i=head[x];i;i=nxt[i])

        {

            ll y=ver[i],w=value[i];

            if(d[y]>d[x]+w)

            {

                d[y]=d[x]+w;

                if(!flag[y])

                {

                    flag[y]=1;

                    q.push(y);

                }

            }

        }

    }

    return ;

}

in ll read()

{

    ll x=0,f=1;char c=getchar();

    while(!isdigit(c))

    {

        if(c=='-') f=-1;

        c=getchar();

    }

    while(isdigit(c))

    {

        x=(x<<1)+(x<<3)+c-'0';

        c=getchar();

    }

    return x*f;

}

in ll astar()

{

//    从每个直接相连的点开始跑A*

    ll ans=0x7ffffff;

    for(ll i=head[1];i;i=nxt[i])

    {

        ll y=ver[i];

        priority_queue<qnode> h;

        memset(flag,0,sizeof(flag));

        qnode s;

        s.v=y,s.w=value[i],s.id=0;

        h.push(s);

        bool ok=0;

        while(!h.empty())

        {

            qnode no=h.top();

//            printf("当前 %d sumvalue=%d\n",no.v,no.w);

            if(no.v==1){

                ans=min(no.w,ans);

                break;

            }

            h.pop();

            flag[no.v]=1;

            for(ll i=head2[no.v];i;i=nxt2[i]){

                ll tu=ver2[i];

//                printf("tu=%d\n",tu);

                if(tu==1&&!ok){

                    ok=1;

//                    printf("tu=%d \n",tu);

                    continue;

                }

                if(flag[tu])

                {/*printf("掠过\n");*/continue;}

//                printf("没有掠过\n");

                qnode t;

                t.v=tu;t.w=value[i]+no.w;t.sz=no.sz+1;

                h.push(t);

//                printf("推入 %d->%d z=%d\n",no.v,tu,value2[i]+no.w);

            }

        }

    }

    return ans;

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        re();

        ll xx,yy;ll zz;

        n=read(),m=read();

        for(ll i=1;i<=m;i++)

        {

            xx=read(),yy=read();zz=read();

            add1(yy,xx,zz);

            add1(xx,yy,zz);

            add2(xx,yy,zz);

            add2(yy,xx,zz);

        }

        spfa(1);

/*        for(ll i=2;i<=tot1;i++){

            printf("%d\n",ver[i]);

        }

        for(ll i=1;i<=n;i++){

            printf("%d\n",d[i]);

        }

*/        ok=1;

        ll ans=astar();

        if(ans>=1000000) cout<<-1<<endl;

        else

        printf("%d\n",ans);

    }

}

巴特西

NOIP模拟测试6「那一天我们许下约定（背包dp）·那一天她离我而去」

那一天我们许下约定

那一天她离我而去

最新文章

热门文章