如果你用三次方复杂度建图但TLE90

P1983 [NOIP2013 普及组] 车站分级

anke2017 @ 2024-10-01 13:22:04

使用 bitset_Find_next 函数可以减少时间。

优化示例:

    for(int i=1,j,t1,t2,l,r,x;i<=m;i++)
    {
        t1=uread();
        have.reset();
        can_do.reset();
        for(j=1;j<=t1;j++)
        {
            t2=uread();
            if(j==1)l=t2;
            if(j==t1)r=t2;
            have[t2]=1;
        }
        can_do=have;
        can_do.flip();
        for(j=have._Find_next(l-1);j<=r;j=have._Find_next(j))
        {
            for(x=can_do._Find_next(l-1);x<=r;x=can_do._Find_next(x))
            {
                if(!have[x]&&!have_e[x][j]){times[j]++;have_e[x][j]=1;}
            }
        }
    }

另外,用 bitset 邻接矩阵来存图也可以得到不错的效果。


|