NOI2008道路设计

Posted on By 二价氢

数学赛高!/数学さいこう!

嘛,这题有两种做法:

1、BYVoid的,不能说差,但至少是在考场上能最快冒出来的想法,之后需要优化,而且这个优化在考场上难以想出。

2、某50行代码,效率很好,但是得有一定的数学功底。

先说说BYVoid大神的算法,有两个数组。

这里,是指,节点下面有若干个子节点,向下连2条铁路(即在线路中间),且不便利度不超过,显然,其前提条件是,得父节点没有向建铁路

是指,节点下面有若干个子节点,向下连1条或0条铁路(即在线路两段,或不在线路上),且不便利度不超过

所以,我们有:

和:

特别的,当时,我们有:

这是BYVoid的50分做法,非常好想,但是上面的优化很难,-〉BYVoid的完整题解

再说说一个非常好的做法

我们知道,对于一条边,我们有两种方法,要么建铁路,要么不建(笑……)

表示这条边不建铁路,它的儿子们能有的情况数

表示这条边建上铁路,它的儿子们能有的情况数

表示节点向下牵条边,最大不便利度为2的方案数

那么,就有

至此AC

下面是一些细节:

的目的是区别真0(本来就没有结果)和假0(取模后恰为0)

由于可取很大的数,所以要开long long

由于状态不会重复,所以记搜没意义了(笑……)

下面是这种做法的AC-Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=100005,MAXM=100005;
struct Edge{int t,next;}E[MAXM*2];
int pStart[MAXN];
int M,N;
long long MOD;bool MOD_FLAG=false;
long long F[MAXN][3][10];//F[i][a][b]=从节点i向下引出a条节点,不便利值为b的方案数
int RES;
void addedge(int u,int v,int m)
{
    E[m].t=v;E[m].next=pStart[u];pStart[u]=m;
}
int dp(int i,int fa)//节点i,节点i他爸
{
    int v,p;
    F[i][0][RES]=1;
    long long R0,R1,R2;
    for (int p=pStart[i];p;p=E[p].next)
    {
        v=E[p].t;
        if (v==fa)
            continue;
        dp(v,i);
        R0=(F[v][0][RES-1]+F[v][1][RES-1]+F[v][2][RES-1])%MOD;
        R1=(F[v][0][RES]+F[v][1][RES])%MOD;
        F[i][2][RES]=(F[i][2][RES]*R0+F[i][1][RES]*R1)%MOD;
        F[i][1][RES]=(F[i][1][RES]*R0+F[i][0][RES]*R1)%MOD;
        F[i][0][RES]=(F[i][0][RES]*R0)%MOD;
    }
    return F[i][2][RES]+F[i][1][RES]+F[i][0][RES];
}
bool init()
{
    int tu,tv;
    scanf("%d%d%lld",&amp;N,&amp;M,&amp;MOD);
    if (MOD&lt;10000)
    {
        MOD*=9997;
        MOD_FLAG=true;
    }
    if (M!=N-1)
        return false;
    for (int i=1;i&lt;=M;i++)
    {
        scanf("%d%d",&amp;tu,&amp;tv);
        addedge(tu,tv,i);
        addedge(tv,tu,i+M);
    }
    return true;
}
int main()
{
    if (init())
    {
        for (RES=0;RES&lt;=10;RES++)
            if (dp(1,0))
                break;
        if (MOD_FLAG)
            MOD/=9997;
        printf("%d\n%lld\n",RES,(F[1][2][RES]+F[1][1][RES]+F[1][0][RES])%MOD);
    }else
    {
        printf("-1\n-1\n");
    }
    return 0;
}