如果你用三次方复杂度建图但TLE90
查看原帖
如果你用三次方复杂度建图但TLE90
1076971
anke2017楼主2024/10/1 13:22

使用 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 邻接矩阵来存图也可以得到不错的效果。

2024/10/1 13:22
加载中...